About TODO Blog RSS Old blog Projects Gallery Notes

Thu, 15 Mar 2007

Multidimensional trie vs. hash table benchmarking.


This time I generated 2^20 elements and inserted them into trie and hash tables with different sizes and with different hash functions.
Lookup was performed for the same elements.
This test allows to eliminate rand(3) influence in lookup performance and allows to see how badly actual data is distributed in the hash tables and trie.

First data - distribution of elements in different layers of hash/trie - each point shows how many lookups are needed (x axis) to get one of the 2^20 elements.



As you can see, mdt trie can access total majority of elements in 3 lookups, while hash table with 2^20 elements has access 'length' of about 1-3 elements per hash chain. With decreased hash size peak is smoothed and overall length of the chain is increased as expected. Number in filename in the upper right corner (like /tmp/jhash_order_19.dist shows order of the size of the hash table).
I need to say, that mdt trie used in test has maximum access 'length' of 4 by design per 32 bits. This picture shows numbers only for one 32 bit entry lookup.

Next data is hash table/mdt trie scalability, i.e. time per one lookup depending on size of the hash table. MDT trie has constant access time showed for reference.



Conclusions.
As you can see, for 2^20 elements in the system, mdt trie performs better than hash table with 2^17.5 elements and about 2.6 times slower than 2^20 elements.
This tests were run in userspace, so increased memory usage (three tries ate about 285 Mb of memory) and per-4k tlb miss can play significant role in benchmark.

So, I as author of the trie implementation, can confirm, that it sucks compared to properly selected hash table as is. But getting into account its additional benefits like lock-less traversal and constant upper bound of access time, it might worth to have.
I will cook up a patch tomorrow and send it to netdev@ for review with link to this analysis.

/devel/other :: Link / Comments (0)