From: "news.spss.com" Date: 2002-09-06T22:30:56+09:00 Subject: Re: Ruby and Judy "Doug Baskins" wrote in message news:34b67111.0209051528.3757601d@posting.google.com... > "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. by email > > # 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. This is correct and this is also my problem with hash tables: how large should they be initially and what is the cost of growing them (there is an article in DDJ a few months back on growing arrays) - yet I must confirm hash tables actually work quite well in praxis and most datastructures breaks down in virtual memory anyway, no matter the theory. When I chose small fanout B-Trees over hash it was because I expected them to better handle small collections while still scaling well. A comparison to a dynamically growing hash table would be interesting. I also chose B-Trees becuase of they are friendlier to memory management: How do you find a large linear space for your hashtable nr. 700 in a memory mapped file, assuming you also delete data and you do not wan't an infitely large file. > # 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 Standard balanced binary trees and similar work quite well up to a certain size. Small fanout B-Trees and JUDY work better because of the improved cache line utilization. For many applications there is no reason to go beyond std::map, std::map in C++. Mikkel