These are graphs from my JavaOne 2013 talk: “Immutable Collections from Clojure and Scala”. The slides from the talk are available at slreynolds.net. The graphs were generated using RegionViewer which allows you to export a region (graph of objects on a JVM) to several different types of graph files. RegionViewer is a pure Java library that uses reflection to export a graph of any type Java objects.
A Java ArrayList with two elements.. The elements in the list are of type Bar.
A Java LinkedList. This is doubly linked and is in a circular configuration. It's not suitable for an immutable list because of the back-pointers.
Two Java Strings: “brother” and “the”. The second string was made as a substring of the first. This shows structural sharing between the two strings.
Two object references were passed to RegionViewer, which then took the first reference (brother) and followed all the object references. Those nodes were colored redish-orange. Then RegionViewer took the second object reference (the) and followed all the object references while being careful to not visit any nodes twice. Those were colored greenish-yellow.
A Clojure list with two elements of type Foo. This is singly linked and is in a linear configuration. The end of the list is indicated by a null pointer (not shown in the graph).
The same Clojure list as before but with two operations applied. The original list (denoted by the symbol w), the second object reference is the result of rest of w, and the last is the conj function applied to w. This conj operation adds an element to the head of the list. Note that RegionViewer colored this third object reference purple.
Operations on the head of the list are constant time, fast operations.
A Scala list with two elements of type Foo. This looks just like the Clojure list. It is singly linked and is in a linear configuration. The end of the list is indicated by an explicit object Nil$.
A Scala list with the same operations applied that we did on the Clojure list.
The following three graphs is a sequence of Scala maps as we add key/values. The first shows a map with one key/value. Scala has a specialized map for one key/value for efficiency.
The we have now added a second key/value. Scala has a now switched to a HaskTrieMap to store them. This uses the HAMT structure created by Phil Bagwell.
The we have now added a third key/value. The trie now has two levels because the first five hashcode bits collided at the first level. Scala pushed down a second level to resolve the ambiguity.
A small map in Clojure. Clojure recognizes that the map is small and uses an efficient structure that is an array of key value pairs.
We can use the hash-map function to insist that Clojure use a proper HAMT. This using the principles from Phil's HAMT like the Scala map.
A before and after diagram showing a Clojure map when we added a key/value. Note the extensive structural sharing.
A small map in Scala. Scala has specialized efficient structures for small maps.
We can insist that Scala use a proper HAMT. This map has two key/values and one level.
A before and after diagram showing a Scala map when we added a key/value. Note the extensive structural sharing.
A before and after diagram showing what happens when we change the value for a key. The key Foo (ID=3) had its value changed from Bar (ID=3) to Bar (ID=30).
A large Clojure map. This diagram is simplified — it does not show the object fields.
A Clojure map with a hashcode collision. The hash code for Foo (ID=1) is identical to the hashcode for Foo (ID-65537). Clojure makes a list of the colliding elements.
A Scala map with a hashcode collision. Scala makes a linked list of the colliding elements.
The following graphs shows a sequence of Scala Vectors as we add elements. We start with one element in the Vector.
Two elements in the Vector.
Three elements in the Vector.
Four elements in the Vector.
Five elements in the Vector.
Six elements in the Vector.
Seven elements in the Vector.
Skipping ahead to thirty elements in the Vector. Two are free in the elements array.
Thirty-one elements in the Vector, one free in the elements array.
Thirty-two elements in the Vector, nothing free in the elements array.
The original level in the tree is full and Scala has created two levels.
Adding another element. Scala adds it in the first level.
Adding another element. Scala adds it in the first level.
A Clojure Vector before any operations. It contains three Foo instances.
The same Clojure Vector after it has had the transient function applied.
The same transient after it has had a Foo instance added to the end. This transient was mutated.
The same transient after it has been converted back to persistent by applying the persistent! function.
A Scala Vector that contains three Bar instances after the par method has been applied. A ParVector has been created.
The same Scala ParVector after the map function has been applied to the elements. The function applied multiplied the Bar ID by 10 and created a new Bar instance. Depending on the operation, it could be done in parallel.
