Größere Zeigersprünge = mehr Zeit ... Warum?

Blubberblase

Hallo Forum!
Ich habe folgendes herausgefunden:

Code

// Algorithmus 1
for(int i = 0; i < N; i++) {
a = *p;
p += N;
}

Code

// Algorithmus 2
for(int i = 0; i < N; i++) {
a = *p;
p += B;
}

Es gilt, dass B deutlich kleiner als N ist.
Nun habe ich beobachtet, dass Algorithmus 2 schneller läuft als Algorithmus 1. Nun brauche ich noch eine "saubere" Erklärung dafür.
Mein Ansatz wäre, dass der Pointer im Algorithmus 1 ja immer einen größeren Weg zurücklegen muss um zur nächsten Speicherzelle zu kommen.
Wie könnte man das etwas "hardwarespezifischer" erklären?

Swoncen

Wenn du auf den Speicher zugreifst, wird ein gewisser Block vorbereitet. Auf den Block kannst du schneller zugreifen. Wenn der Block jetzt sagen wir 128 Byte lang ist und du 16 mal 1 Byte hintereinander ausliest, gehts natürlich schneller, als wenn du 16 mal 1 Byte in z.B.: 32 Byte Abständen ausließt, weil der Speicher danach noch nicht vorbereitet wurde.

Ringding

Es gibt viele Gründe.

1. Wenn B im Extremfall 1 ist, macht die CPU evtl. ein automatisches Prefetching, das die Sache beschleunigt.

2. Cachelinegröße: wenn dein B so klein ist, dass sich mehrere Zugriffe in einer Cache line ausgehen, dann ist das sicher deutlich schneller (cache line ist meisten 32 oder 64 Byte groß)

3. TLB misses: je größer die Sprünge sind, desto höher muss in der Pagetable-Hierarchie nach oben gegangen werden. Dadurch wird's langsamer.

4. Page faults: wenn du das erste Mal auf den Speicher zugreifst, verursacht z.B. unter Linux jeder Zugriff auf eine frische Page einen page fault. Bis der vom OS behandelt ist, vergeht einige Zeit. Der zweite Durchlauf sollte schneller sein.

Das mit dem zweiten Durchlauf gilt allerdings generell, wenn deine Datenmenge klein genug ist, um noch in die Caches zu passen. Wenn N allerdings eine 2er-Potenz ist, wird der Cache wegen Assoziativität recht schnell ausgehen.

Jetzt mitmachen!