Buch für Geschwindigkeitsoptimierung in C/C++

AlexanderKiebler

Also zunächst mal Danke für eure hilfreichen Antworten.

Da ist sehr viel hilfreiches für mich dabei.
Bitte gebt mir doch die Zeit die Info zu ordnen.

P.s.
Nach dem anschauen des der mnemonic-Befehle bin ich immer noch der Überzeugung, dass das was ich machen möchte schneller geht.

Ich verwende GCC in der Version 4.3,
mit den Compiler Flags
CFLAGS = -Wall -ansi -O3 -march=athlon-xp -DVERSION=\"$(VERSION)\"

Ich konnte keine (3D-NOW)MMX befehle finden, wobei diese mit athlon-xp explizit
erlaubt sein sollten oder irre ich mich ??

Dabei wäre über den Vektorrechner die Funktion sehr wohl Parallelisierbar.

Der Athlon XP unterstützt sowohl MMX, 3DNow als auch SSE1.
Tja das sind bspw. Dinge, die man per CPUID direkt vom Prozessor auslesen kann (nur mit Assembler, vesteht sich )

krümelkacker

VF schrieb:

Dinge, die man per CPUID direkt vom Prozessor auslesen kann (nur mit Assembler, vesteht sich )

Mit Intrinsics geht's auch. Soweit ich weiß, bietet mindestens der MSVC Compiler eine intrinsische Funktion für CPUID an.

Ich empfehle Alexander auch mal sich den Assemblercode von dieser Funktion anzugucken:

void axpy(int n, float a, float const x[], float y[])
{
  for (int i=0; i<n; ++i) {
    y[i] = y[i] + a * x[i];
  }
}

Mit -O3 -march=native spuckt mir der GCC eine Funktion raus, die zunächst überprüft, ob die Adressen x und y für SSE "geeignet" sind (alignment). Falls ja, wird eine SSE-optimierte Schleife angesprungen, falls nicht, wird die "normale" Schleife ausgeführt. Das nur mal so als Beispiel. Mich hat das ziemlich beeindruckt und mein Vertrauen in moderne Compiler gestärkt. Ich bin schon an High-Performance-Computing interessiert, aber mein Verlangen, Assembler zu programmieren ist quasi 0. Viel sinniger ist es meiner Meinung nach, die Algorithmen gescheit und Cache-freundlich zu implementieren. Hin und wieder gucke ich mir natürlich auch an, was der Compiler da so ausspuckt. Aber selber schreiben? Nein danke. IMHO Zeitverschwendung. Das höchste der Gefühle sind Intrinsics. Die würde ich im Notfall auch noch einsetzen wollen.

kk

Ich habe einmal in einem halbwegs großen Projekt (~800.000 Zeilen) überprüft, ob wir den asm Code in den 32 Bit Versionen beibehalten, oder nicht. Das Ergebnis war, dass der asm-Code _immer_, manchmal etwas, manchmal sehr viel schneller war.
Neuen asm-Code schreiben wir in der Regel nicht mehr, es ist einfach zu zeitaufwändig.
Ich habe im vorletzten Beitrag auch nur geschrieben, dass sich jeder, der professionell programmieren möchte, sich auch mit den Grundlagen von Assembler vertraut machen sollte. Dass man nicht unbedingt komplexe Funktionen oder gar komplette Programme in dieser Sprache schreiben muss, ist auch klar, dies wird auch nicht zum Grundverständnis benötigt. Dennoch finde ich es faszinierend, dass man auch heutzutage noch Windows-Programme mit eigenem Fenster programmieren kann, deren Binärdatei < 5KB "groß" ist.

AlexanderKiebler

Hi Krümel...

Ja habe mir gestern noch ähnliches angeschaut.
Ebenfalls ne schleife und mit der option -msse2 und -O3 für meinen Prozessor.
-march=athlon-xp reicht komischer Weise nicht, obwohl ich den Text in der Doku so verstanden hab, dass er mir da alles anschält, was mein Prozessor so zu bieten hat.

