Click here to Skip to main content
Click here to Skip to main content
Add your own
alternative version

Squeezing more performance from SortedList

, 10 Oct 2008 CPOL
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
// TODO check replacing % with &8-1,16-1,32-1,etc...
// TODO Make the wrapper class call the fastest BinarySearch implementation
// TODO Make the wrapper class convert int 2 uint for better performance
using System.Collections.Generic;
using System.Diagnostics;
using System;
namespace SplitArrayDictionary
{
    public class CyclicArrayBase<TKey,TValue>
{
    // the array containing the keys
    readonly TKey[] nodeKeys;
    readonly TValue[] nodeValues;
    readonly int[] nodeKeyMSB;
    protected readonly static bool TKeyIsInteger = (typeof(TKey).TypeHandle.Equals(typeof(System.Int32).TypeHandle));

    private readonly int lastIndex;
    protected int LastIndex { get { return lastIndex; } }

    protected void Clear()
    {
        Array.Clear(nodeKeys    , 0, LastIndex);
        Array.Clear(nodeValues  , 0, LastIndex);
        if (!TKeyIsInteger)
        {
            Array.Clear(nodeKeyMSB, 0, LastIndex);
        }        
    }

    /// <summary>
    /// Creates a new instance of CyclicArrayBase
    /// </summary>
    /// <param name="log2Capacity">the log base 2 of the maximum capacity of the array.</param>
    protected CyclicArrayBase(int log2Capacity)
    {

        lastIndex = (1 << log2Capacity)-1;// =2^log2capacity-1
        nodeKeys   = new TKey[LastIndex+1];
        nodeValues = new TValue[LastIndex+1];
        if (TKeyIsInteger)
        {
            nodeKeyMSB = (int[])(object)nodeKeys;
        }
        else
        {
            nodeKeyMSB = new int[LastIndex+1];
        }
    }

    protected int GetSortingPrefetch(int index)
    {
        return nodeKeyMSB[index];
    }

    protected TValue GetValue(int index)
    {
        return nodeValues[index];
    }

    public TKey GetKey(int index)
    {
        return nodeKeys[index];
    }


    // increase index by one
    /* [inline] */
    protected int CyclicInc(int index)
    {
        return CyclicAdd(index, 1);
    }

    // increase index by one
    /* [inline] */
    protected int CyclicSub(int index, int dec)
    {
        Debug.Assert(dec >= 0);
        Debug.Assert(dec <= this.LastIndex+1);
        return CyclicAdd(index, this.LastIndex+1 - dec);
    }

    // decrease index by one
    /* [inline] */
    protected int CyclicDec(int index)
    {
        return CyclicSub(index, 1);
    }

    // increase index by "increase"
    /* [inline] */
    protected int CyclicAdd(int index, int increase)
    {
        Debug.Assert(increase >= 0);
        //return (index + increase) % this.Capacity;
        // if lastIndex = 2^3-1 = 7 = 00000111
        return (index + increase) & this.LastIndex;
    }        

    /* [inline] */
    protected void Insert(TKey key, TValue value, int hint, int index)
    {
        nodeKeys[index] = key;
        nodeValues[index] = value;
        if (!TKeyIsInteger)
        {
            nodeKeyMSB[index] = hint;
        }
    }


