Following text provides a basic technical overview of the specific details of implemented structures. I hope it help you to understand the basic concept of each structure. If you want to contribute some improvements, you are welcome.

 

PersistentList<T>

This is the implementation of persistent list. This structure represent persistent alternative to the well known mutable structure List<T> and it provides very similar interface. It is not implemented using singly linked list like in case of e.g. FSharpList<T>. Instead it uses very shallow tree so access to item on random index is quite efficient.

The implementation is similar to Clojure PersistentVector with the underlying structure HAMT. This text don't cover the explanation of this structure but for more info you can check Bagwell paper or read this article. This implementation uses arrays of length up to 32. (used 5 bits in bit partitioning). The three types of tree nodes are used:

  • ReferenceNode - represents tree node of references to either ReferenceNode or ValueNode
  • ValueNode - full leaf tree node, contains exact 32 generics values
  • TailNode - the tail node which doesn't create part of HAMT tree. It is directly referenced form PersistentList class. The tail node contains array of 32 values (or null) and LastModified field which indicates on which index was added last value. During adding operation, if last modified is equal to index in which item should be set, it will be added to array in mutable way and LastModified will be increased by one. Otherwise, array is copy with appropriate values and LastModified identifier. In order to ensure thread safe performing, synchronization locks are used.

PersistentVList<T>

An alternative implementation of persistent list. The underlying structure is Phil Bagwel's VList. This structure work very fast with Add and RemoveLast operations. Instead of simply linked list it provides better time complexity of accessing i-th item. There is nothing special to say about implementation.

PersistentDictionary<T>

This is the implementation of persistent associative array. It is an persistent alternative to the mutable Dictionary type and it provides similar interface. The underlying structure is HAMT like in case of PersistentList<T> but with some technical differences. The implementation was inspired by Clojure's PersistentHashMap (see this article for more info).

The main difference is that this implementation uses only one type of tree node - MapNode. It contains 3 arrays:

  • Array of generics values
  • Array of collisions - the collections implement interface ICollisionCollection
  • Array of references the next nodes

The benefit is that we don't create leaf node for each value and in path copying we copy only one array in which change occurs. This approach supports better structure sharing so it safe extra time and space using each modification operation. The disadvantage is quite bad design where one class has complex responsibility.

PersistentHashSet<T>

Implementation of persistent set using PersistentDictionary<T, bool>.

PersistentStack<T>

This is implementation of persistent stack using singly linked list.

PersistentQueue<T>

Implementation of persistent queue using two stacks. In Enqueue operation Push is called in the first stack and Dequeue operation Pop is called in the second stack. If the second stack is empty, all items in first stack is moved to the second in reversed order.

This implementation uses PersistentVList<T> to implement stack and PersistentRVList<T> to implement reversed stack. The PersistentRVList<T> is a light weight implementation of VList which can remove items from the end of list. It is much efficient to implement stack in this way because the much complex operation in persistent queue is moving items from first stack to second in reversed order. In VList it can be done simply reversing block descriptors which count is only log(n) in average.

 

Transients

The types PersistentList<T>, PersistentVList<T>, PersistentDictionary<T> and PersistentHashSet<T> provides ability of transients. It is a temporal ephemeral state in which structure is, during performing huge batch operation. After that it returns back to persistent state. The nameing is inspired by Clojure.

example:

 var plist = PersistentList<int>.Empty;
 var transient = plist.AsTransient();

 for(int i = 0; i < 100000; i++)
     transient.Add(i);
 
 plist = transient.AsPersistent();

 

Last edited Jun 2, 2015 at 1:32 AM by majom, version 8