Buch für Geschwindigkeitsoptimierung in C/C++

[krümelkacker]

AlexanderKiebler schrieb:

Bietet Effective C++ in der Hinsicht etwas ??

Nein. Ist aber trotzdem ein gutes Buch, was Du besitzen solltest.

Ich habe ein bisschen den Eindruck, dass Du an der falschen Stelle optimieren willst. Design+Datenstrukturen+Algorithmen ist ein nicht zu unterschätzender Aspekt. Alles andere sind eher "Micro-Optimierungen" -- es sei denn, Du weißt es wirklich besser und kannst zB den SSE-Befehlssatz für einen kleinen Programmteil effektiver einsetzen als der Compiler selbst. Compiler sind aber heutzutage sehr sehr gut. Guck Dir doch einfach mal den Assembler-Code an, den dein Compiler generiert. Mit GCC & co kannst Du das zB so machen:

objdump -Cd soundso.o

Wenn Dir der Assemblercode nicht gefällt, kannst Du eventuell Dein C++ Programm etwas anpassen, andere Optimierungsoptionen verwenden und gucken, wie sich der Assembler-Code verändert. Wenn Dir das dann immer noch nicht gefällt, kannst Du den Teil ja immer noch in Assembler selbst schreiben. Aber bevor Du das machst, kannst Du auch nochmal in die Doku Deines Compilers gucken, ob er nicht noch nette Erweiterungen bietet, wie zB Intrinsics.

Speicherzugriffsmuster sind auch ein nicht zu unterschätzender Aspekt bzgl Performanz. CPUs sind schnell, Zugriffszeiten zum Speicher sind relativ hoch. Ordne Deine Daten geschickt im Speicher an und greife möglichst "linear" drauf zu -- also so, dass die Daten, die schon im Cache sind, wieder verwendet werden können bzw das Hardware-Cache-Prefetching dein Zugriffsmuster erkennt und dementsprechend Daten im voraus anfordern kann. Eine solche Umorganisation hat mir vor ein paar Wochen einen Geschwindigkeits-Faktor von 7 eingebracht. SIEBEN!

AlexanderKiebler schrieb:

Dann würde ich mich noch für ein Buch interessieren, welches sich damit beschäftigt, wie man Assembler in C/C++ einbindet.

Das ist Compiler-spezifisch. Siehe Dokumentation Deines Compilers.

AlexanderKiebler schrieb:

Auch mit dem Augenmerk darauf, wie ich meinen Code dann für bestimmte Prozessoren unterstützen kann durch getrennte Compilierung. Bitte keine Kommentare bezüglich braucht man nicht weil die Compiler so gut sind.

Upps ... Zu spät! :p
Vielleicht solltest Du diese Kommentare auch mal ernst nehmen. Das sagt man ja nicht nur einfach so...

Gruß,
kk

[AlexanderKiebler]

Hi,

Also ich würde mich immer noch für die beiden genannten Buchempfehlungen interessieren.=)

@Krümel...
Also mit Qualifizierer "register" bei oft verwendeten Variablen in einer Methode/Funktion,
und kurtze oft aufgerufene Funktionen mit "inline" ??

Effektiv C++ wird ohnehin gekauft, aber dachte es erhöht ev. die Vorfreude, wenn ich interessantes zu genau dem Thema da finde.
Bin grad am Sparen.

Hast ne Buchempfehlung ??

Dass ich auf der Algo. Seite viel mehr Geschwindigkeit gewinne, weiß ich.
(Unter der Vorraussetzung dass der Vorgänger nicht bereits das Optimum erreicht hat)
Das ist eben Mathe, und darum kümmere ich mich an anderer Stelle.
Ich interessiere mich wirklich für genau die Optimierungen, welche auf der
Implementierungsseite gewonnen werden können.

Also wie implementiere ich einen Vorgegebenen Algorithmus geschwindigkeitsoptimal,
Und nicht wie finde ich zu einem gegeben Problem den schnellsten algo.
Das ist auch ein Problem, aber das würde ich gerne trennen.

Ich gehe also davon aus, dass bei der Implementierug die Frage nach dem richtigen Algo. geklärt worden ist.

Gruß

[volkard]

AlexanderKiebler schrieb:

@Krümel...
Also mit Qualifizierer "register" bei oft verwendeten Variablen in einer Methode/Funktion, und kurze oft aufgerufene Funktionen mit "inline"?

Beides ist inzwischen Unfug.

[Yamakuzure]

Donald Knuth schrieb:

We should forget about small efficiencies, say about 97% of the time: premature optimization is the root of all evil

