Matt Greer

ClojureScript Internals - Vectors

26 January 2015

Today we’re taking a look at how vectors are implemented in ClojureScript. We’ll explore some of the trade offs made between performance and immutability, and we’ll get a feel for how a language like Clojure gets mapped into a language like JavaScript.

A Little Background

Before diving into the how, we need to talk about the why a little bit. If you’re not new to Clojure, feel free to skip to the next section.

Persistent Data Structures

Clojure data structures are persistent and immutable.

(def a [1 2 3])
(def b (conj a 4))
(println a) ; [1 2 3]
(println b) ; [1 2 3 4]

a persists on despite b being created based off of it. a can never change in the Clojure world. ClojureScript needs to maintain this promise of immutability and persistence too.

Data Structure Characteristics

Clojure’s different data structures have different tendencies. Vector’s claim to fame is it is efficient when working with the back of the vector. Lists on the other hand optimize their efficiency at the front. conj is the classic example of when these differences can come to light

(def a [1 2 3])  ; a vector
(def b '(4 5 6)) ; a list

;; vectors conj to the back
(println (conj a 42)) ; [1 2 3 42]

;; and lists conj to the front
(println (conj b 42)) ; (42 4 5 6)

When the ClojureScript team implemented vectors, they needed to maintain this characteristic. This will become apparent as we dig deeper.

Inside ClojureScript’s PersistentVector

Whenever you create a vector in ClojureScript either with the literal form [1 2 3] or perhaps by calling (vector 4 5 6), ultimately this becomes an instance of cljs.core.PersistentVector. PersistentVector lives in the core ClojureScript namespace, which does mean it is accessible from standard ClojureScript code

(def my-vector (PersistentVector.
                 nil
                 4
                 5
                 (.-EMPTY_NODE PersistentVector)
                 #js [5 4 3 2]
                 nil))

(println (first my-vector)) ; 5
(println (rest my-vector))  ; [4 3 2]

This hints at the fact that cljs.core is written in ClojureScript itself; and it is, you can see the implementation of PersistentVector here.

The vector’s root and tail

Internally, vectors have a root and a tail. Up above where we directly instantiated a PersistentVector, the EMPTY_NODE was the root, and the #js [5 4 3 2] was the tail. Small vectors put all of their elements into their tail, leaving an empty root. The tail is simply a JavaScript array.

Technically the root is not empty, it actually contains an array of 32 nulls. Each null slot is a spot where the root can allow grow

(there is a bug in Chrome that makes these diagrams look a bit off)

What happens when the vector is larger than 32 elements? That is where the root comes into play. Generally, the root contains floor(count / 32) * 32 elements and the tail contains count % 32 elements. So if the vector is 900 elements long, 896 elements go to the root, and the remaining 4 head to the tail.

This is simplified and not entirely true. It’s important that the tail never be empty. If a vector’s length is a multiple of 32 (say 64), then the above would suggest all the elements go into the root. But in reality, 32 will be diverted to the tail

Here is what a vector created by (apply vector (range 0 64)) looks like

here’s (apply vector (range 0 900))

and here’s (apply vector (range 0 11000))

The root’s nodes are instances of cljs.core.VectorNode. A VectorNode basically just contains a JavaScript array which either contains more VectorNodes, or actual elements of the vector. VectorNode is not too important for our discussion, so we’ll gloss over it from here on out. Notice elements are always found at the leaves of the tree.

Conj’ing Vectors

Let’s get a feel for how the root and tail work by exploring conj

Here is Vector’s conj implementation. Don’t worry about studying this block too much, we’re going to break it into pieces

(-conj [coll o]
    (if (< (- cnt (tail-off coll)) 32)
      (let [len (alength tail)
            new-tail (make-array (inc len))]
        (dotimes [i len]
          (aset new-tail i (aget tail i)))
        (aset new-tail len o)
        (PersistentVector. meta (inc cnt) shift root new-tail nil))
      (let [root-overflow? (> (bit-shift-right-zero-fill cnt 5) (bit-shift-left 1 shift))
            new-shift (if root-overflow? (+ shift 5) shift)
            new-root (if root-overflow?
                       (let [n-r (pv-fresh-node nil)]
                           (pv-aset n-r 0 root)
                           (pv-aset n-r 1 (new-path nil shift (VectorNode. nil tail)))
                           n-r)
                       (push-tail coll shift root (VectorNode. nil tail)))]
        (PersistentVector. meta (inc cnt) new-shift new-root (array o) nil))))

(This code was taken from here)

This is the vector specific -conj method, the actual conj method we just called is here, it uses Clojure protocols to find and invoke vector’s -conj when called with a vector

Vector’s -conj essentially works out to this

if the tail has room in it (less than 32 elements)
    stick the new element in a new tail
    return a new vector created with the existing root and a new tail
else
    if there is room in the root
        create a new root that has the tail moved into it
        create a new tail containing the new element
        return a new vector with the new root and new tail
    else
        create a new root that is larger by one level
        move things around so there is now room in the new root
        proceed similar to the "room in root" case from here

When the tail has room

Let’s start with a simple case

(def a (apply vector (range 0 34)))
(def b (conj a 99))
(println b) ; [0 1 2 3 4 5 ... 31 32 33 99]

a is 34 elements long, with 32 elements sitting in the root and 2 hanging out in the tail. There’s plenty of room in the tail, so this is the first case inside conj

;; the chunk of conj that handles the "tail has room" case
(let [len (alength tail)
      new-tail (make-array (inc len))]
  (dotimes [i len]
    (aset new-tail i (aget tail i)))
  (aset new-tail len o)
  (PersistentVector. meta (inc cnt) shift root new-tail nil))

make-array will create our new tail that is one larger than the original tail ((inc len)), then we iterate over the original tail and copy its contents into the new tail. At the end of the new tail, the new value o is placed and from there a new instance of PersistentVector is returned.

No room in the tail, but room in the root

This time let’s consider conj’ing onto a vector that has 64 elements

(def a (apply vector (range 0 64)))
(def b (conj a 99))

This time the tail is full, so that makes the tail a candidate to become a new leaf in the root’s tree. And from there we just create a brand new tail containing the new element. We can see this happening in the conj code

;; the part of conj that deals with the "tail is full" case
(let [root-overflow? (> (bit-shift-right-zero-fill cnt 5)
                        (bit-shift-left 1 shift))
      new-shift (if root-overflow? (+ shift 5) shift)
      new-root (if root-overflow?
                  (let [n-r (pv-fresh-node nil)]
                    (pv-aset n-r 0 root)
                    (pv-aset n-r 1 (new-path nil shift (VectorNode. nil tail)))
                    n-r)
                  (push-tail coll shift root (VectorNode. nil tail)))]
  (PersistentVector. meta (inc cnt) new-shift new-root (array o) nil))

The above code has both root cases (whether the root is full or not) intertwined. If root-overflow? is false, then our root still has some room in it. In that case all that really happens is new-root gets set by the call to push-tail, which returns a new root with our existing tail added to it. Then ultimately we return a new vector housing the new root and we quickly whip up a new tail for it that contains the appended element with (array o).

This diagram is pretty telling. b “borrows” everything from a, and a remains unaffected. A great example of how ClojureScript accomplishes persistence and immutability all while maintaining a good performance footprint.

The final case, the root is full

This is the most complex case. If your conj’ed out, feel free to head onto the next section.

introducing shift

It’s no coincidence that 32 is how large VectorNodes can be and the upper bound for the tail’s size. Working with powers of 2 has some nice advantages. You probably noticed the bit-shift... methods up above in the conj code. Clever usage of bitwise operations enables the vector to efficiently determine things about itself like whether its root has overflown, or how many of its elements are in the tail.

Each vector has a shift property, which is a multiple of 5, 1 << 5 is 32. Basically the shift is telling us how many elements the root can hold. When shift is 5, the root has a depth of 1, 10 means a depth of 2, and so on. Way up there when we manually created our own PersistentVector, we passed in 5 as our shift. Shift also tells other things about the vector, as we’ll see later on when we index into one (its name will make more sense then too).

When a vector has a shift of 5, its root can at most hold 32 * 32 elements (1024). That is, the root contains 32 VectorNodes, and each VectorNode holds 32 elements of the vector.

Now we can begin to understand how vectors determine if their root is full

(let [root-overflow? (> (bit-shift-right-zero-fill cnt 5)
                        (bit-shift-left 1 shift))])

Take the case of a vector having 1056 elements

(def a (apply vector (range 0 1056)))
(def b (conj a 9999))

This vector is packed to the gills, root-overflow? will be true. Before it can proceed, the root needs to grow by one level

;; creation of the new root.
;; the root not overflowing case removed for better clarity
(let
  [new-shift (+ shift 5)
  [new-root (let [n-r (pv-fresh-node nil)]
              (pv-aset n-r 0 root)
              (pv-aset n-r 1 (new-path nil shift (VectorNode. nil tail)))
              n-r))

Here a new root node is created with pv-fresh-node, then the existing root is pushed down to become a child, and then the tail becomes the second child with new-path

This last diagram’s a little noisy, but again everything gets shared between a and b.

Advantages to the Root/Tail Design

This is a lot of hoopla just to add a new element onto a vector. Why all the fuss?

(def a (apply vector (range 0 100000)))
; this conj happens quickly
(def b (conj a 1))

Big deal! In JavaScript myGiantArray.push(1) is also very fast! In fact, it’s faster! But ClojureScript is maintaining immutability (and persistence), where push mutates in place. A naive approach to accomplishing immutability in JavaScript would be

function arrayConj(array, x)
  var newArray = array.slice(0);
  newArray.push(x);
  return newArray;
}

That slice() is very costly in time and memory when the array is large. Obviously that’s a terrible way to accomplish immutability, a real JavaScript immutable data structure would probably end up working very similar to ClojureScript’s vector.

Fair enough, but can’t the root just be an array? Not ideally, because as we saw in the above case where the vector had 64 elements, we were able to create a second root very efficiently. The first root is maintained, as the first vector still needs it. The second root was just a matter of moving some tree nodes around. If the root was a flat array, then this would have called for more cloning.

Indexing into the vector

Since the root is a tree, some performance is lost when we need to look up an element. With an array, finding an element is a matter of simple arithmetic. But (nth my-giant-vector 200) will require the vector to dig inside the root and figure out where its 200th element lives before it can return it. This requires a little tree traversal, and is done with the unchecked-array-for function

(defn- unchecked-array-for [pv i]
  (if (>= i (tail-off pv))
      (.-tail pv)
      (loop [node (.-root pv)
             level (.-shift pv)]
        (if (pos? level)
          (recur (pv-aget node (bit-and (bit-shift-right-zero-fill i level) 0x01f))
                 (- level 5))
          (.-arr node)))))

Ultimately a vector is a tree of arrays, so unchecked-array-for is finding the array that contains the queried index, and from there it’s just a matter of indexing into a standard JavaScript array. The top of the if first figures out if the index is in the tail, if so the answer is easy. Otherwise loop is used to move down through the tree. Again, clever use of bitwise operations enables finding the path through the tree to be efficient.

pv-aget is a simple method that knows a VectorNode contains an array, it effectively does node.arr[i], and determining what i is relies on some bit-wise logic. (bit-and (bit-shift-right-zero-fill i level) 0x01f) works out to be (i >>> level) & 31, which tells us which array at each level is the one we need to traverse down into.

That was pretty dense, no? To put that nonsense another way, the index contains its own path into the tree. Let’s take a look at

(def my-giant-vector (apply vector (range 0 1048586)))
;; grab the 142600th element
(def n (nth my-giant-vector 142600))

This looks like:

By chopping 142600 into 5 bit chunks, we find the path into the vector

142600
00100010110100001000
00100
01011
01000
01000
4
11
8
8

And “chopping into 5 bit chunks” is what unchecked-array-for is doing. Pretty clever.

Wrapping It Up

The immutability offered by ClojureScript data structures is great. But at the same time, vectors look and feel like arrays. That familiar feeling can be deceiving. It is useful to get a sense for how they are implemented, so you can make better choices when using them. I was inspired to make this post when one of my first ClojureScript apps ended up being really slow. I was using large vectors and lots of lazy sequences, causing a significant performance degradation. I decided to dig into the code to find out why. I hope to one day also write a bit on how lazy sequences work in ClojureScript too, so stay tuned!