Static search trees: faster than binary search

Totally off topic, but I&#x27;ve started to notice that more and more algorithmic low-ish level content assumes Rust by default. My entire life I&#x27;ve been used to anything algorithmic being either written in sciency pseudocode (invariably in latex-generated PDFs), or plain old C(++), the vulgar latin of computer programming. I know C and I don&#x27;t really know Rust but nevertheless I love that this is changing! I&#x27;d never advise a new programmer interested in low-level&#x2F;fast stuff to begin with C now, so much good content is written around Rust. Like the old C examples, the post doesn&#x27;t even say &quot;this is Rust&quot;. You&#x27;re expected to expect it to be Rust.<p>And, well the language choice doesn&#x27;t really matter for the core subject here. I could follow this post fine even though I don&#x27;t really know Rust (just like I assume a Rust programmer could follow a well written algorithms deep dive with examples in C with a bit of dedication). EDIT okok that was a lie, I could follow the first half of this post, ish, and then it got way too deep for me.<p>But anyway, standardize on Rust, I like it. I&#x27;d love if a bit more Zig was thrown into the mix here but either of them feel like a better default than C at this point to me. After decades of C being <i>The Standard</i> for this stuff, I love that this is finally changing.

One dimension that is not explored is partitioning the <i>queries</i> in batches. The primary cost is doing lookups on the out-of-cache table, so if you have a sufficiently large amount of queries you can resolve a couple layers of the tree in one step while those layers are in cache, grouping them based on where they land deeper in the tree, and then resolving all those queries that touch the same deeper part of the tree in one batch as well.<p>In theory, with an infinitely large amount of input queries you will never have to do an out-of-cache lookup, it can be completely amortized away into linear scans.<p>That said, you now end up with a bunch of results that need to be put back into the correct output order, which likely makes it not worth it. But if the operation can be fused into a reduction (e.g. find the <i>sum</i> of the binary search results) or the output order does not matter in some other way then all of a sudden it might make sense.

Amazingly thorough ! I love how the author leaves no stone unturned. I had no idea you could do the kind of low level efficiency shaving in Rust. I wonder how a C++ implementation with <a href="https:&#x2F;&#x2F;github.com&#x2F;jfalcou&#x2F;eve">https:&#x2F;&#x2F;github.com&#x2F;jfalcou&#x2F;eve</a> would compare.

Nifty thing about eytzinger trees is that there&#x27;s a formula for converting from a node index to its position in an inorder traversal.<p>This is useful if your primary keystore is a normal sorted set of keys - easier to work with - you then don&#x27;t need to store explicit pointers.<p>Also, he didn&#x27;t mention that with eytzinger you can prefetch multiple loop iterations in advance - use 1-based indexing so that sibling nodes line up nicely on cachelines.

this is unbelievably cool. ~27ns overhead for searching for a u32 in a 4GB set in memory is unreal.<p>it&#x27;s interesting that the wins for batching start diminishing at 8. I&#x27;m curious then how the subsequent optimizations fare with batch size 8 (rather than 128).<p>smaller batch sizes are nice since it determines how much request throughput we&#x27;d need to saturate this system. at batch size 8, we need 1s &#x2F; ~30ns * 8 = 266M searches per second to fully utilize this algorithm.<p>the multithreading results are also interesting -- going from 1 to 6 threads only improves overhead by 4x. curious how this fares on a much higher core count machine.

The number of unique int32 values is not that great, and a full bitset would only be 512MB. Hard to bit a dense bitset in performance.<p>As a general purpose data structure, I would look at roaring bitmaps for this purpose, which has good trade-offs with great performance for most use-cases.<p>If only simple lookups are needed over a static set, then it&#x27;s worth looking at minimal perfect hash functions (<a href="https:&#x2F;&#x2F;sux.di.unimi.it" rel="nofollow">https:&#x2F;&#x2F;sux.di.unimi.it</a>).

All this nattering about rust and C++, and then there&#x27;s me thinking about how to do it in Common Lisp, possibly keeping the simd bits.

