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

Hot path optimization, when cache misses become the biggest problem

Bigger grid, worse cache

After the previous optimizations brought us from 10.422 μs to 2.562 μs, I was feeling pretty good. But then I bumped the grid size to 10,000×10,000 (~100MB) and that feeling didn't last long. The cache performance became worse as I had expcted. It was because things were big enough to not fit in my L3 cache anymore.

Measuring cache and branch metrics

Cache and branch numbers for different snake counts:

As the snakes spread out across the grid, cache misses got more frequent. At 1000 snakes, we were only hitting cache ~70% of the time. That's a lot of trips out to RAM.

Why it was thrashing

The problem was my object-oriented design. I had written encapsulated methods for each class (Snake, Apple, etc.) that operated at a per-object level. That kept the code maintainable, but it made any global, grid-level optimization tricky.

Every tick, each snake did this (and there are 1000 snakes per tick):

1. READ grid.get_cell(&new_head) to check if it eats an apple
2. READ grid.get_cell(&new_head) again to check for a collision
3. WRITE grid.set_cell(*tail, Cell::Empty) to clear the old tail
4. WRITE grid.set_cell(*head, Cell::Snake) to set the new head

And for each apple:

1. WRITE grid.set_cell(new_apple_pos, Cell::Apple) to spawn a new apple

With 1000 snakes, that's 4000+ random grid accesses per tick across a 10k×10k grid. So we were pretty much cache thrashing, jumping around randomly in a 100MB grid with no spatial locality.

Spatial batching

I needed those random accesses to happen in spatial order instead. So the plan was to collect all the movement records first, sort them by position, and then process them in that cache-friendly order.

How the tick works now

Phase 1 collects the records, with no grid reads at all:

FOR each alive snake:
    calculate new_head_position
    create MovementRecord(snake_id, new_head_position, empty_cell)
    add to records list

Phase 2 sorts them by spatial locality:

SORT records by (y_coordinate, x_coordinate)
// This groups nearby operations for better cache utilization

Phase 3-5 is one combined loop that reads, processes and writes immediately:

FOR each record in sorted order:
    READ cell_at_new_head from grid
    DEAL with Snake Collision
    DEAL with apple eating
    
    HANDLE Snake Race conditions within tick()
    
    WRITE Snake to new_head position
    IF not growing:
        WRITE Empty to old tail position
    UPDATE snake body

On top of that, I made two more changes.

Partitioning instead of a full sort

Full sorting was expensive. So I used spatial partitioning with 2^8 buckets instead:

CREATE 256 buckets (2^8)
FOR each movement record:
    calculate bucket_index = (y_coord >> 8) * 256 + (x_coord >> 8)
    add record to buckets[bucket_index]

That got us most of the cache benefits with much less overhead.

Batching the tail writes

The tail clearing writes were still causing cache misses. I collected these writes into buckets and processed them at the end:

DURING movement processing:
    IF snake not growing:
        add tail_position to tail_clears records

AT END of tick:
    FOR each tail_position in tail_clears records:
        WRITE Empty to tail_position

Did it help?

Cache hit rate at 1000 snakes:

• before, with random access: 69.95%
• after spatial batching: 78.42%

The hit rate went from ~70% to ~78%. Solid, but not the jump I was hoping for.

Snake bodies on the stack (TinyDeque)

Next was snake body storage. Most snakes in the game are small (3-4 segments), so I suspected that heap allocation for every snake body was wasteful.

Why VecDeque hurts here

The standard VecDeque allocates each snake body on the heap, which means:

• 1000 snakes means 1000 heap allocations
• poor cache locality, since the snake bodies end up scattered across memory
• allocation overhead, for collections that are mostly small

Writing my own deque

I initially tried implementing a custom deque using SmallVec as the backing store:

pub struct Snake {
    pub body: SmallVec<[Point; 16]>,  // Stack-allocated for small snakes
    pub front_idx: usize,             // Circular buffer head
    pub end_idx: usize,               // Circular buffer tail
    // ...
}

I realised it was going to be a bigger rabbit hole than I had imagined, with all sorts of performance and edge case concerns. I was just about to spin it off as its own project when I found a crate for it.

TinyDeque

I found the tinydeque crate, which already does this:

pub struct Snake {
    pub body: TinyDeque<[Point; 16]>,  // Stack-first, heap spill
    // ...
}

Why TinyDeque felt like magic:

• It starts on the stack: small snakes live in an ArrayDeque, which is stack-allocated.
• When the stack buffer fills, there's an automatic heap spill and it switches over to a VecDeque without any fuss.
• It has the same API as VecDeque, so it's a drop-in replacement with no added complexity.
• You get the best of both worlds: fast stack operations for small snakes, and heap flexibility for the large ones.

Final results

The numbers

For the 10_000 * 10_000 grid:

Overall, 52% faster, from ~18 μs down to ~8.6 μs per tick.

What actually mattered

A few lessons about optimization I took from all this:

1. Cache locality trumps algorithmic complexity. Spatial batching is more complex than the plain per-snake loop, but the cache benefits far outweighed that overhead.
2. Measure, don't guess. There were quite a few things I've tried, that seemed really good in theory, but never worked in practice.
3. Premature optimization is still the root of all evil ;)

But for now, I'm happy with this performance. I am parking this project as I've found other projects to bootstrap along the way!