Table of Contents

1 Introduction

1.1 Problem statement
1.2 Motivation
1.3 Recommended reading
1.4 Binary search and Eytzinger layout
1.5 Hugepages
1.6 A note on benchmarking
1.7 Cache lines
1.8 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 prefet…