Table of Contents 1Introduction1.1Problem statement 1.2Motivation 1.3Recommended reading 1.4Binary search and Eytzinger layout 1.5Hugepages 1.6A note on benchmarking 1.7Cache lines 1.8S-trees and B-trees 2Optimizing find2.1Linear 2.2Auto-vectorization 2.3Trailing zeros 2.4Popcount 2.5Manual SIMD 3Optimizing the search3.1Batching 3.2Prefetching 3.3Pointer arithmetic3.3.1Up-front splat 3.3.2Byte-based pointers 3.3.3The final version 3.4Skip prefetch 3.5Interleave 4Optimizing the tree layout4.1L...
