Re: avl-trees vs. hashes

[Jay Glascoe <jglascoe@jay.giss.nasa.gov>]

> On Tue, 27 Oct 1998, Tel wrote:
> > 
> > Just a suggestion, maybe storing the hash value should be an optional
> > thing too since it is a fixed speed overhead versus a fixed memory overhead,
> > there are arguments for both depending on the situation. Ignore this
> > if it makes your code horribly complicated.
> 
> (hashtab-disable foo 'store-hash)
> (hashtab-enable foo 'store-hash)
> 
> yes, I think I could work this in alright, but the resulting code changes 
> for set!, ref, and del! would be so significant that I would just re-write
> each of them.  I would then write some wrappers to call the appropriate
> function depending on whether store-hash is true/false.

I've thought some about this suggestion and have two points to make:

1.  not storing the key's hash in the entry would be a big win for
deletion in certain, relatively common situations.  For example, if the
keys and values you use are small (relative to the size of the [big]
integer hash object), like small strings, integers, booleans, then

(hash (key . value))

is much larger than

(key . value)

and guile will have a much easier time gc'ing the smaller of the two.

2.  not storing the hash would be a big loss for resize since it's
certainly faster (err, at least I hope it is) to do this

index = (scm_num2long(SCM_CAR(entry), "foo", "bar")) % vec_len;

rather than

hash = my_fave_hasher(SCM_CAR(entry));
index = hash % vec_len;

but then again, the speed of the hasher depends on the size of the key
you're hashing.  So if you've small keys...

> 
> > 
> > 	- Tel
> > 
> 
>