Reimplement RepeatedField<T> using an array as the backing store.

This is effectively reimplementing List<T>, but with a few advantages:
- We know that an empty repeated field is common, so don't allocate an array until we need to
- With direct access to the array, we can easily convert enum values to int without boxing
- We can relax the restrictions over what happens if the repeated field is modified while iterating, avoiding so much checking

This is somewhat risky, in that reimplementing a building block like this is *always* risky, but hey...
(The performance benefits are significant...)

1 files changed, 206 insertions, 33 deletions

diff --git a/csharp/src/ProtocolBuffers/Collections/RepeatedField.cs b/csharp/src/ProtocolBuffers/Collections/RepeatedField.cs
index 7dcd060e..0cd5cf80 100644
--- a/csharp/src/ProtocolBuffers/Collections/RepeatedField.cs
+++ b/csharp/src/ProtocolBuffers/Collections/RepeatedField.cs
@@ -6,7 +6,27 @@ namespace Google.Protobuf.Collections
 {
     public sealed class RepeatedField<T> : IList<T>, IEquatable<RepeatedField<T>>
     {
-        private readonly List<T> list = new List<T>();
+        private const int MinArraySize = 8;
+        private T[] array = null;
+        private int count = 0;
+
+        private void EnsureSize(int size)
+        {
+            if (array == null)
+            {
+                array = new T[Math.Max(size, MinArraySize)];
+            }
+            else
+            {
+                if (array.Length < size)
+                {
+                    int newSize = Math.Max(array.Length * 2, size);
+                    var tmp = new T[newSize];
+                    Array.Copy(array, 0, tmp, 0, array.Length);
+                    array = tmp;
+                }
+            }
+        }
 
         public void Add(T item)
         {
@@ -14,38 +34,55 @@ namespace Google.Protobuf.Collections
             {
                 throw new ArgumentNullException("item");
             }
-            list.Add(item);
+            EnsureSize(count + 1);
+            array[count++] = item;
+        }
+
+        /// <summary>
+        /// Hack to allow us to add enums easily... will only work with int-based types.
+        /// </summary>
+        /// <param name="readEnum"></param>
+        internal void AddInt32(int item)
+        {
+            EnsureSize(count + 1);
+            int[] castArray = (int[]) (object) array;
+            castArray[count++] = item;
         }
 
         public void Clear()
         {
-            list.Clear();
+            array = null;
+            count = 0;
         }
 
         public bool Contains(T item)
         {
-            if (item == null)
-            {
-                throw new ArgumentNullException("item");
-            }
-            return list.Contains(item);
+            return IndexOf(item) != -1;
         }
 
         public void CopyTo(T[] array, int arrayIndex)
         {
-            list.CopyTo(array);
+            if (this.array == null)
+            {
+                return;
+            }
+            Array.Copy(this.array, 0, array, arrayIndex, count);
         }
 
         public bool Remove(T item)
         {
-            if (item == null)
+            int index = IndexOf(item);
+            if (index == -1)
             {
-                throw new ArgumentNullException("item");
-            }
-            return list.Remove(item);
+                return false;
+            }            
+            Array.Copy(array, index + 1, array, index, count - index - 1);
+            count--;
+            array[count] = default(T);
+            return true;
         }
 
-        public int Count { get { return list.Count; } }
+        public int Count { get { return count; } }
 
         // TODO(jonskeet): If we implement freezing, make this reflect it.
         public bool IsReadOnly { get { return false; } }
@@ -56,8 +93,10 @@ namespace Google.Protobuf.Collections
             {
                 throw new ArgumentNullException("values");
             }
+            EnsureSize(count + values.count);
             // We know that all the values will be valid, because it's a RepeatedField.
-            list.AddRange(values);
+            Array.Copy(values.array, 0, array, count, values.count);
+            count += values.count;
         }
 
         public void Add(IEnumerable<T> values)
@@ -66,21 +105,21 @@ namespace Google.Protobuf.Collections
             {
                 throw new ArgumentNullException("values");
             }
+            // TODO: Check for ICollection and get the Count?
             foreach (T item in values)
             {
                 Add(item);
             }
         }
 
-        // TODO(jonskeet): Create our own mutable struct for this, rather than relying on List<T>.
-        public List<T>.Enumerator GetEnumerator()
+        public RepeatedField<T>.Enumerator GetEnumerator()
         {
-            return list.GetEnumerator();
+            return new Enumerator(this);
         }
 
         IEnumerator<T> IEnumerable<T>.GetEnumerator()
         {
-            return list.GetEnumerator();
+            return GetEnumerator();
         }
 
         public override bool Equals(object obj)
@@ -88,21 +127,30 @@ namespace Google.Protobuf.Collections
             return Equals(obj as RepeatedField<T>);
         }
 
