In the previous lessons, we built a benchmarking lab and learned how to map algorithmic complexity. Now, we are going to use all of these tools to answer a typical, real world question we might have in our project:

"I have an array of objects. I need to find specific items. Should I just scan the vector, or should I sort it and use binary search?"

We will benchmark these two strategies against each other. We'll imagine the data we're working with a std::vector<Player>, and each Player looks like the following:

Player.h

1struct Player {
2  int id;
3  int score;
4  int health;
5};

We frequently need to find specific players in our collection based on their ID. We have two contending strategies. We leave the vector exactly as it is. When we need to find a player, we use linear search - an $O(n)$ algorithm.

Alternatively, we sort the array by ID at a $O(n \log n)$ cost. Then, we can use binary search at $O(\log n)$ cost any time we need to find a player by ID.

So which is better? It depends. This isn't really helpful, so we generally want to ask a different question: "under what conditions is this better?" In this scenario, the answer we're trying to get is "under what conditions should I consider sorting my data?"

The Lookup Reality

Before we even consider the cost of sorting, let's check our premises. Will binary search ever be faster than linear search for the data we're working with?

We know linear search is hardware-friendly so, even if the data was already sorted and we didn't need to pay the cost, we might still prefer linear search to binary search. Let's test.

We will create a benchmark that runs on already sorted data. We will compare find() (linear search) against binary_search():

benchmarks/main.cpp

1#include <benchmark/benchmark.h>
2#include <vector>
3#include <algorithm>
4#include <random>
5#include <ranges>
6
7struct Player {/*...*/};
13
14std::vector<Player> GetSortedPlayers(int n) {/*...*/};
20
21static void BM_LinearLookup(benchmark::State& state) {
22  int n = state.range(0);
23  
24  // Player ids from GetSortedPlayers() range from 0 to n*2
25  auto players = GetSortedPlayers(n);
26  
27  int target = n; // Look for a middle-ish value
28
29  for (auto _ : state) {
30    auto result = std::ranges::find(players, target, &Player::id);
31    benchmark::DoNotOptimize(result);
32  }
33}
34
35static void BM_BinaryLookup(benchmark::State& state) {
36  int n = state.range(0);
37  auto players = GetSortedPlayers(n);
38  int target = n;
39
40  for (auto _ : state) {
41    auto result = std::ranges::binary_search(
42      players, target, {}, &Player::id
43    );
44    benchmark::DoNotOptimize(result );
45  }
46}
47
48BENCHMARK(BM_LinearLookup)->RangeMultiplier(2)->Range(4, 128);
49BENCHMARK(BM_BinaryLookup)->RangeMultiplier(2)->Range(4, 128);

Benchmarking Results

On my machine, this experiment produced the following results:

1----------------------------
2Benchmark                CPU
3----------------------------
4BM_LinearLookup/4    2.14 ns
5BM_LinearLookup/8    2.92 ns
6BM_LinearLookup/16   4.60 ns
7BM_LinearLookup/32   6.14 ns
8BM_LinearLookup/64   11.5 ns
9BM_BinaryLookup/4    3.08 ns
10BM_BinaryLookup/8    3.30 ns
11BM_BinaryLookup/16   4.01 ns
12BM_BinaryLookup/32   4.60 ns
13BM_BinaryLookup/64   5.94 ns

So, with 8 or fewer items in our collection, linear search wins. Binary search begins to outperform the scanning when $n \ge 16$ . Note these results are only valid for this experiment. If we change the variables, the result will change. The two most important variables for this experiment are:

The hardware running the benchmarks: We should run our benchmarks on hardware representative of how our final code will be used
The data type being used: If our type was more expensive to compare (usually the == operator), doing fewer comparisons would skew the results in favor of binary search. If the type was more expensive to sort (usually the < operator) and move, that would hurt binary search.

But, for this scenario, we can see that if we're dealing with $n \le 8$ then we wouldn't sort our data. Even if it was already sorted, we'd just use linear search. For $n \ge 16$ , we should start considering binary search. But we haven't factored in the cost of sorting yet.

The Cost of Sorting

Let's switch our parameters - we'll assume we know that we're working with player counts in the region of 10,000. Based on our previous results, we know binary search will be much faster than linear scans on that data.

But the binary search has a prerequisite: the data must be sorted. We have to pay a cost to sort it. And specifically, it must be sorted based on the thing we're searching for. If we want to find a player by id and the data is sorted by score, that isn't helpful. We'd need to use linear search, or re-sort the data by id.

Additionally, if players are being added and removed from the array, or if the thing we're searching by can change (like the player's score), we have to pay the cost to sort it again if we want to keep using binary search.

