Tuesday, February 01, 2011

Some numbers on .Net Collections performance

After @GaryShort's talk on Saturday at DDD9 I've just spent an hour hacking some initial numbers together on performance:

BaselineAdd     of size 1000    took 10856 ticks
BaselineAdd     of size 10000   took 47490 ticks
BaselineAdd     of size 100000  took 343267 ticks

ListAdd of size 1000    took 5459 ticks
ListAdd of size 10000   took 43505 ticks
ListAdd of size 100000  took 738327 ticks

PreSizedListAdd of size 1000    took 4241 ticks
PreSizedListAdd of size 10000   took 152861 ticks
PreSizedListAdd of size 100000  took 664572 ticks

WronglyPreSizedListAdd  of size 100000  took 746042 ticks
VeryWronglyPreSizedListAdd      of size 100000  took 772499 ticks

LinkedListAdd   of size 1000    took 4210 ticks
LinkedListAdd   of size 10000   took 42905 ticks
LinkedListAdd   of size 100000  took 794595 ticks

ListRemoveByIndex       of size 1000    took 145411 ticks
ListRemoveByObject      of size 1000    took 3590562 ticks

These numbers already show some interesting facts....
  • If you can help it, don't use Remove() - use RemoveAt()!
  • For smallish lists, LinkedLists perform rather well
  • The penalty for wrongly sizing lists seems small (maybe the code is wrong or maybe my understanding is!).
  • It's remarkably hard to write generics that rely on generics (especially when LinkedList<> doesn't derive from the same interfaces as List<>)
But there's still plenty more to do...

The code so far is:

using System;

using System.Collections.Generic;

using System.Linq;

using System.Text;

using System.Diagnostics;

 

namespace CollectionsTiming

{

    class Program

    {

        private const int TestSize = 100000;

 

        static void Main(string[] args)

        {

            var p = new Program();

            p.DoIt();

        }

 

        public void DoIt()

        {

            InternalListAddTestRun("BaselineAdd", TestSize / 100, () => new NopList<TestObject>());

            InternalListAddTestRun("BaselineAdd", TestSize / 10, () => new NopList<TestObject>());

            InternalListAddTestRun("BaselineAdd", TestSize, () => new NopList<TestObject>());

            Console.WriteLine();

            InternalListAddTestRun("ListAdd", TestSize / 100, () => new List<TestObject>());

            InternalListAddTestRun("ListAdd", TestSize / 10, () => new List<TestObject>());

            InternalListAddTestRun("ListAdd", TestSize, () => new List<TestObject>());

            Console.WriteLine();

            InternalListAddTestRun("PreSizedListAdd", TestSize / 100, () => new List<TestObject>(TestSize / 100));

            InternalListAddTestRun("PreSizedListAdd", TestSize / 10, () => new List<TestObject>(TestSize / 10));

            InternalListAddTestRun("PreSizedListAdd", TestSize, () => new List<TestObject>(TestSize));

            Console.WriteLine();

            InternalListAddTestRun("WronglyPreSizedListAdd", TestSize, () => new List<TestObject>(TestSize / 100));

            InternalListAddTestRun("VeryWronglyPreSizedListAdd", TestSize, () => new List<TestObject>(TestSize / 1000));

            Console.WriteLine();

            InternalListAddTestRun("LinkedListAdd", TestSize / 100, () => new LinkedList<TestObject>());

            InternalListAddTestRun("LinkedListAdd", TestSize / 10, () => new LinkedList<TestObject>());

            InternalListAddTestRun("LinkedListAdd", TestSize, () => new LinkedList<TestObject>());

            Console.WriteLine();

            InternalListRemoveTestRun("ListRemoveByIndex", TestSize, TestSize / 100, (list, index, obj) => list.RemoveAt(index));

            InternalListRemoveTestRun("ListRemoveByObject", TestSize, TestSize / 100, (list, index, obj) => list.Remove(obj));

            Console.WriteLine();

            //InternalListRemoveTestRun("PreSizedAdd", TestSize, TestSize / 100, () => new List<TestObject>(TestSize / 100));

            Console.WriteLine();

 

            Console.ReadLine();

        }

 

        public void InternalListRemoveTestRun(string name, int totalSize, int removeSize, Action<List<TestObject>, int, TestObject> removeAction)

