Unity (Pre 5.5) Memory Safe Enumerators with C5 Generic Collection Library

DISCLAIMER: The topic treated in this article is only valid for version of Unity up to 5.4

Long time ago I posted an article on how disposable value types were treated in Unity and why they used to generate unnecessary and unwanted garbage. It emerged that in the official Mono compiler as well as in the Microsoft C# compiler (but not in Unity) a violation of the C# specification lead to an optimisation of disposable structs within a using statement. Disposable value types are used in C# mainly to implement iterator blocks, which are used to iterate over collections. Two years ago I  decided to fix this issue by re-implementing the enumerators in a library called C5 which is a project for generic collection classes for C# and other CLI languages. However with the release of Unity 5.5 back in March 2017 version 4.4 of the Mono C# compiler was shipped and finally this issue was properly fixed and became history.

This solution is not relevant anymore 🙂 unless you use an old version of Unity but I would still like to share with you the solution I came up with before the release of the new Mono compiler.

C5 implements a lot of data structures not provided by the standard .NET Framework, such as persistent trees, heap based priority queues, hash indexed array lists and linked lists, and events on collection changes. The source code is available on GitHub and MIT license makes you free to modify and re-distribute it if you want. I started my journey in creating my own enumerator implementation for the main collections (ArrayList, DictionaryHash, SortedDictionary etc) and I came up with the idea of a “reusable” enumerator.

With this approach only one enumerator instance per collection iterated is used at a time. Naturally this has some limitations. For example, multiple iterations of the same collection, multithread access and LINQ will not work.

To accommodate all the cases I implemented three memory models called:

  1. Normal: An enumerator is created anytime the collection is iterated. This is the normal behaviour expected and thus is not memory safe, but supports multiple iterations, multithread and LINQ.
  2. Safe: An enumerator is created once and then re-used. This approach doesn’t generate garbage. However, if the collection is iterated using nested loops or accessed by multiple threads, a new enumerator is created. The collection will save memory unless it is forced not to do so.
  3. Strict: An enumerator is created only once. This approach doesn’t generate garbage at all cost.  if the collection is iterated using nested loops or accessed by multiple threads an exception is thrown.

The memory model is implemented as an enum and it is passed to the constructor. For example:

   HashSet<inta = new HashSet<int>(MemoryType.Strict);
Screen Shot 2016-03-02 at 14.36.38

Figure 1 – MemoryType.Normal – 56 bytes of garbage every frame

Figure 1 and 2 shows two different scenarios: in the former garbage is generated by iterating over an ArrayList while in the latter no garbage is reported by the memory profiler.

MemoryType.Normal replicates the normal behaviour. The amount of garbage generated depends really on the size of the struct that is used to iterate the collection, therefore its size can vary. Figure 2 shows instead that no garbage is generated when an ArrayList is iterated.

Screen Shot 2016-03-02 at 14.35.43
Figure 2 – C5 ArrayList with MemoryType.Safe – No garbage

This is possible by reusing the same enumerator. Although it is not shown, 56 bytes are allocated only the first time the collection is iterated.

 

Currently the garbage free memory model is implemented for the following collections:

  • ArrayList<T>
  • HashedArrayList<T>
  • SortedArray<T>
  • WrappedArray<T>
  • CircularQueue<T>
  • HashSet<T>
  • TreeBag<T>
  • HashBag<T>
  • HashDictionary<T>
  • TreeDictionary<T>
  • TreeSet<T>
  • LinkedList<T>
  • HasedLinkedList<T>
  • IntervalHeap<T>

This is the source code for the MemorySafeEnumerator:

 internal abstract class MemorySafeEnumerator<T> : IEnumerator<T>, IEnumerable<T>, IDisposable {
     private static int MainThreadId;
 
     //-1 means an iterator is not in use.
     protected int IteratorState;
 
     protected MemoryType MemoryType { getprivate set; }
 
     protected static bool IsMainThread {
         get { return Thread.CurrentThread.ManagedThreadId == MainThreadId; }
     }
 
     protected MemorySafeEnumerator(MemoryType memoryType) {
         MainThreadId = Thread.CurrentThread.ManagedThreadId;
 
         IteratorState = -1;
     }
 
     protected abstract MemorySafeEnumerator<TClone();
     public abstract bool MoveNext();
     public abstract void Reset();
 
     public T Current { getprotected set; }
 
     object IEnumerator.Current {
         get { return Current; }
     }
 
     public virtual void Dispose() {
         IteratorState = -1;
     }
 
     public IEnumerator<TGetEnumerator()
     {
         MemorySafeEnumerator<Tenumerator;
 
         switch (MemoryType) {
             case MemoryType.Normal:
                 enumerator = Clone();
                 break;
             case MemoryType.Safe:
                 if (IsMainThread) {
                     enumerator = IteratorState != -1 
                     ? Clone() 
                     : this;
                     IteratorState = 0;
                 }
                 else {
                     enumerator = Clone();
                 }
                 break;
             case MemoryType.Strict:
                 if (!IsMainThread) {
                     throw new ConcurrentEnumerationException("Multithread access detected! In Strict memory mode is not possible to iterate the collection from different threads");
                 }
 
                 if (IteratorState != -1) {
                     throw new MultipleEnumerationException("Multiple Enumeration detected! In Strict memory mode is not possible to iterate the collection multiple times");
                 }
 
                 enumerator = this;
                 IteratorState = 0;
 
                 break;
             default:
                 throw new ArgumentOutOfRangeException();
         }
 
 
         return enumerator;
     }
 
     IEnumerator IEnumerable.GetEnumerator() {
         return GetEnumerator();
     }
 }

Everything happens in the GetEnumerator() method. In normal mode the enumerator is always cloned while in safe mode the enumerator is cloned only for multithread access and/or multiple enumerations, otherwise the same instance is reused. The strict model optimise at all cost but throws an exception for the other cases.

Conclusions

This solution is clearly outdated and I’m glad that Unity has eventually adopted a proper version of the Mono compiler. However I had a lot of fun coding a hand-made solution, and it was also a good opportunity to dive into the nitty-gritty implementation of C5 and I learnt a lot about data structures. Next time I will remember to publish an article on time 😀

See you soon!

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s