Re: hash tables without GC cost

[Bruno Haible <bruno@cl...>]

Sam wrote:
> Some smart-ass will use it in his HT and will be stunned with
>
>      (setf (gethash 'foo ht) 'bar)
>      (gc)
>      (gethash 'foo ht) ==> NIL
>
> are we willing to live with this?

No, we can give an error during (setf gethash).

> if not, we can add a setfable SYS::HT-GC-INVARIANT-P.

We can verify for the simple cases (EQ, EQL and CLASS-HASHCODE) that all
keys in the hash table are GC-invariant.

> E.g., (case x (1 'one) (2 'two) (t 'many)) will create an HT which will
> not need to be rehashed.

Cool! I hadn't thought of this.

Bruno

hash tables without GC cost

[Bruno Haible <bruno@cl...>]

In order to speed up the generic function dispatch (which, as you
remember, is mostly a (gethash (class-of argument) effective-method-table)),
I would like to add a precomputed hash code to all classes and specializers.
I can arrange that the hash code be stored as (sys::%record-ref class 1)
for each class. How do I declare that the hash table does not need rehashing
after GC? Can you add such an option to MAKE-HASH-TABLE?

Bruno

Re: hash tables without GC cost

[Sam Steingold <sds@gn...>]

> * Bruno Haible <oehab@...> [2004-04-26 22:15:22 +0200]:
>
> How do I declare that the hash table does not need rehashing after GC?

either add a flag for that - our use of HT flags is overly generous, 4
flags for HT test when 3 is enough -
OR just make EQUAL instead of EQ hash tables.
since the keys are classes, EQ and EQUAL are the same.

> Can you add such an option to MAKE-HASH-TABLE?

MAKE-HASH-TABLE options are user-visible.
Some smart-ass will use it in his HT and will be stunned with

     (setf (gethash 'foo ht) 'bar)
     (gc)
     (gethash 'foo ht) ==> NIL

are we willing to live with this?
if not, we can add a setfable SYS::HT-GC-INVARIANT-P.

BTW, also adding SYS::GC-INVARIANT-P will enable us to make _some_ CASE
HT's HT-GC-INVARIANT-P and thus probably save on them too.
E.g., (case x (1 'one) (2 'two) (t 'many)) will create an HT which will
not need to be rehashed.


-- 
Sam Steingold (http://www.podval.org/~sds) running w2k
<http://www.camera.org>; <http://www.iris.org.il>; <http://www.memri.org/>;
<http://www.mideasttruth.com/>; <http://www.honestreporting.com>;
.sigs are like your face - rarely seen by you and uglier than you think

Re: hash tables without GC cost

[Bruno Haible <bruno@cl...>]

Sam wrote:
> Some smart-ass will use it in his HT and will be stunned with
>
>      (setf (gethash 'foo ht) 'bar)
>      (gc)
>      (gethash 'foo ht) ==> NIL
>
> are we willing to live with this?

No, we can give an error during (setf gethash).

> if not, we can add a setfable SYS::HT-GC-INVARIANT-P.

We can verify for the simple cases (EQ, EQL and CLASS-HASHCODE) that all
keys in the hash table are GC-invariant.

> E.g., (case x (1 'one) (2 'two) (t 'many)) will create an HT which will
> not need to be rehashed.

Cool! I hadn't thought of this.

Bruno

Re: hash tables without GC cost

[Sam Steingold <sds@gn...>]

> * Bruno Haible <oehab@...> [2004-04-27 14:31:54 +0200]:
>
> Sam wrote:
>> Some smart-ass will use it in his HT and will be stunned with
>>
>>      (setf (gethash 'foo ht) 'bar)
>>      (gc)
>>      (gethash 'foo ht) ==> NIL
>>
>> are we willing to live with this?
>
> No, we can give an error during (setf gethash).

Alternatively, just mark the table as requiring a rehash.
Actually, just create all HTs as GC-INVARIANT and turn them into
non-invariant as needed.

>> if not, we can add a setfable SYS::HT-GC-INVARIANT-P.
>
> We can verify for the simple cases (EQ, EQL and CLASS-HASHCODE) that all
> keys in the hash table are GC-invariant.

yes, before marking the HT as GC-INVARIANT, a check should be required.

BTW, how about the tree hash code?
I sent you my patch a couple of times...

-- 
Sam Steingold (http://www.podval.org/~sds) running w2k
<http://www.camera.org>; <http://www.iris.org.il>; <http://www.memri.org/>;
<http://www.mideasttruth.com/>; <http://www.honestreporting.com>;
We're too busy mopping the floor to turn off the faucet.