Sequential Structure Layout For Speed

We are going to declare a Matrix which is used to house a Set.. Explicitly.  Just by putting the iteration value in the middle of the sequence you can speed up that example code by a factor of 36% !.. and that is just by adjusting the location of data in the memory....

The code below highlights the differences (there was a nice table here to show the differences... but it has been improved to be actual code (not it's intent, so I edited it out :( ) Nearly Full code is given below.


The thing to notice is that position of the class member i is in different places.. the reason this is so useful is that it highlights quite nicely the effect of cache misses... a quick look at the Compiler choice classes will show you where the differences are...

And Here are the results from adding i to the matrix elements... (this was individually timed inside of a for loop  200 times, then a simple average was taken)... Total savings 0.0175 seconds! This was pitted against the CLR and CLR results are somewhere in between (as would be expected).

--Upgraded From My Blog.... :laugh:


Here is the Running code, The CompilerChoice classes are CLR layout comparisons (results not shown)

[StructLayout(LayoutKind.Explicit)]
public class PoorChoice
{
    [FieldOffset(0)]
    public int i;
    [FieldOffset(4)]
    public int m00;
    [FieldOffset(8)]
    public int m01;
    [FieldOffset(16)]
    public int m02;
    [FieldOffset(20)]
    public int m03;
    [FieldOffset(24)]
    public int m10;
    [FieldOffset(28)]
    public int m11;
    [FieldOffset(32)]
    public int m12;
    [FieldOffset(36)]
    public int m13;
    [FieldOffset(40)]
    public int m20;
    [FieldOffset(44)]
    public int m21;
    [FieldOffset(48)]
    public int m22;
    [FieldOffset(52)]
    public int m23;
    [FieldOffset(56)]
    public int m30;
    [FieldOffset(60)]
    public int m31;
    [FieldOffset(64)]
    public int m32;
    [FieldOffset(68)]
    public int m33;
}

[StructLayout(LayoutKind.Explicit)]
public class GreatChoice
{
    [FieldOffset(0)]
    public int m00;
    [FieldOffset(4)]
    public int m01;
    [FieldOffset(8)]
    public int m02;
    [FieldOffset(12)]
    public int m03;
    [FieldOffset(16)]
    public int m10;
    [FieldOffset(20)]
    public int m11;
    [FieldOffset(24)]
    public int m12;
    [FieldOffset(28)]
    public int m13;
    [FieldOffset(32)]
    public byte i;
    [FieldOffset(33)]
    public int m20;
    [FieldOffset(37)]
    public int m21;
    [FieldOffset(41)]
    public int m22;
    [FieldOffset(45)]
    public int m23;
    [FieldOffset(49)]
    public int m30;
    [FieldOffset(53)]
    public int m31;
    [FieldOffset(57)]
    public int m32;
    [FieldOffset(61)]
    public int m33;
}

public class CompilerChoice1
{
    public int i;
    public int m00;
    public int m01;
    public int m02;
    public int m03;
    public int m10;
    public int m11;
    public int m12;
    public int m13;
    public int m20;
    public int m21;
    public int m22;
    public int m23;
    public int m30;
    public int m31;
    public int m32;
    public int m33;
}

public class CompilerChoice2
{
    public int m00;
    public int m01;
    public int m02;
    public int m03;
    public int m10;
    public int m11;
    public int m12;
    public int m13;
    public byte i;
    public int m20;
    public int m21;
    public int m22;
    public int m23;
    public int m30;
    public int m31;
    public int m32;
    public int m33;
}
    public GreatLayoutTest(System.Windows.Forms.Label label)
    {
        Console.WriteLine("the Size of Poor Choice is:" + System.Runtime.InteropServices.Marshal.SizeOf(typeof(PoorChoice)).ToString());
        Console.WriteLine("the Size of Great Choice is:" + System.Runtime.InteropServices.Marshal.SizeOf(typeof(GreatChoice)).ToString());
        //Type 'ThreadingBestPractices.CompilerChoice1' cannot be marshaled as an unmanaged structure; no meaningful size or offset can be computed."
        //Console.WriteLine("the Size of Compiler Choice 1 is:" + System.Runtime.InteropServices.Marshal.SizeOf(typeof(CompilerChoice1)).ToString());
        //Type 'ThreadingBestPractices.CompilerChoice1' cannot be marshaled as an unmanaged structure; no meaningful size or offset can be computed."
        //Console.WriteLine("the Size of Compiler Choice 2 is:" + System.Runtime.InteropServices.Marshal.SizeOf(typeof(CompilerChoice2)).ToString());
        List<double[]> ControlResults = new List<double[]>();
        PoorLayout pl = new PoorLayout();
        label.Text = pl.Test();
        TimeSpan[] ts = new TimeSpan[2];
        DateTime[] ts_start = new DateTime[2];
        double[] duration = new double[4];

        PoorChoice poor = new PoorChoice();
        GreatChoice great = new GreatChoice();
        CompilerChoice1 clr1 = new CompilerChoice1();
        CompilerChoice2 clr2 = new CompilerChoice2();

        for (int i = 0; i < 200; i++)
        {
            label.Text = (200 - i).ToString(); label.Refresh();
            #region Poor
            Stopwatch sw = Stopwatch.StartNew();
            poor.m00 += poor.i;
            poor.i++;
            poor.m01 += poor.i;
            poor.i++;
            poor.m02 += poor.i;
            poor.i++;
            poor.m03 += poor.i;
            poor.i++;
            poor.m10 += poor.i;
            poor.i++;
            poor.m11 += poor.i;
            poor.i++;
            poor.m12 += poor.i;
            poor.i++;
            poor.m13 += poor.i;
            poor.i++;
            poor.m20 += poor.i;
            poor.i++;
            poor.m21 += poor.i;
            poor.i++;
            poor.m22 += poor.i;
            poor.i++;
            poor.m23 += poor.i;
            poor.i++;
            poor.m30 += poor.i;
            poor.i++;
            poor.m31 += poor.i;
            poor.i++;
            poor.m32 += poor.i;
            poor.i++;
            poor.m33 += poor.i;
            poor.i++;
            duration[0] = sw.Elapsed.TotalMilliseconds;
            #endregion

            #region great
            sw = Stopwatch.StartNew();
            great.m00 += great.i;
            great.i++;
            great.m01 += great.i;
            great.i++;
            great.m02 += great.i;
            great.i++;
            great.m03 += great.i;
            great.i++;
            great.m10 += great.i;
            great.i++;
            great.m11 += great.i;
            great.i++;
            great.m12 += great.i;
            great.i++;
            great.m13 += great.i;
            great.i++;
            great.m20 += great.i;
            great.i++;
            great.m21 += great.i;
            great.i++;
            great.m22 += great.i;
            great.i++;
            great.m23 += great.i;
            great.i++;
            great.m30 += great.i;
            great.i++;
            great.m31 += great.i;
            great.i++;
            great.m32 += great.i;
            great.i++;
            great.m33 += great.i;
            great.i++;
            duration[1] = sw.Elapsed.TotalMilliseconds;
            #endregion

            #region Compiler1
            sw = Stopwatch.StartNew();
            clr1.m00 += clr1.i;
            clr1.i++;
            clr1.m01 += clr1.i;
            clr1.i++;
            clr1.m02 += clr1.i;
            clr1.i++;
            clr1.m03 += clr1.i;
            clr1.i++;
            clr1.m10 += clr1.i;
            clr1.i++;
            clr1.m11 += clr1.i;
            clr1.i++;
            clr1.m12 += clr1.i;
            clr1.i++;
            clr1.m13 += clr1.i;
            clr1.i++;
            clr1.m20 += clr1.i;
            clr1.i++;
            clr1.m21 += clr1.i;
            clr1.i++;
            clr1.m22 += clr1.i;
            clr1.i++;
            clr1.m23 += clr1.i;
            clr1.i++;
            clr1.m30 += clr1.i;
            clr1.i++;
            clr1.m31 += clr1.i;
            clr1.i++;
            clr1.m32 += clr1.i;
            clr1.i++;
            clr1.m33 += clr1.i;
            clr1.i++;
            duration[2] = sw.Elapsed.TotalMilliseconds;
            #endregion

            #region Compiler2
            sw = Stopwatch.StartNew();
            clr2.m00 += clr2.i;
            clr2.i++;
            clr2.m01 += clr2.i;
            clr2.i++;
            clr2.m02 += clr2.i;
            clr2.i++;
            clr2.m03 += clr2.i;
            clr2.i++;
            clr2.m10 += clr2.i;
            clr2.i++;
            clr2.m11 += clr2.i;
            clr2.i++;
            clr2.m12 += clr2.i;
            clr2.i++;
            clr2.m13 += clr2.i;
            clr2.i++;
            clr2.m20 += clr2.i;
            clr2.i++;
            clr2.m21 += clr2.i;
            clr2.i++;
            clr2.m22 += clr2.i;
            clr2.i++;
            clr2.m23 += clr2.i;
            clr2.i++;
            clr2.m30 += clr2.i;
            clr2.i++;
            clr2.m31 += clr2.i;
            clr2.i++;
            clr2.m32 += clr2.i;
            clr2.i++;
            clr2.m33 += clr2.i;
            clr2.i++;
            duration[3] = sw.Elapsed.TotalMilliseconds;
            #endregion
            results.Add(new double[] {
                duration[0],
                duration[1],
                duration[2],
                duration[3]});
        }
        IO.WriteOut("GreatLayoutTest.txt", results);
        label.Text = "Done";
    }