Optimizing position updates

By Robin Dowling · 2 months ago

The simulation's double-buffer state architecture had a performance bottleneck. Every iteration, it rewrote the position of every entity in the world, thousands of organisms and environmental objects, into a spatial index. This happened regardless of whether an entity had actually moved.

Sessile organisms like plants never move, yet their positions were being rewritten every single tick. Dead organisms weren't moving either, but their positions were still being updated. Even motile organisms that decided to stay in place for that tick would trigger position updates.

I was using a double-buffer implementation where all positions from one buffer were copied into the other, then the buffers swapped. This ensured determinism, all reads happened from a stable buffer while writes went to the other, but the cost was O(N) writes every iteration for all N entities.

The fix was to replace double-buffering with a single persistent spatial index and a deferred update queue. When an organism decides to move, instead of immediately updating the spatial index, the change is queued. The queue stores each entity's "from" position and "to" position.

At the end of the iteration, after all organisms have made their decisions, the queued updates are applied atomically. Each relevant entity is removed from its old position in the spatial index and added to its new position. Then the queue is cleared.

Organisms that don't move never queue updates. Sessile organisms, often the majority of the population, cost nothing. Dead organisms that remain positioned during decay cost nothing. Only organisms that actually move create entries in the update queue.

The performance impact is substantial. In a simulation with 1000 entities, maybe 200 motile organisms move while 800 sessile organisms stay in place, an 80% reduction in position writes.

Determinism is preserved because all position queries read from the frozen spatial index during iteration. No entity sees updated positions until the deferred updates are applied at the end, after all decisions are made. The simulation remains fully deterministic, order-independent, and correct.

The change was entirely internal. External consumers see no difference in behavior, only improved performance. It's the kind of optimization that makes scaling possible, reducing unnecessary work without changing what the system does.