Übung zu »malloc« (Nachtrag)

/    Übungsaufgabe Experimente zu Speicheranforderungen

Versuchen Sie durch Ausprobieren zu ermitteln, wie sich eventuelle Speicherbeschränkungen Ihrer C -Implementation in den folgenden sechs Fällen bemerkbar machen:

• Es wird versucht einen sehr großen Speicherbereich mit statischer Lebensdauer anzufordern.
• Es wird versucht sehr viele kleine Speicherbereiche mit statischer Lebensdauer anzufordern.
• Es wird versucht einen sehr großen Speicherbereich mit automatischer Lebensdauer anzufordern.
• Es wird versucht sehr viele kleine Speicherbereiche mit automatischer Lebensdauer anzufordern.
• Es wird versucht einen sehr großen Speicherbereich mit allozierter Lebensdauer anzufordern.
• Es wird versucht sehr viele kleine Speicherbereiche mit allozierter Lebensdauer anzufordern.

Hinweis Das oben verwendete Wort „sehr“ stammt vom althochdeutschen Adverb „sēro“, das „schmerzlich“ bedeutet, und soll oben jeweils Größen oder Mengen beschreiben, die so groß sind, daß sich das Verhalten des Systems erkennbar von Anforderungen kleiner Größen oder Mengen unterscheidet.

Hinweis Bei der Anforderung von Speicher wird manchmal nur ein Adreßbereich reserviert, so daß der Eindruck entstehen könnte, daß mehr Speicher verfügbar ist als physikalisch vorhanden, selbst wenn eine Auslagerungsdatei auf der Festplatte berücksichtigt wird. Falls sichergestellt werden soll, daß der angeforderte Speicher auch wirklich vorhanden  ist, so kann dies dadurch erzwungen werden, daß Daten in diesen geschrieben werden.

Hinweis Wenn ein Prozeß zur Laufzeit viel Speicher reserviert, kann dies die Reaktionszeit des gesamten Systems vergrößern oder dazu führen, daß andere Prozesse beendet werden, um Speicher freizugeben (“OOM killer ”).

Hinweis Durch das Kommando »ulimit« (csh: »limit«) können unter Linux  Speicherbegrenzungen für Prozesse festgelegt werden (»man sh«, »man bash« beziehungsweise »man csh«).

Optimierung in C 

„Ich versuche nicht, schnell zu sein,
ich versuche nur, genau zu sein.“

— unbekannter Westernheld auf die Frage nach dem Geheimnis seiner Schnelligkeit

Begriffsdefinition

Eine funktionale Eigenschaft  eines Systems ist eine Aussage über sein Verhaltens oder seine Ausgabe, die nichts über Ressourcennutzung sagt, zu der in diesem Zusammenhang auch die Nutzung der verfügbaren Zeit – also die Geschwindigkeit  – gezählt wird.

Unter Refaktorierung  eines Programms versteht man solch eine Veränderung des Quelltextes, welche keine Veränderung der funktionalen Eigenschaften dieses Programms zur Folge hat. Sie kann beispielsweise mit der Absicht einer Verbesserung von Lesbarkeit und Wartbarkeit  erfolgen.

Eine nichtfunktionale Eigenschaft  eines Systems beschreibt die Nutzung von Ressourcen durch das System, also etwa den Bedarf an Rechenzeit  oder Speicherplatz.

Auch Softwareprojekte  selber haben funktionale Eigenschaften (Erzeugung eines bestimmten Produkts) und nichtfunktionale Eigenschaften (Einhaltung bestimmter Termine und Kosten).

Meist werden mit Quelltext nur die funktionalen Eigenschaften direkt  kodiert. Die nichtfunktionalen Eigenschaften lassen sich normalerweise nicht direkt oder unabhängig davon einstellen, weil sie sich durch bestimmte – manchmal komplizierte – technische Gesetzmäßigkeit aus dem Quelltext und der Umgebung ergeben. Dennoch können die nichtfunktionalen Eigenschaften durch mehr oder weniger aufwendiges Tüfteln manchmal wenigstens tendenziell in eine bestimmte Richtung oder bis zu einer bestimmten Grenze in gewollter Weise beeinflußt werden.

Unter Optimierung  versteht man meist die Refaktorierung eines Programms mit dem Ziel der Verbesserung nichtfunktionaler Eigenschaften, meist mit dem Ziel der Verminderung der Rechenzeit. (Der Begriff ist vielleicht irreführend gebildet, da Optimierung eines Programms normalerweise niemals beweisbar zu einem „Optimum“ führt, sondern nur die Verbesserung  einer nichtfunktionalen Eigenschaft auf Kosten anderer nichtfunktionaler Eigenschaften bezeichnet.)

Eine Mikrooptimierung  ist die Optimierung eines kleinen Details an einer Stelle eines Quelltextes.

Ein Benchmark  ist ein Testverfahren, mit dem Eigenschaften von Programmen, wie etwa deren Geschwindigkeit miteinander verglichen werden (oder ein solch ein Verfahren verwendender Test).

Ein Microbenchmark  ist ein Benchmark zur Untersuchung von Mikrooptimierungen.

Die Laufzeitanalyse  (englisch “profiling ”) ist die Untersuchung des Ablaufs eines Programms mit dem Ziel zu erfahren, wieviel Zeit von einzelnen Programmteilen gebraucht wird.

Mit Architektur  meint man die Grobgliederung eines großen Programms und den Programmaufbau betreffende strategische Entscheidungen. Die Übergänge zwischen Architektur, Entwurf und Programmierung sind aber fließend.

Das Dreieck der Qualität

Eine Faustregel besagt:

• Wenn ein Software-Produkt schnell und gut  sein soll, dann wird es teuer.
• Wenn ein Software-Produkt schnell und billig  sein soll, dann wird es schlecht.
• Wenn ein Software-Produkt gut und billig sein  soll, dann wird es langsam.
• Aber es ist nicht  möglich, ein Software-Produkt billig, gut und schnell  zu machen.

Diese Regel faßt man auch im „Dreieck der Qualität zusammen

