Data locality (sometimes) beats algorithmic complexity

I've been ECS-curious ever since I learned about it in the Bevy game engine documentation.

The ECS architecture predictably improves performance in languages that give you low-level control over memory (C, C++, Rust, Zig, and friends). But how does it fare when used in high-level, dynamic, garbage-collected languages such as JavaScript?

This is the question Dan Murphy set out to answer in The Physics of Memory:

Is it possible to use an ECS-style architecture in Javascript? And for applicable operations, does that actually do better than objects + V8’s garbage collection?

To answer the question, Murphy built a 2D physics simulation of 15,000 balls bouncing around in a box using several different techniques. He found that a JavaScript implementation of the simulation that used ECS outperformed the usual "giant graph of objects" OOP implementation by 24x. He writes:

  1. Cache Locality > Algorithmic Complexity: At 15,000 entities, pointer-chasing and unpredictable tree branching cannot compete with the contiguous L1/L2 cache locality of a flat 1D array sort—even though trees have a better theoretical Big-O complexity.
  2. You Don’t Need WASM for ECS Wins: Simply switching your JavaScript codebase to a flat Structure of Arrays (SoA) layout yields up to a 24x speedup over OOP. WASM is the cherry on top (another 2.5x), not the entry ticket.
  3. Pragmatism Wins: While a hand-tuned SoA is the absolute fastest, using a production ECS library like bitECS still gives you a massive 14x speedup over OOP while providing a clean, scalable API. IMO, for 99% of applications using a library is the correct engineering choice.

It's also worth noting how the usual OOP implementation creates GC pressure:

In OOP, entities are scattered across the heap. As they move and interact, the JavaScript engine’s garbage collector is constantly triggered, and the CPU frequently stalls waiting for pointer lookups. This causes sporadic frame drops (micro-stutter). Because ECS uses pre-allocated, flat TypedArrays, memory access is 100% predictable and GC overhead is zero, guaranteeing perfectly smooth frame delivery.

My favorite thing about Murphy's post is that you can run all his benchmarks in your own browser. I love it when technical explanations or benchmarks are accompanied by embedded "apps" you can play around with.

I'm surprised at how much data locality matters for performance. An algorithm with worse big-O complexity can outperform one with better complexity if it makes good use of the CPU's L1/L2 caches. Very cool.