CPU Cache and JavaScript: Why Sorting an Array Can Make Loops 7x Slower

Same million objects, same loop, same result. The only difference is the order of the items in the array:

in creation order: 1.04 ns per element
shuffled:          7.51 ns per element

for (let i = 0; i < rows.length; i++) total += rows[i].value;

From JavaScript's point of view, both runs do exactly the same work. The difference is in where the objects sit in memory.

The mental model: a courier's route

Think of the CPU as a courier and your objects as houses.

An array of objects doesn't hold the houses. It holds a list of addresses. When you create objects one after another, V8 builds them side by side on the same street. The courier walks door to door, and every trip to the warehouse brings back the next few houses' packages too.

Shuffle or sort the array and you only reorder the address list. The houses don't move. Now every stop is across town.

Sorting an array of objects reorders the addresses, not the objects.

How it works

Two hardware tricks make the street walk fast:

1. Cache lines. Memory comes into the CPU cache in blocks (128 bytes on this chip). One fetch brings in about three neighboring 40-byte objects for free.
2. Prefetching. When the CPU notices you walking steadily forward, it starts fetching ahead of you.

Random jumps defeat both. Each read is likely a cache miss, so the CPU waits on slower main memory.

If that's really the cause, small arrays shouldn't care about order, because they fit in the cache either way. They don't:

Node 26.13 (V8 14.6), Apple M3 Pro with a 16 MB L2 cache, median of 5 fresh processes.

4 MB fits in the 16 MB cache and barely slows down. 40 MB doesn't fit, and takes the big hit. That match is strong evidence, but no hardware counters were read, so it's still an inference.

Sorting by an unrelated key gave the same slowdown (7.66 ns). The garbage collector doesn't fix the order for you either.

In practice

Make the memory order match the order you read in:

// 1. after sorting, copy the objects so they're created in read order
rows = rows.map((r) => ({ id: r.id, value: r.value }));

// 2. or put the hot number in a typed array: no addresses to follow
const values = new Float64Array(rows.length);
for (let i = 0; i < rows.length; i++) values[i] = rows[i].value;

Copying is the small change and brings back almost all the speed. The typed array is fastest because the numbers themselves sit side by side, but you now keep a separate column next to your objects.

Honest stakes: this is 7.5 ms instead of 1 ms per pass over a million objects. A loop that runs once per request won't care. A loop that constantly crunches big in-memory data will.

Say it in an interview

"A JavaScript array of objects stores references, and the objects live elsewhere on the heap. Objects created in sequence usually sit next to each other, so walking them is cache-friendly: cache lines and prefetching do the work. Sorting or shuffling reorders only the references, so each access jumps around memory and misses the cache. For big data in hot loops, keep objects in traversal order or move hot numbers into a typed array."

Cheat sheet

TL;DR

• An array of objects holds addresses, so array order and memory order can differ.
• Sorting or shuffling turns a steady walk into random jumps the CPU cache can't help with.
• Here a million shuffled objects were 7× slower to sum, while 1,000 objects showed no difference.
• Copying after sorting, or using a Float64Array, brought the speed back.

Going deeper

Advanced and optional. Everything above is enough to explain this in an interview. This part is for the curious: full numbers, edge cases and what's still unproven.

Full measurements

Node 26.13 (V8 14.6), Apple M3 Pro, median of 5 fresh processes. The objects are settled by two forced GCs, then shuffled with Fisher-Yates. sysctl reports a 16 MB L2 cache for the performance cores.

What isn't proven

The match with the 16 MB L2 cache is strong, but it's still an inference. No hardware counters were read, and address translation misses (the TLB) probably contribute too. Below 100,000 objects the numbers are too close to call: at 10,000 objects, the shuffled run came out faster in one set of runs, which is noise.

The garbage collector doesn't fix it

You might hope the GC tidies objects into order as it moves them. Shuffling while the objects were still young, then forcing a collection, only brought the time to 6.75 ns. A real sort by an unrelated key measured 7.66 ns, in line with the shuffle.

All the fixes, measured

Copying costs a one-time pass and briefly doubles that memory until the old objects are collected. If most reads use one order and only some need another, keep the objects as they are and hold a separate sorted array of indexes for the rarer read.

Originally published on Bitlyst.