Dreieck der Qualität: Man kann daraus zwei Eigenschaften auswählen

             schnell
               /\
              /  \
             /    \
            /      \
           .________.
        billig     gut

Die Projektkosten repräsentieren dabei den Projektaufwand, der mit der Dauer und der Größe des Projektes verbunden ist.

Eine aktuelle Meldung berichtet etwas Ähnliches (Beziehung zwischen Qualität, Eile und Effizienz)

http://www.heise.de/newsticker/meldung/Umfrage-Geringe-Qualitaet-und-Effizienz-durch-uebereilte-Software-Releases-903653.html

Allgemeine Erfahrungen

“Speed Kills! ”

www.speedkills.org

Ein berühmtes Zitat zur Optimierung

“We should forget about small efficiencies, say about 97% of the time: premature optimization is the root of all evil. Yet we should not pass up our opportunities in that critical 3%. A good programmer will not be lulled into complacency by such reasoning, he will be wise to look carefully at the critical code; but only after that code has been identified.”

Donald E. Knuth

Donald E. Knuth, "Structured Programming With Go To Statements,"; Computing Reviews. Vol. 6, December 1974, p. 268.

Ein weiteres berühmtes Zitat zur Optimierung

“The First Rule of Program Optimization: Don't do it. The Second Rule of Program Optimization (for experts only!): Don't do it yet.”

Michael A. Jackson

Zur Optimierung gibt es viele – teilweise widersprüchliche – Empfehlungen. Einerseits soll man Quellcode zunächst schreiben ohne an Optimierung zu denken, denn zu oft verschlechtert die zu frühe Berücksichtigung von Optimierungszielen die Qualität des Quelltextes. Andererseits sind eine frühe strategische Entscheidungen der Projektplanung später kaum noch rückgängig zu machen, so daß manchmal eine rechtzeitig Berücksichtigung von Optimierungszielen geboten sein kann.

Man kann beispielsweise sagen, daß die Wahl von Algorithmen am Anfang bestimmte Aspekte der Effizienz schon weitgehend festlegt, weil das Austauschen von Algorithmen in späteren Projektphasen zu aufwendig sein kann. Andererseits könnte man aber Schnittstellen von Anfang an auch so festlegen, daß Algorithmen hinter diesen verborgen werden und auch in späteren Projektphasen leicht ausgetauscht werden können.

Softwareprojekte scheitern oft daran, daß sie sich als zu ambitioniert erweisen. Deswegen sollte bei Projektbeginn die Aufgabenstellung weitestmöglich vereinfacht werden und kein Gedanken an Optimierung verschwendet werden. Es sollte lediglich versucht werden, den Weg zu einer späteren Erweiterung und Optimierung nicht zu verbauen. Besonderes Augenmerk gilt dann der Korrektheit der Implementation (die für das Produkt festgelegten funktionalen Eigenschaften müssen implementiert werden) und der Übersichtlichkeit des Quellcodes (er soll leicht verständlich und wartbar sein).

Das Wort „Definition“ kommt vom lateinischen „definire“, was „begrenzen“ und „abgrenzen“ bedeutet. Dieses sind genau die wichtigen Schritte am Anfang eines Projekts, also bei der Projektdefinition : Zuerst muß das Projekt nach außen hin begrenzt  werden: Der wichtigste Teil der Projektdefinition ist es, festzulegen, was alles nicht  Teil des Projekts sein soll, denn um so größer die Ambitionen sind, desto schwieriger wird im allgemeinen deren Realisierung werden. Es folgt dann die Abgrenzung  von Teilprojekten untereinander, also die Definition von Schnittstellen. Diese Festlegungen sind später tatsächlich nur noch schwer zu ändern, denn wenn man eine Einheit ändert, die sich hinter einer Schnittstelle befindet, dann muß man nur diese Einheit ändern. Von der Änderung einer Schnittstelle können aber viele Einheiten und Dokumente betroffen sein. Daher ist die Festlegung von Schnittstellen nach außen und im Inneren die kritischste Aufgabe bei der Projektplanung und wird oft erfahreneren Entwicklern zugewiesen.

Wenn das Produkt bei einer Erstellung ohne Berücksichtigung von Optimierung schon schnell genug ist, ist ja keine weitere Optimierung nötig und es können dann weitere – zunächst weggelassene – Eigenschaften implementiert werden. Man hat somit nicht unnötig Zeit für eine gar nicht nötig Optimierung aufgewendet.

“Don't optimize until you know you have a problem.” ist ein Spezialfall von “If it ain't broke, don't fix it.”

Nur, wenn  das Produkt sich dann als zu langsam erweist, wird Optimierung nötig. Aber auch hier sollte wiederum die Arbeitszeit des Programmierers nicht verschwendet werden. Es zeigt sich, daß die meisten Programme den größten Teil ihrer Rechenzeit nur in einigen wenigen Programmteilen verbringen. Diese Programmteile können mit einem Laufzeitanalysator (“profiler ”) gefunden werden. Der Programmierer sollte nicht versuchen. ohne Laufzeitanalysator zu vermuten, wo das Programm seine Zeit verbringt, da solches Raten oft falsche Ergebnisse liefert.

Dann kann versucht werden, dies zu optimieren.

Rob Pike's 5 Rules of Programming

Rule 1. You can't tell where a program is going to spend its time. Bottlenecks occur in surprising places, so don't try to second guess and put in a speed hack until you've proven that's where the bottleneck is.

Rule 2. Measure. Don't tune for speed until you've measured, and even then don't unless one part of the code overwhelms the rest.

Rule 3. Fancy algorithms are slow when n is small, and n is usually small. Fancy algorithms have big constants. Until you know that n is frequently going to be big, don't get fancy. (Even if n does get big, use Rule 2 first.)

Rule 4. Fancy algorithms are buggier than simple ones, and they're much harder to implement. Use simple algorithms as well as simple data structures.

Rule 5. Data dominates. If you've chosen the right data structures and organized things well, the algorithms will almost always be self-evident. Data structures, not algorithms, are central to programming.

