Implementing immutable vectors in JavaScript

March 24, 2014

Update: The library described in this post has now been publicly released.

This weekend I took a stab at implementing immutable vectors in JavaScript. Immutable vectors are arrays guaranteed never to be changed. Instead, you “change” them by obtaining a new copy with the change made:

// Create an immutable vector
var v1 = new ImmutableVector(1, 2, 3);
console.log(v1.toArray()); // [ 1, 2, 3 ]

// "Change" it by pushing 4 to the end
var v2 = v1.push(4);
console.log(v2.toArray()); // [ 1, 2, 3, 4 ]

// The original is still unchanged:
console.log(v1.toArray()); // [ 1, 2, 3 ]

It’s like dealing with numbers. You can update a numeric variable if you want: x = x + 1. But you can also compute something and assign the result to a different variable: y = x + 1. In that case, x stays the same. With immutable vectors, update methods like .push(val) and .set(index, val) work just like +.

You may have seen these in Clojure, where they’re the default array-like data structure, or in Scala. Clojure calls them “persistent vectors”, but that confuses everyone, so let’s go with Scala’s choice of “immutable”.

My approach was:

On a 10,000-element vector, the naive, copy-everything approach performed like this:

A vector trie with a branching factor of 2 sped things up nicely:

Then, simply setting the branching factor to 32 brought us to a 24-70x speedup over the naive approach:

I tried every power of two from 2 to 128. 128-way tries were slightly faster on in-place changes but worse on appends. Other than that, 32 won.

Bit shifting

When I implemented the last part of the Understanding Clojure’s persistent vector article, things got a little disappointing. “Bit partitioning” takes advantage of the fact that my branching factors are all powers of 2 by using bit shifting and bit masks to look up elements — rather than division and modular arithmetic. It’s really just a micro-optimization, and it didn’t help much:

The conventional wisdom on JavaScript is not to bother with bit operations since all numbers are floating-point anyway, but I thought V8 would be smart enough to know these numbers only take on integer values and optimize accordingly. Apparently not. That, or division and modulo weren’t the bottleneck to begin with.

Still to do

This is a hack I’m not ready to show off yet. If you dig a little you can find it on my GitHub page, but I’m not going to link directly.

The worst part is I cheated on implementing .slice() (not benchmarked). It simply copies the whole array. Clojure’s subvec is O(1), so there is a way to achieve that, but I know that will take longer to figure out. Maybe store some kind of a view on the original vector, with an offset. I’m worried about performance degrading when you attempt to operate on the vector slice.

Also, .pop() simply calls .slice(), so removing elements from the end of the array will be horrendously inefficient.

Finally, I’d like to beef up the benchmarking, testing random-access and sequential reads and perhaps finding a way to simulate realistic use in an application.

Why I’m doing this

It might seem silly to go up against Mori, a highly performant implementation of immutable collections which can be used from JavaScript. But Mori is a straight port of the standard lib from ClojureScript, and using it in JS feels weird. A solid, pure-JS implementation could feel truly native and be easier for JavaScript programmers to contribute to and use.

I’ve gone with JavaScript Array-like method names (push, pop, slice, as well as get and set), and I’m still not sure whether that’s a good idea. Pro: It’s familiar. Con: Since the semantics are different from pushing to or popping from an array, those names could be confusing. I’d appreciate feedback on this.

You should subscribe to my rss feed here.