index  news

Modified 2005-02-07 09:01

Hash table performance

NOTE: I made a mistake when running the ght test with move-to-front heuristics, so it really uses transpose heuristics as well. I've not redone the tests completely, but it does not seem to make any big difference compared to transposing. Sorry. I hope the comparison should please you anyhow.

I have made a program to benchmark different hash tables. The benchmark has been run on libghthash, hsearch from GNU Libc and hash_map from the C++ STL (hash_map is an SGI extension but available almost anywhere).

Note that I'm the main author of libghthash and therefore not strictly speaking an independent part in this. I have not done any deeper research on how to do benchmarks as this fairly, so the values here should not be taken as proof of one way or the other. I am also not an expert user either on hsearch or hash_map, so I do not guarantee that I used them optimally.

The benchmark program

The benchmark program stores words from a text file in a hash table, then opens another text file and tries to find the words there in the hash table. Both the data stored and the keys are strings (actually, both the data and the key are the same), the data is never freed. Upon finding the data, the key and the data found is compared (they should match, otherwise some error has occurred).

The benchmark is separated into three parts. The first part is the main program, another part implements the benchmark (can be replaced if another benchmark is wanted) and one part that specifies an interface each hash table has to implement. All tested tables run the same program, except for the part that has to be implemented for each hash table.

When compiled, the benchmark generates one executable for each hash table to test.

Method

The benchmark programs are fed with normal books as input. More precisely, the books were "The monster men" and "Tarzan of the Apes" by Edgar Rice Burroughs and "The bible" by unknown authors. The books were not selected by any special criteria, except for "The bible" which was selected for its large size. The books have been downloaded from Project Gutenberg.

The idea with using books is that it probably provides a fairly realistic test, especially when it comes to locality of reference (some words occur often, others not). On the other hand, one might argue that the insertion phase, where many insertions fail when the program tries to insert already present words, is unrealistic. Criticism should be directed my way in that case.

Three different tests were carried out:

1. Reading words "The monster men" and matching them to "Tarzan of the Apes". This test have a fairly equal proportion between the number of elements inserted and the number of elements searched for.
2. Reading words "Tarzan of the Apes" and matching them to "The bible". This tests a case where the number of words searched is larger then the number of inserted words.
3. Reading words "The bible" and matching them to "Tarzan of the Apes". This tests a case where the number of words inserted is larger then the number of words searched for.

libghthash has automatic rehashing enabled, and has been run with different combinations of hash functions and heuristics.

All the programs are compiled with GCC with the options -O2 -DNDEBUG -Wall. -DNDEBUG removes assert-statements. The programs are also linked statically, which improves performance but generates larger executables.

The time was measured with the UNIX time program (the 'user'-part), and the tests were carried out on three computers. First on my laptop, a Pentium 150Mhz with 32 Mb RAM running Debian GNU/Linux 2.2. This tests how computers behaved a few years ago. Moreover, a dual Pentium III 500 Mhz and a Pentium IV 1.5Ghz was used, both having 256 Mb of memory.

Results

The results for all the tests can be seen below. The fastest implementation in each category (and for each computer) is marked with green, the slowest with red.

The monster men, Tarzan of the apes

Tarzan of the apes, the bible

The bible, Tarzan of the apes

It is not possible to declare which hash table is really fastest (all of them actually won some part). However, a few trends have been noticed.

• hash_map and GNU libc both caused the laptop to engage in heavy swapping in the last test. Probably the memory overhead is higher for those two implementations than libghthash. hash_map won the test even on the laptop, but the real time was much higher then libghthash's.
• The use of heuristics with libghthash improved performance, but only slightly.
• The hash function is very important (of course). The times when using rotating hash with libghthash are twice as high as for CRC or one-at-a-time hash.
• The libc hsearch was very slow on larger data. This makes me unsure if it has been used correctly. What I consider most likely, however, is that the bucket-hints was too small for "the bible" and that hsearch doesn't do rehashing.

I have also done some preliminary measurements on the average number of clock cycles used for inserting and looking up entries on the P150. The results are interesting. hash_map and GNU libc hsearch uses fewer clock cycles for inserting then looking up, whereas with libghthash inserting is more expensive than looking up.

In absolute numbers, inserting in hash_map is also cheaper than in libghthash and GNU libc hsearch (in that order). Looking up, however, is cheapest with libghthash, with hash_map second and hsearch third. This would explain why libghthash is faster when looking up words from "tarzan of the apes" in "the bible", where the lookups dominates the inserts.

The clock cycles were measured using the rdtsc instruction found in intel CPUs.

Conclusions

As said, it is not possible to declare one of the hash table implementations as winner here. Rather, all have their strong and weak points. For my own part, I'm happy to see that libghthash compared well with the other implementations.

There seems to be room for improvement in inserting elements in libghthash, and I will have a look at that some day.

Further work

The obvious work to be done here is to compare more hash tables. Especially interesting would be to see how a less general-purpose, more performence-oriented hash table would compare.

It would also be interesting to see how the hash tables would behave on a different test, not storing strings. The benchmark should be fairly easy to accomodate to this.

Download

The benchmark program can be downloaded below. It needs (currently) libghthash, GNU libc and the C++ standard template library. It is released under the GNU General Public License.

hashbenchmark.tar.gz(source, 5.1 Kb).

Project Gutenberg (free electronic books) can be found at www.gutenberg.org.

ska[at]bth[dot]se

You can click here to see some statistics on the page.