Re: Scheme style auto-resizing hashtable

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

On 18 Oct 1998, Harvey J. Stein wrote:

> What about with a bigger hash table size, such as 2999 or 1499 or
> 1091?  As far as I recall, TCL's (& thus STk's) hash tables resize
> when a 4th element is inserted into a bucket.
>

these hashtables resize, the vector's length doubles, when a bucket
exceeds the max-bucket-size.  (make-hashtab 0) is a very bad idea.

> 
> It'd also be interesting to run your speed test in STk.
> 

Unfortunately, I'm not familiar with STk.  I've read a bit about it, 
but never really looked into it.

> > In fact, except for the hashing functions, both the hash tables and
> > the hashtabs could easily be rewritten in Scheme, with only a modest
> > speed penalty (umm, 100% slower?).
> 
> You implemented your hashtabs in C?
> 

but of course, I had to write them in C because I wanted them to be fast. 
And, BTW, I did get around to re-implementing the hashtabs in Scheme. The
Scheme-based hashtabs are about 2.5 times slower than the C-based ones
(not bad, really).

It was much funner (and easier) to write the thing in Scheme.  The Scheme
code is about a third as long (and the C version still doesn't have a
deletion procedure). 

I did have to write my own hashing function in C, though.  Guile's current
hashing function mods out by a given number (I tried giving it a big, big
number, but it just didn't work very well). And yes, I stole my hashing
function from Python ;)

> You can make them opaque if you want.  Have (make-hash-table) return a
> closure with the data built in.  Then do things like:
> 
<snip>
> 
> But I'd say you're better off leaving them open.
> 

I agree.  Scheme programmers should be smart enough not to hang themselves
when given a bunch of rope.

	Jay
	jglascoe@jay.giss.nasa.gov