About :: TODO :: Blog :: RSS :: Old blog :: Projects :: GIT :: Gallery :: Notes

Fri, 16 Mar 2007

Super optimized multidimensional trie implementation.


After morning tea and quite interesting optimization lookup for 96 bit key on 32 bit arch takes about 90-100 nanoseconds! This basically means that my multidimensional trie implementation outperforms hash table in any workload with any hash table size. But I need to admit, that it is random values (three 32 bit values without zeroes in any byte, the same are used for hash table tests), so things can differ in real life.
Memory overhead is about 97 Mb.
Test was performed in userspace.

Update: and the same speed (upto 110 nanoseconds) and memory overhead (about 98 Mb) can be achieved for 160 bit keys - so they can include bound device index and protocol number.

/devel/other :: Link / Comments ()