Do C# collections care about cache friendlyness?

Question

I've been running a lot of tests comparing an array of structs with an array of classes and a list of classes. Here's the test I've been running:

struct AStruct {
    public int val;
}
class AClass {
    public int val;
}

static void TestCacheCoherence() 
{
    int num = 10000;
    int iterations = 1000;
    int padding = 64;

    List<Object> paddingL = new List<Object>();

    AStruct[] structArray = new AStruct[num];
    AClass[] classArray = new AClass[num];
    List<AClass> classList = new List<AClass>();

    for(int i=0;i<num;i++){
        classArray[i] = new AClass();
        if(padding >0) paddingL.Add(new byte[padding]);
    }
    for (int i = 0; i < num; i++)
    {
        classList.Add(new AClass());
        if (padding > 0) paddingL.Add(new byte[padding]);
    }

    Console.WriteLine("\n");
    stopwatch("StructArray", iterations, () =>
    {
        for (int i = 0; i < num; i++)
        {
            structArray[i].val *= 3;
        }
    });
    stopwatch("ClassArray ", iterations, () =>
    {
        for (int i = 0; i < num; i++)
        {
            classArray[i].val *= 3;
        }
    });
    stopwatch("ClassList  ", iterations, () =>
    {
        for (int i = 0; i < num; i++)
        {
            classList[i].val *= 3;
        }
    });

}

static Stopwatch watch = new Stopwatch();

public static long stopwatch(string msg, int iterations, Action c)
{
    watch.Restart();
    for (int i = 0; i < iterations; i++)
    {
        c();
    }
    watch.Stop();

    Console.WriteLine(msg +":  " + watch.ElapsedTicks);
    return watch.ElapsedTicks;
}

I'm running this in release mode with the following:

 Process.GetCurrentProcess().ProcessorAffinity = new IntPtr(2); // Use only the second core 
 Process.GetCurrentProcess().PriorityClass = ProcessPriorityClass.High;
 Thread.CurrentThread.Priority = ThreadPriority.Highest;

RESULTS:

With padding=0 I get:

StructArray: 21517
ClassArray:  42637
ClassList:   80679

With padding=64 I get:

 StructArray: 21871
 ClassArray:  82139
 ClassList:   105309

With padding=128 I get:

 StructArray: 21694
 ClassArray:  76455
 ClassList:   107330

I am a bit confused with these results, since I was expecting the difference to be bigger. After all the structures are tiny and are laid one after the other in memory, while the classes are separated by up to 128 bytes of garbage.

Does this mean that I shouldn't even worry about cache friendlyness? Or is my test flawed?

Well, most modern processors have pretty darn big caches. I wouldn't be all that surprised if your entire program fit into your L2 cache. — Servy, Aug 28 '12 at 20:06
By *cache coherence* do you mean the coherence of memory values across different CPU caches? And what type of CPU are you talking about x86/x64? — Peter Ritchie, Aug 28 '12 at 20:08
I think I should have just said "cache friendlyness", I'll edit. — Alejandro Guillen, Aug 28 '12 at 20:49
The garbage collector compacting the heap is a crucial feature. Puts everything nicely back together. — Hans Passant, Aug 28 '12 at 22:24
@HansPassant That's exactly what I am wondering... Does the GC try to put elements belonging to the same array back together? — Alejandro Guillen, Aug 28 '12 at 22:31

score 1 · Answer 1 · answered Aug 28 '12 at 19:53

1

There are a number of things going on here. The first is that your tests don't take GC's into account- it is distinctly possible that the arrays are being GC'd during the loop over the list (because the arrays are no longer used while you are iterating the list, they are eligible for collection).

The second is that you need to keep in mind that List<T> is backed by an array anyway. The only reading overhead is the additional function calls to go through List.

answered Aug 28 '12 at 19:53

Chris Shain

50,833
6
93
125

+1 for garbage collector problem. calling GC.Collect(); then GC.WaitForPendingFinalizers(); between benchmarks should help (WaitForPendingFinalizers() call is to make sure everything is done before benchmarking since GC operation is not necessarily blocking). if you really want to be sure it doesn't affect results, compile and run three different version of the program separately. – tigrou Aug 28 '12 at 20:28
@tigrou I added the GC calls, results are the same though. – Alejandro Guillen Aug 28 '12 at 22:38

Do C# collections care about cache friendlyness?

1 Answers1