Re: Ruby and Judy

"Doug Baskins" <[e-mail]> wrote in message
news:[e-mail]...
> "MikkelFJ" <[e-mail]> wrote in message
news:<3d68f556$0$166$[e-mail]>...
> > > 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