In the previous lesson, we established the syntax for working with bits. In this lesson, we will use these techniques to pack multiple boolean values together, using | to set them and & to check them.

The immediate benefit of this is memory density. A bool requires 1 byte of memory to store a single boolean value, but a uint8_t can store 8 booleans - one per bit - in the same space. We can there therefore shrink our bandwidth and storage demands by up to 87%.

This also improves our cache efficiency, but there is a second benefit that is often even more impactful: execution speed. When we process game entities, financial transactions, or network packets, we often ask compound questions: "Is this entity alive AND friendly AND nearby?"

Our typical instinct is to write this using the logical AND operator (&&). This operator has a specific behavior called short-circuiting. If the first condition is false, it skips the rest.

In theory, this sounds good. Fewer variables are checked, so short-circuiting saves work. But what happens in reality?

Boolean Algebra

Let's imagine we have a collection of players. Each player has three boolean properties, stored as standard bool types (1 byte each).

1struct Player {
2  bool friendly;
3  bool alive;
4  bool nearby;
5};
6
7std::vector<Player> players;

If we want to count how many players satisfy all three conditions, the typical approach looks like this:

1int count = 0;
2for (const auto& p : players) {
3  // If the player can help...
4  if (p.friendly && p.alive && p.nearby) {
5    // ...then increase count by 1
6    count++;
7  }
8}

This code contains three hidden if statements (branches). The CPU checks friendly. If true, it jumps to check alive. If true, it jumps to check nearby. If true, it increments the count.

Now consider the bitwise alternative. We treat the booleans as integers (0 or 1) and use the bitwise AND (&) operator.

1int count = 0;
2for (const auto& p : players) {
3  // Important: using & operator, not &&
4  bool canHelp = (p.friendly & p.alive & p.nearby);
5
6  // Increase count by 0 or 1
7  count += int(canHelp);
8}

Benchmarking

Why would we want to do more work? Logic tells us that checking three variables is slower than checking just one. If p.friendly is false, we know canHelp will be false. Checking p.alive and p.nearby would be a waste of resources - it won't change the result.

Let's verify this hypothesis with a benchmark, using the lab we created in a . We will generate a large dataset of random booleans and compare the two approaches.

1#include <benchmark/benchmark.h>
2#include <vector>
3#include <random>
4#include <algorithm>
5
6struct Player {
7  bool friendly;
8  bool alive;
9  bool nearby;
10};
11
12std::vector<Player> GenerateData(size_t size) {/*...*/}
25
26static void BM_PlayerFlag_Logical(benchmark::State& state) {
27  auto players = GenerateData(state.range(0));
28    
29  for (auto _ : state) {
30    int count = 0;
31    for (const auto& p : players) {
32      if (p.friendly && p.alive && p.nearby) {
33        count++;
34      }
35    }
36
37    benchmark::DoNotOptimize(count);
38  }
39}
40
41static void BM_PlayerFlag_Bitwise(benchmark::State& state) {
42  auto players = GenerateData(state.range(0));
43    
44  for (auto _ : state) {
45    int count = 0;
46    for (const auto& p : players) {
47      bool canHelp = (p.friendly & p.alive & p.nearby);
48      count += int(canHelp);
49    }
50    benchmark::DoNotOptimize(count);
51  }
52}
53
54#define BENCHMARK_CONFIG(FUNC) \
55  BENCHMARK(FUNC) \
56    ->RangeMultiplier(10) \
57    ->Range(100000, 10000000) \
58    ->Unit(benchmark::kMillisecond)
59
60BENCHMARK_CONFIG(BM_PlayerFlag_Logical);
61BENCHMARK_CONFIG(BM_PlayerFlag_Bitwise);

The "dumb" bitwise approach that checks all the variables is over 10x faster on my system:

1-----------------------------------------
2Benchmark                             CPU
3-----------------------------------------
4BM_PlayerFlag_Logical/100000     0.586 ms
5BM_PlayerFlag_Logical/1000000     5.72 ms
6BM_PlayerFlag_Logical/10000000    56.2 ms
7BM_PlayerFlag_Bitwise/100000     0.047 ms
8BM_PlayerFlag_Bitwise/1000000    0.471 ms
9BM_PlayerFlag_Bitwise/10000000    4.85 ms