This is really interesting and a thorough write up. Thanks to the author for sharing their work.<p>Whenever I read about super low-level optimisation, my immediate feeling is that of gratitude to the author for spending so much time shaving off nanoseconds which the entire SE community gets to enjoy.<p>I wonder how much time humanity has collectively saved simply as a result of how all these optimisations stack up.

I think there is an error in 1.7 figure 3: Layer 1 should have a 10 instead of a 12.<p>Edit: Also, 1.3 figure 1: Should the y-axis label be &quot;Inverse throughput&quot; to match later figures?

Interesting. If you need to support occasional writes, you could have a large static search tree and a small writable tree that you check afterwards. The when you have enough changes, you could occasionally ship those changes into a new version of the static tree

suffix-array-searching&#x2F;static-search-tree&#x2F;src&#x2F;s_tree.rs: <a href="https:&#x2F;&#x2F;github.com&#x2F;RagnarGrootKoerkamp&#x2F;suffix-array-searching&#x2F;blob&#x2F;master&#x2F;static-search-tree&#x2F;src&#x2F;s_tree.rs">https:&#x2F;&#x2F;github.com&#x2F;RagnarGrootKoerkamp&#x2F;suffix-array-searchin...</a> partitioned_s_tree.rs: <a href="https:&#x2F;&#x2F;github.com&#x2F;RagnarGrootKoerkamp&#x2F;suffix-array-searching&#x2F;blob&#x2F;master&#x2F;static-search-tree&#x2F;src&#x2F;partitioned_s_tree.rs">https:&#x2F;&#x2F;github.com&#x2F;RagnarGrootKoerkamp&#x2F;suffix-array-searchin...</a>

Recently I tried to optimize a set implementation and found that interpolation search works quite well, being competitive with HashSet in C# (both single digit ns for my use case), with zero memory overhead. Unfortunately, it only works well with uniform data, so I guess I&#x27;ll give static search trees a try. This explanation was clear and extremelly well detailed.

Given the fact that the keys are fixed-size integers with a not-too-terrible distribution, I would consider chasing the partitioning idea a bit harder, and possibly even removing all the fancy S-tree parts. Some ideas:<p>For 32 bits, using the first few or even a lot (16? 20?) bits to index an array and then chasing down the remaining bits somehow (adaptively depending on size of that partition?) seems like it could work.<p>In this direction, and with really impressive asymptotic performance, there’s the van Emde Boas tree and its variants.

I wish graph did not show 2 values with the same blue color

Elastic Binary Trees <a href="https:&#x2F;&#x2F;wtarreau.blogspot.com&#x2F;2011&#x2F;12&#x2F;elastic-binary-trees-ebtree.html?m=1" rel="nofollow">https:&#x2F;&#x2F;wtarreau.blogspot.com&#x2F;2011&#x2F;12&#x2F;elastic-binary-trees-e...</a>

Nice post. Would the larger amount of code result in different performance in a scenario where other code is being run as well, or would the instruction cache be large enough to make this a non-issue?

I&#x27;ve never had the use case for this amount of throughput. What are use-cases for this. From the website I presume this is gene-matching related?

Is binary search on su ch large integer data sets common? I guess maybe time series data. But I would think that this isn’t amenable to representing strings?

Absolutely love the level of detail here! Not often you see the process of optimising something spelled out in so much depth

This looks like something that patricia trees would be good for.<p>Then again, Eytzinger looks like binary heaps.

cant understand the comp sci stuff yet, but love the way this site looks

so a tree when the data cannot be updated?<p>What is the point?

Cool! Thanks for the investigation.

I predict that more and more of these kinds of optimized algorithms will be designed &#x2F; written &#x2F; assisted by machines.<p>I wonder when the next such malicious algorithm(s) passes under our noses, and what its hidden purpose might be.

This would have been easier for a larger number of people to read if it had been in C or Python.

This is a great new interview question for junior and senior software engineering candidates.<p>Definitely going to use this for our next round of interviews.