[HaBo]

Indi

Anzeige

Hallo HaBo,

ich suche nach Büchern die sich mit der Laufzeit-Optimierung von C++-Programmen beschäftigen.

Konkret geht es darum, die Laufzeit eines Programms, das unter Linux mit g++ kompiliert wird, best möglich zu verringern. Mir geht's nicht/weniger um spezielle Algorithmen, sondern um verschiedenste Aspekte, an die man bei "normalen" Programmen eher nicht denkt: zb. das Vermeiden von Rekursionen oder mehrdimensionalen Arrays, Programmstrukturen, Speicherzugriff/Adressierung oder ähnliche Aspekte.

Dh. ich möchte besser verstehen, was der Compiler bzw. der Prozessor aus meinem Code macht und wie ich unnötige Operationen vermeiden kann.

Nachteile einer solchen Vorgehensweise, wie mangelnde Lesbarkeit des Quellcodes, Portierungsprobleme usw. sind mir bewusst und auch relativ egal.

Weiters bin ich prinzipiell auch nicht abgeneigt, Assembler-Code direkt in meinen C++-Quellcode einzubauen. Allerdings erscheint mir das zum derzeitigen Zeitpunkt noch zu früh. Aber falls in diese Richtung jemand Tipps hat, das Programm läuft derzeit auf einem Intel Core i5 und wird auch langfristig gesehen nur auf Intel-Prozessoren zum Einsatz kommen.

Falls jemand ein paar Ansätze hat und interessante Bücher (englisch/deutsch) in diese Richtung kennt, bin ich für alle Hinweise dankbar.

lg

enkore

Probier erstmal ein paar Compiler aus, neben GCC lohnt sich idR ein Blick auf LLVM. Der kann einige Dinge nämlich um Welten besser optimieren als der GCC (prinzipbedingt).
Ansonsten ist das meiste nicht an die Sprache gebunden, da die Sprachfeatures (abgesehen von Späßen wie RTTI) von C++ eh compile-time sind und daher die Laufzeit kaum beeinflussen.

Grundlegende Ratschläge:
-bei großen Datenstrukturen, besonders mit vielen Entitäten (=> flyweights) entweder spezialisierte Strukturen nehmen (siehe Klammer vor dieser) oder direkt, ganz un-C++ig, direkt auf Speicher arbeiten, d.h. so wie du es in C machen würdest.
-RTTI vermeiden. S.o.
-Häufig aufgerufene Funktionen ("for x in große_liste: calculate(x)") möglichst in modulübergreifenden Dateien, also idR Headers auslagern, um Inlining zu ermöglichen*
-Effiziente Algorithmen verwenden, nicht die schönste/einfachste Datenstruktur nehmen und dann mit schlechten Algorithmen arbeiten, sondern möglichst schnell operierende Datenstrukturen verwenden. Binärbäume sind nicht wirklich schön oder elegant, aber wahnsinnig schnell zu durchsuchen

Wenn du das beachtest, kann man selbst mit großem Aufwand die Perfomance nur noch marginal steigern.

Weitere Schlagwörter: Lazy Evaluation, runtime optimization (wie es z.B. LLVM machen kann), Profiling - grundlegendes Werkzeug um nicht an den falschen Stellen Zeit mit Optimierungen zu verschwenden, ...

* So kann z.B. PyPy in einigen Fällen 2-4 mal schneller sein, als das gleiche Programm in C

__________________

"It is the human race! The deterioration of the spirit of man. Man undermining himself, causing a self-willed, self-imposed, self-evident self-destruction."

+++ BREAKING +++ Troll ertrinkt im Planschbecken +++

Defcon_5

Hast Du Dir schon mal dieses Buch angesehen?: Linux-UNIX-Programmierung. Das umfassende Handbuch - Das Buch von Galileo Computing

Ich hatte mal damit angefangen, hab es dann aber vor einem Jahr wieder verkauft, da ich kein Linux mehr benutze. Ich fand das Buch gut, ob Du aber darin findest was Du speziell suchst weiß ich nicht; gibt eine neuere Auflage.

CDW

Von den Papers von Agner hatte ich einen guten Eindruck:
Software optimization resources. C++ and assembly. Windows, Linux, BSD, Mac OS X
Da gibt es jede Menge "high level" Möglichkeiten, die architekturbedingt z.B deutlich schneller laufen, aber nicht (immer) vom Compiler durchgeführt werden können[0].
Es sollte auch was von Intel geben (intel c++ compiler optimization), wobei das eher auf den Intelcompiler eingeht.