Bei der Umsetzung von Optimierungen könnten auch Fehler eingebaut werden. Hier kann ein automatisches Testsystem helfen.

Oft ist eine bestimmte Optimierung nur bei Verwendung einer bestimmten C -Implementation und einer bestimmten Laufzeitumgebung vorteilhaft, während sie bei einer anderen das Programm wieder ausbremsen könnte. Wenn man also optimieren muß, dann unter der Umgebung, die auch im Normalbetrieb verwendet wird und mit Messen der Auswirkungen jedes Eingriffs. Auf keinen Fall darf man sich hier darauf verlassen, daß man die Auswirkungen an Hand des Quelltextes schon selber beurteilen kann.

Optimierungen können die Qualität des Quelltextes verschlechtern: Durch die Notwendigkeit zur Berücksichtigung einer bestimmten Umgebung wird ein optimiertes Programm eng an diese Umgebung gebunden und ist dann weniger portabel. Auch wird der Quellcode durch Optimierung manchmal aufgebläht oder verkompliziert, was die Wartbarkeit eines Programms so weit vermindern kann, daß Änderungen daran sehr aufwendig und Fehlersuchen erschwert werden.

Es ist nun hoffentlich klar geworden, daß solange keine Gedanken an Optimierungen verschwendet werden sollten, solange noch keine Probleme mit der Laufzeit bekannt sind, weil die Optimierung oft auf Kosten anderer Projektziele und Qualitäten von Software geht. Allerdings wird man von Anfang an, Algorithmen und Architekturen vermeiden, die als besonders ineffizient bekannt sind, wenn sie sich ohne besonderen Aufwand oder Einschränkungen anderer Qualitäten umgehen lassen.

Optimization: Your Worst Enemy

2008-04-20

Dr. Joseph M. Newcomer

http://www.flounder.com/optimization.htm

Für die praktische Arbeit sehr empfehlenswerter Text über Optimierung.

2010-01-13T02:11:38+01:00

Supercompiling Java Programs

2002-04

Ben Goertzel, Andrei Klimov, Arkady Klimov

http://www.supercompilers.com/white_paper.shtml

Über die theoretischen Möglichkeiten automatischer Optimierung.

2010-01-13T02:45:30+01:00

Automatische Optimierung

Die meisten Compiler optimieren heute bereits bei der Übersetzung. Sie erkennen beispielsweise einige in C -Programmen wiederkehrende Konstrukte und ersetzen diese durch effiziente Maschinensprachenanweisungen.

Diese führt dazu, daß manche gutgemeinten manuellen Optimierungen im Quellcode ein Programm tatsächlich bremsen, weil sie den Quelltext so verwirren, daß der Compiler keine gewohnten Muster mehr findet und dann nicht mehr optimieren kann. Daher lautet eine Empfehlung zur Optimierung, einfachen, übersichtlichen und naheliegenden Code zu schreiben, weil diese die besten Ansatzpunkte für eine automatische Optimierung bietet.

Bei »gcc« kann die stärkste Stufe 3 der Optimierung mit »-O3« verlangt werden. Diese ist aber nicht voreingestellt, weil eine stärkere Optimierung manchmal zu Fehlern führt.

So wurde nach »struct sock *sk = tun->sk;« die Anweisung »if (!tun) return POLLERR;« als »return POLLERR;« übersetzt. Dies ist zwar zulässig, da »tun->sk« undefiniertes Verhalten hätte, wenn »tun« 0 wäre, aber führte in einem Fall zu einem Sicherheitsproblem.

http://www.heise.de/newsticker/meldung/142171*/?view=print

http://www.heise.de/security/meldung/Root-Exploit-fuer-Linux-Kernel-veroeffentlicht-6901.html?view=print

Analyse

“It's really all about measurement if you want fast code.”

Carl Cook  (at the cppcon 2017 )

80 % der Laufzeit werden in 20 % des Codes verbraucht. (Faustregel)

Es ist schwierig oder unmöglich, an Hand eines Quelltextes zu erkennen, an welchen Stellen ein Prozeß die meiste Zeit verbraucht, da dies von Umständen der Laufzeitumgebung abhängt. Da aber – falls eine Optimierung überhaupt nötig ist – nur die Stellen gezielt optimiert werden sollten, die auch tatsächlich zeitkritisch sind, müssen diese Stellen zunächst unter der Zielumgebung ermittelt werden.

Außerdem sollte der Code bereits soweit refaktoriert (gepflegt) worden sein, daß er modular und frei von Wiederholungen ist, da sonst eine Analyse des Laufzeitverhaltens erschwert wird.

Compilerausgabe lesen (statische Analyse)

Wie ein bestimmter Programmteil übersetzt wird, kann direkt aus der Compiler-Ausgabe gelesen werden. Dazu müßte man allerdings die dort verwendete Assemblersprache kennen. Die Bedeutung von Assemblerprogrammen kann aber vielleicht auch manchmal ohne diese Kenntnis erraten werden.

Eine Assemblerausgabe kann beispielsweise die Frage beantworten, ob die switch -Anweisung in dem folgenden Programm in eine Sprungtabelle übersetzt wird, oder ob mehrere Vergleiche hintereinander ausgeführt werden.

Anlegen und Ausgeben eines Baumes

#include <stdlib.h> /* rand */
int main( void )
{ switch( rand() )
  { case 0: return 3; break;
    case 1: return 1; break;
    case 2: return 4; break;
    case 3: return 1; break;
    case 4: return 5; break;
    case 5: return 9; break;
    case 6: return 2; break;
    case 7: return 6; break;
    case 8: return 5; break;
    case 9: return 3; break; }}

Konsole

gcc -S test.c -O3 -o -

Die Assemblerausgabe wird mit der Option »-S« verlangt.

Mit »-o -« wird die Ausgabe auf die Konsole gelenkt.

Präsenzübung

Erraten Sie aus der Ausgabe des Compilers, ob die obige switch -Anweisung in eine Folge von Vergleichen oder in eine Sprungtabelle übersetzt wurde.

