Click here to Skip to main content
11,490,007 members (63,730 online)
Click here to Skip to main content
Add your own
alternative version

Squeezing more performance from SortedList

, 10 Oct 2008 CPOL 41.4K 224 30
A SortedList implementations using a cyclic algorithm and C# IDictionary tweaks.
SplitArrayDictionary_demo.zip
SplitArrayDictionary_bin
Debug
SplitArrayDictionary.exe
SplitArrayDictionary.vshost.exe
SplitArrayDictionary.vshost.exe.manifest
Release
SplitArrayDictionary.exe
SplitArrayDictionary_src.zip
SplitArrayDictionary_src
Properties
src
using System.Diagnostics;
using System.Collections.Generic;
using System.Collections.Specialized;
namespace SplitArrayDictionary
{
    public static class Program
    {
        const int _iterations = (int)50;

        const int randomPercent = 100;
        public static void Main(string[] args)
        {
            WarmUpJIT(new SortedList<int, string>());
            WarmUpJIT(new SplitArrayIntDictionary<string>(100));
            WarmUpJIT(new SortedDictionary<int,string>());

            for (int capacity = 2; capacity < (int)1E+4; capacity = (int) (capacity*1.5))
            {
                Test(new SortedList<int, string>(), capacity);
                Test(new SplitArrayIntDictionary<string>(capacity), capacity);
                Test(new SortedDictionary<int, string>(),capacity);
            }

        }

        static void WarmUpJIT(IDictionary<int, string> obj)
        {
            var testCase = new DictionaryRandomTestCase(100, randomPercent, 0);
            PerformanceTest.Test(
                100,
                obj,
                testCase);
        }

        static void Test(IDictionary<int, string> obj, int capacity)
        {
            var testCase = new DictionaryRandomTestCase(capacity, randomPercent, 0);
            // actual test
            var results =
                PerformanceTest.Test(
                _iterations,
                obj,
                testCase);
            System.Console.WriteLine(string.Format("Capacity={0:E1} Time={2} Type={1}", capacity, obj.GetType().Name, results.Time / (double)_iterations));
        }
    }

    class SplitArrayIntDictionary<TValue> : SplitArrayDictionary<int, TValue>
    {
        public SplitArrayIntDictionary(int capacity)
            :base(capacity)
        {

        }

        public sealed override int PrefetchKeyMSB(int key)
        {
            return key;
        }

        public sealed override int Compare(int left, int right)
        {
            if (left > right) return 1;
            if (right < left) return -1;
            return 0;

        }

        public sealed override bool LessOrEqual(int left, int right)
        {
            return (left <= right);
        }

        public sealed override bool GreaterOrEqual(int left, int right)
        {
            return (left >= right);
        }


        public sealed override bool Less(int left, int right)
        {
            return (left < right);
        }
        

        public sealed override bool Greater(int left, int right)
        {
            return (left > right);
        }

        public override bool Equal(int left, int right)
        {
            return (left == right);
        }
    }

    class TestResults
    {
        public long Time { get; private set;}
        public long Memory {get; private set;}

        public TestResults (long time, long memory)
	    {
            Time = time;
            Memory = memory;
	    }
    }

    class PerformanceTest
    {

        static public  TestResults Test<T>(int iterations,T obj, ITestCase<T> testCase)
        {
            //release all memory
            System.GC.WaitForPendingFinalizers();

            //milliseconds counter
            long totalElapsed = 0;

            //measure current memory consumption level
            //as a reference.
            System.Threading.Thread.MemoryBarrier();
            long testMemory = System.GC.GetTotalMemory(true);
            
            for (int i = 0; i < iterations; i++)
            {
                testCase.SetUp();
                Stopwatch sw = Stopwatch.StartNew();
                bool result = testCase.Test(obj);
                long elapsed = sw.ElapsedMilliseconds;
                totalElapsed += elapsed;
                if (!result)
                {
                    throw new System.InvalidProgramException("test failed.");
                }
            }//for i

            System.Threading.Thread.MemoryBarrier();
            long memory = (System.GC.GetTotalMemory(true)>>10) - (testMemory>>10);
            return new TestResults(totalElapsed, memory);
        }   

        class BlankTest<T> : ITestCase<T>
        {

            #region ITestCase<IDictionary<int,string>> Members

            public void SetUp()
            {
            }

            public bool Test(T obj)
            {
                return true;
            }

            #endregion
        }
      
    }

    interface ITestCase<T>
    {
        void SetUp();
        bool Test(T obj);
    }
 
    class DictionaryRandomTestCase : ITestCase<IDictionary<int,string>>
    {
        private readonly int[] _keys;
        private readonly string[] _values;
        private readonly int _capacity;
        private readonly int _randomPercent;
        private readonly int _randomSeed;

        public DictionaryRandomTestCase (int capacity, int randomPercent, int randomSeed)
	    {
            _capacity = capacity;
            _randomPercent = randomPercent;
            _randomSeed = randomSeed;
            _keys = new int[_capacity];
            _values = new string[_capacity];
	    }

        public void SetUp()
        {
            Debug.Assert(_keys.Length == _values.Length);
            System.Random rand = new System.Random(_randomSeed);
            for (int inc = -1, key = 0, j = 0; j < _keys.Length; j++)
            {
                if (rand.Next(100) < _randomPercent)
                {
                    inc *= -1;
                    key += inc * rand.Next(System.Int32.MaxValue);
                }
                else
                {
                    key += inc;
                }
                _keys[j] = key;
                _values[j] = "test:" + key;
            }//for j
        }

        public bool Test(IDictionary<int,string> dictionary)
        {
            dictionary.Clear();
            
            for (int j = 0; j < _capacity; j++)
            {
                string value = _values[j];
                int key = _keys[j];
                dictionary[key] = value;
                if (!dictionary.ContainsKey(key))
                {
                    throw new System.InvalidProgramException("test failed.");
                }

                dictionary[key] = value + "_";
                string valuecopy = dictionary[key];
                if (valuecopy != value + "_")
                {
                    throw new System.InvalidProgramException("test failed.");
                }
            }//for j 

            for (int j = 0; j < _capacity && dictionary.Count > 0; j++)
            {
                int count = dictionary.Count;
                int key = _keys[j];
                string value = "";
                bool success = dictionary.Remove(new System.Collections.Generic.KeyValuePair<int, string>(key, value));
                if (success)
                {
                    throw new System.InvalidProgramException("test failed.");
                }
                dictionary.TryGetValue(key, out value);                
                success = dictionary.Remove(new System.Collections.Generic.KeyValuePair<int, string>(key, value));
                if (!success || dictionary.ContainsKey(key))
                {
                    throw new System.InvalidProgramException("test failed.");
                }
                if (dictionary.Count != count - 1)
                {
                    throw new System.InvalidProgramException("test failed.");
                }                
            }//for j 

            return true;   

        }
    }

}

By viewing downloads associated with this article you agree to the Terms of Service and the article's licence.

If a file you wish to view isn't highlighted, and is a text file (not binary), please let us know and we'll add colourisation support for it.

License

This article, along with any associated source code and files, is licensed under The Code Project Open License (CPOL)

Share

About the Author

itaifrenkel
Software Developer
Israel Israel
No Biography provided

| Advertise | Privacy | Terms of Use | Mobile
Web01 | 2.8.150520.1 | Last Updated 10 Oct 2008
Article Copyright 2007 by itaifrenkel
Everything else Copyright © CodeProject, 1999-2015
Layout: fixed | fluid