[gambit-list] About tables and equal? performance

Christian christian at pflanze.mine.nu
Sun May 14 12:04:00 EDT 2006


Hello

I've tested the performance of the Gambit (hash-)tables. When loaded
with many values, they beat perl hashes (I've tried to only measure
the actual hash manipulation in perl, which means I've subtracted the
time needed for loops. The following timings are a bit unfair to perl
though, since perl is treating integers as strings in hash keys.)

My timings with big tables (1 mio keys) and random integers as keys
(on a Athlon (32bit) 2Ghz, Debian, perl 5.8.7):

One table-ref requires about 1500 cpu cycles. Table-set! with
previously non-existing keys called on a table which has not been
created with a big enough initial size (e.g. resizing is necessary)
requires about 3000-5000 cycles. Perl requires about 5500 cycles per
hash write (with this many keys). (When pre-allocating gambit tables
with a big enough size, writing time drops to about 1330 cycles.)

BTW, the purely functional wt-tree implementation found in mit-scheme
or slib, adapted to gambit by me (ask me if you want the code)
requires about 5000 cycles per read. Adding a new value takes about
15000 cycles.

I guess Gambit is so fast because it uses open-addressing (afaik, perl
is using (or at least has been in the past) linked lists for the
buckets), and because I'm using real integers in Gambit, whereas perl
treats everything as strings when being used as keys.


But surprisingly, accessing or updating small hashes in perl is very
fast. With something like

   perl -we 'for(1..10000000){$z{"funun"}++}; print keys(%z),"\n"'

each hash update (after subtraction of the loop time) only takes about
300 cycles. (I don't know whether they are reverting to a different
data structure in this case or if it's just that fast.)


I've written a table implementation for small tables, which can be
found at http://scheme.mine.nu/gambit/scratch/quicktable/. (The
implementation using vectors is a bit faster than the one (also
included there) using alists.)

This implementation takes about 200 cycles for one
quicktable-ref/add1/quicktable-set! operation series, or about 160
cycles for one quicktable-update! operation (both when using eq? for
key comparison), whereas Gambit's builtin table implementation takes
about 1200 cycles for one table-ref/add1/table-set! operation series.

Maybe my approach (just scanning the vector linearly, instead of
calculating a hash value first to be used for addressing, if the table
size is small) could be integrated into the gambit table
implementation easily? There is one issue about this though: I must
warn that the scan in quicktables is only fast when using
eq?. Gambit's equal? function is very slow. Just comparing about 2-5
keys using equal? increases the time to about the same 1200 cycles as
taken by the current Gambit hash tables. Now I'm not sure if that's
only because equal? is not inlined (as I've mentioned in a previous
mail, such function calls cost about 200 cycles), or if its
implementation is slow.

(BTW I'm also a bit surprised how costly structures are in safe
mode. Doing manual safety checks and declaring (not safe) is *much*
faster.)

Cheers
Christian.




More information about the Gambit-list mailing list