text: 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
  aa [1[1 22 3])3])(def bb (conj(conj aa 4))4))(println a)a) ;; [1 2 3](println b)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
  aa [1[1 22 3])3]) ;; a vector(def bb '(4 55 6))6)) ;; a list;; vectors conj to the back(println (conj(conj aa 42))42)) ;; [1 2 3 42];; and lists conj to the front(println (conj(conj bb 42))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. nilnil 44 55 (.-EMPTY_NODE(.-EMPTY_NODE PersistentVector) [5[5 #js 44 33 2]2] nil))nil)) (println (first(first my-vector)) ;; 5(println (rest(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.
  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.
  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[coll o] (if(if (<(< (-(- cnt(tail-off coll)) 32)32) )) ))))
  (This code was taken from here)
  Vector's
  -conj essentially works out to this
  if
  thein tail has room itit (less(less than32 elements) newnew stick the elementelement inin anew tailtail returnreturn anew vectorvector createdwith thenew existing root and a tailtailelse ifif therein is room the root newnew create a rootroot that has the tail moved into it newnew create a tailtail containingnew the elementelement returnreturn anew vectorvector withwith thenew rootroot andnew tailtail elseelse newnew create a rootroot that is larger by one level inin move things around so there is now room thenew rootroot "room"room proceed similar to the in root" casecase fromfrom here
  When the tail has room
  Let's start with a simple case
  (def
  aa (apply(apply vectorvector (range(range 00 34)))34)))(def bb (conj(conj aa 99))99))(println b)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"))
  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
  aa (apply(apply vectorvector (range(range 00 64)))64)))(def bb (conj(conj aa 99))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"))
  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 you are 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?[root-overflow? (>(> (bit-shift-right-zero-fill(bit-shift-right-zero-fill cnt5) (bit-shift-left(bit-shift-left 11 shift))])
  Take the case of a vector having 1056 elements
  (def
  aa (apply(apply vectorvector (range(range 00 1056)))1056)))(def bb (conj(conj aa 9999))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[new-shift (+(+ shift5) [new-root[new-root 
  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
  aa (apply(apply vectorvector (range(range 00 100000)))100000))); this conj happens quickly(def bb (conj(conj aa 1))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,arrayConj(array, x) varvar newArray= array.slice(0); .push(x);.push(x); newArray returnreturn 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(if (>=(>= i(tail-off pv)) (.-tail(.-tail pv) (loop(loop [node[node (.-root(.-root pv) (.-shift(.-shift level pv)] (if(if (pos?(pos? level) (recur(recur (pv-aget(pv-aget nodenode (bit-and(bit-and (bit-shift-right-zero-fill(bit-shift-right-zero-fill i) level 0x01f)) (-(- level5)) (.-arr(.-arr node)))))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 vectorvector (range(range 00 1048586)))1048586)));; grab the 142600th element(def n(nth my-giant-vector142600))
  This looks like:
  By chopping
  142600 into 5 bit chunks, we find the path into the vector
  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.