2012-04-08 10 views
-1

den folgenden Code Gegeben:Cache-Miss? Wie kann ich das sehen?

for (int i=0; i<n; i++) 
{ 
    counter += myArray[i]; 
} 

und die Schleife Abrollen Version:

for (int i=0; i<n; i+=4) 
{ 
    counter1 += myArray[i+0]; 
    counter2 += myArray[i+1]; 
    counter3 += myArray[i+2]; 
    counter4 += myArray[i+3]; 
} 

total = counter1+ counter2 + counter3+ counter4; 
  1. Warum wir eine Cache-Miss in der ersten Version haben?
  2. Hat die zweite Version tatsächlich eine bessere Leistung als die erste? Warum ?

Grüße

+3

Was machen Sie denken, dass es eine Cache-Miss in der ersten Version ist? – templatetypedef

+0

Ich bin nicht sicher, dass es eine große Differenz sein wird ... –

+0

Riecht wie Hausaufgaben zu viel ... – m0skit0

Antwort

4

Warum haben wir eine Cache-Miss in der ersten Version?

Wie Oli in den Kommentaren darauf hinweist. Diese Frage ist unbegründet. Wenn sich die Daten bereits im Cache befinden, werden keine Cache-Fehler gemeldet.

Abgesehen davon gibt es keinen Unterschied im Speicherzugriff zwischen Ihren beiden Beispielen. Das wird wahrscheinlich keinen Unterschied zwischen ihnen ausmachen.

Hat die zweite Version tatsächlich eine bessere Leistung als die erste? Warum ?

Normalerweise ist die Sache zu tun, tatsächlich zu messen. Aber in diesem speziellen Beispiel würde ich sagen, dass es wahrscheinlich schneller sein wird. Nicht wegen des besseren Cache-Zugriffs, sondern wegen des Loop-entrollings.

Die von Ihnen durchgeführte Optimierung wird "Node-Splitting" genannt, wobei Sie die counter Variable trennen, um die Abhängigkeitskette zu durchbrechen.

In diesem Fall führen Sie jedoch eine einfache Reduktion durch. Viele moderne Compiler sind in der Lage, dieses Muster zu erkennen und dieses Knotensplitting für Sie durchzuführen.

So ist es schneller? Höchstwahrscheinlich. Aber Sie sollten überprüfen, ob der Compiler es für Sie tut.


Für das Protokoll: ich dies nur 2010
auf Visual Studio getestet und ich bin ziemlich überrascht, dass es nicht in der Lage ist diese Optimierung zu tun.

; 129 : 
; 130 :  int counter = 0; 
; 131 : 
; 132 :  for (int i=0; i<n; i++) 
    mov ecx, DWORD PTR n$[rsp] 
    xor edx, edx 
    test ecx, ecx 
    jle SHORT [email protected] 
[email protected]: 

; 133 :  { 
; 134 :   counter += myArray[i]; 

    add edx, DWORD PTR [rax] 
    add rax, 4 
    dec rcx 
    jne SHORT [email protected] 
[email protected]: 

; 135 :  } 

Visual Studio 2010 scheint nicht für dieses (triviales) Beispiel für die Durchführung "Node Splitting" in der Lage zu sein ...

Verwandte Themen