If we sort the vector and then only look up one player before we need to resort it, we have made a terrible investment. We paid for a full sort just to avoid a single linear scan.

If we sort the vector and then look up one million players, we have probably made a fantastic investment. The massive savings on the searches should pay for the initial sort.

But where is the break-even point?

Implementing the Amortization Benchmark

Mathematically, we are looking for the number of queries $K$ where:

\text{Sort} + (K \times \text{Binary}) < (K \times \text{Linear})

To find $K$ , we need a benchmark that simulates the full lifecycle: prepare + query.

We will fix our dataset size ( $n$ ) to a number we know our project requires (e.g., $n=10,000$ ). Then, we will vary the number of searches per sort ( $K$ ) using the library's range feature.

benchmarks/main.cpp

1#include <benchmark/benchmark.h>
2#include <vector>
3#include <algorithm>
4#include <random>
5#include <ranges>
6
7struct Player {/*...*/};
13
14std::vector<Player> GenerateRandomPlayers() {/*...*/};
25
26void GenerateRandomQueries() {/*...*/};
35
36const int N = 10000;
37
38// No setup cost, high query cost
39static void BM_RepeatedLinear(benchmark::State& state) {
40  auto original_data = GenerateRandomPlayers(N);
41  
42  // Create K random queries
43  int K = state.range(0);
44  std::vector<int> queries(K);
45  GenerateRandomQueries(queries, N * 10); 
46
47  for (auto _ : state) {
48    std::vector<Player> players = original_data; 
49    
50    // Perform K linear searches
51    for (int target_id : queries) {
52      auto result = std::ranges::find(
53        players, target_id, &Player::id
54      );
55      benchmark::DoNotOptimize(result);
56    }
57  }
58}
59
60// High setup cost (Sort), low query cost
61static void BM_SortAndBinary(benchmark::State& state) {
62  auto original_data = GenerateRandomPlayers(N);
63  
64  // Create K random queries
65  int K = state.range(0);
66  std::vector<int> queries(K);
67  GenerateRandomQueries(queries, N * 10); 
68
69  for (auto _ : state) {
70    std::vector<Player> players = original_data;
71    
72    // THE COST: Sort the vector
73    std::ranges::sort(players, {}, &Player::id);
74    
75    // THE BENEFIT: K binary searches
76    for (int target_id : queries) {
77      auto result = std::ranges::binary_search(
78        players, target, {}, &Player::id
79      );
80      benchmark::DoNotOptimize(result);
81    }
82  }
83}
84
85BENCHMARK(BM_RepeatedLinear)
86  ->Range(1, 1<<10) // Number of Queries (K)
87  ->Unit(benchmark::kMillisecond);
88  
89BENCHMARK(BM_SortAndBinary)
90  ->Range(1, 1<<10) // Number of Queries (K)
91  ->Unit(benchmark::kMillisecond);

Amortization Benchmark Results

Here are the results from my machine:

1---------------------------------
2Benchmark                     CPU
3---------------------------------
4BM_RepeatedLinear/1      0.004 ms
5BM_RepeatedLinear/8      0.020 ms
6BM_RepeatedLinear/64     0.153 ms
7BM_RepeatedLinear/512     1.29 ms
8BM_RepeatedLinear/1024    2.35 ms
9BM_SortAndBinary/1       0.475 ms
10BM_SortAndBinary/8       0.455 ms
11BM_SortAndBinary/64      0.445 ms
12BM_SortAndBinary/512     0.481 ms
13BM_SortAndBinary/1024    0.502 ms

So, for these variables, on this hardware, our basic linear searching strategy wins for $K \le 64$ , whilst sort + binary search wins for $K \ge 512$ . We can run this again with a tighter range within these bounds to get a more accurate result if needed.

But from these results, we can conclude that if we typically get fewer than 64 reads of our data before we need to sort it again, the investment doesn't pay off. If we read our data 512 times or more between sorts, the sorts are a good investment.

Obviously, there is a lot of nuance here, and real world software is a lot more complex. Perhaps we can sort the data in a different thread, making it much cheaper. Perhaps other components in our system have pointers to our players, making sorting more disruptive as it invalidates those pointers.

The most important thing for now is that we have a lab to test our ideas. The academic theory gives us intuition on what ideas are worth experimenting with, and the lab lets us test if those ideas hold water in our specific use cases, with our specific data types.

Amortized Costs and Crossover Points

Player.h

The Lookup Reality

benchmarks/main.cpp

Benchmarking Results

The Cost of Sorting

Implementing the Amortization Benchmark

benchmarks/main.cpp

Amortization Benchmark Results

Google Benchmark for C++