So, what is going on here? Why is the "smarter" code that checks fewer variables so much slower? There are a few compounding reasons for this, but two are particularly important.

The first is that the bitwise approach is easier to automatically vectorize, which allows it to use SIMD techniques we covered in a .

The second advantage of the bitwise implementation is that it eliminates branch mispredictions.

Branch Misprediction

Modern CPUs are factories. They fetch instructions, decode them, and execute them in stages. To keep the factory moving, the CPU tries to guess the outcome of if statements before they happen. This is branch prediction.

If the data is predictable (e.g., all players are friendly), the predictor guesses right, and the pipeline flows smoothly. The logical && is fast in this case.

But in our benchmark (and in many real-world situations), the data is random. The CPU guesses "true", but the data is "false" half of the time.

Pipeline Flush: The CPU realizes it guessed wrong.
Stall: It must throw away all the work currently in the pipeline (10-20 cycles).
Restart: It starts fetching the correct instructions.

The bitwise version has no branches. It executes simple, 1-cycle instructions. The CPU never has to guess, never has to stop, and never flushes the pipeline. Even though it technically evaluates "more" variables, it finishes sooner because it never trips.

Adding Flags

Let's walk through a practical example of this. We'll bring back our our PlayerStorage - the structure of arrays from the .

If you're following along from that chapter and want to run the examples, feel free to continue to update your container. To focus on the new content, we've provided a starting point below that strips out a lot of the previous topics, but in a real system, you would layer these features together.

1#pragma once
2
3#include <vector>
4#include <ranges>
5#include <tuple>
6#include <algorithm>
7#include <array>
8#include <cstdint>
9
10namespace PlayerFlags {
11  constexpr uint8_t None     = 0;
12  constexpr uint8_t Friendly = 1 << 0;
13  constexpr uint8_t Alive    = 1 << 1;
14  constexpr uint8_t Nearby   = 1 << 2;
15}
16
17struct PlayerRef {
18  int& id;
19  int& score;
20  uint8_t& flags;
21};
22
23class PlayerStorage {
24public:
25  std::vector<int> m_ids;
26  std::vector<int> m_scores;
27  std::vector<uint8_t> m_flags;
28
29  void AddPlayer(int id, int score, uint8_t flags) {
30    m_ids.push_back(id);
31    m_scores.push_back(score);
32    m_flags.push_back(flags);
33  }
34
35  auto GetView() {
36    return std::views::zip(m_ids, m_scores, m_flags) 
37      | std::views::transform([](auto&& tuple) {
38          auto& [id, scores, flags] = tuple;
39          return PlayerRef{id, scores, flags};
40        });
41  }
42};

API Improvements

Raw bitmasks are efficient, but they aren't very user-friendly. We don't want consumers of our container to be manually shifting bits.

We can update our PlayerRef proxy to hide the bitwise logic behind semantic methods. This gives us the best of both worlds: the dense storage and performance of raw bits and the readability of OOP methods like IsFriendly() and SetFriendly():

1// ...
2
3class PlayerRef {
4public:
5  int& id;
6  int& score; 
7  
8  PlayerRef(int& idRef, int& scoreRef, uint8_t& flagsRef)
9    : id(idRef), score(scoreRef), flags(flagsRef) {} 
10
11  bool IsFriendly() const {
12    return (flags & PlayerFlags::Friendly) != 0;
13  }
14
15  void SetFriendly(bool enable) {
16    if (enable) {
17      flags |= PlayerFlags::Friendly;
18    } else {
19      flags &= ~PlayerFlags::Friendly;
20    } 
21  }
22  
23  // ...etc
24
25private:
26  uint8_t& flags;
27};
28
29// ...

We can also optimize our iteration. Currently, consumers have to implement that filtering logic themselves. Their instinct would perhaps be to perform this filtering using the slower branching approach using &&, so we can intervene here and provide a faster method.

We can add an overload to GetView() that accepts a mask. This allows us to implement filtering in a way that is fast and branchless where possible:

