PhysicEngine, Fragen zur Datenstruktur

[Medium]

Verlet! Danke

Ich vermute fast, das bei Arrays der schwerer wiegende Anteil ist, dass diese hübsch am Stück im Speicher liegen und nacheinander sehr effizient abgefuttert werden können, auch wenn die Referenzierung am Ende vielleicht mehr Aufwand ist. (Wen das stört, der kann über ein Array auch noch mit Pointer-Arithmetik iterieren, wieder ein Sparpotenzial, dass eine Sammlung von "losen" Records nicht böte.)

Ich will das auch gar nicht beschönigen, das sieht am Ende etwas aus wie Code aus den 80ern. Aber das ist einer der seltenen Fälle, wo ich es aus eigener Erfahrung mit Ausprobieren mehrerer Varianten gerechtfertigt finde. (Grafikkarten legen sich ihre Streams intern nach Möglichkeit nicht ohne Grund aehr ähnlich aus. Stream-Processing macht bei den üblichen Architekturen einfach was aus.)

[dmdjt]

Das komische ist, dass p: array of Tpoint langsamer als x,y,z: of double ist. Zumindest bei dem oben beschrieben Test.

Ich verstehe davon leider zu wenig und hab nie den richtigen Zugang gefunden. Da fehlt mir einiges...

[Aphton]

Zitat von Medium:

Verlet! Danke

Ich vermute fast, das bei Arrays der schwerer wiegende Anteil ist, dass diese hübsch am Stück im Speicher liegen und nacheinander sehr effizient abgefuttert werden können, auch wenn die Referenzierung am Ende vielleicht mehr Aufwand ist.

Das ist genauso auch bei Array of Record's der Fall.
Ein Rekord gibt ja nur an, wie viel Speicher benötigt wird und wie man an die einzelnen Elemente rankommt (Delphi-Record <> Delphi-Class)

Ich habs nun getestet und erstaunlicherweise ist deine Variante doch schneller..

Code:

#define ARR_SIZE 1024 * 1024 /* 1mb */
#define REPETITIONS   3000

double x[ARR_SIZE];
double y[ARR_SIZE];
double z[ARR_SIZE];
point xyz[ARR_SIZE];

int main(int argc, char **args) {
   const double val = 123.456;

   // cpu-warmup
   for (int i = 0; i < REPETITIONS; i++) { }

   // test #1
   int t = get_tick_count_ms();
   for (int i = 0; i < REPETITIONS; i++)
      for (int j = 0; j < ARR_SIZE; j++)
         x[j] = y[j] = z[j] = val;
   t = get_tick_count_ms() - t;
   printf("Test #1\t %dms\t x[], y[], z[]\n", t);

   // test #2
   t = get_tick_count_ms();
   for (int i = 0; i < REPETITIONS; i++) {
      double *x_ptr = &x[0];
      double *y_ptr = &y[0];
      double *z_ptr = &z[0];
      for (int j = 0; j < ARR_SIZE; j++)
         *x_ptr++ = *y_ptr++ = *z_ptr++ = val;
   }
   t = get_tick_count_ms() - t;
   printf("Test #2\t %dms\t x_ptr, y_ptr, z_ptr\n", t);

   // test #3
   t = get_tick_count_ms();
   for (int i = 0; i < REPETITIONS; i++) {
      for (int j = 0; j < ARR_SIZE; j++)
         xyz[j].x = xyz[j].y = xyz[j].z = val;
   }
   t = get_tick_count_ms() - t;
   printf("Test #2\t %dms\t xyz[]\n", t);

   // test #4
   t = get_tick_count_ms();
   for (int i = 0; i < REPETITIONS; i++) {
      point *xyz_ptr = &xyz[0];
      for (int j = 0; j < ARR_SIZE; j++)
         xyz_ptr++->x = xyz_ptr->y = xyz_ptr->z = val;
   }
   t = get_tick_count_ms() - t;
   printf("Test #2\t %dms\t xyz_ptr\n", t);
}

Code:

Test #1    12338ms    x[], y[], z[]
Test #2    11623ms    x_ptr, y_ptr, z_ptr
Test #2    17074ms    xyz[]
Test #2    13396ms    xyz_ptr

[Namenloser]

@Aphton: Ich weiß nicht mehr genau, wo ich es ursprünglich gelesen hatte, aber für hohe Performance wird soweite ich weiß gerade empfohlen, Structs of Arrays zu verwenden statt Arrays of Structs. Den genauen Grund weiß ich nicht mehr, aber es hatte glaube ich irgendwas mit Cache und Vectorization zu tun (wobei der Delphi-Compiler letzteres wohl sowieso nicht unterstützt).