Pointerarithmetik vs. Direktzugriff

\LaTeX

Hallo Leute..

Mich interessiert, welche Methode effizienter (im Sinne der Geschwindigkeit) ist. Die Methode mit dem Direktzugriff:

Code

#define INDEX(x,y,z) (z*xdim*ydim + y*xdim + x)
unsigned int my_array = new unsigned int[xdim*ydim*zdim];
...
unsigned int cur_a=0;


for (int z=0; z<zdim; z++)
{
  for (int y=0; y<ydim; y++)
  {
    for (int x=0; x<xdim; x++)
    {
      cur_a = my_array[INDEX(x,y,z)];
      ...
      // Zugriff auf die 26 Nachbarn des Elementes an der Position x,y,z
      if (my_array[INDEX(x-1,y-1,z-1)] < cur_a) // Nachbar: 01
      {
        ...
      }
      ...
      if (my_array[INDEX(x+1,y+1,z+1)] < cur_a) // Nachbar: 26
      {
        ...
      }
      ...
    }
  }
}

Alles anzeigen

... oder die mit Pointerarithmetik:

Code

...
unsigned int my_array = new unsigned int[xdim*ydim*zdim];
unsigned int *cur_a=0;


// nur 9 Verweise auf die Nachbarn (die restlichen Nachbarn
// werden mittels Pointerarithmetik ermittelt)
unsinged int *a01=0;
unsinged int *a02=0;
unsinged int *a03=0;
...
unsinged int *a09=0;


for (int z=0; z<zdim; z++)
{
  for (int y=0; y<ydim; y++)
  {
    cur_a = &my_array[INDEX(x,y,z)];
    ...
    // Zugriff auf die 9 Nachbarn des Elementes an der Position x,y,z
    a01 = &my_array[INDEX(x-1,y-1,z-1)];
    ...
    a09 = &my_array[INDEX(x+1,y+1,z+1)];


    for (int x=0; x<xdim; x++)
    {
      ...
      if (*(a01+x) < cur_a) // Nachbar: 01
      {
        ...
      }
      if (*(a01+x+1) < cur_a) // Nachbar: 02
      {
        ...
      }
      if (*(a01+x+2) < cur_a) // Nachbar: 03
      {
        ...
      }
      ...
      if (*(a02+x) < cur_a) // Nachbar: 04
      {
        ...
      }
      if (*(a02+x+1) < cur_a) // Nachbar: 05
      {
        ...
      }
      if (*(a02+x+2) < cur_a) // Nachbar: 06
      {
        ...
      }
      ...
      ...
      if (*(a09+x) < cur_a) // Nachbar: 24
      {
        ...
      }
      if (*(a09+x+1) < cur_a) // Nachbar: 25
      {
        ...
      }
      if (*(a09+x+2) < cur_a) // Nachbar: 26
      {
        ...
      }
    }
  }
}

Alles anzeigen

D.h. die konkrete Frage, die ich mir hier stelle ist, ob "if (*(a+x+1) < cur_a)" teurer ist als "if (my_array[z*xdim*ydim + y*xdim + x] < cur_a)"? Also auf der einen Seite [Zwei Additionen und ein Derefenzieren] und auf der anderen Seite [3 Multiplikationen und zwei Additionen]. Oder anders ausgedrueckt: dauert das Dereferenzieren eines Pointers laenger als wenn man 3 uint Werte multipliziert (wenn man die Ermittlung des Pointers a mal auszer Acht laeszt)?

Koennt ihr mir eine Empfehlung geben, ohne, dass ich's jetzt selber testen muss?

Danke im Voraus,
ciao..

Shine

also ich bin jetzt ja dabei kein profi, aber ich würde fast sagen, dass man das allgemein gar net so sagen sagen..
Soweit ich weiß, sind normalerweise additionen billiger als multiplikationen, allerdings kann ich mir durchaus vorstellen, dass das ganze auch auf deinen compiler ankommt, was er in welcher weise optimiert.

außerdem würd ich bei beiden vorgehensweisen mal aufpassen, auf was du da zugreifst, weil die "Ränder des würfels" haben ja keine 26 nachbarn ;-), owa das nur nebenbei

also ich würd ja die erste version bevorzugen, weil sie einfach viel leserlicher ist..
aber vielleicht noch etwas.
du führst rechnungen durch, die in der form zu oft durchgeführt werden, nämlich wird in jedem durchlauf der innersten schleife alles an multiplikationen durchgeführt, was net notwendig is...

Code

for (int z=0; z<zdim; z++)
{
 
// aeusserste multiplikation z * xdim * ydim
int zMult = z* xdim* ydim;


  for (int y=0; y<ydim; y++)
  {
// naechste multiplikation plus wert von vorher
// yMult = zMult + y*xdim;
int yMult = ZMult + y*xdim;


	for (int x=0; x<xdim; x++)
	{
// und hier nur noch x dazu addieren
	  cur_a = my_array[yMult+x];
	  ...
	  // Zugriff auf die 26 Nachbarn des Elementes an der Position x,y,z
	  if (my_array[INDEX(x-1,y-1,z-1)] < cur_a) // Nachbar: 01
	  {
		...
	  }
	  ...
	  if (my_array[INDEX(x+1,y+1,z+1)] < cur_a) // Nachbar: 26
	  {
		...
	  }
	  ...
	}
  }
}

