LBTree - Writing and Testing a Lookup Tree
Design
Each fork in the tree has an associated key bit index, for lookup, at each fork the indexed bit is sampled from the given key and the right or left path is traversed dependent of the value of the bit. This allows for 2 benefits over a standard search tree such as a red-black tree:
- The number of comparisons is limited to the key size in bits.
- each comparison only needs to load 1 bit of the key from memory (realistically, a character is loaded, but only 1 bit is theoretically required).
This does make the add method somewhat non-obvious, but I had an idea to perform a lookup on a key to add and take the "closest" node match, find the index of the least significant bit difference between the given key and the matched node. Work back down the tree from this until the fork's index was less than this difference index. The new node can then be inserted at this point.
Testing
I designed a test that uses a remove probability equal to the number of nodes added divided by a configurable maximum. Each iteration, if an element is not removed it is added, and if there are zero nodes in the tree at any point after the first iteration the test is complete.
Competition
To both verify my tests and to get an idea of relative performance, tsearch from glibc and LibCFU were selected as the most highly recommended comparable options. Tsearch implemnts a red-black tree and LibCFU a hash table. Note that the test requires a replace that returns the replaced element, something that to the best of my knowledge tsearch does not implement, therefore the Add test for tsearch involves 2 traversals of the tree and the results may not apply well to your use case.
The following graphs are average cycles over multiple test runs for each operation on the Y axis, plotted against maximum tree size on the X. All compiled with gcc -O3. Valgrind and KCachegrind were used to get reliable and deterministic cycle counts.
02/06/23