+        IEnumerator IEnumerable.GetEnumerator()
+        {
+            return GetEnumerator();
+        }
+
+        /// <summary>
+        /// Returns an enumerator of the values in this list as integers.
+        /// Used for enum types.
+        /// </summary>
+        internal Int32Enumerator GetInt32Enumerator()
+        {
+            return new Int32Enumerator((int[])(object)array, count);
+        }
+
         public override int GetHashCode()
         {
             int hash = 23;
-            foreach (T item in this)
+            for (int i = 0; i < count; i++)
             {
-                hash = hash * 31 + item.GetHashCode();
+                hash = hash * 31 + array[i].GetHashCode();
             }
             return hash;
         }
 
-        IEnumerator IEnumerable.GetEnumerator()
-        {
-            return GetEnumerator();
-        }
-
         public bool Equals(RepeatedField<T> other)
         {
             if (ReferenceEquals(other, null))
@@ -119,9 +167,9 @@ namespace Google.Protobuf.Collections
             }
             // TODO(jonskeet): Does this box for enums?
             EqualityComparer<T> comparer = EqualityComparer<T>.Default;
-            for (int i = 0; i < Count; i++)
+            for (int i = 0; i < count; i++)
             {
-                if (!comparer.Equals(this[i], other[i]))
+                if (!comparer.Equals(array[i], other.array[i]))
                 {
                     return false;
                 }
@@ -135,7 +183,20 @@ namespace Google.Protobuf.Collections
             {
                 throw new ArgumentNullException("item");
             }
-            return list.IndexOf(item);
+            if (array == null)
+            {
+                return -1;
+            }
+            // TODO(jonskeet): Does this box for enums?
+            EqualityComparer<T> comparer = EqualityComparer<T>.Default;
+            for (int i = 0; i < count; i++)
+            {
+                if (comparer.Equals(array[i], item))
+                {
+                    return i;
+                }
+            }
+            return -1;
         }
 
         public void Insert(int index, T item)
@@ -144,24 +205,136 @@ namespace Google.Protobuf.Collections
             {
                 throw new ArgumentNullException("item");
             }
-            list.Insert(index, item);
+            if (index < 0 || index > count)
+            {
+                throw new ArgumentOutOfRangeException("index");
+            }
+            EnsureSize(count + 1);
+            Array.Copy(array, index, array, index + 1, count - index);
+            count++;
         }
 
         public void RemoveAt(int index)
         {
-            list.RemoveAt(index);
+            if (index < 0 || index >= count)
+            {
+                throw new ArgumentOutOfRangeException("index");
+            }
+            Array.Copy(array, index + 1, array, index, count - index - 1);
+            count--;
+            array[count] = default(T);
         }
 
         public T this[int index]
         {
-            get { return list[index]; }
+            get
+            {
+                if (index < 0 || index >= count)
+                {
+                    throw new ArgumentOutOfRangeException("index");
+                }
+                return array[index];
+            }
             set
             {
+                if (index < 0 || index >= count)
+                {
+                    throw new ArgumentOutOfRangeException("index");
+                }
                 if (value == null)
                 {
                     throw new ArgumentNullException("value");
                 }
-                list[index] = value;
+                array[index] = value;
+            }
+        }
+
+        public struct Enumerator : IEnumerator<T>
+        {
+            private int index;
+            private readonly RepeatedField<T> field;
+
+            public Enumerator(RepeatedField<T> field)
+            {
+                this.field = field;
+                this.index = -1;
+            }
+
+            public bool MoveNext()
+            {
+                if (index + 1 >= field.Count)
+                {
+                    return false;
+                }
+                index++;
+                return true;
+            }
+
+            public void Reset()
+            {
+                index = -1;
+            }
+
+            public T Current
+            {
+                get
+                {
+                    if (index == -1 || index >= field.count)
+                    {
+                        throw new InvalidOperationException();
+                    }
+                    return field.array[index];
+                }
+            }
+
+            object IEnumerator.Current
+            {
+                get { return Current; }
+            }
+
+            public void Dispose()
+            {
+            }
+        }
+
+        internal struct Int32Enumerator : IEnumerator<int>
+        {
+            private int index;
+            private readonly int[] array;
+            private readonly int count;
+
+            public Int32Enumerator(int[] array, int count)
+            {
+                this.array = array;
+                this.index = -1;
+                this.count = count;
+            }
+
+            public bool MoveNext()
+            {
+                if (index + 1 >= count)
+                {
+                    return false;
+                }
+                index++;
+                return true;
+            }
+
+            public void Reset()
+            {
+                index = -1;
+            }
+
+            // No guard here, as we're only going to use this internally...
+            public int Current { get { return array[index]; } }
+
+            object IEnumerator.Current
+            {
+                get { return Current; }
+            }
+
+            public void Dispose()
+            {
             }
         }
     }