Alles anzeigen

naja vielleicht bringt das ja was

mfg Shine

jeuneS2

Zitat von \LaTeX

D.h. die konkrete Frage, die ich mir hier stelle ist, ob "if (*(a+x+1) < cur_a)" teurer ist als "if (my_array[z*xdim*ydim + y*xdim + x] < cur_a)"? Also auf der einen Seite [Zwei Additionen und ein Derefenzieren] und auf der anderen Seite [3 Multiplikationen und zwei Additionen]. Oder anders ausgedrueckt: dauert das Dereferenzieren eines Pointers laenger als wenn man 3 uint Werte multipliziert (wenn man die Ermittlung des Pointers a mal auszer Acht laeszt)?

Gute Compiler sollten x als Induktionsvariable erkennen und z*xdim*ydim+y*xdim als innerhalb der innersten Schleife konstanten Ausdruck und dementsprechend zweitere Form in erstere Überführen (irgendwo in den Unterlagen zur LVA Optimierende übersetzer findet sich ein schönes Beispiel dafür). Im Zweifelsfall würde ich aber Benchmarks vornehmen, nicht jeder Compiler macht auch immer das, was möglich wäre.

PS: "dereferenzieren" ist quasi kostenlos, in der internen Darstellung der meisten Compiler ist a[i] das gleiche wie *(a+i) - sofern die Elemente des Arrays die Größe 1 haben, versteht sich.

Plantschkuh!

Zitat von \LaTeX

Also auf der einen Seite [Zwei Additionen und ein Derefenzieren] und auf der anderen Seite [3 Multiplikationen und zwei Additionen].

Naja, zwei Additionen und nix ist unoptimiert sicher billiger als zwei Additionen und irgendwas... Und den Speicherzugriff hast du bei beiden Varianten dabei.

Zitat von jeuneS2

in der internen Darstellung der meisten Compiler ist a[i] das gleiche wie *(a+i) - sofern die Elemente des Arrays die Größe 1 haben, versteht sich.

Mehr noch: Laut C-Standard sind a[i] und *(a+i) völlig äquivalent. Das geht sogar so weit, daß man statt array[index] genauso auch index[array] schreiben darf, da die Addition ja kommutativ ist...
Und die Größe der Array-Elemente ist unerheblich, da Zeiger-Offsets immer automatisch in Elementen, nicht in Bytes ö.ä. gezählt werden.

hal

Zitat von Plantschkuh!

Mehr noch: Laut C-Standard sind a[i] und *(a+i) völlig äquivalent. Das geht sogar so weit, daß man statt array[index] genauso auch index[array] schreiben darf, da die Addition ja kommutativ ist...

hmmm...

Code

main() {
        char str[] = "hallo!";
        printf("%c\n",str[3]);
        printf("%c\n",3[str]);
}

funktioniert tatsächlich! Selbst nach 7 Jahren C-Erfahrung kann man trotzdem noch was dazulernen... Danke Plantschkuh!

Dieses Wissen hilft mir aber wohl eher für den C-Obfuscation-Wettbewerb als anderswo... Die komplizierteste Art, 1+1 zu rechnen: &1[(char*)1]

\LaTeX

Zitat von Shine

außerdem würd ich bei beiden vorgehensweisen mal aufpassen, auf was du da zugreifst, weil die "Ränder des würfels" haben ja keine 26 nachbarn ;-), owa das nur nebenbei

Klar, das war auch durch '...' im Code repraesentiert Die Raender musst ja eh' fuer beide Varianten ueberpruefen.

Zitat von Shine

du führst rechnungen durch, die in der form zu oft durchgeführt werden, nämlich wird in jedem durchlauf der innersten schleife alles an multiplikationen durchgeführt, was net notwendig is...

naja vielleicht bringt das ja was

Da hast' Recht, danke fuer'n Hinweis.

Zitat von Plantschkuh!

Naja, zwei Additionen und nix ist unoptimiert sicher billiger als zwei Additionen und irgendwas... Und den Speicherzugriff hast du bei beiden Varianten dabei.

Cool, d.h. der Dereference Operator ist zur Laufzeit in diesem Fall "for free"?

Danke nochmals fuer euere Beitraege. Jetzt ist einiges klarer.
ciao

Plantschkuh!

Zitat von \LaTeX

Cool, d.h. der Dereference Operator ist zur Laufzeit in diesem Fall "for free"?

Nein, Speicherzugriffe sind nicht for free, sie sind sogar vergleichsweise teuer. Ich wollte nur ausdrücken, daß * und [] beides Operatoren zur Dereferenzierung sind, also hast du bei beiden die gleichen Kosten für den Speicherzugriff.

Jetzt mitmachen!