Performance der Basisoperationen. Wie teuer ist...

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

hellihjb

Das ist aber m.E. weder eine Aussage zu oder gegen Inline-Coding.
Kannst Du erläutern, was Du darunter verstehst und wo hier insbesondere Vorteile oder Nachteile liegen.

ich moechte jetzt keine groessere abhandlung ueber optimierungen auf superskalaren architekturen schreiben, darum nur kurz:
da es im urspruenglichen thema darum ging, welche befehle besonders schnell ausfuehrbar seien, muss man sich zunaechst vor augen halten, dass das rechenwerk, abgesehen vom bekannten pipeline-aufbau, seit dem pentium-1 aus einer ansteigenden anzahl unabhaengiger teile besteht; naemlich (mehrere) addierer, shifter, binaerlogik, multiplizier, dividiererer plus das ganze nochmal fuer fliesskomma und mehrmals bei multicore.
um die bestmoegliche performance zu erzielen, muss man das gesamte rechenwerk ideal auslasten - dabei kann inlining hilfreich sein.

jox schrieb:

Was meinst Du mit "vierer- oder gar achter-schritten"??? Kannst Du das etwas präziser ausdrücken?

Ich denke er will damit sagen, dass es effizienter ist gleich 4 bytes auf einmal auf Gleichheit (oder 0) zu testen als immer nur ein Byte. Also anstatt einzelne chars zu vergleichen lieber gleich ein int oder ein long.

jox

TactX schrieb:

jox schrieb:

Was meinst Du mit "vierer- oder gar achter-schritten"??? Kannst Du das etwas präziser ausdrücken?

Ich denke er will damit sagen, dass es effizienter ist gleich 4 bytes auf einmal auf Gleichheit (oder 0) zu testen als immer nur ein Byte. Also anstatt einzelne chars zu vergleichen lieber gleich ein int oder ein long.

... und wie willst Du das performant machen???? Wie willst Du - performant und in C - überprüfen, ob eines von 4 bzw. 8 Bytes eines Wortes 0x00 ist???

http://graphics.stanford.edu/~seander/bithacks.html#ZeroInWord

jox

TactX schrieb:

http://graphics.stanford.edu/~seander/bithacks.html#ZeroInWord

Mag ggf. genau dann super funktionieren, wenn die Character-Strings genau auf Wort-Grenzen beginnen, auf Wort-Grenzen enden und dann noch ein Vielfaches von 4 bzw. 8 lang sind. Das dem i.d.R. nicht so ist, wissen wir beide. Anderenfalls muss man am Anfang und am Ende noch einen Haufen Sonderbehandlungen machen, was den Code natürlich auch nicht übersichtlich und ggf. nicht schneller macht.

Aber sei's drum .... falls es schneller gehen sollte, kann man den Code natürlich auch als Makro implementieren und vielleicht ist er dann sogar immer noch schneller als der Funktionsaufruf. Einen Versuch ist es ja Wert...

P.S. Danke für den Link, ich schau mal, was ich da so von gebrauchen kann

hellihjb

Mag genau dann super funktionieren, wenn die Character-Strings genau auf Wort-Grenzen beginnen

zb wenn man's mit "malloc" allokiert hat

Anderenfalls muss man noch einen Haufen Sonderbehandlungen machen

und genau das macht zb strlen.
deswegen ist deine trivial-implementierung auch auf kurzen strings pauschal schneller; bei langen strings (im sinne von kilobyte) relativiert sich dann der call-overhead schnell.
grundsaetzlich sollte man allignment aber bedenken - sonst waeren 128bit-prozessoren ja unnuetz...

jox

hellihjb schrieb:

Mag genau dann super funktionieren, wenn die Character-Strings genau auf Wort-Grenzen beginnen

zb wenn man's mit "malloc" allokiert hat

Strings sind, so ist der heutige Stand, auf Byte-Grenzen ausgerichtet. Ich kann jederzeit einen char* pointer irgendwo mittenrein zeigen lassen (dann nützt mir auch der Basis-String mit malloc() nix) und das Ding hört leider auch nicht auf Wort-Grenzen auf...

hellihjb schrieb:

Anderenfalls muss man noch einen Haufen Sonderbehandlungen machen

und genau das macht zb strlen.
deswegen ist deine trivial-implementierung auch auf kurzen strings pauschal schneller; bei langen strings (im sinne von kilobyte) relativiert sich dann der call-overhead schnell.

... mal ne blöde Frage, wieviel Strings haben eine solche Länge. Ich schätze mal, dein Vorname, Nachname, Wohnort usw. sind wohl entscheidend kürzer. Selbst bei Filenamen und URL's kommt man kaum auf kBs. Probier es einfach aus, manchmal überholt die Praxis die Theorie.

hellihjb schrieb:

... - sonst waeren 128bit-prozessoren ja unnuetz...

Das ist zwar ein ganz anderes Thema, aber: Hast Du schon mal 32-Bit-Prozessoren mit 64-Bit-Prozessoren verglichen? Ich schon (SUN/Solaris). Das Ergebnis würde Dich überraschen. Aber ich will hier keine pauschalen Äußerungen machen. Probier's oder google mal ein wenig zu diesem Thema.

jox schrieb:

Mag ggf. genau dann super funktionieren, wenn die Character-Strings genau auf Wort-Grenzen beginnen, auf Wort-Grenzen enden und dann noch ein Vielfaches von 4 bzw. 8 lang sind. Das dem i.d.R. nicht so ist, wissen wir beide. Anderenfalls muss man am Anfang und am Ende noch einen Haufen Sonderbehandlungen machen, was den Code natürlich auch nicht übersichtlich und ggf. nicht schneller macht.

Nun eben das hat volkard vorhin schon mehr oder weniger so gesagt.

jox

TactX schrieb:

Nun eben das hat volkard vorhin schon mehr oder weniger so gesagt.

... ich weiß, aber warum wird man hier kritisiert, wenn man hier etwas wiederholt bzw. wenn man das Wort "überlegt" für andere Leute etwas präzisiert?

... oder war das keine Kritik?

volkard

jox schrieb:

Aber sei's drum .... falls es schneller gehen sollte, kann man den Code natürlich auch als Makro implementieren und vielleicht ist er dann sogar immer noch schneller als der Funktionsaufruf. Einen Versuch ist es ja Wert...

jetzt, wo ich deine messung widerlegt habe, kann ich ja mal versuchen, anzufangen, sich von deiner makromanie wegzubringen.

kann dein compiler inline-funktionen?

kann dein compiler optimieren?

ist manchmal inline und manchmal outline schneller?

kann dein compiler selber inlineisieren, ohne daß du inline schreibst?