Prematurely hand-optimizing C++ code for shits and giggles
Tags: cpp, performance
Published: 2021-11-01 06:50:18

---
title: Prematurely hand-optimizing C++ code for shits and giggles
published: true
description: 
tags: #cpp, #performance
canonical_url: https://drbearhands.com/articles/hand-optimized-c
---

Left in the void that comes after abandoning a project, I decided to port a previous JavaScript / WebGL project to C++. Changing languages meant a complete overhaul of some core systems. I was looking at a [post by Austin Morlan about ECS achitectures](https://austinmorlan.com/posts/entity_component_system/) for inspiration.

Here I saw this procedure:

```C++
EntityManager()
{
  // Initialize the queue with all possible entity IDs
  for (Entity entity = 0; entity < MAX_ENTITIES; ++entity)
  {
    mAvailableEntities.push(entity);
  }
}
```

this isn't bad code. Nonetheless, I did not like it. And not just because I have a distaste for CamelCase.

Initializing the value `mAvailableEntities` potentially takes a long time. In the example `MAX_ENTITIES` was set to 5k, so it's not so bad, but I may require far more entities than that.

Had this been a regular project with a clear goal, the correct approach would be to leave the code as is, since it's certainly readable. Then *if* we run into performance issues in practice, find the procedures taking up the most times and optimize *those*, and [*use statistical analysis* to determine if our changes actually mattered](https://youtu.be/r-TLSBdHe1A). That is the correct way to optimize performance. That's not what I'm going to do here.

In this particular architecture, `mAvailableEntities` is a pool of *all available entities*. That is why it must be filled. We cannot use a simple incrementing counter because entities can be destroyed as well, in which case we'd want to recycle them.

Instead, we can combine the incrementing counter and the recycling pool. If the pool is not empty, grab an element from there, otherwise, use the counter. Unfortunately, that sentence contains the word "if".

Naive implementation of the above is:

```C++
#include <queue>
#include <cstdint>

using entity = std::uint32_t;
entity counter = 0;
std::queue<entity> recycling_pool;

entity create_entity() {
  if (recycling_pool.empty()) {
    return counter++;
  } else {
    auto e = recycling_pool.front();
    recycling_pool.pop();
    return e;
  }
}
```

(I've left out the check to prevent going over `MAX_ENTITIES`)

and as we see on [compile explorer](https://godbolt.org/), this compiles to conditional jumps (jne):

```LLVM
create_entity():
        movq    recyclingPool+16(%rip), %rax
        cmpq    recyclingPool+48(%rip), %rax
        pushq   %r12
        jne     .L9
...
```

conditional jumps can be a performance problem. 

Modern CPUs have deep pipelines. Rather than fully executing one instruction and then moving on to the next one, they execute every instruction in multiple steps like an assembly line. While instruction `n` is going through step `x`, instruction `n-1` (the instruction that came before `n`) is going through step `x+1` and `n+1` is going through step `n-1`. A pipeline of 20 steps is essentially doing 20 things at the same time and therefore ~20x as fast as it would be executing instructions one-by-one.

These pipelines require knowing ahead of time which instructions are coming up, which is uncertain with conditional jumps. Branch prediction works in some cases, such as loops, but not always.

So how do we get rid of branching?

The concept is conditional write-back. Rather than pick one branch or another, we do all branches, but don't write back the result in some cases. 

[C++ does not support conditional writeback directly, so we improvise a bit](https://www.chessprogramming.org/Avoiding_Branches).

First, replace `std::queue` with a stack, and just use a primitive array `entity recycling_pool[MAX_ENTITIES]`. This will be a bit easier to hack.

Then, we specify entity 0 to be invalid. We initialize `recycling_pool` with a `0` in the first element. Now we can take the head of `recycling_pool` and it will function both as condition and value. This is rather like `Maybe Entity` in e.g. Haskell, but more efficient and far less safe.

```C++
entity create_entity()
{
  entity new_entity = recycling_pool[unused_idx];
  bool b_stack_empty = !new_entity;
...
}
```
Now we have divergence: if not `b_stack_empty`, we want to `pop` the stack, otherwise, we want to increment the counter.

`b_stack_empty` is a boolean with the value 0 or 1, since it was generated from the `!` operation (anything that isn't 0 counts as true in C++, but true as output is 1). we can abuse this:

```
  unused_idx -= !b_stack_empty;
  gen_counter += b_stack_empty;
```
(NOTE: `gen_counter` starts at 0, but valid values start at 1, so it's increment-then-use)

this is a specialized form of conditional write-back.

Then, if `b_stack_empty`, we want to replace `new_entity`, which will be an all-0 bits invalid value, with the current value of `gen_counter`:

```C++
  new_entity += -b_stack_empty & gen_counter;
```

since `b_stack_empty` can have values 0 or 1, a non empty stack will evaluate to `0 & gen_counter`, which equals 0, whereas an empty stack will give `-1 & gen_counter` and since we're dealing with *unsigned* integers, -1 is all 1's in binary, so `-1 & gen_counter` equals `gen_counter`. In the latter case we also know `new_entity = 0`, and `0 + gen_counter = gen_counter`.

And so the full code (minus checking MAX_ENTITIES violation) is:

```C++
#include <cstdint>

using entity = std::uint32_t;
entity unused_idx;
entity gen_counter;
const entity MAX_ENTITIES = 5000;
entity recycling_pool[MAX_ENTITIES];

entity create_entity()
{
  entity new_entity = recycling_pool[unused_idx];
  bool b_stack_empty = !new_entity;
  unused_idx -= !b_stack_empty;
  gen_counter += b_stack_empty;
  new_entity += -b_stack_empty & gen_counter;
  return new_entity;
}
```

Compiler explorer confirms there are no conditional jumps.

The resulting assembly is also a lot smaller (24 lines vs 103), but I expect that is mostly due to the omission of `std::queue`.

I want to reiterate that this is *dumb*. The code is likely to have gotten slower in practice, even though it is more consistent, because branch prediction is probably right more often than not, and now we're executing *all* the branches. Code maintainability has also suffered.

This is merely an interesting learning experience.