PDA

Archiv verlassen und diese Seite im Standarddesign anzeigen : array/speicherzugriff: was ist schneller


Gast
2004-01-25, 13:00:23
Variante 1:
2 Arrays a1, a2
die Zugriffsweise ist so:for(size_t i=0; i<x; ++i) {
a1[i]
a2[i]
}

Variante 2:
1 Array, enthält abwechselnd a1 und a2:for(size_t i=0; i<x; ++i) {
a[2*i]
a[2*i+1]
}


die Arrays enthalten int's.

Gnafoo
2004-01-25, 13:02:28
Ich denke von der Geschwindigkeit gibt sich da nichts. Nimm das,
was logischer / besser strukturiert ist.

cu DerTod

zeckensack
2004-01-25, 13:14:42
Variante 2, wenn du überwiegend beide Elemente gleichzeitig benutzt.
Variante 1, wenn du überwiegend nur eins der Elemente benutzt.

Data prefetch ahoi.

Gast
2004-01-25, 13:57:06
Original geschrieben von zeckensack
Variante 2, wenn du überwiegend beide Elemente gleichzeitig benutzt.Was heißt "gleichzeitig"?

Genauer ist meine Schleife so:
for(size_t i=0; i<x; ++i) {
bearbeite a1[i], unabhängig von a2[i]
if (a1[i] == a2[i])
continue;
bearbeite a2[i], unabhängig von a1[i]
}

Magnum
2004-01-25, 14:56:46
Original geschrieben von Gast
Was heißt "gleichzeitig"?

Genauer ist meine Schleife so:
for(size_t i=0; i<x; ++i) {
bearbeite a1[i], unabhängig von a2[i]
if (a1[i] == a2[i])
continue;
bearbeite a2[i], unabhängig von a1[i]
}
Ich würde hier die Variante mit einem Array bevorzugen! Wenn du nacheinander auf a[i] und a[i+1] zugreifst kannst du deinen Cache ausnutzen!
(das ganze dürfte sich aber nach einer entsprechenden Compiler-Optimierung nicht viel geben!)

zeckensack
2004-01-25, 17:55:22
Original geschrieben von Gast
Was heißt "gleichzeitig"?

Genauer ist meine Schleife so:
for(size_t i=0; i<x; ++i) {
bearbeite a1[x], unabhängig von a2[x]
if (a1[x] == a2[x])
continue;
bearbeite a2[x], unabhängig von a1[x]
} "Gleichzeitig" sollte heissen, dass du auf beide Werte im gleichen Schleifendurchlauf lesend und/oder schreibend zugreifst. In deinem Beispiel scheint das der Fall zu sein.

Zum Mitdenken:
Wenn a1[x] nicht im Cache ist, muss eine komplette Cacheline aus dem Speicher eingelesen werden. Da a2[x] definitiv kurze Zeit später auch benötigt wird, kann es nicht schaden, diesen Wert auch schon in den Cache zu holen. Indem man die beiden Arrays ineinander verschachtelt, erfolgt dies ganz automatisch.

Wären die Arrays getrennt, bestünde das Risiko pro Schleifendurchlauf zweimal auf den Hauptspeicher zugreifen zu müssen. Das ist an sich nicht wirklich wild, weil der Bandbreitenverbrauch insgesamt gleich ist. Zwei Gründe sprechen trotzdem dagegen:
a)ein cache miss bedeutet neben dem Bandbreitenverbrauch auch immer ein schlechtere Zugriffslatenz für den ersten Wert, der aus der neuen Cacheline gebraucht wird. Diese 'Strafe' nur einmal zahlen zu müssen, kann sich auszahlen.

b)aktuelle Prozessoren haben Hardware prefetch, dh sie 'raten' bei bestimmten Zugriffsmustern, welche Daten in Kürze gebraucht werden, und laden diese schonmal auf Verdacht in den Cache. Diese Technik kann aber idR nur mit einer begrenzten Anzahl von gleichzeitigen 'Streams' umgehen. Auch sollte das Zugriffsmuster möglichst einfach sein (linear ansteigende Adressen), damit es überhaupt erkannt werden kann. Beide Unterpunkte sprechen für ein verschachteltes Array.

____________

Wird dagegen a2[x] nicht garantiert benutzt, so wirkt es bei verschachtelten Arrays wie unnötiger Ballast. Es wird Bandbreite verbraucht, erzeugt aber keinen Mehrnutzen.

PS: ich habe i durch x ersetzt, weil das Board sonst italics draus macht.
PPS: http://www.namesys.com/v4/v4.html#cache_design

GloomY
2004-01-25, 20:25:58
Das ist das Prinzip der räumlichen Lokalität der Daten eines Caches, welches man hier ausnutzt. Dadurch dass die Daten von a1 und a2 in der zweiten Variante "hintereinander" im Speicher liegen, werden diese auch zusammen in eine Cache Line geladen. Der Zugriff auf ein Element von a1 (und das Laden dieses in den Cache) sichert damit, dass das nachfolgende Element von a2 auch im Cache drin ist.
Bei zwei unterschiedlichen Arrays (Variante 1) hat der Zugriff auf a1 keinerlei Auswirkungen, ob sich a2 auch im Cache befindet.

Gast
2004-01-26, 16:43:33
Danke!