Und ich habe noch zwei Zitate, die aus einem Buch kommen, das sich tatsächlich mit "premature optimization/pessimization" beschäftigt. Es ist eine Weile her, und es steht bei mir im Büro. Ich kann dir Titel und Autoren also leider erst am Montag mitteilen. (Dann werde ich auch die Quellen der folgenden beiden Zitate nachtragen, und die Zitate, wenn nötig, korrigieren)

Quelle unbekannt schrieb:

Es ist sehr leicht ein korrektes Programm schnell zu machen, aber anders herum fast unmöglich.

Quelle unbekannt schrieb:

Wenn du glaubst, dass du es besser weißt als dein Compiler, wird sich dein Compiler an dir rächen. Fürchterlich.

[interessant]

[volkard]

Yamakuzure schrieb:

...

Das sind bloß Sprüche für Leute, die Sprüche brauchen.

Struppi bringt es in der Bibel viel besser auf den Punkt, wo er sagt, daß Performance-Überlegungen von Anfang an die Entwicklung des Programms begleiten müssen.

Und ich sage, daß es gut ist, seine Sprache und seinen Compiler genau zu kennen, auch in den unwichtigen Grenzfällen, über die keiner ein Buch schreibt. Früher oder später kommt mal die Gelegenheit, die Konkurrenz wie zufällig platt zu machen, vernichtend zu schlagen, weil man einfach ein besseres Gefühl für das Werkzeug entwickelt hat.

[krümelkacker]

AlexanderKiebler schrieb:

@Krümel...
Also mit Qualifizierer "register" bei oft verwendeten Variablen in einer Methode/Funktion,
und kurtze oft aufgerufene Funktionen mit "inline" ??

Ich verstehe die Frage nicht. Das Schlüsselwort "register" ist bei den modernen Compilern, die wir haben, eher überflüssig. Ich würde sogar vermuten, dass moderne Compiler mit schlauer Register-Allozierung sich von dem Schlüsselwort nicht wirklich beeindrucken lassen. Der aktuelle Entwurf des kommenden C++ Standards enthält sogar diesen Text:

A register specifier is a hint to the implementation that the variable so declared will be heavily used. [ Note: the hint can be ignored and in most implementations it will be ignored if the address of the variable is taken. This use is deprecated (see D.4). — end note ]

Zum inline Schlüsselwort gibt es zwei wichtige Punkte:

(1) Es beeinflusst die Semantik des Programms bzgl der "one definition rule".

(2) Was das tatsächliche "inlining" angeht, ist es nur ein Hinweis für den Compiler.

Der Effekt von (1) ist der, dass Du in jeder Übersetzungseinheit, in der Du eine bestimmte Inline-Funktion benutzen willst, auch die Definition derselben Inline-Funktion vorhanden sein muss. Das erleichtert es dem Compiler natürlich, diese tatsächlich "zu inlinen" -- oder zumindest zu überprüfen, ob es sich lohnen könnte. Man denke nur an getrennte Übersetzung und wie wenig verbreitet "link time optimization" ist. Das "Inlining" bzw die Überprüfung ist natürlich nicht auf Inline-Funktionen beschränkt. Innerhalb einer Übersetzungseinheit könnte ein Compiler natürlich auch nicht-Inline-Funktionen "inlinen" -- nach der as-if-Regel.

AlexanderKiebler schrieb:

Hast ne Buchempfehlung ??

Leider nicht.

[VF]

