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. Copy2. Modify
JS objectcopy = {...original}copy[x] = y
immutable Mapcopy = Map(original.entries())copy = copy.withMutations(mutable => mutable.set(x, y)
You can see why developers might prefer the object — its syntax is simpler.

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:

objectMapimmutable Map
Chrome4.14419
Firefox555720
Safari1148218
Immutable.js Map has the best-worst-case on my desktop, with 20ms on Firefox.

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

How about some older mobile devices?

objectMapimmutable Map
Pixel 4a 5G (2020
Chrome
2110564
Samsung A50 (2019)
Chrome
3317079
iPad (2018)
Safari
17810142
Immutable.js Map wins here too, with 79ms on an old Samsung phone.

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.

This entry was posted in Hexerals. Bookmark the permalink.

Leave a Reply

Your email address will not be published. Required fields are marked *

This site uses Akismet to reduce spam. Learn how your comment data is processed.