Was ist schneller: Berechnen oder aus Tabelle auslesen?

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?

Bashar

Das erste.

SeppJ

Das sollte nicht nur heute, sondern zu allen Zeiten so sein. Was ist denn ein Zugriff auf ein 2D-Feld? Eine Multiplikation und zwei Additionen und ein Speicherzugriff (wenn es wirklich ein 2D-Array ist. Wenn es eine Liste von Listen ist, dann ist es noch viel aufwändiger). Damit eine Multiplikation und eine Addition ersetzen zu wollen ist ein schlechter Plan.

Ich hab mal versucht, sqrt-Operationen durch Tabellenlookups schneller zu bekommen (sqrt ist meist so ungefähr Faktor 100 mal teurer als dein Bitshift + Addition). Das ging ordentlich nach hinten los.

volkard

ars schrieb:

Ich hab mal versucht, sqrt-Operationen durch Tabellenlookups schneller zu bekommen (sqrt ist meist so ungefähr Faktor 100 mal teurer als dein Bitshift + Addition). Das ging ordentlich nach hinten los.

Alter Prozessor, würde ich meinen.

sqrt brauchen die Gamer oft. Die Prozessorbauer hauen Zig von Millionen Transistoren nur für diesen einen Befehl rein, damit die Games mehr FramesPerSecond packen und man eben diese Prozessorsorte als Gamer kauft.

sqrt(x) ist halt viel böser als 64*x+5. Insofern verstehe ich nicht, was Du verglichen hast. Klar ist (derzeit?) eine einfache Plutimikation billiger als eine Radizierung.

edit: Ach, der Pythagoras hat schuld am dem Kack, und vielleicht ein wenig daß es _hypot2 gibt aber nicht _hypot3, und vielleicht ein ganz wenig, daß Programmierer, die in 3 Dimensionen denken, nicht mehr 2-dimensionale Basisoperationen kennen. *hihi*

volkard schrieb:

Alter Prozessor, würde ich meinen.

Dürfte ein Athlon XP gewesen sein.

volkard schrieb:

sqrt(x) ist halt viel böser als 64*x+5. Insofern verstehe ich nicht, was Du verglichen hast. Klar ist (derzeit?) eine einfache Plutimikation billiger als eine Radizierung.

Nun, worauf ich damit hinauswollte ist, wenn sich Lookuptabellen schon für eine recht teures sqrt nicht gelohnt haben, dann braucht man bei sowas wie 64*x+5 noch lange keinen Gedanken daran zu verschwenden. Letzteres schafft ein aktueller Prozessor gleich zweimal pro Takt, würde ich vermuten.

volkard schrieb:

edit: Ach, der Pythagoras hat schuld am dem Kack, und vielleicht ein wenig daß es _hypot2 gibt aber nicht _hypot3, und vielleicht ein ganz wenig, daß Programmierer, die in 3 Dimensionen denken, nicht mehr 2-dimensionale Basisoperationen kennen. *hihi*

War bei mir auch der Pythagoras, ich wollte sich überlagernde Wellen graphisch schon flüssig darstellen oder irgendso eine Spielerei. Wusste nicht, wie ich das sqrt da wegbekommen sollte, aber immerhin war des großen Carmacks sqrtf-Funktion schneller als das SSE-sqrt, wenn die Erinnerung nicht trügt.

volkard schrieb:

Die Prozessorbauer hauen Zig von Millionen Transistoren nur für diesen einen Befehl rein, damit die Games mehr FramesPerSecond packen und man eben diese Prozessorsorte als Gamer kauft.

Die Prozessorbauer bauen aber auch zig von Millionen Transistoren für die eine Multiplikation ein.

Und dann bauen die Prozessorbauer noch auch einen Befehl für einen schnellen Lookup in einer Table ein. Wenn die Tabelle in der ersten Dimension eine Zweierpotenz ist wären das ein shift und eine(!) Addition und ein Lookup mit Offset.

Aber klar ist 64+5 hier schneller.

Btw: Der invsqrt von Carmack war auf meinem alten Rechner auch um einen grossen Faktor schneller als 1/sqrt.

volkard

Anmerkung: Und wenn die Zweierpotenz nicht mehr als 8 ist, isses nur ein LEA-Befehl, ein Takt.

rapso

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.

Und was ist schneller:

(FeldIndex + 8 * (FeldIndex & 7)) & 63

oder Tabelle?

DarkShadow44

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 ?

pöfornace schrieb:

Und was ist schneller

Kann man so nicht sagen. Austesten.

Ich hab mal ein kleines Testprogramm gemacht (siehe Pastebin, allerdings ist dabei stets die Variante mit der Tabelle schneller gewesen (sowohl Debug als auch Release)
Also habe ich entweder irgendwo nen Fehler drin, oder ich verstehe meinen Prozessor nicht

volkard

DarkShadow44 schrieb:

Ich hab mal ein kleines Testprogramm gemacht (siehe Pastebin, allerdings ist dabei stets die Variante mit der Tabelle schneller gewesen (sowohl Debug als auch Release)
Also habe ich entweder irgendwo nen Fehler drin, oder ich verstehe meinen Prozessor nicht

Also Messergebnisse Deines Programms:

Loops: 1000
x1: 1842209536 time1: 2.8
x2: 1842209536 time2: 2.27

Multiplikationen waren also lahmer als Array.

Erste Änderung ist es, die Optimierungen einzuschalten.

Loops: 1000
x1: 1842209536 time1: 0.18
x2: 1842209536 time2: 0.18
Ähm, natürlich schaltet man die Optimierungen an, ist ja mehr als 10-mal schneller.

Loops: 10000
x1: 1242226176 time1: 1.86
x2: 1242226176 time2: 1.72

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

for(int a=1; a!=0; a=(a*17+1)%512)

x1: -1649733632 time1: 8.98
x2: -1649733632 time2: 9.04

Aber Du hast was vollkommen anderes gemessen, als von was wir ausgingen. Du hat einen int** und kein int[64][]!
Scheint aber nix auszumachen. Ich vermute, bei den Arrayzugriffen, gerade mit MME und so Extensions, kann er besser parallelisieren.

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.