In dem obigen Programm findet sich die Anweisungsfolge »return 1; break;« zweimal. Gibt es auch für jede ihrer Wiederholungen ein entsprechendes Stück Assemblercode?

Prozeßanalyse (dynamische Analyse)

Den Ergebnissen von Zeitmessung darf nicht blind vertraut werden, weil diese manchmal empfindlich auf Störungen reagieren. Daher sollte solche Messungen wiederholt werden. Dabei kann beispielsweise die Reihenfolge zweier Anweisungen vertauscht werden, wenn diese verglichen werden sollen, weil es sein könnte, daß die Ausführungsgeschwindigkeit einer Anweisung auch von ihrer Reihenfolge abhängt. Sie könnte sonst fälschlicherweise der Anweisung selber zugeschrieben werden (das wird auf einem anderen Gebiet auch „fundamentaler Attributionsfehler“ genannt).

time

Das Kommando »time« zeigt verschiedene von einem Prozeß verwendete Ressourcen an.

Konsole

$ time gcc test.c
0.036u 0.012s 0:00.19 21.0%     0+0k 3832+32io 4pf+0w

Die genaue Bedeutung der Ausgabe kann mit »man time« erlernt werden. Der erste Wert ist beispielsweise beschrieben als “Total number of CPU-seconds that the process used directly (in user mode), in seconds.”, und »u« bedeutet wohl „µs“.

Die Ausgabe dieses Kommandos ist jedoch mit Vorsicht zu genießen, da sie nur eine beschränkte Genauigkeit hat, wie auch im Handbuch (»man time«) erklärt wird. Bevor dieses Kommando also zum Messen eingesetzt wird, sollte es erst selber ausgetestet werden

gcc -pg

Die gcc -Option »-pg« stattet die erzeugten Programme mit einen Laufzeitanalysator (“profiler ”) aus. Damit dessen Ausgaben möglichst aussagekräftig sind, sollte gcc  mit der Option »-g2« aufgerufen werden, so daß zusätzliche Informationen in das Kompilat eingebracht werden.

Aufruf (Kurzform)

gcc -pg -g2 -o test{,.c}

Aufruf (Langform)

gcc -pg -g2 -o test test.c

Nach dem Start des erzeugten Programms (hier also »test«) wird die Datei »gmon.out« angelegt. Sie kann mit »gprof« angezeigt werden.

Aufruf (Kurzform)

gprof test

Aufruf (Langform)

gprof test gmon.out

Fehlermöglichkeit »gmon.out file is missing call-graph data«

Diese Fehlermeldung erscheint, wenn in dem Programm keine andere Funktion aus dem Programm aufgerufen wird. Dann kann eine Ausgabe mit der grpof -Option »-p« erzwungen werden, ist aber nicht sehr informativ. Tatsächlich sollte das Hauptprogramm dann in mehrere Funktionen zerlegt werden.

Initialisierung einer quadratischen Matrix

#define N 1000
int a[ N ][ N ]={ 0 };
void l0( void )
{ int i; for( i = 0; i < N; ++i )
  { int j; for( j=0; j < N; ++j )a[ j ][ i ] = 1; }}
void l1( void )
{ int i; for( i = 0; i < N; ++i )
  { int j; for( j=0; j < N; ++j )a[ i ][ j ] = 1; }}
int main( void ){ l1(); l0(); l0(); l1(); }

Präsenzübung

Untersuchen Sie mit »gprof« welche der beiden Funktionen »l0« und »l1« aus dem obigen Programm schneller läuft.

Kann das Ergebnis bestätigt werden, wenn die Aufrufe dieser beiden Funktionen vertauscht werden?

Falls sich ein Unterschied in der Laufzeit ergeben sollte, wie könnte man diesen erklären?

Valgrind

Valgrind  ist eine „virtuelle Maschine“, die weitere Analysen des Verhaltens von Prozessen erlaubt. Wenn es nicht schon installiert ist kann es unter von »http://valgrind.org/downloads.html« abgerufen und dann wie folgt installiert werden.

Installation von Valgrind

bzip2 -d valgrind-〈version number 〉.tar.bz2
tar -xf valgrind-〈version number 〉.tar
cd valgrind-〈version number 〉
./configure
make
make install

Die letzten drei Kommandos bilden eine bei vielen im Quellcode ausgelieferten Linux -Programmen üblich Sequenz zur Konfiguration und Installation von Software, bei der auch eine „Makefile“ erzeugt und eingesetzt wird. Auch hier sollte mit »-g« oder »-g2« kompiliert worden sein.

Anzeige der Laufzeitkosten (?)

valgrind --tool=callgrind 〈path to executable 〉
callgrind_annotate --cumulative=yes --auto=yes

Alternative Anzeige der Laufzeitkosten (ungetestet)

KCacheGrind

Anzeige der Pufferverfehlungen

valgrind --tool=cachegrind 〈path to executable 〉

Anzeige eines kommentierten Quelltextes

cg_annotate --8926 test1.c

Gekürzte Ausgabe

      D1mw 
         . #define N 1000
         . int a[ N ][ N ]={ 0 };
         . void l0( void )
         0 { int i; for( i = 0; i < N; ++i )
12,000,000   { int j; for( j=0; j < N; ++j )a[ j ][ i ] = 1; }}
         . void l1( void )
         0 { int i; for( i = 0; i < N; ++i )
   125,002   { int j; for( j=0; j < N; ++j )a[ i ][ j ] = 1; }}
         0 int main( void ){ l1(); l0(); l0(); l1(); }

Die numerische Option (»8926«) ist bei neueren Versionen nicht mehr nötig. Sie muß sonst mit der Zahl am Ende der von »valgrind --tool=cachegrind« erzeugten Datei übereinstimmen.

Unter dem Spaltentitel »D1mw« finden sich oben die “D1 cache write misses ” des von Valgrind  simulierten Intel-x86-Prozessors.

Handbuch

http://valgrind.org/docs/manual/valgrind_manual.pdf

Programm mit Mängeln

#include <stdlib.h>
int main( void )
{ char * x = malloc( 10 ); int y;
  x[ 10 ]= 0;
  if( y )y = 0;
  return 0; }

