Benchmarking JavaScript Collections

Code for this post: github.com/neolefty/js-collection-benchmarks

Hexerals uses immutable.js for its game state — could it switch to JavaScripts native collections? That would make the code more readable, but how would effect performance?

Summary: In Chrome, object operations are much faster than immutable Map — just don’t freeze() them. But in Firefox and Safari, immutable Map still wins. Chrome’s advantage might come from Hidden Classes.

The strengths of immutable.js are:

• Memory — immutable.js only duplicates sections that are changed, which saves memory. It makes keeping a full history of a game especially efficient.
• Speed — it’s fast! For example, Hexerals robots use the game state to make decisions, and if it slows down, it limits their intelligence.

Hexerals uses a lot of Maps and Lists.

For example, its board is represented using a Map, matching each location (a Hex) to contents (a Tile) — the hexagon in upper left might be Hex (0, 6), with a Tile whose owner is Red, population 8, and no special terrain.

So how expensive would it be to switch from those Maps and Lists to JavaScript’s built-in Objects and Arrays?

To the Benchmarks!

These are run in your local browser (click the gear to change settings & run again):

What are these benchmarks doing? Something that resembles the internal state transitions in a single turn of Hexerals. See BenchWorkers.ts for actual code.

• Collection Size: Create a collection with that many simple items in it.
• Iterations: Copy it this many times.
• Mutation Fraction: Each time it’s copied, also randomly replace a fraction of its contents. For example, if Collection Size is 1000 and Mutation Fraction is 0.1, then 100 entries will be modified at random during each Iteration.

	1. Copy	2. Modify
JS object	copy = {...original}	copy[x] = y
immutable Map	copy = Map(original.entries())	copy = copy.withMutations(mutable => mutable.set(x, y)

Surprises

• Object.freeze() is slow for objects but practically free for arrays!
• Immer (which uses Object.freeze) is slow if you use it inner loops. But it’s very safe! And almost nobody needs it to be inside inner loops anyway.
• Structura is an interesting alternative to Immer. It “freezes at compile time” which … is not quite freezing, but relying on TypeScript’s Readonly<T>. Anyway it looks like that’s the key to performance in JS — and it’s what the winning benchmark is doing with object.
• JavaScript’s built-in Map is slow for this kind of operation, compared to plain old objects — which is too bad because Map is more flexible than objects. It turns out that copying a map is slow. There is another slightly faster way (using an iterator to insert one by one) but it’s not enough faster to close the gap. Probably worth revising the benchmark to include it tbh.

The fastest would be to skip all this and go straight to WebAssembly. That’s what Figma does, but it would mean switching from TypeScript to Rust/C++. Hmm …

---

Comparing Firefox, Safari, and Chrome

In short, Safari and Firefox both really like Immutable.js Map, and Chrome likes object.

For 1000 x 1000 x 0.1, on an M1 laptop, in milliseconds:

	object	Map	immutable Map
Chrome	4.1	44	19
Firefox	55	57	20
Safari	114	82	18

Chrome loves object, but everybody does well with immutable.js.

How about some older mobile devices?

	object	Map	immutable Map
Pixel 4a 5G (2020 Chrome	21	105	64
Samsung A50 (2019) Chrome	33	170	79
iPad (2018) Safari	178	101	42

So, what’s the best choice? The widest bottleneck is clearly Immutable.js’s Map. The object spread operator (and object.assign) is too dang slow on Safari, and so is Map on Chrome.

---

Tools learned: Next.js (with static deployment), Tailwind CSS, DaisyUI.

Caveats: The benchmarks run synchronously. Still working on getting web-workers right.