[0] Z.B Zugriffe auf mehrdimensionale Arrays:
vs.
Die erste Version dürfte deutlich langsamer sein (vor allem bei großen Arrays) - da die innere Schleife immer einen "Zeilensprung" macht und der Cache kaum zur Geltung kommt.

__________________
Noch mal, für alle Pseudo-Geeks: 1+1=0. -> 10 wäre Überlauf!
Selig, wer nichts zu sagen hat und trotzdem schweigt.

lookshe

Das dürfte aber kaum Auswirkung haben, da auch mehrdimensionale Arrays letztendlich als eindimensionale abgebildet werden und es somit beides nur eine einfache Pointerarithmetik ist.

Ansonsten wäre noch erwähnenswert, dass man sich mal den Zwischencode des Compilers anzeigen lässt. Dort sieht man oftmals schon einige Optimierungen, die die Compiler aus dem Code machen.

Und bei Schleifen ist noch wichtig, sofern diese eine feste Größe haben (also bspw. for (int i=0;i<4;i++)), dass sie aufgedrösselt werden, also der Inhalt der Schleife einfach 3 mal hingeschrieben wird. Das erspart die Initialisierung der Laufvariable, das Weiterzählen selbiger und letztendlich auch die Prüfung, ob die Endbedingung erreicht ist. Macht zum Beispiel Sinn, wenn man mit Vektoren und Matrizen fester Größe hantiert.

benediktibk

Ich habe Effektiv C++ programmieren von Scott Meyers gelesen und fand das Buch eigentlich recht gut. Nicht alle Dinge darin sind empfehlenswert, einfach nur stur die Ratschläge anwenden würde ich nicht empfehlen, aber wenn man es mit Hirn durchliest hilft es auf jeden Fall weiter.

mfg benediktibk

__________________
The essential prerequisite for building an expert system is to have an expert. - Frederick P. Brooks, Junior

Und wenn Ihr einen Politiker trefft der das gut findet - trefft ihn bitte ordentlich. - Chromatin

enkore

@lookshe:
Das machen Compiler ggf. automatisch. Es bringt fast nie etwas das von Hand zu machen...

__________________

"It is the human race! The deterioration of the spirit of man. Man undermining himself, causing a self-willed, self-imposed, self-evident self-destruction."

+++ BREAKING +++ Troll ertrinkt im Planschbecken +++

CDW

Sicher?

"arr[y][x]" sollte letzendlich in sowas wie
arr_addr + y*row_size + x aufgedröselt werden.
Angenommen wir arbeiten in einem 256 * 256 int Array.
in der ersten Schleife wird so zugegriffen:
1:addr + 0*1024 + 0
2:addr + 1*1024 + 0
3:addr + 2*1024 + 0
...

also in 1 KB Abstand
in der zweiten dagegen

1:addr + 0*1024
2:addr + 0*1024 + 4
Also 4 Byte Abstand.

Die Vor/Nachteile haben nichts mit der Abbildung auf 1 Dimension zu tun, sondern mit dem Abstand zwischen den Speicherzugriffen sowie "Cachelines"

Soweit ich mich entsinne, wird Cache in Blöcken gefüllt - d.h bei einem Cachemiss wird nicht nur 1 Byte nachgeladen, sondern direkt ein ausgerichteter Speicherblock (zumindest vom Prinzip - Details nachzuschlagen überlasse ich hier dem Leser *g* ).

Die zweite Variante dürfte also das Cachen deutlich besser ausnuzten (sofernt die Elementgröße < Cachelinegröße ist, oder so um den Drehe - vereinfacht gesagt nuten Caches die Lokalitätseigenschaften der Programmzugriffe aus - daher sollte man die Lokalität zumindest nicht absichtlich zerstören ).

PS:
"Pointerarithmetik" im Sinne von C/C++ ist optimierungstechnisch sehr problematisch.
Insbesondere bei Arrayzugriffen sollte man eher "natürlichen" Code wählen, anstatt selbstständig mit Pointer zu rechnen - Arrayzugriffe sind sehr häufig gebrauchte Muster und können dementsprechend gut erkannt und optimiert werden.

Edit:

__________________
Noch mal, für alle Pseudo-Geeks: 1+1=0. -> 10 wäre Überlauf!
Selig, wer nichts zu sagen hat und trotzdem schweigt.

Defcon_5

Das mehrdimensionale Felder linear gespeichert werden, daran kann ich mich auch noch erinnern; jedenfalls war es mal so:

benediktibk