Mängelanalyse mit Valgrind

gcc -g 〈path to source 〉
valgrind --tool=memcheck --leak-check=yes --show-reachable=yes 〈path to executable 〉

Auszüge aus der Analyse

==4541== Invalid write of size 1 at main (test1.c:5)
==4541== Conditional jump or move depends on uninitialised value(s) at main (test1.c:6)
==4541== malloc/free: in use at exit: 10 bytes in 1 blocks.

Valgrind  findet also einen unerlaubten Schreibzugriff in Zeile 5; einen „Sprung“, der von einem nicht initialisierten Wert abhängt und einen Block mit 10 am Programmende nicht freigegebene Bytes (ein “memory leak ”).

(Valgrind  findet jedoch angeblich keine unerlaubten Schreibzugriffe bei Reihungen mit automatischer Lebensdauer: Dafür wird aber ein extra Werkzeug »Ptrcheck« mitausgeliefert.)

PS: Neuen Produkte aus diesem Bereich sind ASan, AddressSanitizer  (Speicherbeschädigung), ThreadSanitizer  (Wettlaufsituationen) und MemorySanitizer (Verwendung nicht-initialisierten Speichers) [2015-05-20T04:57:53+01:00]

Ansatzpunkte Optimierung

Es gibt unterschiedliche Aussagen darüber, wodurch Programm am meisten ausgebremst werden. Einige der öfter genannten Punkte werden hier als erste genannt:

Bei einer großen Zahl n  verarbeiteter Entitäten kann die Komplexität eines Algorithmus der wesentlich Faktor werden, so wird ein O(n)-Algorithmus dann meist schneller sein als ein O(n²)-Algorithmus.

Bei bedingten Sprüngen in Programmen weiß der Prozessor nicht, für welche Möglichkeit er Befehle vorverarbeiten muß, er versucht dies zu erraten (branch prediction ), bei einem Fehler kann es aber sein, daß er alle Vorarbeiten verwerfen muß und die Vorverarbeitung für das anderen Sprungziel neu aufbauen muß.

Überarbeitungen von Quellcode (Refaktorierung oder Optimierung)

Vor jeder Überarbeitung von Quellcode sollte sichergestellt werden, daß es bereits eine ausreichende Menge an automatisierten Tests  für ein Programm gibt. Durch Überarbeitungen werden vermutlich Fehler in eine Programm eingebaut, und diese können mit automatisierten Tests dann teilweise gefunden werden. Während ein Compiler Syntaxfehler findet, sollen automatisierte Tests fehlerhaftes Verhalten des Programms erkennen.

Es sollte ein Versionskontrollsystem  (wie RCS, CSV, SVN  (=subversion ) oder git ) verwendet werden, das es erlaubt leicht zur letzten noch intakten Version zurückzukehren, wenn ein Programm nach Änderungen nicht mehr brauchbar sein sollte.

Es empfiehlt sich im allgemeinen nur eine einzige (kleine) Änderung  vorzunehmen und dann das Programm wieder zu kompilieren und zu starten (testen). Wenn dann ein Fehler auftritt, kann er der gerade vorgenommenen Änderung zugeschrieben werden und muß nicht lange gesucht werden.

Einzelne Möglichkeiten der Optimierung

(Es wurde ja weiter oben schon wiederholt betont, daß Programme möglichst nicht  optimiert werden sollten. Daher sind alle folgenden Erklärungen nur unter der Einschränkung „wenn es unbedingt sein muß … “ zu verstehen.)

Für alle folgenden Möglichkeiten der Optimierung gilt: Die verschiedenen „Tricks“ ergeben im allgemeinen nicht  notwendigerweise ein schnelleres Programm! Sie sind nur als Anregungen für Tests zu verstehen: Bei ihrem Einsatz wird man das Programm also einmal mit  und einmal ohne  die vermutliche „Optimierung“ testen. Danach ist dann vielleicht bekannt, in welchem Fall das Programm unter der Testumgebung schneller läuft. Wird die Ausführungsumgebung jedoch später einmal gewechselt, müßten alle Tests wiederholt werden, weil ein Trick, der ein Programm unter einer Umgebung beschleunigt, es unter einer andere bremsen  kann. Das zeigt wieder, daß Optimierung sich nur selten lohnt.

Auch sollte ein Revisionverwaltungssystem verwendet werden, damit bei Experimenten vorgenommene Änderungen jederzeit wieder rückgängig gemacht werden können.

Es sollte immer nur ein Aspekt auf einmal verändert werden, um nicht die Übersicht zu verlieren.

Wenn ein Programm bereits gut geschrieben ist, kann es sich auch zeigen, daß es gar keine  wesentliche erkennbare Möglichkeit der Optimierung mehr gibt, alle Veränderungen das Programm also eher verlangsamen oder nur unwesentlich beschleunigen.

In manchen Fällen zeigt es sich, daß für Effizienz ein Verzicht auf Einfachheit und Eleganz des Quelltextes nötig ist.

Zugriffszeiten beachten

Zugriffe auf Äußeres , also beispielsweise Ein-/Ausgabe, insbesondere auf die Konsole, Zugriffe auf Dateien und Geräte, Zugriffe auf externe Prozesse (Datenbanken, Webdienste) (oft verbunden mit Serialisierung und Deserialisierung), sind im allgemeinen besonders langsam und sollten weitgehend vermieden werden.

Typische Zeiten für Vorgänge

One cycle on a 3 GHz processor                            1   ns
L1 cache reference                                        0.5 ns            
Branch mispredict                                         5   ns       
L2 cache reference                                        7   ns                   14x L1 cache    
Mutex lock/unlock                                        25   ns        
Main memory reference                                   100   ns                   20x L2, 200x L1    
Compress 1K bytes with Snappy                         3,000   ns       
Send 1K bytes over 1 Gbps network                    10,000   ns     0.01 ms       
Read 4K randomly from SSD*                          150,000   ns     0.15 ms     
Read 1 MB sequentially from memory                  250,000   ns     0.25 ms     
Round trip within same datacenter                   500,000   ns     0.5  ms    
Read 1 MB sequentially from SSD*                  1,000,000   ns     1    ms       4X memory    
Disk seek                                        10,000,000   ns    10    ms       20x datacenter RT    
Read 1 MB sequentially from disk                 20,000,000   ns    20    ms       80x memory, 20X SSD    
Send packet CA->Netherlands->CA                 150,000,000   ns   150    ms     
from: Jeff Dean via Chandler Carruth