Ob es sich lohnt, inline asm in die eigene Anwendung einzubauen, muss sehr gründlich nachgemessen werden. Asm-Code ist länger, schwerer nachzuvollziehen und daher schwerer zu warten. Zu allem Überfluss dauert es gewöhnlich auch noch wesentlich länger, ihn zu schreiben.
Ich bin jedoch der Meinung, dass sich jeder C/C++-Programmierer auch mit den Grundlagen von Assembler vertraut machen sollte. Ein gutes Buch für den Einstieg bietet Joachim Rohde (http://www.amazon.de/Assembler-Grundlagen-Programmierung-Joachim-Rohde/dp/3826614690/ref=sr_1_1?ie=UTF8&s=books&qid=1286023408&sr=8-1). Dieses Buch geht zwar nicht auf den SSE-Befehlssatz ein, ein Einarbeiten kann aber nach Verständnis der Grundlagen auch online geschehen. Außerdem ist es mMn didaktisch hervorragend aufgebaut.

Ach ja, viele Spielehersteller sind mittlerweile davon abgerückt, asm zu verwenden, erstens wegen der Portierung, zweitens wegen des Zeitdrucks. Algorithmen und Datenstrukturen zu "tunen" ist i.d.R. weniger zeitintensiv.

Solltest du dennoch weitermachen wollen, findest du hier eine kleine, hilfreiche Code-Table (http://www.jegerlehner.ch/intel/index_de.html).

We should forget about small efficiencies, say about 97% of the time: premature optimization is the root of all evil

Das ist untertrieben, inline asm kommt für höchstens 1% des Codes in Frage.

[Athar]

AlexanderKiebler schrieb:

Also mit Qualifizierer "register" bei oft verwendeten Variablen in einer Methode/Funktion,
und kurtze oft aufgerufene Funktionen mit "inline" ??

Eben nicht. Ich zitiere nochmal:

krümelkacker schrieb:

Vielleicht solltest Du diese Kommentare auch mal ernst nehmen. Das sagt man ja nicht nur einfach so...

Gerade register und inline werden von modernen Compilern schlicht und einfach ignoriert, da sie diese Entscheidungen i.d.R. besser treffen können.

Wenn du effizient programmieren möchtest, solltest du in Grundzügen mit deiner Ziel-CPU vertraut sein - z.B. dass Division vergleichsweise langsam ist, du solltest über potenzielle Probleme mit conditional jumps Bescheid wissen, über den Cache usw.
Zweitens solltest du wissen, wie dein Compiler verschiedene Sprachmittel letztendlich auf Assemblerebene implementiert. Das meiste dürfte recht offensichtlich sein, in den anderen Fällen kannst du dir jederzeit den Assembleroutput ansehen.
Und drittens und vielleicht am wichtigsten: du solltest wissen, wie weit die Optimierungsfähigkeiten deines Compilers gehen und wo seine Grenzen sind. Da du den Compilern jetzt (noch) nicht viel zuzutrauen scheinst, wirst du in deinen Nachforschungen hier so manche Überraschung erleben.

Wenn du über alle vier (der letzte ist "Algorithmen und Datenstrukturen") Punkten einigermaßen gut informiert bist, wirst du automatisch schnelle Programme schreiben. Denn meist hat man für ein Problem mehrere mögliche Lösungswege, die sich an Aufwand, Lesbarkeit und Wartbarkeit kaum unterscheiden, ab und zu aber in ihrer Effizienz. Wenn du das richtig einschätzen kannst, wirst du unbewußt immer die effizienteste Variante nehmen.

[Nexus]

AlexanderKiebler schrieb:

Also wie implementiere ich einen Vorgegebenen Algorithmus geschwindigkeitsoptimal

Auch hier gibt es Punkte, bei deren Beachtung du um einiges mehr herausholen kannst als bei Mikro- und Pseudooptimierungen.

Punkte, bei denen du ansetzen könntest, wären unter Anderem:

• Wahl der richtigen Datenstrukturen
• Caching von mehrfach benötigten Daten statt erneuter Berechnung
• Vermeidung von vielen kleinen dynamischen Allokationen oder Einsatz eines speziellen Allokators
• Verwendung von vorgefertigten, optimierten Lösungen (z.B. STL-Algorithmen oder Boost.Graph) statt eigener Implementierung
• Beachtung technischer Merkmale wie Cache-Lokalität oder Ausnutzung mehrerer Prozessorkerne
• Vermeidung unnötiger Kopien durch Referenzen, Swap, RVO, Move-Semantik

Hingegen solltest du den Zweck folgender "Optimierungen" kritisch hinterfragen und wirklich nur einsetzen, wenn die Alternativen bereits ausgereizt sind und der zusätzliche Performancegewinn entscheidend ist:

• inline – sollte primär verwendet werden, um Funktionen im Header definieren zu können
• register – kann im Normalfall komplett vergessen werden
• Übermässiger Einsatz von const im Glauben, es steigere die Performance
• Bit-Hacks, die der Compiler gut selbst optimieren kann (z.B. x << 1 statt 2*x ) und die auf Kosten der Übersicht gehen
• Verzicht auf Kapselung, weil Funktionsaufrufe ja langsam sind
• Inline-Assembler
• Zeiger-Frickeleien, die undefiniertes Verhalten erzeugen (z.B. reinterpret_cast zwischen inkompatiblen Typen)

[asdfghjkl]

volkard schrieb:

Und ich sage, daß es gut ist, seine Sprache und seinen Compiler genau zu kennen, auch in den unwichtigen Grenzfällen, über die keiner ein Buch schreibt. Früher oder später kommt mal die Gelegenheit, die Konkurrenz wie zufällig platt zu machen, vernichtend zu schlagen, weil man einfach ein besseres Gefühl für das Werkzeug entwickelt hat.

Das sind bloß Sprüche für Leute, die Sprüche brauchen.

[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.

[VF]

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

[VF]

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 ??

[VF]

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.