Performance der Basisoperationen. Wie teuer ist...

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?

volkard

GPC schrieb:

manchmal sind echte inline-Funktionen schneller, manchmal Makros...

zeig mir ein beispiel. und nicht eins, wo die inlinefunktion so riesig ist, daß der compiler sie einfach nicht inlined.

hellihjb

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.

absolut richtig. aber ein string kann zb auch aus einer xml-datei kommen und eine ascii-repraesentation von mehreren tausend fliesskomma-zahlen beinhalten.
je nachdem, welche art von daten man nun hat, ist eben die eine oder die andere umgehensweise dafuer geeigneter - deshalb ist haeufig der einsatz irgendeiner maechtigen string-klasse nicht auch pauschal ideal.
und - uebrigens voellig kritikfrei - wenn man einen algorithmus in einem bestimmten testfeld fuer performanter befunden hat, sollte man auch erwaehnen, wie dieses testfeld aussieht.

jox

hellihjb schrieb:

...je nachdem, welche art von daten man nun hat, ist eben die eine oder die andere umgehensweise dafuer geeigneter - deshalb ist haeufig der einsatz irgendeiner maechtigen string-klasse nicht auch pauschal ideal.
und - uebrigens voellig kritikfrei - wenn man einen algorithmus in einem bestimmten testfeld fuer performanter befunden hat, sollte man auch erwaehnen, wie dieses testfeld aussieht.

Darauf können wir uns locker einigen

Mein Ansatz war aber nicht irgendwelche String-Operationen, sondern ging auf das ursprüngliche Thema ein, wieviel CPU-Zeit ein Befehl braucht. Mal so ganz grob zusammengefasst: Ich habe gesagt, bei den heutigen Prozessoren kann man das nicht mehr so einfach sagen, da muss man u.a. den Prozessor-Cache berücksichtigen. Dann habe ich mal so als unverbindliches Beispiel Inline-Code angeführt, dass man eben hierdurch ggf. erhebliche Performance-Gewinne erzielen kann. Selbstverständlich kommt es dabei auf die Anwendung an. Tut mir wirklich leid, dass das unverbindliche Beispiel nun ausgerechnet ein strlen()-Ersatz war. War halt nur ein Beispiel, was man mit Hilfe des Prozessor-Caches (und ggf. weiterer interner paralleler Abarbeitungen) erreichen kann. Man kann halt für einen Algorithmus nicht mehr einfach die Prozessorzyklen ermitteln und zusammenzählen (wie beim 80386), sondern muss halt noch mehr berücksichtigen. Mehr wollte ich nicht sagen