Schleifen kann er wiklich in SIMD parllelisieren. Aber eben auch nicht jede.
Wenn die arrays als zeiger übergeben werden, dann macht er es zum Beispiel nicht.

Also ist die Frage, wie muss ich meinen C++ code umstellen, damit mir der GCC automatisch mit den richtigen compilerflags den optimalen code erzeugt.
Und schon sind wir mitten im Thema =).....

Ich finds Brutal interessant =)....

Ich kann mir gut vorstellen, dass in bestimmten Sonderfällen der Vektorrechner noch in Assembler programmiert werden kann, so dass man einen geschwindigkeitsvorteil bekommt.

AlexanderKiebler

@ VF

Ja genau, so stell ich mir das schon auch vor. Hab doch schon ein paar kleinigkeiten in Assembler programmiert.

Würde aber in einem großen C++ Projekt generell versuchen Assembler zu vermeiden,
wenn ich nicht den verdacht hätte ein wirklich großen Geschwindigkeitsvorteil zu bekommen, und der zu schreibende Codeteil sehr überschaubar wäre.

Dann bekommt man glaube ich ein echt sehr gutes Gefühl dafür was der Compiler aus dem geschriebenen C/C++-Code macht, wenn man sich angewöhnt den Assmeblercode kurtz an zu schauen.

Also ich finds faszinierend und interessant

Gibts denn ne gute Beschrreibung für die AT&T syntax ???
Oder kann gcc auch Intel ???

AlexanderKiebler

Wie kann ich denn
Cache-freundlich
Prorammieren, und woran erkenne ich wann ich das getan habe ??

Das ist ein wirklich sehr, sehr großes Problem von Assembler. Soweit ich weiß, versteht der gcc nur die AT&T-Syntax, die Intel-Syntax ist jedoch weiter verbreitet und wird bspw. vom MSVC verstanden.
Das von mir vorgeschlagene Buch beleuchtet übrigens auch fast ausschließlich die Intel-Syntax.

Nexus

AlexanderKiebler schrieb:

Wie kann ich denn Cache-freundlich Prorammieren, und woran erkenne ich wann ich das getan habe ??

Es gibt örtliche und zeitliche Cache-Lokalität. Örtlich bezieht sich darauf, dass mehrmals auf nahe gelegene Speicherbereiche zugeriffen wird; zeitlich darauf, dass der Zugriff mehrmals hintereinander oder in kurzen Abständen geschieht.

Beispielsweise kann hier der std::vector gegenüber std::list einen Vorteil ausspielen, da sein Speicher zusammenhängend ist.

SeppJ

AlexanderKiebler schrieb:

und woran erkenne ich wann ich das getan habe ??

Es gibt Profiler für so etwas. valgrind kann das zum Beispiel.

edit: Du fragst über Mikrooptimierung und kennst nicht einmal die Möglichkeiten eines Profilers? Du solltest lernen zu krabbeln, bevor du anfängst zu rennen.

SeppJ schrieb:

AlexanderKiebler schrieb:

und woran erkenne ich wann ich das getan habe ??

Es gibt Profiler für so etwas. valgrind kann das zum Beispiel.

edit: Du fragst über Mikrooptimierung und kennst nicht einmal die Möglichkeiten eines Profilers? Du solltest lernen zu krabbeln, bevor du anfängst zu rennen.

Das einer, der nach allgemeinen "Geschwindigkeitsoptimierungen in C/C++" fragt, nichts kann, ist doch mindestens dreimal offensichtlich.

Yamakuzure

So, jetzt habe ich das Buch.

Es handelt sich um "C++ Coding Standards", von Herb Sutter und Andrei Alexandrescu, 2005. Sehr gutes Buch, kann ich nur empfehlen.

Bevor ich die korrigierten Versionen der letzten beiden Zitate bringe, hier noch ein kleiner Hinweis an meinen Vorgänger im Thread: Nein, denn selbst gestandenen Programmierern ist manchmal nicht klar, das sie Postinkrement/-dekrement-Operatoren meiden sollten, wenn sie mit Objekten wie Iteratoren arbeiten. Es gibt eine Menge Möglichkeiten zur "Geschwindigkeitsoptimierung in C/C++", die alles Andere als trivial sind.

