Table of Contents

1 Introduction

1.1 Problem statement
1.2 Recommended reading
1.3 Binary search and Eytzinger layout
1.4 Hugepages
1.5 A note on benchmarking
1.6 Cache lines
1.7 S-trees and B-trees


2 Optimizing find

2.1 Linear
2.2 Auto-vectorization
2.3 Trailing zeros
2.4 Popcount
2.5 Manual SIMD


3 Optimizing the search

3.1 Batching
3.2 Prefetching
3.3 Pointer arithmetic

3.3.1 Up-front splat
3.3.2 Byte-based pointers
3.3.3 The final version


3.4 Skip prefetch
3.5 Interleave


4 Optimizing the tree layout

4.1 Left-tree
4.2 Memory layouts
4.3 Node size \(B=15\)

4.3.1 Data structure size


4.4 Summary


5 Prefix partitioning

5.1 Full layout
5.2 Compact subtrees
5.3 The best of both: compact first level
5.4 Overlapping trees
5.5 Human data
5.6 Prefix map
5.7 Summary


6 Multi-threaded comparison
7 Conclusion

7.1 Future work

7.1.1 Branchy search
7.1.2 Interpolation search
7.1.3 Packing data smaller
7.1.4 Returning indices in original data
7.1.5 Range queries







In this post, we will implement a static search tree (S+ tree) for
high-throughput searching of sorted data, as introduced on Algorithmica.
We’ll mostly take the code presented there as a starting point, and optimize it
to its limits. For a large part, I’m simply taking the ‘future work’ ideas of that post
and implementing them. And then there will be a bunch of looking at assembly
code to shave off all the instructions we can.
Lastly, there will be one big addition to optimize throughput: batching.

Hacker News is a community-driven platform for sharing and discussing technology news, startups, and programming-related topics. Through user submissions and comments, Hacker News offers insights into emerging technology trends, industry developments, and entrepreneurial ventures. Readers can participate in discussions, share their insights, and stay informed about the latest advancements in technology and innovation.

Hacker News

The post introduces and optimizes a static search tree (S+ tree) to enhance the high-throughput searching of sorted data. The implementation involves various strategies such as batching, prefetching, and optimized tree layouts. The optimization techniques include auto-vectorization, manual SIMD, and using hugepages for better memory management. The post provides significant speedup (over 40x) compared to traditional binary search by reducing the number of memory access and improving CPU efficiency.

Static search trees: 40x faster than binary search

5.3 The best of both: compact first level

<p>For those wondering, this is optimized for the case when you want to make a huge number of binary searches all at once. The input is an (large) array of values to search.</p>
