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, Maciej Stachowiak wrote:
> 
> > 
> > This isn't directly on-topic, but I was going to suggest earlier that
> > you change the header alist to a vector despite your readability
> > concerns; it should be trivial to write a hashtab-header-alist or
> > hashtab-properties in Scheme to translate it, and the more I think
> > about it, the more convinced I am it would be a noticeable performance
> > win.
> > 

wow.  My hash tables are kicking some serious ass now!

jay:/gcm/jglascoe/SCHEME/GUILE/EXTENSIONS/hashtab-new
$ ./myguile -s httest.scm 
number buckets: 8192
number buckets: 8192
number buckets: 8192
number buckets: 8192
number buckets: 8192
number buckets: 8192
number buckets: 8192
number buckets: 8192
number buckets: 8192
number buckets: 8192
*time: 564*

jay:/gcm/jglascoe/SCHEME/GUILE/EXTENSIONS/hashtab-new
$ ./myguile -s gtest.scm 8192
*time: 558*

<disable "number buckets" output>

jay:/gcm/jglascoe/SCHEME/GUILE/EXTENSIONS/hashtab-new
$ ./myguile -s httest.scm 
*time: 539*

"gtest.scm" tests Guile's hash tables, the argument (8192 above) specifies
the length of the vector to be used.  "httest.scm" is the same as
"gtest.scm" (their basically copies of each other -- code re-use
moron-style ;) but tests my hash tables.  The heart of the test is

	  (for-each (insert-entry mydict insert-proc) lines)
	  (for-each (find-entry mydict find-proc) lines)

where "lines" is actually a list of 10,000 unique random numbers ranging
from -(2^28) to 2^28 - 1.  The "insert-entry" procedure uses the random
number as key (thus putting my-hasher and the Guile hasher on equal
footing) and the null list as value.  By default, my hash tables start off
with a vector of 4 buckets and resize from there.

	Jay
	jglascoe@jay.giss.nasa.gov

p.s.

my hash tables now look like this
guile> (define mytab (make-hashtab))
guile> mytab
(#(5 #f 0 0 0) . #((0) (0) (0) (0)))
guile> (do ((i 1 (+ i 1))) ((> i 30)) (hashtab-set! mytab i '()))
guile> mytab
(#(5 #f 4 1 30) . #((3 (24 24) (8 8) (16 16)) (4 (25 25) (1 1) (9 9) (17
17)) (4 (26 26) (2 2) (10 10) (18 18)) (4 (27 27) (3 3) (11 11) (19 19))
(4 (28 28) (4 4) (12 12) (20 20)) (4 (29 29) (5 5) (13 13) (21 21)) (4 (30
30) (22 22) (6 6) (14 14)) (3 (23 23) (7 7) (15 15))))