Ich habe einen Artikel gelesen (1,5 Jahre alt)http://www.drdobbs.com/parallel/cache-friendly-code-solving-manycores-ne/240012736), die über Cache-Leistung und Datengröße spricht. Sie zeigen den folgenden Code, den sie sagen, dass sie auf einer i7 (sandigen Brücke) liefen

static volatile int array[Size];
static void test_function(void)
{
    for (int i = 0; i < Iterations; i++)
        for (int x = 0; x < Size; x++)
          array[x]++;
}

Sie behaupten, dass sie, wenn sie Size * Iterations konstant halten und Size erhöhen, wenn die Größe im Speicher des Arrays über die L2-Cache-Größe hinausgeht, einen großen Zeitanstieg für die Ausführung beobachten (10x).

Als Übung für mich selbst wollte ich dies versuchen, um zu sehen, ob ich die Ergebnisse für meine Maschine reproduzieren kann. (i7 3770k, win7, Visual C ++ 2012-Compiler, Win32-Debug-Modus, keine Optimierungen aktiviert). Zu meiner Überraschung kann ich jedoch keinen Anstieg der Ausführungszeit feststellen (auch nicht über die L3-Cache-Größe hinaus), was mich glauben ließ, dass der Compiler diesen Code irgendwie optimiert hat. Optimierungen sehe ich aber auch nicht. Die einzige Geschwindigkeitsänderung, die ich sehe, ist, dass es unterhalb der Wortgröße meiner Maschine etwas länger dauert. Im Folgenden sind meine Timings, Codelisten und die dazugehörige Demontage aufgeführt.

Weiß jemand warum:

1) Warum nimmt die benötigte Zeit unabhängig von der Größe meines Arrays überhaupt nicht zu? Oder wie könnte ich das herausfinden?

2) Warum beginnt die Zeit, die benötigt wird, hoch und nimmt dann ab, bis die Cache-Zeilengröße erreicht ist, sollten nicht mehr Iterationen verarbeitet werden, ohne aus dem Cache zu lesen, wenn die Daten kleiner als die Zeilengröße sind?

Timings:

Size=1,Iterations=1073741824, Time=3829
Size=2,Iterations=536870912, Time=2625
Size=4,Iterations=268435456, Time=2563
Size=16,Iterations=67108864, Time=2906
Size=32,Iterations=33554432, Time=3469
Size=64,Iterations=16777216, Time=3250
Size=256,Iterations=4194304, Time=3140
Size=1024,Iterations=1048576, Time=3110
Size=2048,Iterations=524288, Time=3187
Size=4096,Iterations=262144, Time=3078
Size=8192,Iterations=131072, Time=3125
Size=16384,Iterations=65536, Time=3109
Size=32768,Iterations=32768, Time=3078
Size=65536,Iterations=16384, Time=3078
Size=262144,Iterations=4096, Time=3172
Size=524288,Iterations=2048, Time=3109
Size=1048576,Iterations=1024, Time=3094
Size=2097152,Iterations=512, Time=3313
Size=4194304,Iterations=256, Time=3391
Size=8388608,Iterations=128, Time=3312
Size=33554432,Iterations=32, Time=3109
Size=134217728,Iterations=8, Time=3515
Size=536870912,Iterations=2, Time=3532

Code:

#include <string>
#include <cassert>
#include <windows.h>

template <unsigned int SIZE, unsigned int ITERATIONS>
static void test_body(volatile char* array)
{
     for (unsigned int i = 0; i < ITERATIONS; i++)
    {
        for (unsigned int  x = 0; x < SIZE; x++)
        {
            array[x]++;
        }
    }
}

template <unsigned int SIZE, unsigned int ITERATIONS>
static void test_function()
{
    assert(SIZE*ITERATIONS == 1024*1024*1024);
    static volatile char array[SIZE];

    test_body<SIZE, 1>(array); //warmup

    DWORD beginTime = GetTickCount();
    test_body<SIZE, ITERATIONS>(array); 
    DWORD endTime= GetTickCount();
    printf("Size=%u,Iterations=%u, Time=%d\n", SIZE,ITERATIONS, endTime-beginTime);
}

int main()
{
    enum { eIterations= 1024*1024*1024};
    test_function<1, eIterations>();
    test_function<2, eIterations/2>();
    test_function<4, eIterations/4>();
    test_function<16, eIterations/16>();
    test_function<32, eIterations/ 32>();
    test_function<64, eIterations/ 64>();
    test_function<256, eIterations/ 256>();
    test_function<1024, eIterations/ 1024>();
    test_function<2048, eIterations/ 2048>();
    test_function<4096, eIterations/ 4096>();
    test_function<8192, eIterations/ 8192>();
    test_function<16384, eIterations/ 16384>();
    test_function<32768, eIterations/ 32768>();
    test_function<65536, eIterations/ 65536>();
    test_function<262144, eIterations/ 262144>();
    test_function<524288, eIterations/ 524288>();
    test_function<1048576, eIterations/ 1048576>();
    test_function<2097152, eIterations/ 2097152>();
    test_function<4194304, eIterations/ 4194304>();
    test_function<8388608, eIterations/ 8388608>();
    test_function<33554432, eIterations/ 33554432>();
    test_function<134217728, eIterations/ 134217728>();
    test_function<536870912, eIterations/ 536870912>();
}

Demontage

    for (unsigned int i = 0; i < ITERATIONS; i++)
00281A59  mov         dword ptr [ebp-4],0  
00281A60  jmp         test_body<536870912,2>+1Bh (0281A6Bh)  
00281A62  mov         eax,dword ptr [ebp-4]  
00281A65  add         eax,1  
00281A68  mov         dword ptr [ebp-4],eax  
00281A6B  cmp         dword ptr [ebp-4],2  
00281A6F  jae         test_body<536870912,2>+53h (0281AA3h)  
    {
        for (unsigned int  x = 0; x < SIZE; x++)
00281A71  mov         dword ptr [ebp-8],0  
00281A78  jmp         test_body<536870912,2>+33h (0281A83h)  
00281A7A  mov         eax,dword ptr [ebp-8]  
    {
        for (unsigned int  x = 0; x < SIZE; x++)
00281A7D  add         eax,1  
00281A80  mov         dword ptr [ebp-8],eax  
00281A83  cmp         dword ptr [ebp-8],20000000h  
00281A8A  jae         test_body<536870912,2>+51h (0281AA1h)  
        {
            array[x]++;
00281A8C  mov         eax,dword ptr [array]  
00281A8F  add         eax,dword ptr [ebp-8]  
00281A92  mov         cl,byte ptr [eax]  
00281A94  add         cl,1  
00281A97  mov         edx,dword ptr [array]  
00281A9A  add         edx,dword ptr [ebp-8]  
00281A9D  mov         byte ptr [edx],cl  
        }
00281A9F  jmp         test_body<536870912,2>+2Ah (0281A7Ah)  
    }
00281AA1  jmp         test_body<536870912,2>+12h (0281A62h)