#14 header only implementation

open
nobody
None
5
2006-01-30
2006-01-30
Anton Povarov
No

Hello.

First i'd like to thank you for the remarkable job
you've acomplished on Judy!

i've made some simple tests recently comparing
judy and almost-standard C++ hash tables, namely
the gcc implementation.

and it seems that judy performs 2 times worse than
the general purpose hash table! :(
AFAIK this is because the compiler is able to
optimize the c++ example because it has full access
to it's source code and in the case with Judy it
doesn't. compiling Judy from sources with maximum
optimizations turned on doesn't seem to help it.

of course the __gnu_cxx::hash_map benefints
greatly from the larger number of hash buckets, but
if we turn optimization off it performs 3 times worse
than Judy.

therefore i suppose if one had the header only Judy
implementation she can get two/three times faster
lookups!

have i missed something?

and here are the test results.

this is the judy implemetation from the first example
(http://judy.sf.net/examples/Judy_hashing.pdf)
> gcc -O3 -msse2 -march=pentium4 -o simple
simple.c -lJudy
> ./simple
Storing 1000000 random numbers in a Judy scalable
hash array.
Insertion of 1000000 indexes took 1.061 microsec/
index.
Retrieval of 1000000 indexes took 0.577 microsec/
index.

and here are the results for __gnu_cxx::hash_map
> g++ -O3 -msse2 -march=pentium4 -o
common_hash common_hash.cc
> ./common_hash
Begin storing 1000000 random numbers in a
__gnu_cxx::hash_map.
Insertion of 1000000 indexes took 1.134 microsec/
index.
Retrieval of 1000000 indexes took 0.284 microsec/
index.

please see attached files for full source code(the
common_hash.cc is attached, and simple.c can be
copy-pasted from the example pdf, sf.net allows
attaching only one file :( ).

thanks.

Discussion

  • S. Nikolov
    S. Nikolov
    2006-05-05

    Logged In: YES
    user_id=1253319

    Sorry for butting in (I am not affiliated with judy).
    2 comments
    1) Compilers that can do IPO (interprocedural optimization)
    such as the intel icc obviate the need for a header only
    implementation. Implementing everything in headers tends to
    create mess (look at linux kernel headers for an example).
    2) are you sure the random number sequences are comparable?
    If not, then you may be comparing apples to oranges.