    protected void CyclicArrayCopy(int source, int destination, int length)
    {
        Debug.Assert(source != destination);        
        Debug.Assert(length > 0);
        Debug.Assert(source >= 0);
        Debug.Assert(destination >= 0);
        Debug.Assert(source <= LastIndex);
        Debug.Assert(destination <= LastIndex);
        // the following assert makes sure we do not require
        // an auxillary memory.
        bool shiftLeft = CyclicSub(destination,source) >= CyclicSub(source,destination);
        bool shiftRight = CyclicSub(destination,source) <= CyclicSub(source,destination);
        Debug.Assert(shiftRight || (shiftLeft  && (CyclicSub(source,destination) + (length-1)<=LastIndex)));
        Debug.Assert(shiftLeft  || (shiftRight && (CyclicSub(destination,source) + (length-1)<=LastIndex)));
        
        int srcEndIndex = CyclicAdd(source, length-1);
        int dstEndIndex = CyclicAdd(destination, length-1);
        if (destination <= dstEndIndex )      
        {
            if (source <= srcEndIndex)
            {
                // 00abcd00 --> 0000abcd
                ArrayCopy(source, destination, length);
                return;
            }

            Debug.Assert(source > srcEndIndex);
            Debug.Assert(destination + length-1 == dstEndIndex);
            Debug.Assert(source + length-1 - LastIndex-1 == srcEndIndex);     
                        
            int length1 = LastIndex+1-source;
            
            if (destination > srcEndIndex)
            {
                // cd000ab --> 00abcd0
                // cd000ab --> 000abcd                                

                #region proof
                // if condition
                Debug.Assert(destination > srcEndIndex);
                Debug.Assert(destination > source+length-1-LastIndex-1);
                Debug.Assert(destination > 0+length-length1-1);
                #endregion

                ArrayCopy(source, destination, length1);
                ArrayCopy(0, destination + length1, length - length1);
                return;
            }
            
            // cd000ab --> abcd000
            // cd000ab --> 0abcd00
            Debug.Assert(destination <= srcEndIndex);
            //split assumptions
            Debug.Assert(destination < source); // follows since src is split and dst is not
            
            // shiftright assumption
            Debug.Assert(shiftRight);
            Debug.Assert(CyclicSub(destination,source) + (length-1)<=LastIndex);
            
            // split+shiftright assumptions
            Debug.Assert(destination-source+LastIndex+1 + (length-1)<=LastIndex);
            Debug.Assert(destination-source + (length-1)<0);
            Debug.Assert(destination + (length-1) < source);
            Debug.Assert(destination + length1 + (length-length1)-1 < source);
            // concludes the proof that the first ArrayCopy destination
            // will not overwrite the source of the second ArrayCopy
            ArrayCopy(0, destination + length1, length - length1);
            ArrayCopy(source, destination, length1);
            return;
        }

        Debug.Assert(destination >= dstEndIndex);
        
        if (source <= srcEndIndex)
        {
            
            int length2 = LastIndex+1 - destination;
            if (source > dstEndIndex)
            {                                
                // 00abcd0 --> cd000ab
                // 000abcd --> cd000ab
                
                Debug.Assert(source > dstEndIndex); //if assumption
                Debug.Assert(source > destination + length-1 - LastIndex-1);
                Debug.Assert(source > length-1 - (LastIndex+1 - destination));
                Debug.Assert(source > 0 + length-1 - length2);
                // concludes the proof that the first ArrayCopy destination
                // will not overwrite the source of the second ArrayCopy

                ArrayCopy(source + length2, 0, length - length2);                
                ArrayCopy(source, destination, length2);                
                return;
            }

            // abcd000 --> cd000ab
            // 0abcd00 --> cd000ab
            
            //shift left assumption
            Debug.Assert(source <= dstEndIndex); // !if
            Debug.Assert(shiftLeft); // !if condition equivalent            
            Debug.Assert(CyclicSub(source,destination) + (length-1)<=LastIndex);

            //dst is split and src is not split assumption
            Debug.Assert(source < destination);

            //shift + split assumptions together
            Debug.Assert((source - destination+LastIndex+1) + (length-1)<=LastIndex);
            Debug.Assert((source - destination) + (length - 1) < 0);
            Debug.Assert((source) + (length - 1) < destination);
            Debug.Assert(srcEndIndex < destination);
            
            ArrayCopy(source, destination, length2);  
            ArrayCopy(source + length2, 0, length - length2);
            return;
        }

        Debug.Assert(destination > dstEndIndex);
        Debug.Assert(source > srcEndIndex);
        
        if (destination > source)
        {
            // d000abc --> bcd000a
            
            int length3 = LastIndex+1 - destination;
            int shift = destination - source;

            #region proof
            Debug.Assert(length3 > 0);
            Debug.Assert(shift > 0);

            // if condition
            Debug.Assert(destination > source);
            
            //Shift Right assumption
            Debug.Assert(shiftRight);
            Debug.Assert(CyclicSub(destination, source) + (length - 1) <= LastIndex);
            Debug.Assert(shift + (length - 1) <= LastIndex);
                     
            // applying if condition
            Debug.Assert(destination - source + (length - 1) <= LastIndex);
            Debug.Assert(destination + (length-1) - LastIndex-1  < source);
            Debug.Assert(dstEndIndex < source);
            Debug.Assert(shift + srcEndIndex < source);
            //completes the proof that the first arraycopy does not overwritre the third one                      
            #endregion
            
            ArrayCopy(0, shift, srcEndIndex+1); 
            ArrayCopy(LastIndex+1 - shift, 0, shift);                        
            ArrayCopy(source, destination,length3);
            return;
        }
        
        // bcd000a --> d000abc
        #region proof 
        Debug.Assert(destination < source);
        int length5 = LastIndex+1 - source;
        int shift_ = source - destination;
        Debug.Assert(shiftLeft);        
        Debug.Assert(shift_ + (length - 1) <= LastIndex);
        Debug.Assert((source - destination) + (length - 1) <= LastIndex);
        
        //given definition of srcEndIndex = srcBeginIndex+(length-1)-Capacity
        Debug.Assert(srcEndIndex - destination  <0);
        Debug.Assert(destination > srcEndIndex);
        // concludes the proof
#endregion

        ArrayCopy(source, destination, length5);
        ArrayCopy(0, LastIndex+1 - shift_, shift_);
        ArrayCopy(shift_, 0, srcEndIndex+1);
    }

    /*inline*/
    protected void ArrayCopy(int source, int destination, int length)
    {
        System.Array.Copy(nodeKeys, source,
                   nodeKeys, destination,
                   length);

        System.Array.Copy(nodeValues, source,
                   nodeValues, destination,
                   length);

        if (!TKeyIsInteger)
        {
            Debug.Assert(!nodeKeys.Equals(nodeKeyMSB));
            System.Array.Copy(nodeKeyMSB, source,
                   nodeKeyMSB, destination,
                   length);
        }
        else
        {
            Debug.Assert(nodeKeyMSB.Equals(nodeKeys));
        }
    }


  }//class

}//namespace

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
Web03 | 2.8.150301.1 | Last Updated 10 Oct 2008
Article Copyright 2007 by itaifrenkel
Everything else Copyright © CodeProject, 1999-2015
Layout: fixed | fluid