“Doug Baskins” doug@sourcejudy.com wrote in message
news:34b67111.0208290825.45942f59@posting.google.com…
“MikkelFJ” mikkelfj-anti-spam@bigfoot.com wrote in message
news:3d68f556$0$166$edfadb0f@dspool01.news.tele.dk…
This (Judy in general) is a very interesting concept to
me, partly because I find it hard to imagine this kind
of thing coded with the kind of efficiency we seem to
talking about, and yet presumably in a platform-independent
manner.
I’m not knocking it, I’m just surprised that Judy exists.
[Mikkel]
I have been working with some similar concept using B-Trees:
Having an efficient in-memory tree with a reduced level of branching
compared to typically page sized trees does work quite efficiently.
However,
you have to have very large hash tables before the B-tree it outperforms
a
hashed 32 bit key.
Have you got some code to compare? SLcompare.c benchmark at
<www.sourcejudy.com> 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.
I couldn’t run the test as I’m running Windows.
I rewrote the test under windows on a laptop 750 MHz laptop. Given the
comparable machine configuration and the comparable getline speeds, I assume
you can compare to the data posted in the “SLCompare.c” file are reasonably
comparable. I compared to Hash and Splay, but not Judy as didn’t want to
port Judy to NT. Still I think the numbers are comparable.
Note that I modified the test slightly to terminate the line with a padding
up to a 32bit boundary. I also changed the test such the line length was
available to insert and find functions.
I banged up the optimization as much as I could to deal with the lack of
inlining in the BTrie code. The preliminary results show that the B-Trie
uses 3 times more memory than the other methods and 4 times the raw data (I
haven’t space optimized for small nodes yet so I never allocate less than
128 bytes). 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
// 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