This is the mail archive of the guile@cygnus.com mailing list for the guile project.

Index Nav: [Date Index] [Subject Index] [Author Index] [Thread Index]
Message Nav: [Date Prev] [Date Next] [Thread Prev] [Thread Next]

Re: Scheme style auto-resizing hashtable

On Fri, 23 Oct 1998, Jay Glascoe wrote:

> I've found that the expected maximum bucket size seems to be related to
> log(number-entries).  I can't prove that, but I am currently modifying
> max-bucket-size to grow at this rate and it does seems to work well. 
> 
....
> 
> My current tests use a big file filled with unique, and very large, random
> numbers.  But still, the bigger the hashtable, the bigger the expected
> largest bucket size (relative to average bucket size).
> 

in my resize function, I have

	if (imax_bucket_size < log_inumber_entries)
	{
	    imax_bucket_size = (int)floor(log_inumber_entries + 0.5);
	    max_bucket_size = SCM_MAKINUM(imax_bucket_size);
	}

which gives fantastic performance.  For large hashes (~100,000 entries),
I'm actually out-pacing the Python-style dictionaries.  (Which are opaque,
all the book-keeping is kept in a C struct, whereas my hash tables are 
constantly convert numbers back and forth between C and Scheme).

> 	Jay
> 	jglascoe@jay.giss.nasa.gov
> 
> 
>