Erfahrungen::ANSI C::Performante Datenstruktur

[Winn]

Servus,

ich weiß, welch ein leidiges Thema und es läßt sich nicht Compilerspzifisch antworten,... mich interessiert jedoch euere Erfahrungen und welche Struktur Ihr in der Regel bevorzugt innerhalb von ANSI C ?!

Hab immer einen großen Bogen um structs gemacht, stellte jedoch in einem wahrscheinlich nicht repräsentativen Benchmark fest, das ein struct so schnell ist, wie ein statisches 3D Array bzw. ein 1D Array... nur ein 3D Pointer Array war "richtig" langsam... (Getestet mit Gcc 3.3 -O3, auf Apple G4 650MHz)

Hier mein "Benchmark" und freu mich auf eure Antworten

Winn

STRUCT::Es wurde 18.000000 (Sekunden) Rechenzeit benoetigt
Static3D::Es wurde 17.000000 (Sekunden) Rechenzeit benoetigt
1D::Es wurde 18.000000 (Sekunden) Rechenzeit benoetigt
Ptr3D::Es wurde 94.000000 (Sekunden) Rechenzeit benoetigt

#include <time.h>
#include <stdio.h>
#include <stdlib.h>

int main()	
{
	time_t t1, t2;
	double calculated_time;

	int i,j,k,x,iteration;
	double Grid1[40][40][40];
	double Line2[64000];
	double ***test;
	typedef struct
		{
			double Value;
		} Line;
	Line Grid[40][40][40];

	test=(double ***)calloc(40,sizeof(double));
	for(i=0;i<40;i++)
		{
			test[i]=(double **)calloc(40,sizeof(double));
			for(j=0;j<40;j++)
				{
					test[i][j]=(double *)calloc(40,sizeof(double));
					for(k=0;k<40;k++)
						{
							test[i][j][k]=0.;
						}
				}
		}

	t1 = time(NULL);

	for(iteration=0;iteration<10000;iteration++)
		{
		for(i=0;i<40;i++) 
			{
			for(j=0;j<40;j++)
				{
				for(k=0;k<40;k++) 
					{
						Grid[i][j][0].Value=0.;
						Grid[i][j][0].Value+=10;
						Grid[i][j][0].Value*=10;

						Grid[i][j][k].Value=0.;
						Grid[i][j][k].Value+=10;
						Grid[i][j][k].Value*=10;
					}
				}
			}
		}

	t2 = time(NULL);
	calculated_time = difftime( t2, t1);
	printf("STRUCT::Es wurde %f (Sekunden) Rechenzeit benoetigt\n", calculated_time);

	t1 = time(NULL);

	for(iteration=0;iteration<10000;iteration++)
		{
		for(i=0;i<40;i++) 
			{
			for(j=0;j<40;j++)
				{
				for(k=0;k<40;k++) 
					{
						Grid1[i][j][0]=0.;
						Grid1[i][j][0]+=10;
						Grid1[i][j][0]*=10;

						Grid1[i][j][k]=0.;
						Grid1[i][j][k]+=10;
						Grid1[i][j][k]*=10;
					}
				}
			}
		}

	t2 = time(NULL);
	calculated_time = difftime( t2, t1);
	printf("Static3D::Es wurde %f (Sekunden) Rechenzeit benoetigt\n", calculated_time);

	t1 = time(NULL);

	for(iteration=0;iteration<10000;iteration++)
		{
		for(i=0;i<40;i++) 
			{
			for(j=0;j<40;j++)
				{
				for(k=0;k<40;k++) 
					{
						Line2[1600*(i) + 40*(j)]=0;
						Line2[1600*(i) + 40*(j)]+=10;
						Line2[1600*(i) + 40*(j)]*=10;

						Line2[1600*(i) + 40*(j) + (k)]=0;
						Line2[1600*(i) + 40*(j) + (k)]+=10;
						Line2[1600*(i) + 40*(j) + (k)]*=10;
					}
				}
			}
		}

	t2 = time(NULL);
	calculated_time = difftime( t2, t1);
	printf("1D::Es wurde %f (Sekunden) Rechenzeit benoetigt\n", calculated_time);

	t1 = time(NULL);

	for(iteration=0;iteration<10000;iteration++)
		{
		for(i=0;i<40;i++) 
			{
			for(j=0;j<40;j++)
				{
				for(k=0;k<40;k++) 
					{
						test[i][j][0]=0.;
						test[i][j][0]+=10;
						test[i][j][0]*=10;

						test[i][j][k]=0.;
						test[i][j][k]+=10;
						test[i][j][k]*=10;
					}
				}
			}
		}

	t2 = time(NULL);
	calculated_time = difftime( t2, t1);
	printf("Ptr3D::Es wurde %f (Sekunden) Rechenzeit benoetigt\n", calculated_time);
}

[ChockoCookie]

Es kommt immer darauf an, wofür du die Struktur brauchst. Wenn die Menge der Daten, so wie in deinem Fall, zur Compilezeit bzw. Zeit der Initialisation feststeht und du nur mehr wahlfreien Zugriff brauchst, sind die klassischen C - Datenstrukturen das Mittel der Wahl. Wobei es egal ist, ob du Structs oder Arrays in welcher Dimension auch immer verwendest, weil da einfach zum Pointer eine andere Variable addiert wird. Komplizierter wird es, wenn die Strukturen dynamisch sein sollen. dH. du brauchst: Einfügen und Entfernen von Elementen, und Suchen. Dazu bietet sich verschiedenes an. zB verkettete Listen (einfach, doppelt oder ring), oder aber auch dynamische Arrays (empfehle ich eher für Leute mit masochistischer Ader ). Aber über so etwas gibt es eh genug Webseiten.
btw. Bei deinem "Benchmark" ist etwas lustiges aufgefallen: (auf AthlonXP 2600+)

Das Programm mit MVSC voll optimiert schrieb:

STRUCT::Es wurde 2.000000 (Sekunden) Rechenzeit benoetigt
Static3D::Es wurde 1.000000 (Sekunden) Rechenzeit benoetigt
1D::Es wurde 2.000000 (Sekunden) Rechenzeit benoetigt
Ptr3D::Es wurde 24.000000 (Sekunden) Rechenzeit benoetigt

Das Programm mit MinGW (=GCC) -O3 --fexpensive-optimizations schrieb:

STRUCT::Es wurde 1.000000 (Sekunden) Rechenzeit benoetigt
Static3D::Es wurde 2.000000 (Sekunden) Rechenzeit benoetigt
1D::Es wurde 1.000000 (Sekunden) Rechenzeit benoetigt
Ptr3D::Es wurde 1.000000 (Sekunden) Rechenzeit benoetigt

Sieht so aus als würde GCC den überflüssigen Pointer test eliminieren und damit den selben Code erzeugt wie bei Static3D . Mich wundert nur, das das bei dir nicht der Fall war .

[Winn]

Habs jetzt auch nochmal mit -fexpensive-optimizations und mit -faltivec ausgeführt... keine Besserung. Pointer auf Pointer auf Pointer ist auf'm Mac ne lahme Krücke... das ist schonmal gut zu wissen Trotzdem seltsam...