        {

            InternalTestRun(name, removeSize, () => InternalRemoveTestRun(totalSize, removeSize, removeAction));

        }

 

        public long InternalRemoveTestRun(int totalSize, int removeSize, Action<List<TestObject>, int, TestObject> removeMethod)

        {

            var testList = new List<TestObject>(totalSize);

            for (int i = 0; i < totalSize; i++)

            {

                testList.Add(new TestObject(i));

            }

            SortedList<int, Tuple<int, TestObject>> toRemove = new SortedList<int, Tuple<int, TestObject>>(removeSize);

            var rand = new Random();

            while (toRemove.Count < removeSize)

            {

                int candidate = rand.Next(totalSize);

                toRemove[candidate] = new Tuple<int, TestObject>(candidate, testList[candidate]);

            }

           

            Stopwatch s = new Stopwatch();

            s.Start();

            foreach (var tuple in toRemove.Values.Reverse())

            {

                removeMethod(testList, tuple.Item1, tuple.Item2);

            }

            s.Stop();

            var result = s.ElapsedTicks;

            return result;

        }

 

        public void InternalListAddTestRun(string name, int maxSize, Func<LinkedList<TestObject>> initialiser)

        {

            InternalTestRun(name, maxSize, () => LinkedListAddTestRun(maxSize, initialiser));

        }

 

        public void InternalListAddTestRun(string name, int maxSize, Func<IList<TestObject>> initialiser)

        {

            InternalTestRun(name, maxSize, () => ListAddTestRun(maxSize, initialiser));

        }

 

        public void InternalTestRun(string name, int maxSize, Func<long> testMethod)

        {

            var result = testMethod();

            Console.WriteLine("{0}\tof size {1}\ttook {2} ticks", name, maxSize, result);

        }

 

        public long ListAddTestRun(int maxSize, Func<IList<TestObject>> initialiser)

        {

            Stopwatch s = new Stopwatch();

            s.Start();

            var testObject = initialiser();

            for (int i = 0; i < maxSize; i++)

            {

                testObject.Add(new TestObject(i));

            }

            s.Stop();

            var result = s.ElapsedTicks;

            return result;

        }

 

        public long LinkedListAddTestRun(int maxSize, Func<LinkedList<TestObject>> initialiser)

        {

            Stopwatch s = new Stopwatch();

            s.Start();

            var testObject = initialiser();

            for (int i = 0; i < maxSize; i++)

            {

                testObject.AddLast(new TestObject(i));

            }

            s.Stop();

            var result = s.ElapsedTicks;

            return result;

        }

    }

 

    class NopList<T> : IList<T>

    {

        public void Add(T to)

        {

        }

 

        public NopList()

        {

 

        }

 

        public NopList(int capacity)

        {

 

        }

 

        public int IndexOf(T item)

        {

            throw new NotImplementedException();

        }

 

        public void Insert(int index, T item)

        {

            throw new NotImplementedException();

        }

 

        public void RemoveAt(int index)

        {

            throw new NotImplementedException();

        }

 

        public T this[int index]

        {

            get

            {

                throw new NotImplementedException();

            }

            set

            {

                throw new NotImplementedException();

            }

        }

 

 

        public void Clear()

        {

            throw new NotImplementedException();

        }

 

        public bool Contains(T item)

        {

            throw new NotImplementedException();

        }

 

        public void CopyTo(T[] array, int arrayIndex)

        {

            throw new NotImplementedException();

        }

 

        public int Count

        {

            get { throw new NotImplementedException(); }

        }

 

        public bool IsReadOnly

        {

            get { throw new NotImplementedException(); }

        }

 

        public bool Remove(T item)

        {

            throw new NotImplementedException();

        }

 

        public IEnumerator<T> GetEnumerator()

        {

            throw new NotImplementedException();

        }

 

        System.Collections.IEnumerator System.Collections.IEnumerable.GetEnumerator()

        {

            throw new NotImplementedException();

        }

    }

 

    class TestObject

    {

        public string MyKey { get; set; }

        public string SomeRandomText { get; set; }

        public int Index { get; set; }

 

        public TestObject(int index)

        {

            MyKey = Guid.NewGuid().ToString();

            SomeRandomText = Guid.NewGuid().ToString();

            Index = index;

        }

    }

}


Will tidy this up and add more when I get some more "spare time"!

No comments:

Post a Comment