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.
Afficher les réponses par date