Legt ihr alle denn immer alles am Stack ab? Bei mir landen mehrdimensionale Arrays (z.B. Bitmaps) üblicherweise im Heap, und da liegen die Zeilen dann kreuz und quer im Speicher herum. Da ist es schon sinnvoll das per Hand zusammenzufassen in ein eindimensionales Array, wie soll das der Compiler denn auch automatisch machen.

Noch ein kleiner Tipp zum Optimieren: Zuerst herausfinden was wirklich lange dauert (Profiler oder einfach ein paar Zeitmessungen im Code) und erst dann optimieren anfangen. Da reicht es dann häufig eine oder zwei Funktionen zu optimieren weil eh 95% der Laufzeit dort draufgehen. Den Rest sollte man lieber so lassen wie er ist, da er dann höchst wahrscheinlich besser lesbar bleibt und eine Optimierung nicht wirklich merkbar wäre. Für den User bemerkbar sind Beschleunigungen um zum Beispiel den Faktor 2. Ob das Dingens aber 10% schneller ist wird dir als Benutzer nicht wirklich auffallen. Und so große Verbesserungen erreicht man üblicherweise nur durch einen besseren Algorithmus.
Ich will damit jetzt aber niemanden vom Optimieren abhalten, man sollte aber nur dann Optimieren, wenn es Sinn macht. Oft ist die bessere Wartbarkeit ein guter Grund die langsamere Variante zu wählen.

mfg benediktibk

__________________
The essential prerequisite for building an expert system is to have an expert. - Frederick P. Brooks, Junior

Und wenn Ihr einen Politiker trefft der das gut findet - trefft ihn bitte ordentlich. - Chromatin

BieblSoft

Hallo,

zunächst mal möchte ich einigen der "Vorredner" in folgenden Punkten beipflichten:

1. "Vertraue moderner Compiler-Technologie"
Die Optimierungsmöglichkeiten des Compilers sind excellent und in vielen Fällen auch manuell nicht zu verbessern.
Selbst der Versuch, in Assembler oder C Laufzeitgewinne gegenüber optimiertem C++ Code zu erreichen, ist sinnlos, der optimierende Compiler ist allemal besser. Also @Indy: vergiss inline-Assembler !
Wer es nicht glaubt: Ich sende gerne Testcode zu

2. RTTI vermeiden
immer empfehlenswert, da es nur kostet und so gut wie nichts bringt. Einziger Verlust ist der dynamic_cast, aber es geht auch ohne den ganz gut.
In bestimmten Fällen Exception Handling ausschalten. Der verzicht bringt zusätzlichen Speicher und Geschwindigkeit, wenn man darauf verzichten kann.

3. Gute Algorithmen verwenden
Das gilt in erster Linie für die STL. Hier kann man aber sagen, dass die besten Algorithmen meist die sind, die der Container ohnehin bereitstellt, denn diese sind auf den jeweiligen Container optimiert.
Der häufigste Fehler ist der, den falschen Container zu benutzen oder den richtigen Container mit den falschen Methoden zu benutzen.

Zusätzlich möchte ich noch raten, bestimmte Code-Konstrukte zu vermeiden, wie z.B. den Bedingungsoperator. Einfach nur Mist, und fast immer schlechter als eine normale Fallunterscheidung. Lasst euch mal ein Assembler-Listing erzeugen und vergleicht mit normalem "if". Im besten Fall erzeugt der Bedingungsoperator identischen Code (z.B. bei gcc), im schlechtesten erheblich mehr Code (Microsoft, ohne Optimierungen)
Wieder: sende gerne Testcode zu, um zu beweisen, was ich behaupte

Virtualität wenn möglich vermeiden !
Virtual calls benötigen 10% mehr Laufzeit. Ebenso wird eine Menge zusätzlicher Speicher verbraten (VTable pro Klasse, pointer to vtable pro Objekt)

Templates verwenden ! Hier kann viel vom Compiler erledigt werden, was dann nicht zur Laufzeit ins Gewicht fällt.

Buchtip: "write great Code" von Randall Hyde, No starch press, 2 Bände.
Und alles von Scott Myers (hier aber darauf achten, die neuesten Auflagen zu nehmen, nur dort verwendet er massiv Templates.

Indi

Vielen Dank Leute für die zahlreichen und tollen Anregungen; insbesondere für den Link an CDW bzw. die Buchtipps an BieblSoft. Hatte nicht mit sovielen Antworten gerechnet.

Damit dürfte ich jetzt einige Zeit beschäftigt sein. Thx nochmal.