Was ist schneller: Berechnen oder aus Tabelle auslesen?

otze

Nebenbei ist das auch der optimalfall, und der grund dafür liegt in diesem Kommentar:

//x2+= table[b][a]; //very slow

Und das ist auch total richtig. Dein Experiment misst ja nur, wie teuer es ist, wenn du das array linear ließt. das ist so trivial, das optimiert dir jeder compiler und jeder prozessor bis zur Unkenntlichkeit.

Bei Random access - welcher sehr ähnlich dazu ist, b a in der Summe zu vertauschen, sieht die Sache schon ganz anders aus.

//edit wenn du linear ließt, müsstest du theoretisch die Array-Version mit folgendem vergleichen, damit es nicht ganz unfair ist:

for(int a=0; a< 1000; a++)
{
    int temp =a*64;
    for(int b=0; b<1000; b++)
    {
        x1+= temp;
        temp++;
    }
}

Was ist schneller Hashcode berechnen oder Tabelle?

DarkShadow44

für 100000 Loops (beide Male Optimiert):
bei codeblocks mit gcc sind es 0 zu 46 sekunden
bei visual studio sind sind es 56 zu 25 Sekunden

Kann mir gut denken, daß er bei der Array-Version bekannte Muster kennt zum Unrollen. Dagegen mache ich ihn mal durcheinander.

Das durcheinander Würfeln sagt aber ja nicht viel aus, wenn man einen Loop programmiert macht man das schon meistens linear, nicht nur zum testen. Deshalb würde ich für die Tabellenmethode auch von der effizientesten Umsetung ausgehen.

wenn du linear ließt, müsstest du theoretisch die Array-Version mit folgendem vergleichen, damit es nicht ganz unfair ist:

Was heißt hier unfair ? Es ging darum welche Methode schneller ist oder nicht ? Dann darf ich ja wohl von der optimiertesten Version ausgehen, oder würdest du eine extra de-optimierte Version in produktivem Code einbauen ?

Aber Du hast was vollkommen anderes gemessen, als von was wir ausgingen. Du hat einen int** und kein int[64][]!!!

Dem kann ich nicht zustimmen. Wo steht denn was von int[64][] ? Ich bin davon ausgegangen dass das einfach eine Berechnung für beliebige a und b ist, könnte auch
"x = a*53 + b;"
sein, das würde an der Tabelle doch auch nichts ändern ?

@TS
Naja die Moral von der Geschichte: Mal so mal so, lass diese Minioptimierungen lieber bleiben, das ist wie Lotto spielen

volkard

Hab mal

clock_t time1Start= clock();
	srand(0);
	for(int i=0; i<TEST; i++) {
		int a=rand()%1000;
		int b=rand()%64;
		x1+=64*a+b;
	}
	clock_t time1End= clock();

gebaut.

Loops: 100000000
x1: 75350243 time1: 1.76
x2: 75350243 time2: 1.78

volkard

DarkShadow44 schrieb:

Das durcheinander Würfeln sagt aber ja nicht viel aus, wenn man einen Loop programmiert macht man das schon meistens linear, nicht nur zum testen. Deshalb würde ich für die Tabellenmethode auch von der effizientesten Umsetung ausgehen.

Wenn ich tatsächlich die Wahl habe, ob ich x=rechne(a,b) mache oder x=tabelle[a][b], dann ist das allermeist eine look-up-table und ich rechne mit durcheinanderen zugriffen.

Ansonsten gestatte ich mir, für die Multilikationsvariante eine Summenformel zu nehmen.

DarkShadow44

Ups stimmt, mein Fehler.
Aber auch dann ist es ein Glücksspiel bezüglich des Compilers.

rapso

DarkShadow44 schrieb:

eigentilch wird bei allen aktuellen x86 cpus sowohl die addresse als auch generische integer math von denselben units berechnet. die befehle haben lediglich einfluss auf die binary size, sollte keinen performanceunterschied geben.

Aber eigentlich sollte der Speicherzugriff langsamer sein als eine Operation auf Registern oder ?

meine aussage bezog sich auf LEA vs MUL+ADD.
aber das impliziert natuerlich, dass die berechnungen in jedem fall gemacht werden, der load wird anschliessen 'extra' gemacht.
je nachdem wie der compiler das auslegt und die cpu das pipelinen kann, wird die version mit speicherzugrif gleich schnell oder langsammer, aber nie schneller sein

pöfornace schrieb:

Und was ist schneller:
(FeldIndex + 8 * (FeldIndex & 7)) & 63
oder Tabelle?

push

hustbaer

Probier' es aus.

hmmmmmm schrieb:

Betrachte z.B. folgende Situation:
// 1. Variante
x = a*64 + b;

// 2. Variante
x = a_b_table[a][b]; // wobei a_b_table so gefüllt ist, dass sie x wie in 1. Variante berechnet
Was ist heutzutage schneller?

Kommt drauf an. Wenn du den Wert der Tabelle noch nicht im 1st level cache hattest, dann dauert das ziemlich lange (mindestens etwa 300 Zyklen). Und die Multiplikation mit 64 kann schön per Bit-Shift optimiert werden. Das machen gute Compiler inzwischen automatisch. So'n Shift ist heutzutage auf modernen general-purpose Rechnern nur 1 Taktzyklus, genauso wie eine Addition. Antwort bitte selbst überlegen oder messen.