Snake Battle Royale: High-Frequency Game Server optimization project (Part 2)

When poor benchmarking, and cache misses bite back

But, first

After the initial 11x performance improvement from 51.71 μs to 4.56 μs, I wanted to keep going down the optimization rabbit hole. But first, I needed to make the problem harder to measure smaller improvements.

I increased the grid size from 1000×1000 to 4000×4000. Still fits in L3 cache (barely), but it makes the problem slightly more realistic, and micro-optimizations are easier to measure against it.

My benchmark was bad

My original benchmark was not the best, and had not given it much thought. Silly me, thinking benchmarking is not going to be my problem. I was using random game states and inputs, which meant every run was different. When I saw a 5% improvement, I couldn't tell if it was real optimization or just random variance. I needed results I could actually reproduce.

Making it deterministic

So I rewrote the benchmark so the game state evolves exactly the same way every time:

• Fixed starting positions. The snakes are placed in specific spots so the collisions are predictable.
• Deterministic inputs. The movement patterns lead to known outcomes (25% die, 25% grow, 50% unchanged).
• Predictable game state. With the start and the inputs fixed, every tick produces identical results, run after run.

That got rid of the random noise, and I could focus on measuring actual performance improvements.

Still noisy

But then my benchmark results were still all over the place. One run would show 40 μs, the next 57 μs, then back to 41 μs. Not the deterministic results I was looking for.

And then, in the quiet of my room, I heard my CPU fan go brrr because of another background process. That's when it clicked that the benchmark was fine, and my environment was the problem.

What was actually varying

Two things in the environment were moving my numbers around:

1. CPU frequency. My CPU kept switching between:

   • powersave mode, at 800 MHz, which is energy-efficient but slow
   • performance mode, where the frequency still scales with load
   • thermal throttling, which drops the frequency when things get hot

2. Cache variance. CPU caching wasn't consistent from one run to the next.

Even with core pinning, the frequency was jumping around like a snake on caffeine, and caches were warming up between runs.

Locking it all down

I wanted both of those gone completely. Nothing fancy, but it worked:

1. Lock the CPU governor to "performance" mode.
2. Set the min/max frequency to the same value (4.0 GHz).
3. Pin the benchmark to one specific CPU core (core 0).
4. Do warm-up runs so the cache state is consistent.
5. Restore the original settings after the benchmark.

I hacked together a CPU control script:

#!/bin/bash
# Store original settings
ORIGINAL_GOVERNOR=$(cat /sys/devices/system/cpu/cpu0/cpufreq/scaling_governor)
ORIGINAL_MIN_FREQ=$(cat /sys/devices/system/cpu/cpu0/cpufreq/scaling_min_freq)
ORIGINAL_MAX_FREQ=$(cat /sys/devices/system/cpu/cpu0/cpufreq/scaling_max_freq)

# Lock to performance mode at 4.0 GHz
echo performance | sudo tee /sys/devices/system/cpu/cpu0/cpufreq/scaling_governor
echo 4000000 | sudo tee /sys/devices/system/cpu/cpu0/cpufreq/scaling_min_freq
echo 4000000 | sudo tee /sys/devices/system/cpu/cpu0/cpufreq/scaling_max_freq

# Run benchmark with core pinning
sudo -u $ACTUAL_USER taskset -c 0 /home/boopop/.cargo/bin/cargo bench --bench game_bench hot_path/100_snakes

# Restore original settings
echo $ORIGINAL_GOVERNOR | sudo tee /sys/devices/system/cpu/cpu0/cpufreq/scaling_governor
echo $ORIGINAL_MIN_FREQ | sudo tee /sys/devices/system/cpu/cpu0/cpufreq/scaling_min_freq
echo $ORIGINAL_MAX_FREQ | sudo tee /sys/devices/system/cpu/cpu0/cpufreq/scaling_max_freq

In the end I locked the CPU to 4.0 GHz, pinned it to core 0, ran the benchmark twice and measured the second run. This gives me consistent performance that also matches real-world conditions, or at least that's what I tell myself. So I moved on.

Inlining didn't help much

Now that we added a bunch of wrappers in the previous post, function entry and exits could be significant. Inlining them should help, right?

Turns out they weren't really helping that much.

My guess was that something else, maybe cache misses, are taking up a larger chunk of time as we increase the number of snakes.

I ran some perf analysis, and the guess was correct. The actual cache numbers are further down. I'd been meaning to replace the HashMap with a simple static vector anyway to see the performance difference. That should help with cache performance too, since a HashMap is a lot harder to optimize for cache locality.

HashMap to vector

A vector is more straightforward for most cases except deletion of snakes. I just decided to keep the dead snakes in the vector all the time. There's a tradeoff because we'll be iterating over dead snakes, but the cache benefits should outweigh this cost, given new snakes are not spawned.

Cache performance across the tick() loop was now good, but not great yet:

At 900+ snakes the cache hit percentage drops off significantly, to around 78%.

Cache padding (false sharing?)

I made the snake cache-padded as well:

pub struct GridAwareSnake {
    snake: CachePadded<Snake>,
}

That really seemed to help:

The cache hit percentage went from ~78% to ~94%. The padding stopped false sharing between snake objects, and that made a huge difference to cache performance.

Numbers so far

These two optimizations helped a lot:

1. HashMap to vector
2. Cache padding the snake

Together they took the tick from 10.422 μs down to 2.562 μs, which is a ~4x additional performance improvement.

What's next

Okay, now it's time to bump the grid size up because making the entire grid fit in cache felt too easy.

So I bumped it to 10,000 × 10,000. That definitely doesn't fit in cache, so we'll need to get creative with memory access patterns.

Optimizations in the next blog!