Performance der Basisoperationen. Wie teuer ist...

Fellar

...z.B. eine unsigned integer Addition? Oder in Relation dazu eine Integer Division? Was gilt für Floating-Point?
Wie viel Zeit kosten Funktionsaufrufe? Was kostet eine if-Abfrage? Wie schnell ist switch?

Fragen, die ich mir schon lange stelle aber noch nie eine Antwort gefunden habe. Toll wäre z. B. eine Tabelle, wo alles aufgeführt ist, so etwa:

unsigned Integer Addition : 1 Zeiteinheit
signed Integer Addition : 2 ZE
floating Point division : 8 ZE
Funktionsaufruf : 2 ZE + f(#Parameter)
.
.
.

Grüße
FellaR

Swordfish

Angabe bezogen auf einen Intel 80386:

Tz ... Taktzyklen

Integeraddition (unsigned):
   Register / Register       2 Tz
   Register / Speicher       6 Tz
   Speicher / Register       7 Tz
   Register / Immediate      2 Tz
   Speicher / Immediate      7 Tz
Akkumulator / Immediate      2 Tz

Fellar schrieb:

Toll wäre z. B. eine Tabelle, wo alles aufgeführt ist.

Das hängt von Compileroptimierungen, Speicherbandbreite, verwendete CPU, Erweiterten Befehlssätzen (SSE, SSE2, 3D-Now, ...), Wetterlage und was weis ich noch sonst allem ab. Damit sollte klar sein, dass die von dir gewünschte Tabelle schwachfug ist.

Viel wichtiger ist die Frage ob ein bestimmter Algorithmus hochperformant ist, als seine kleinstmöglichen Einzelteile.

Greetz, Swordfish

c.rackwitz

abhaengig vom prozessor. swordfish: egal woher du die tabelle hast, sie gilt nur fuer spezifische prozessortypen.
ausserdem kriegst du auf nem multitasking system eh nie die volle rechenzeit.

mach doch ein benchmark. zeit fuer eine milliarde ausfuehrungen nehmen?

Fellar

OK, die Universaltabelle ist vielleicht etwas naiv gedacht, aber die Übersicht für den 80386 ist doch schon mal gar nicht so schlecht. Gibts sowas auch für aktuelle Prozessoren?
Desweiteren interessieren mich halt auch noch die Performance (oder besser gesagt die Arbeitsweise) der Kontrollstatements. Was geschieht z.B. (performancetechnisch) bei einem Funktionsaufruf? Wie lange dauert das speichern der aktuellen Codeadresse auf dem Stack, das Übergeben der Parameter, etc. ?
Wie kann ich beurteilen, ob ein Algorithmus hochperformant ist, wenn ich seine Einzelteile nicht untersuchen kann?
Die Theorie ist mir soweit bekannt, aber in der Theorie ist z.B. eine Binärsuche auf sortierten Listen auch immer schneller als eine Linearsuche, auch wenns nur 10 Elemente sind. Das stimmt in der Praxis halt einfach nicht und deswegen interessieren mich die Maßstäbe, nach denen man die Performanz eines Algorithmus einordnen kann.

Grüße
FellaR

GPC

Wenn euch die Zeiten von Operationen, Funktionsaufrufen usw. interessiert, messt sie doch:

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

#define MAXN 100000
int x[MAXN];
int startn = 5000;
int n;

/* FUNCTIONS TO BE TIMED */

int intcmp(int *i, int *j)
{   return *i - *j; }

#define swapmac(i, j) { t = x[i]; x[i] = x[j]; x[j] = t; }

void swapfunc(int i, int j)
 {  int t = x[i];
	x[i] = x[j];
	x[j] = t;
 }

#define maxmac(a, b) ((a) > (b) ? (a) : (b))

int maxfunc(int a, int b)
{	return a > b ? a : b; }

/* WORKHORSE */

#define T(s) printf("%s (n=%d)\n", s, n);
#define TRIALS 5
#define M(op)							\
	printf(" %-22s", #op);				\
	k = 0;								\
	timesum = 0;						\
	for (ex = 0; ex < TRIALS; ex++) {	\
		start = clock();				\
		for (i = 1; i <= n; i++) {		\
			fi = (float) i;				\
			for (j = 1; j <= n; j++) {	\
				op;						\
			}							\
		}								\
		t = clock()-start;				\
		printf("%6d", t);				\
		timesum += t;					\
	}									\
	nans = 1e9 * timesum / ((double)	\
		n*n * TRIALS * CLOCKS_PER_SEC);	\
	printf("%8.0f\n", nans);

int main()
{   int i, j, k;
	float fi, fj, fk;
	int t, ex, timesum, start, globalstart;
	double nans;
	globalstart = clock();
	for (i = 0; i < n; i++)
		x[i] = rand();
	n = startn;
	printf("C Time Cost Model, n=%d\n", n);
	T("Integer Arithmetic");
	M({});
	M(k++);
	M(k = i + j);
	M(k = i - j);
	M(k = i * j);
	M(k = i / j);
	M(k = i % j);
	M(k = i & j);
	M(k = i | j);
	T("Floating Point Arithmetic");
	M(fj=j;);
	M(fj=j; fk = fi + fj;);
	M(fj=j; fk = fi - fj;);
	M(fj=j; fk = fi * fj;);
	M(fj=j; fk = fi / fj;);
	T("Array Operations");
	M(k = i + j);
	M(k = x[i] + j);
	M(k = i + x[j]);
	M(k = x[i] + x[j]);
	T("Comparisons");
	M(if (i < j) k++);
	M(if (x[i] < x[j]) k++);
	T("Array Comparisons and Swaps");
	M(k = (x[i]<x[k]) ? -1:1);
	M(k = intcmp(x+i, x+j));
	M(swapmac(i, j));
	M(swapfunc(i, j));
	T("Max Function, Macro and Inline");
	M(k = (i > j) ? i : j);
	M(k = maxmac(i, j));
	M(k = maxfunc(i, j));
	n = startn / 5;
	T("Math Functions");
	M(fk = j+fi;);
	M(k = rand(););
	M(fk = sqrt(j+fi));
	M(fk = sin(j+fi));
	M(fk = sinh(j+fi));
	M(fk = asin(j+fi));
	M(fk = cos(j+fi));
	M(fk = tan(j+fi));
	n = startn / 10;
	T("Memory Allocation");
	M(free(malloc(16)););
	M(free(malloc(100)););
	M(free(malloc(2000)););

	/* Possible additions: input, output, malloc */
	printf("  Secs: %4.2f\n",
		((double) clock()-globalstart)
		/ CLOCKS_PER_SEC);
	return 0;
}

MfG

GPC

Fellar

Danke, das hilft schon mal sehr bei der groben Orientierung!

Swordfish

c.rackwitz schrieb:

swordfish: egal woher du die Tabelle hast, sie gilt nur fuer spezifische Prozessortypen.

aus: "PC-Programmieren in Maschinensprache" von Peter Monadjemi. Warum denkst du hab' ich

Swordfish schrieb:

Angabe bezogen auf einen Intel 80386

darübergeschrieben!?

c.rackwitz schrieb:

Außerdem kriegst du auf nem multitasking System eh nie die volle Rechenzeit.

Tja, ich weiß es, du weißt es, ...

c.rackwitz schrieb:

Mach doch einen Benchmark. Zeit für eine milliarde Ausführungen nehmen?

GPC schrieb:

Wenn euch die Zeiten von Operationen, Funktionsaufrufen usw. interessiert, messt sie doch

Wenn es mich (selten ist es so) interessiert, mach ich das auch.
@GPC: mich interessierts im Moment nicht wirklich, und wenn s.O.
BTW:
@GPC: Mit meinem Artikel könnte es noch bis Anfang/Mitte nächste Woche dauern. Hab zuviel Stress gehabt.

Fellar schrieb:

Wie lange dauert das speichern der aktuellen Codeadresse auf dem Stack, das Übergeben der Parameter, etc. ?

Grundsätzlich musst du da je nach Calling-Convention unterscheiden...

Fellar schrieb:

Wie kann ich beurteilen, ob ein Algorithmus hochperformant ist, wenn ich seine Einzelteile nicht untersuchen kann?

Landau-Notation
oder mit einer einfachen Laufzeitmessung.

Greetz, Swordfish

Fellar

Swordfish schrieb:

Landau-Notation

Wie ich schon sagte, die Theorie kenne ich bereits. Landau-Notation hat nichts mit dem Thread zu tun.

Werd in Zukunft einfach Zeit messen und gut is.

Swordfish

Fellar schrieb:

Werd in Zukunft einfach Zeit messen und gut is.

Ja, tu das.

Greetz, Swordfish

GPC

Swordfish schrieb:

@GPC: mich interessierts im Moment nicht wirklich, und wenn s.O.

Ich schrieb "euch"... dabei meinte ich nur den OP.

BTW:
@GPC: Mit meinem Artikel könnte es noch bis Anfang/Mitte nächste Woche dauern. Hab zuviel Stress gehabt.

take your time. (Und schreib mir ne Mail, wenn's um solche Sachen geht )

MfG

GPC

jox

Fellar schrieb:

... Die Theorie ist mir soweit bekannt, aber in der Theorie ist z.B. eine Binärsuche auf sortierten Listen auch immer schneller als eine Linearsuche, auch wenns nur 10 Elemente sind. Das stimmt in der Praxis halt einfach nicht und deswegen interessieren mich die Maßstäbe, nach denen man die Performanz eines Algorithmus einordnen kann.

Ich habe die Erfahrung gemacht, dass die Theorie heutzutage leider nicht mehr immer stimmt. Der Prozessor-Cache hat heute immense Auswirkungen auf die Geschwindigkeit eines Algorithmus. So kann man heute durch Inline-Coding (z.B. mit Macros) an Stelle von Funktionsaufrufen erhebliche Geschwindigkeitsvorteile erreichen. Ich habe in einem größeren Programmpaket die Funktion strlen() durch ein entsprechendes Macro ersetzt und so mal locker 10% mehr Gesamt-Performance erreicht. Der Algorithmus ist dabei (wahrscheinlich) ähnlich, allein der Prozessor-Cache und der fehlende Funktionsaufruf schafft die Geschwindigkeit.

Was ich damit sagen will ... die "alte" Theorie muss in Zusammenhang mit den Prozessor-Cache und Code-Prefetching neu überdacht werden.

GPC

So kann man heute durch Inline-Coding (z.B. mit Macros) an Stelle von Funktionsaufrufen erhebliche Geschwindigkeitsvorteile erreichen.

oder der Algo wird langsamer. Die Aussage "durch inline wird der Algo schneller" ist nicht selten falsch. manchmal sind echte inline-Funktionen schneller, manchmal Makros... man muss wirklich messen, bevor man sagen kann, dass a schneller als b ist.

MfG

GPC

jox

GPC schrieb:

Die Aussage "durch inline wird der Algo schneller" ist nicht selten falsch. manchmal sind echte inline-Funktionen schneller, manchmal Makros... man muss wirklich messen, bevor man sagen kann, dass a schneller als b ist.

Korrekt, das kann ich bestätigen.

Inline-Coding kann insbesondere Sinn machen bei kleineren Code-Schnipseln ohne viel lokale Variablen.
Wie gesagt, Ersatz von strlen() durch ein Macro brachte 10% Performance-Vorteil,
Ersatz von strcmp() durch ein entsprechendes Macro war leider langsamer.

Tuning durch Maßnahmen im Quellcode ist leider nicht ganz simpel. Grundkenntnisse im Compilerbau, ein geschicktes Maß an Erfahrung bzw. Intuition und vor allem Probieren, Probieren, Probieren ...

Aber, was ich u.A. ausdrücken will, ist:
Man kann zwar irgendwie die Anzahl der Prozessorzyklen für einen bestimmten Befehl und einen bestimmten Prozessortyp herausbekommen (z.B. aus der Spezifikation). Was man aber nicht bestimmen kann, ist die tatsächlich benötigte CPU-Zeit für diesen Befehl. Das kommt halt darauf an, ob der Befehl aus dem CPU-Cache ausgeführt wird oder halt nicht. Für einen 80386 war das noch einfach, weil der noch keinen CPU-Cache hatte.
Auch durch Austesten bekommt man keine genauen Werte. Diese Tests beschränken sich i.d.R. auf zig-faches Wiederholen gleicher Programm-Statements. Dann sind diese Befehle natürlich im Cache, und man erhält im besten Fall eine Minimum-Zeit. Die festgestellte Zeitdauer kann dann nicht einfach durch die Anzahl der Schleifendurchläufe geteilt werden, denn wenn der Befehl mal nicht im Cache sein sollte, braucht er halt wesentlich länger. Lediglich für einen Zeitvergleich zwischen verschiedenen benutzten Code-Sequenzen lassen sich solche Tests benutzen (vorausgesetzt, auf dem System laufen sonst keine weiteren Aktivitäten und der Testjob ist die einzige Task).

Aber, was ist das eigentliche Ziel, wenn man die benötigte CPU-Zeit für bestimmte Befehle herausfinden will? Eigentlich will man doch ein Performance-Tuning erreichen. Hierzu kann ich nur mein Statement von oben zitieren, das mit dem "... Probieren, Probieren, Probieren ... ". Aber mit ein wenig Gespür und dem Tunen von häufig genutzten Routinen oder Schleifen sollten im Minimum 10-20% auf jeden Fall drin sein.

net 0

jox schrieb:

Ersatz von strlen() durch ein Macro brachte 10% Performance-Vorteil,
Ersatz von strcmp() durch ein entsprechendes Macro war leider langsamer.

kannste die makros hier mal posten? besonders das erste würd' mich interessieren...

jox

... kein Problem (wenn nicht wieder irgendwer über den Programmierstil meckert ;-), ist ein Auszug aus einem Original Include-File (übrigens natürlich auf Geschwindigkeit getrimmt, deswegen vielleicht nicht ganz einfach zu interpretieren ;-).

#define	TXTLEN(s,l) { register char * __hcp__; \
    __hcp__ = (s); \
    do ; while (*__hcp__++ != 0x00); \
    (l) = --__hcp__ - (s); \
    }

/* char *s;			--  I:  string */
/* int l;			-- I/O: length of string */
/* Calculates length "l" of string "s", */
/* same as system library call strlen(). */
/* Very fast version by using internal processor cache. */
/* At gcc 3.2 two times faster than strlen()!. */

Leider muss man dann den Aufruf überall etwas ändern:

len = strlen(txt);

/* ==> in ==> */

TXTLEN(txt,len);

Das Ändern nervt vielleicht etwas, kann man zu Anfang ggf. auch nur an häufig benutzten Stellen machen.
Bringt aber in meinem Programmpaket ordentlich was!!!

P.S.: Das Macro für strcmp() habe ich auch nicht mehr, weil - es wie gesagt - keinen Erfolg brachte.

net 0

ach so, das übliche
ich dachte du hättest so ein makro: 'len=TXTLEN(txt)'

btw: wenn strlen etc. zu lahm sind, bietet es sich an, die strings in einem anderen format zu speichern z.b. zuerst längenangabe und dann die zeichen. dann braucht man nicht jedes mal diese zählschleife (nur beim konvertieren einmal)

volkard

jox schrieb:

... kein Problem (wenn nicht wieder irgendwer über den Programmierstil meckert ;-), ist ein Auszug aus einem Original Include-File (übrigens natürlich auf Geschwindigkeit getrimmt, deswegen vielleicht nicht ganz einfach zu interpretieren ;-).
#define	TXTLEN(s,l) { register char * __hcp__; \
    __hcp__ = (s); \
    do ; while (*__hcp__++ != 0x00); \
    (l) = --__hcp__ - (s); \
    }

/* char *s;			--  I:  string */
/* int l;			-- I/O: length of string */
/* Calculates length "l" of string "s", */
/* same as system library call strlen(). */
/* Very fast version by using internal processor cache. */
/* At gcc 3.2 two times faster than strlen()!. */
Leider muss man dann den Aufruf überall etwas ändern:
len = strlen(txt);

/* ==> in ==> */

TXTLEN(txt,len);
Das Ändern nervt vielleicht etwas, kann man zu Anfang ggf. auch nur an häufig benutzten Stellen machen.
Bringt aber in meinem Programmpaket ordentlich was!!!
P.S.: Das Macro für strcmp() habe ich auch nicht mehr, weil - es wie gesagt - keinen Erfolg brachte.

ich fürchte, du hast nicht 10% durch den aufruf gewonnen, sondern du hast 10% gewonnen, weil du in deinem programmpaket in weit überwiegendem maße kurze strings hast und ein normales strlen, das vorher und nachher ein paar takte überlegt aber innen in vierer- oder gar achter-schritten voranstiefelt, bei den kurzen strings ein wenig lahmer ist.

hellihjb

Was man nicht bestimmen kann, ist die tatsächlich benötigte CPU-Zeit für einen Befehl.
Das kommt darauf an, ob der Befehl aus dem CPU-Cache ausgeführt wird oder nicht.
Für einen 80386 war das noch einfach, weil der noch keinen CPU-Cache hatte.

das ist ziemlich oberflaechlich pauschalisiert.
der gesamte code geht durch den code-cache, der im zuge einer fehlvorhersage der branchprediktion einen falschen code-zweig enthalten kann.
relevanter ist aber mittlerweile die ausnutzung des gesamten parallelen & mehrstufigen rechenwerks - wodurch viele, zum teil langsamere, operationen umsonst sind.

jox

... interessante Diskussion, hat zwar kaum noch etwas mit dem ursprünglichen Thema zu tun, aber sei's drum:

volkard schrieb:

ich fürchte, du hast nicht 10% durch den aufruf gewonnen, sondern du hast 10% gewonnen, weil du in deinem programmpaket in weit überwiegendem maße kurze strings hast und ein normales strlen, das vorher und nachher ein paar takte überlegt aber innen in vierer- oder gar achter-schritten voranstiefelt, bei den kurzen strings ein wenig lahmer ist.

no, wenn ich mich richtig errinnere, habe ich es damals auch mit längeren Strings (so um die 80 Zeichen) getestet. Und das Ergebnis war, dass es (in meiner Linux-Umgebung) fast doppelt so schnell war wie ein strlen().
Was meinst Du mit "vierer- oder gar achter-schritten"??? Kannst Du das etwas präziser ausdrücken?

Probier's einfach irgendwann aus. Ich schätze, Du wirst Dich wundern....

hellihjb schrieb:

der gesamte code geht durch den code-cache, der im zuge einer fehlvorhersage der branchprediktion einen falschen code-zweig enthalten kann.

Das ist schlicht und einfach korrekt, aber m.E. weder eine Aussage zu oder gegen Inline-Coding.

hellihjb schrieb:

relevanter ist aber mittlerweile die ausnutzung des gesamten parallelen & mehrstufigen rechenwerks - wodurch viele, zum teil langsamere, operationen umsonst sind.

Kannst Du erläutern, was Du darunter verstehst und wo hier insbesondere Vorteile oder Nachteile liegen. Sehe ich auf den ersten Blick nicht, aber ich bin ja wissbegierig ...

jox

net schrieb:

ach so, das übliche
ich dachte du hättest so ein makro: 'len=TXTLEN(txt)'

Leider nicht, aber ich arbeite dran ...
Wenn Du schneller bist, sag Bescheid