Table of Contents1 Introduction1.1 Problem statement1.2 Recommended reading1.3 Binary search and Eytzinger layout1.4 Hugepages1.5 A note on benchmarking1.6 Cache lines1.7 S-trees and B-trees2 Optimizing find2.1 Linear2.2 Auto-vectorization2.3 Trailing zeros2.4 Popcount2.5 Manual SIMD3 Optimizing the search3.1 Batching3.2 Prefetching3.3 Pointer arithmetic3.3.1 Up-front splat3.3.2 Byte-based pointers3.3.3 The final version3.4 Skip prefetch3.5 Interleave4 Optimizing the tree layout4.1 Left-tree4.2 ...