Speicherlokalität beachten

Wenn ein Wert nicht in einem der Pufferspeicher (cache ) des Prozessors vorhanden ist (cache miss ), muß er zeitaufwendig aus dem Hauptspeicher geholt werden. Dies ist heute ein ganz wesentlicher Faktor der Laufzeit heutiger Programme. Daher sollten Speicherzugriffe möglichst benachbart zu zeitlich benachbarten Zugriffen (also lokal) erfolgen. Oft sind Reihungen schneller als Datenstrukturen, die verkettete Listen enthalten, wenn die einzelnen Komponenten der Liste weit über den Speicher verteilt sind.

Verkettete Listen erlauben es zwar, Daten meist schneller einzufügen als bei Verwendung von Reihungen, aber dafür ist das Aufsuchen einer Komponente an einer gegebenen Position bei ihnen oft wieder langsamer als bei Verwendung von Reihungen. Daher sollte die Datenstruktur auch in Hinblick auf die erwartete Verteilung von Operationen gewählt werden.

Damit solche Entscheidungen später noch verändert werden können, ist es hilfreich, Datenstrukturen hinter Schnittstellen zu verstecken.

Verzweigungen

Wenn eine automatische Sprungvorhersage in einem bestimmten Fall meist daneben liegt, kann sie durch eine Änderung der Formulierung einer Bedingung vielleicht verändert werden: »if(x)f();« ↦ »if(!x); else f();«.

Schleifen

Wenn Schleifen auf eine übliche und einfache Weise geschrieben werden, eröffnet dies dem Compiler schon viele Möglichkeiten für eine automatische Optimierung, und zu „schlaue“ Formulierungen verhindern dies gerade manchmal.

Alle Berechnungen und Prüfungen, die bei jedem Schleifendurchlauf das gleiche Ergebnis haben, sollten aus der Schleife herausgezogen werden und nur einmal vor dieser erledigt werden.

Beim Ausrollen  (“loop unrolling ”) wird eine Schleife ganz oder teilweise durch Anweisungsfolgen ersetzt und damit der Verwaltungsaufwand vermindert.

Schleife

for( i = 0; i < 3; ++i )j += i;

„ausgerollte“ Schleife

j += 0; j += 1; j += 2; 

Schleife

sum = 0;
for( i = 0; i < N; ++i ){ sum += a[ i ]; }

2-ausgerollte Schleife

sum = sum_ = 0;
for( i = 0; i < N; i+=2 ){ sum += a[ i ]; sum_ += a[ i + 1 ]; }
sum += sum_;

Schleifen, insbesondere innere Schleifen  (also Schleifen in anderen Schleifen) wiederholen ihre Inhalte oft. Daher lohnt es sich anscheinend besonderes die Inhalte innerer Schleifen zu optimieren, da sie dies bei jeder Wiederholung auszahlt. Bei Verschachtelungen von Kontrollstrukturen, unter denen sich auch Schleifen befinden, kann es helfen, möglichst viele Berechnungen oder Entscheidungen von innen nach außen zu bewegen.

Algorithmen

Wie schon beschrieben kann durch Literaturrecherchen oder eigene Experimente geprüft werden, ob es einen effizienteren Algorithmus  für eine Aufgabe gibt.

Der Austausch eines Algorithmus ändert oft die Zeitkomplexität, beispielsweise von O(n²) auf O(n log n). Bei der Änderung der Komplexität wird man natürlich im allgemeinen eine vorteilhafte Änderung anstreben, jedoch könnte ein Algorithmus mit günstigerer Zeitkomplexität (für kleine n ) langsamer sein als ein Algorithmus mit weniger günstiger Komplexität, so daß auch hier immer gemessen werden muß.

Faktoroptimierungen

Optimierungen, welche Algorithmen nicht verändern, werden Faktoroptimierungen  genannt, da sie die Komplexität (wie O(n²)) nicht verändern, sondern die Laufzeit eines Programmteils um einen von n  unabhängigen („konstanten“) Faktor ändern.

Je nach dem Anwendungsfall kann man ein effizienterer Algorithmus und mal eine Faktoroptimierung den größeren Gewinn bringen.

Speicherzugriffe

Eine Optimierung (“cache-friendly loop interchange ”) in Hinblick auf Speicherzugriffe wurde schon weiter oben bei der Initialisierung einer quadratischen Matrix behandelt.

Funktionsaufrufe

Funktionsraufrufe kosten im allgemeine Zeit, auch wenn die aufgerufenen Funktion gar nichts macht. Durch den Einsatz von Makros oder »inline«/»static« können besonders Aufrufe kleiner Funktionen durch deren Anwendung im Quellcode ersetzt werden und so die Zeit für den Funktionsaufruf (“function call overhead ”) eingespart werden.

Da dies aber den Umfang des Programms vergrößern kann, kann es auch wieder zu mehr Hauptspeicherzugriffen führen (weil das Programm nicht mehr so gut in den Pufferspeicher paßt) und so ein Programm verlangsamen.

http://lwn.net/Articles/82495/

Stärkeminderung

Bei der Stärkeminderung (“strength reduction ”) werden langsame Operationen durch schnellere ersetzt.

Beispielsweise ist die ganzzahlige Division  oft langsam und kann manchmal durch Schiebeoperation ersetzt oder durch eine Umformulierung oder Auswechselung des Algorithmus vermieden werden.

Für »x*x > 0« kann beispielsweise oft auch »x != 0« verwendet werden.

Register-Variablen