1// ...
2
3class PlayerStorage {
4public:
5  // ...
6
7  auto GetView(uint8_t mask = PlayerFlags::None) {
8    return std::views::zip(m_ids, m_scores, m_flags)
9      | std::views::filter([mask](const auto& tuple) {
10          const auto& flags = std::get<2>(tuple);
11          return (flags & mask) == mask;
12      })
13      | std::views::transform([](auto&& tuple) {
14          auto& [id, scores, flags] = tuple;
15          return PlayerRef{id, scores, flags};
16      });
17  }
18  }
19  
20  // ...
21};

Example Usage

This results in an API that is expressive and friendly:

1#include <dsa/PlayerStorage.h>
2#include <iostream>
3#include <algorithm>
4#include <ranges>
5
6int main() {
7  PlayerStorage ps;
8
9  using namespace PlayerFlags;
10  ps.AddPlayer(1, 100, Friendly | Alive);
11  ps.AddPlayer(2, 200, Alive);
12  ps.AddPlayer(3, 150, Friendly | Alive | Nearby);
13  
14  // The range interface still allows consumers to provide
15  // their own filtering logic, will full flexibility
16  auto nearby_friendlies = std::views::filter(
17    [](PlayerRef p) {
18      return p.IsFriendly() && p.IsNearby();
19    }
20  );
21  
22  for (PlayerRef p : ps.GetView() | nearby_friendlies) {
23    // ...
24  }
25  
26  // But we provide a easier, optimized option for simple cases:
27  for (PlayerRef p : ps.GetView(Friendly | Nearby)) {
28    // ...
29  }
30}

MapReduce

Let's go back to our original problem - how do we count how many players in our collection meet a certain criteria, like friendly & nearby?

Our consumers could find out themselves by handing one of our views to std::distance():

1// Option 1 - Branching (slow)
2auto nearby_friendlies = std::views::filter(
3  [](PlayerRef p) {
4    return p.IsFriendly() && p.IsNearby();
5  }
6);
7size_t opt1 = std::ranges::distance(
8  ps.GetView() | nearby_friendlies
9);
10
11// Option 2 - Bitwise (faster, but still counts
12// elements one by one)
13size_t opt2 = std::ranges::distance(
14  ps.GetView(Nearby | Friendly)
15);

However, this comes at a performance cost. Lazy-evaluated views are perfect for iterating through containers element-by-element, but they're not designed for asking questions about our data as a whole.

The most famous design pattern for analyzing large amounts of data and generating a report is MapReduce, which the C++ standard library implements as std::transform_reduce(). We covered MapReduce in more detail in our

If a problem can be expressed as a mapping (transformation) action applied to all objects in a collection, followed by reducing (combining) those transformed objects to a the result we're asking for, then MapReduce can help.

As it turns out, almost any data processing problem can be expressed in this form. Our original task of "count the players who are friendly, alive, and nearby" is a mapping and reduction problem. We solved it by mapping each player to a 0 or 1, then reducing all of those 0s and 1s to a final count:

1// Starting value
2int count = 0;
3
4// Range to map/reduce
5for (const PlayerRef& p : players) {
6  // MAP each player to 0 or 1
7  bool canHelp = (p.friendly & p.alive & p.nearby);
8
9  // REDUCE all the 0s and 1s to a final total via addition
10  count += canHelp;
11}

Here is the equivalent logic expressed via arguments to std::transform_reduce():

1int count = std::transform_reduce(
2  // Range to map/reduce
3  players.begin(), players.end(),
4  
5  // Starting value
6  0,
7  
8  // REDUCE all the 0s and 1s to a final total via addition
9  std::plus<>(),
10  
11  // MAP each player to 0 or 1
12  [](const PlayerRef& p) {
13    return p.friendly & p.alive & p.nearby;
14  }
15);

Implementing MapReduce

Below, we add a CountPlayers() method to our system to support expressions like CountPlayers(Alive | Nearby) :

1// ...
2#include <numeric> // for transform_reduce 
3
4// ...
5
6class PlayerStorage {
7public:
8  // ...
9
10  int CountPlayers(uint8_t mask = PlayerFlags::None) const {
11    // Trivial case - no filters provided
12    // Just return total player count
13    if (mask == PlayerFlags::None) return m_ids.size();
14    
15    return std::transform_reduce(
16      // Range to map/reduce
17      m_flags.begin(), m_flags.end(),
18      
19      // Starting value
20      0,  
21      
22      // REDUCE all the 0s and 1s to a final total via addition
23      std::plus<>(),
24      
25      // MAP from uint8_t to 0 or 1
26      [mask](uint8_t flags) {
27        return (flags & mask) == mask ? 1 : 0;
28      }
29    );
30  }
31  // ...
32};

