From: "(Doug Baskins)" (Doug Baskins) Date: 2002-09-06T08:49:23+09:00 Subject: Re: Ruby and Judy "MikkelFJ" wrote in message news:<3d7531f5$0$59288$edfadb0f@dspool01.news.tele.dk>... > > [Doug Baskins] > > Have you got some code to compare? SLcompare.c benchmark at > > compares JudySL with the best 3 methods I have > > been able to get code. I do not write code for known methods because > > I am too tainted. Still looking forward to adding your code to the benchmark. ....del > [Mikkel] > It also showed that for small datasets (8000 lines, 300KB i.e. > Hamlet), the B-Trie is actually faster than the hash. For larger sets it is > slower than the hash but consistently faster than the Splay tree. > In comparison I also noted that a "strdup" and a hash key operation both > takes about 0.5 uS so all methods are quite fast. > > Note: memory is measured as requested alloc size, not counting internal > allocator overhead. > > I didn't test the full Google repos.00 as I didn't have enough RAM - not > with the memory consumed by the BTrie anyway. > > // test machine Windows 2000, IBM X21 laptop, 392MB RAM, 750 MHz PIII. > > // test data set: 338.528 bytes > // http://the-tech.mit.edu/Shakespeare/hamlet/full.html > // this test set requires hi-res timer, clock() can't separate hash from > btrie. > # hamlet.html > # lines avg_linelen getline dup_lines RAMused/line store/line > lookup/line ADT > 7728 43.8 bytes 0.640 uS 2770 181.9 bytes 2.036 uS > 1.606 uS BTrie > 7728 43.8 bytes 0.668 uS 2770 68.0 bytes 2.543 uS > 1.943 uS SPLAY > 7728 43.8 bytes 0.643 uS 2770 60.0 bytes 2.500 uS > 1.687 uS HASH Thought I would throw in my 2 cents. My hash table was 2^20 in size which is why I think the insert time for Hash is high. I wouldn't put much stock in benchmarks that are mostly in the data cache -- results might not be representive of typical use. wc Hamlet.html 8882 39581 349041 Hamlet.html This test deletes blank lines -- 8882 - 7729 = 1165 lines. I shortened the number of colums of output to fit: getline = 0.670 uS for all # Judy Hamlet.html #lines avg_linelen Uqlines RAMused/line store lookup/line ADT 7729 45.2 bytes 4959 60.2 bytes 2.506 uS 1.591 uS JUDY 7729 45.2 bytes 4959 77.5 bytes 4.654 uS 1.622 uS HASH 7729 45.2 bytes 4959 85.6 bytes 2.487 uS 2.048 uS SPLAY 7729 45.2 bytes 4959 85.7 bytes 2.974 uS 2.243 uS REDBL > > // test data set: 9.907.357 bytes > // first 200000 lines of google repos.00 testset > # rp200.txt > # lines avg_linelen getline dup_lines RAMused/line store/line > lookup/line ADT > 199998 49.5 bytes 0.591 uS 83703 234.9 bytes 2.973 uS > 2.433 uS BTrie > 199998 49.5 bytes 0.591 uS 83703 85.5 bytes 3.732 uS > 3.150 uS SPLAY > 199998 49.5 bytes 0.596 uS 83703 77.5 bytes 2.353 uS > 1.827 uS HASH > > test data set: 50.045.886 bytes > first 1.000.000 lines of test data set > # rp1000.txt > # lines avg_linelen getline dup_lines RAMused/line store/line > lookup/line ADT > 997621 50.2 bytes 0.606 uS 452649 234.3 bytes 3.450 uS > 2.940 uS BTrie > 997621 50.2 bytes 0.605 uS 452649 87.7 bytes 4.523 uS > 4.001 uS SPLAY > 997621 50.2 bytes 0.607 uS 452649 79.7 bytes 2.384 uS 1.90 > 9 uS HASH > > Mikkel Doug Baskins