Durch das Schlüsselwort »register« kann der Zugriff auf eine Variable eventuell (auf Kosten anderer Zugriff) beschleunigt werden. Dies wäre empfehlenswert, wenn erkannt wird, daß auf diese Variable in einem kritischen Programmteil sehr oft zugegriffen wird. Normalerweise sorgt eine C -Implementation aber ohnehin schon dafür, daß solche Variablen in Registern gehalten werden.

Registerdruckminderung

Es kann sein, daß der Wert einer Variablen eine Funktion des Wertes einer anderen Variablen ist. Dann kann es effizienter sein, diesen Wert aus der anderen Variablen zu berechnen und so die Anzahl der Variablen einzusparen. Dadurch kann ein größerer Anteil der Variablen in Prozessorregistern gehalten werden, was eine Funktion beschleunigen könnte.

Anforderungsminderungen

Die Aufgaben kritischer Programmteile können auch umdefiniert werden, so daß diese weniger tun müssen und entsprechend schneller werden.

Wahl von Datentypen

Oft sind Rechnungen mit »int« schneller als Rechnungen mit Gleitkommawerten und selbst als Rechnungen mit anderen ganzzahligen Typen.

Bibliotheken nutzen

Manchmal enthalten fertige Bibliotheken bereits optimierte Funktionen für bestimmte Aufgaben. Dann ist es effizienter, diese zu nutzen, als die entsprechenden Funktionen neu zu schreiben.

Maschinensprache

Kritische Programmteile können direkt in Assembler (Maschinensprache) geschrieben werden. Ein Maschinensprachenexperte könnte dabei eventuell effizienteren Code schreiben als er von einem Compiler erzeugt wird. Es ist dabei auch möglich eventuelle Befehlssatzerweiterungen eines speziellen – gerade verwendeten – Prozessors auszunutzen.

Manchmal können auch die Prozessoren von Graphikkarten oder Spezialzweckprozessoren bestimmte Operationen effizienter ausführen als der Hauptprozessor.

Es könnte auch für eine bestimmten Anwendung ein zugeschnittener Spezialprozessor aufgebaut werden.

Einige häufig vorkommende Operationen finden sich so auch schon in der C-Bibliothek, wie etwa »memmove«, das statt einer eigenen Kopierschleife zum Kopieren von Speicher verwendet werden sollte.

Parallelisierung

Bei Parallelisierung werden verschiedene Aufgaben eines Programms so auf mehrere Kerne, Prozessoren oder Rechner aufgeteilt, daß sie gleichzeitig erledigt werden können.

Code-Inspektionen

Wenn andere Programmierer Quellcode inspizieren, entdecken sie manchmal Möglichkeiten der Optimierung, an die der Autor nicht dachte.

Zeiger

Um Informationen an eine Funktion zu übergeben, sollten diese nicht alle einzeln kopiert werden. Oft reicht es, sie einmal in eine Struktur oder Reihung zu legen und dann nur einen Zeiger auf diese Objekt zu übergeben.

Gerätekäufe

Die Beschaffung eines schnelleren Rechners kann möglicherweise weniger Geld kosten als die Arbeitszeit eines Programmierers.

Genauso kann eine Speichererweiterung Prozesse beschleunigen, wenn dann weniger Daten auf eine Festplatte ausgelagert werden müssen.

Prioritäten

Durch Linux -Kommandos wie »nice« kann die Priorität eines Prozesses erhöht werden, so daß dieser – auf Kosten anderer Prozesse – schneller läuft.

Bedarfsgesteuerte Berechnungen

Wenn eine Liste von Werten benötigt wird, die aufwendig zu berechnen sind, werden die Werte erst dann eingesetzt, wenn sie zum ersten Mal abgerufen werden, um die Zeit für die Berechnung der Werte einzusparen, die nie abgerufen werden.

Gedächtnisfunktionen

Wenn eine Funktion aufwendig berechnete Ergebnisse liefert, dann speichert sie die zuletzt berechneten Ergebnisse. Wird sie dann mit einem Argumentwert aufgerufen, für den schon ein Ergebnis gespeichert wurde, dann kann dies aus dem Speicher zurückgeliefert werden, und muß nicht erneut berechnet werden.

Endmarkierungen

Wenn ein Wert in einer Behälter (etwa einer Reihung) gesucht wird, dann kann dieser als Endmarkierung (“sentinel ”) ans Ende gesetzt werden, so daß in der Schleife neben der Wertsuche keine zusätzliche Prüfung auf das Behälterende nötig ist.

Statische Berechnungen

In manchem Fällen können wiederkehrende Berechnungen auch nur einmal erledigt werden und deren Ergebnis dann in den Quelltext eingesetzt werden. Allerdings rechnen viele Compiler die Werte konstanter Ausdrücke ohnehin schon selber aus.

Bit-Tricks (“bit hacks ”)

Durch Berücksichtigung der Bitdarstellung von Informationen kann eine Operation manchmal effizienter erledigt werden. Teilweise geschieht dies auf Kosten der Portabilität. So ist in manchen Fällen »int j=i>>31; return (i^j)-j;« ein möglicher Ersatz für die Berechnung eines Betrags mit »return i < 0 ? -i : i;«. Da der Bit-Trick in diesem Fall möglicherweise einen Sprung vermeidet, könnte er schneller sein, auch wenn sein Quelltext nicht einfacher aussieht als die Formulierung mit dem ternären Operator.

»const«, »restrict«

Die korrekte Verwendung von »const« und – in C99  – auch »restrict« erlaubt einem Compiler manchmal mehr Optimierungen.

switch

Mögliche Vorteile von »switch« im Vergleich mit mehreren if -Anweisungen wurden oben schon angesprochen.

Puffern

Häufiger benötigte Informationen werden im Speicher zwischengepuffert anstatt sie immer wieder von externen Medien zu lesen.

Sicherheitsprüfungen

Sicherheitsprüfungen im Rahmen des „defensiven Programmierens“ können deaktiviert werden.

Aufrufe von »malloc«

Wenn viele Objekte gleicher Größe wiederholt angefordert und freigegeben werden, können sie an Stelle einer Freigabe weiterhin gehalten und dann wiederverwendet werden, um die relativ aufwendigen Aufrufe von »malloc« einzusparen.