Herb Sutter & Andrei Alexandrescu schrieb:

It is far, far easier to make a correct program fast than it is to make a fast program correct.

Das Dritte waren eigentlich zwei, die mein Gedächtnis zu Einem verschmolzen hatte.

Brian Kernighan & P.J. Plauger schrieb:

Trying to outsmart a compiler defeats much of the purpose of using one

Henry Spencer schrieb:

If you lie to the compiler, it will get its revenge.

An Alle, die meinen, dass das ja "Nur Sprüche" sind: Ja. Aber Sprüche der Wahrheit von Profis, die es besser wissen als du und ich zusammen. Wir wären Idioten, wenn wir nicht von deren Wissen profitierten.

Zeus

Yamakuzure schrieb:

An Alle, die meinen, dass das ja "Nur Sprüche" sind: Ja. Aber Sprüche der Wahrheit von Profis, die es besser wissen als du und ich zusammen. Wir wären Idioten, wenn wir nicht von deren Wissen profitierten.

Sprüche übernehmen ohne die Substanz zu kennen bzw. den Hintergrund ist nicht besonder gut - sieht eher nach Halbwissen aus. Man muss schon einiges mehr Aufwand treiben, damit die Sprüche Akzeptanz finden, reines Zitieren reicht nicht.

volkard

Zum Beispiel wird in manchen Kreisen der Spruch mit der premature optimization so unglaublich überstrapaziert, daß JEDE Anfrage nach Geschwindigkeit damit abgeklatsch wird, wenn man nicht nachweist, daß das Programm verkaufsfertig ist man mit einem Profiler den Bedarf nachgewiesen hat.
http://www.c2.com/cgi/wiki?PrematureOptimization
Ah, wieder ein Grund für eine Sig.

Yamakuzure

Zeus schrieb:

Yamakuzure schrieb:

An Alle, die meinen, dass das ja "Nur Sprüche" sind: Ja. Aber Sprüche der Wahrheit von Profis, die es besser wissen als du und ich zusammen. Wir wären Idioten, wenn wir nicht von deren Wissen profitierten.

Sprüche übernehmen ohne die Substanz zu kennen bzw. den Hintergrund ist nicht besonder gut - sieht eher nach Halbwissen aus. Man muss schon einiges mehr Aufwand treiben, damit die Sprüche Akzeptanz finden, reines Zitieren reicht nicht.

Soll ich noch die betreffenden Seiten und Kapitel nennen, und die Kapitel zusammenfassen? Kann ich gerne machen, aber es wurde nach einer Buchempfehlung gefragt, die habe ich geliefert, und die Zitate sind aus jenem Buch. Ich war der Meinung, dass das offensichtlich ist. Da habe ich mich wohl geirrt.

Edith meint: @volkard: Stimmt, da gebe ich dir absolut Recht. Darf ich deine neue Sig dann auch gegen "Absolute Statements" wie "dynamic_casts sind böse" oder "throw() ist nutzlos" verwenden?

knivil

VF schrieb:

Der Athlon XP unterstützt sowohl MMX, 3DNow als auch SSE1.
Tja das sind bspw. Dinge, die man per CPUID direkt vom Prozessor auslesen kann (nur mit Assembler, vesteht sich )

> cat /proc/cpuinfo

Wohl gemerkt nur unter Linux ...

volkard

Yamakuzure schrieb:

Edith meint: @volkard: Stimmt, da gebe ich dir absolut Recht. Darf ich deine neue Sig dann auch gegen "Absolute Statements" wie "dynamic_casts sind böse" oder "throw() ist nutzlos" verwenden?

Klar. Aber wozu den wackeligen Umweg schreiten? Wende die Sig doch einfach gegen sich selbst an.

krümelkacker

volkard schrieb:

(Sig:) Absolute statements are the root of all evil.

Heheh
War das jetzt gewollt selbstironisch oder hast Du ein "except this one" vergessen? :p

Nexus

Dass alle Pauschalisierungen schlecht sind, ist ja nichts Neues.