Let's check how our CountPlayers() function performs compared to the previous attempts. We compare:

Logical: The traditional iteration of an array-of structures using &&.
Bitwise: Iterating the array of structures with boolean algebra using &.
MapReduce: Using transform_reduce() on an m_flags column within our structure-of-arrays:

1// ...
2#include <dsa/PlayerStorage.h> 
3
50
51PlayerStorage GenerateData(size_t size) {/*...*/}
71
72static void BM_PlayerStorage_MapReduce(benchmark::State& state) {
73  auto ps = GenerateData(state.range(0));
74
75  for (auto _ : state) {
76    using namespace PlayerFlags;
77    int count = ps.CountPlayers(Friendly | Alive | Nearby);
78    benchmark::DoNotOptimize(count);
79  }
80}
81
90BENCHMARK_CONFIG(BM_PlayerStorage_MapReduce);

On my system, the SoA layout and the optimizations of std::transform_reduce() is returning a result 50 times faster than the original approach, and 5 times faster than the bitwise operations on std::vector<Player>:

1---------------------------------------------
2Benchmark                                 CPU
3---------------------------------------------
4BM_PlayerFlag_Logical/1000000         5.72 ms
5BM_PlayerFlag_Logical/10000000        59.7 ms
6BM_PlayerFlag_Bitwise/1000000        0.496 ms
7BM_PlayerFlag_Bitwise/10000000        5.31 ms
8BM_PlayerStorage_MapReduce/1000000   0.112 ms
9BM_PlayerStorage_MapReduce/10000000   1.14 ms

Multithreading

The real power of the MapReduce pattern is how well it scales across many cores or, for large-scale work, many systems. We covered execution policies in a but, to prompt std::transform_reduce() to run in parallel, we just pass std::execution::par as the first argument:

1// ...
2#include <execution> // for std::execution::par 
3
4// ...
5
6class PlayerStorage {
7public:
8  // ...
9
10  int CountPlayers(uint8_t mask) const {
11    return std::transform_reduce(
12      std::execution::par, 
13      m_flags.begin(), m_flags.end(),
14      0,
15      std::plus<>(),
16      [mask](uint8_t f) {
17        return (f & mask) == mask ? 1 : 0;
18      }
19    );
20  }
21  // ...
22};

For large data sets, this execution policy can result in yet another order of magnitude performance increase on a typical system:

1---------------------------------------------
2Benchmark                                 CPU
3---------------------------------------------
4BM_PlayerFlag_Logical/10000000        59.9 ms
5BM_PlayerFlag_Bitwise/10000000        5.51 ms
6BM_PlayerStorage_MapReduce/10000000   0.16 ms

Reducing Filtering

Being able to quickly filter our collection is great, but it still has a performance cost. If we find we're using the same filter often ("iterate over all of the nearby players") we can instead be slightly smarter in how we arrange our data.

Our collection is currently a monolith. Conceptually, all of our data is in one big table where each of our arrays is a column and each player is a row. Later in the course, we'll expand our design to multiple tables. This lets our systems iterate and query just the things they care about, but we'll still maintain the friendly "player" abstraction that hides the underlying complexity.

Summary

In this lesson, we demonstrated that how you ask a question matters as much as the data you are asking about.

Branchless Logic: We replaced logical operators (&&) with bitwise operators (&). This prevents branch mispredictions, allowing the CPU pipeline to flow without interruption.
Bit Packing: We consolidated multiple booleans into a single uint8_t flags column in our SoA system, improving memory density and cache usage.
Encapsulation: We exposed this optimized data via PlayerRef, proving we can have the speed of bits with the readability of functions like IsFriendly().
Map Reduce: We implemented std::transform_reduce() as a tool for aggregate queries, showing massive speedups over manual loops.

We have successfully compressed our boolean logic. But booleans are just the beginning.

In the next lesson, we will attack the larger data types clogging our memory bus: integers and floating-point numbers. We will take our bit packing further, and also implement quantization.

Fast Filtering and Branchless Logic