Betriebssystemaufrufe

Durch bestimmte Betriebssystemaufrufe, die nicht zum Standardumfang von C  gehören, können Aufgaben effizienter erledigt werden, etwa Dateizugriffe mit Dateien, die auf den Speicher abgebildet werden (“memory-mapped files ”).

Umwandlungen vermeiden

Umwandlung von Datendarstellung kosten Zeit, beispielsweise zwischen der internen Darstellung von Gleitkommazahlen und ihrer Textdarstellung. Daher sollte es vermieden werden, solche Informationen unnötig hin-und-her zu wandeln.

Compiler

Es können verschiedene Compileroptionen und verschiedene Compiler ausprobiert werden, um zu sehen, wann der schnellste Code produziert wird. Eventuell sogar verschiedene Programmiersprachen. Auch sollte gelegentlich geprüft werden, ob eine neuere Version des Compilers verfügbar ist, die vielleicht schnelleren Code erzeugt.

Manchmal sind Programme einfach nur deswegen langsam, weil vergessen wurde, vor der Auslieferung an Kunden, assert-Aufrufe mit NDEBUG zu deaktivieren und eine hohe Optimierung des Compilers einzustellen.

Lokale Variablen

Der gerade aktive Teil des Stapelspeichers befindet sich wahrscheinlich meist im Prozessor-Cache. Deswegen sind die sich dort befindlichen lokalen Variablen wahrscheinlich schneller erreichbar als statische oder dynamische Objekte.

Allgemein hilft es, wenn aufeinanderfolgende Speicherzugriffe benachbarte Speicherplätze ansprechen und nicht weit voneinander entfernte.

Sprungvermeidung

Da Sprünge (die nach der Übersetzung im Programm stehen) moderne Prozessoren bremsen können, sollten sie möglichst durch Programmteile ohne Sprünge ersetzt werden. Die Anweisung »if( rand() % 2 == 0 )return 1; else return 3;« kann beispielsweise durch »return rand() % 2 * 2 + 1;« ersetzt werden.

Speicherlokalität (Cache, Prefetcher)

Wenn viele Daten aus dem Speicher gelesen oder in diesen geschrieben werden, dann ist es wesentlich besser, wenn die einzelnen Speicheradressen dabei wie bei einer Reihung gemäß einer einfachen Regel aufeinanderfolgen und relative nahe benachbart sind als wenn wie bei einer verketteten Luste unregelhaft in einem großen Speicherbereich hin- und hergesprungen wird, weil im ersten Fall der Cache und der Prefetcher moderner Prozessoren viel besser genutzt werden kann.

Löschen von Werten aus Reihungen

Falls ein Wert aus der Mitte einer Reihung mit unsortierten Werten gelöscht werden soll, so ist es nicht nötig, den ganzen Rest zu verschieben, um die frei gewordene Stelle zu füllen, es reicht die letzte Komponente dorthin zu bewegen.

Um eine Queue zu implementieren, die nur für eine begrenzte Zeit verwendet werden soll, ist es nicht nötig, die am Anfang weggenommenen Komponenten wirklich zu löschen, es reicht den Anfangszeiger zu verschieben.

Spezielle Möglichkeiten von Compilern wie GCC

Die folgende Escape-Funktion erlaubt es, dem Compiler zu sagen, daß das übergebene Objekt ausgelesen oder beschrieben werden kann. Dies verhindert es, daß er es „wegoptimiert“, was in Vergleichsmessungen nützlich sein kann.

Escape-Funktion

static void escape( void * p ) 
{ asm volatile( "" : : "g"(p) : "memory" ); }

Durch ein »__builtin_expect« kann dem Compiler mitgeteilt werden, welcher Zweck einer Verzweigung oder Schleife schneller sein soll.

Beispiel

__builtin_expect(p<q,0)?p:q

Beispiel

#define ifx( expr ) if( __builtin_expect( ( expr )!= 0, 0 ))

…

ifx( p >= top )p = text;

Code, der nur selten ausgeführt wird und eine Funktion unnötig vergrößert (so daß sie weniger gut in den Cache paßt), kann ausgelagert werden.

Beispiel

__attribute__((noinline,cold)) static void error_handling_code()
{ fprintf( stderr, "Erreur de débordement." ); exit( 99 ); }

…

if( result < previous_result )error_handling_code();

Funktionen, die durch die Werte ihrer Parameter (und globaler Variablen?) bestimmt sind, können gekennzeichnet werden.

Beispiel

__attribute__((pure))

Daten können vorausschauend in den Cache geladen werden.

Beispiel

__builtin_prefetch( text, 0, 0 )

Abschließender Hinweis

Egal, welcher „Optimierungs-Trick“ ausprobiert wird: Es muß immer gemessen werden, ob dieser wirklich zu einer Beschleunigung führt, und zwar am besten unter realistischen Bedingungen (Einsatzbedingungen).

Übungen

/    Übungsaufgabe Textverbindungen

Warum könnte das folgende Programmstück ineffizient sein, und wie könnte es effizienter formuliert werden?

char buff[ 1000 ];
strcpy( buff, "One "   );
strcat( buff, "Two "   );
strcat( buff, "Three " );
strcat( buff, "Four "  );
.
.
.

/    Übungsaufgabe Schleifen

Warum könnte das folgende Programmstück ineffizient sein, und wie könnte es effizienter formuliert werden?

for( i = 0; i < 9; ++i )a[ i ]= x ? y : y * y;

Bauen Sie diese Schleife in ein Programm ein, in dem [A:] die Werte von »x« und »y« vor dieser Schleife erst zur Laufzeit festgelegt werden und [B:] die Werte von »a[ 0 ]« bis »a[ 8 ]« nach Ende der Schleife auch alle zur Festlegung des Programmverhaltens verwendet werden.

Vergleichen Sie dann die mit und ohne Optimierung erzeugten Kompilate (Assembler-Ausgabe).

Warum sind „A“ und „B“ hierfür wichtig?