http://www.complang.tuwien.ac.at/anton/lvas/skriptum-effizienz.html

M. Anton Ertl                    Some things have to be seen to be believed
anton@mips.complang.tuwien.ac.at Most things have to be believed to be seen
http://www.complang.tuwien.ac.at/anton/home.html

Literatur
---------

Allgemein:

J. L. Bentley, Writing Efficient Programs, Prentice Hall, 1982.

Bitte Kapitel 2 nicht im vorhinein lesen (kann auch bersprungen werden).


Mikrooptimierungen: Optimierungsmanuals diverser Prozessorhersteller,
z.B.:
     * Intel Architecture Optimization Reference Manual
     * AMD Athlon Processor x86 Code Optimization Guide
     * Intel Pentium 4 Processor Optimization Reference Manual
       

Ist Effizienz ntig?
--------------------

Hufige Behauptung: "Heute sind die Computer so schnell (haben soviel
Speicher, etc.), dass man sich keine Gedanken um Effizienz machen
muss."

Andererseits: Warum ersetzen die meisten ihre alten Computer noch
immer durch neuere?  Warum geben die Kufer mehr Geld fr
schnellere/grere Computer aus, statt sich den billigsten (und damit
langsamsten etc.) zu kaufen, wenn der langsamste ohnehin schnell genug
ist?

Nicht jede Software und ihre Anwendung ist gleich; es gibt

- Software, die auf allen Computern der letzten fnf Jahre bei allen
vorkommenden Eingaben so schnell reagiert, dass es von Menschen als
"sofort" wahrgenommen wird, bzw. die bei wiederholter Eingabe oder
gleichzeitigem Betrieb mehrerer Prozesse den Prozessor nicht voll
auslastet.

Auf diese Software trifft die obige Behauptung zu.  Aber es gibt auch:

- Software, die frher langsam war, und heute immer noch merkliche
Zeit braucht.  Mehr Geschwindigkeit reduziert die Wartezeiten noch
weiter.

- Software, die frher selten aufgerufen wurde, und heute oft
aufgerufen wird (schnelles Feedback erlaubt andere Arbeitsablufe).
Mehr Geschwindigkeit bietet noch mehr Freiheiten bei den
Arbeitsablufen.

- Software, bei der die zu verarbeitenden Eingaben mit der Zeit grer
oder komplexer geworden sind, sodass sie noch immer hnlich lange
braucht wie frher.  Mehr Geschwindigkeit erlaubt die Verarbeitung noch
grerer Mengen an Daten.

- Software, bei der die schnellere Hardware zu Verbesserungen in der
Funktionalitt ausgenutzt wurde, sodass die Geschwindigkeit immer noch
gleich ist, aber die Software besser/schner.  Mehr Geschwindigkeit
erlaubt noch mehr Funktionalitt.

bung: Nennen sie fr jeden dieser fnf Flle ein Software-Produkt.


Arten von Effizienz
-------------------

Laufzeit
  CPU
  Festplatte
  Netzwerk
  andere I/O
Speicher
  Hauptspeicher (RAM)
  ROM (bei embedded systems)
  Plattenspeicher
Effizienz in der Benutzung (Requirements-Analyse, user interface design)


Kosten von Ineffizienz
----------------------

Bei interaktiven Anwendungen: Wartezeit des Benutzers.  Wartezeiten im
Bereich von 1-10s fhren zu ca. dem dreifachen Zeitverlust beim
Benutzer.

Frher: CPU-Sekunden-Verrechnung.  Bentley (1982) nennt z.B. $200 pro
CPU-Stunde einer DEC-10 und $50 Kosten pro Programmiererstunde.

Heute auf Servern: Mehr Server (Hardware, Administrationsaufwand,
Platz- und Energieverbrauch).

Bei embedded systems: Teurere Hardware (mehr RAM/ROM, schnellerer
Prozessor, strkere Stromversorgung, bessere Abschirmung, etc.), in
x-facher Ausfhrung.


Wieviel Effizienz ist sinnvoll?
-------------------------------

Interaktive Software: Latenzzeiten von unter 0.3s werden bei
Befehl-Antwort-Interaktion als "sofort" empfunden.  Bei interaktiver
Software mit Hand-Auge-Koordination (oder auch Hand-Ohr-Koordination)
sind noch wesentlich geringere Latenzzeiten erforderlich (20ms im
Musik-Bereich).

Animierte Software: mehr Frames/s als die Bildwiederholrate des
Bildschirms knnen nicht gezeigt werden.

Wenn ein Teilsystem den Zeitverbrauch (oder sonstigen
Resourcenverbrauch) dominiert und nicht weiter optimiert werden kann,
ist es meist nicht sinnvoll, die anderen Teilsysteme noch effizienter
zu machen.

Bei vorgegebenen Resourcen und vorgegebener Funktionalitt
(z.B. embedded systems) ist es "nur" notwendig, mit den Resourcen
auszukommen.

Bei allgemein verwendbaren Komponenten (z.B. der STL) kann man oft
kein oberes Limit fuer die sinnvolle Effizienz angeben; das hngt von
der jeweiligen Anwendung ab.

Kommerziell: Solange die Kunden fuer das effizientere Produkt soviel
mehr zahlen, wie die Optimierung gekostet hat, ist die Optimierung
kommerziell sinnvoll.  Diese berlegung setzt voraus, dass eine
nicht-optimierte Version existiert; wenn dagegen ohne Zwischenschritt
eine effizientere Version entwickelt wird, sind die Entwicklungskosten
mglicherweise geringer, aber mglicherweise auch die Einnahmen, wenn
das Prodokt spter auf den Markt kommt.


Andere Ziele, oder: Kosten von Effizienz
----------------------------------------

Korrektheit
  "If a program is not correct, it matters little how fast it runs."
  Kernighan und Plauger, The Elements of Programming Style
Klarheit, Einfachheit
Entwicklungsaufwand
Wartungsaufwand
geringe time-to-market


Software Engineering
--------------------

Keine Effizienz-berlegungen ->
  u.U. unbrauchbares Programm
  u.U. grobe nderungen spt im Entwicklungszyklus, mit entsprechenden Folgen
  fr time-to-market, Entwicklungskosten und Wartungsaufwand.

"Wir optimieren alles" ->
  hoher Entwicklungsaufwand
  hoher Wartungsaufwand
  lange Entwicklungszeit (und time-to-market)
  komplexes Programm -> bersehen von wichtigen Optimierungsmglichkeiten oder
                        grobe nderungen spt im Entwicklungszyklus

Beobachtungen:
  Kleine Teile des Codes brauchen den Groteil der Laufzeit
  Man kann Programme so schreiben, dass kleine Teile den Groteil
    des Datenspeichers verwalten
  Aber: Was wieviel braucht, wei man oft erst durch Messungen am
        laufenden Code.  Programmierer verschtzen sich dabei oft erheblich.

Konsequenz: Fr Einfachkeit, Flexibilitt, und Wartbarkeit entwerfen
  und codieren, dann messen, dann die kritischen Teile optimieren, und
  zwar schrittweise (dabei noch mglichst einfach und flexibel
  bleiben, sonst werden sptere Optimierungsschritte schwerer).

Problem: Manche Effizienzprobleme sind schon im Design oder in der
Spezifikation festgelegt -> Prototyping ("Plan to trow one away; you
will, anyway." Fred Brooks).


Methoden
--------

Ist das Programm effizient genug?
  Messung, Instrumentierung (Einfgen von Messcode im Programm)
Wodurch wird die meiste Zeit verbraucht?
  Profiling, Performance Counter, Instrumentierung
Wie mache ich einen Programmteil effizienter?
  Korrektheitserhaltende Transformation
Wurden durch die Optimierung Bugs eingefhrt?
  Automatisches Testsystem und Testflle.

unoptimiertes Programm
  |
  V
Tests
  | bestanden
  V____________________
Messung                \
  | zu ineffizient     |
  V                    |
Profiling              |
  |                    |
  V                    |
Programmtransformation |
  |                    |
  V                    |
Tests                  |
  | bestanden          |
  \____________________/


Was knnen optimierende Compiler, was nicht?
--------------------------------------------

Compiler verwenden auch korrektheitserhaltende Transformationen, aber

- sie wissen nicht soviel ber das konkrete Programm und seine
Korrektheitsbedingungen (z.B. don't-care-Resultate).

- sie betrachten oft nur einen Teil des Programms auf einmal
(z.B. einen Basic Block, eine Schleife, eine Prozedur, oder eine
Compilation Unit), und sehen keine Optimierungsmglichkeiten jenseits
davon.

- sie wissen oft nicht, was wie oft ausgefhrt wird, und was daher
eine Optimierung wre (aber: profile-guided Optimization).

- die Anzahl der Optimierungen in Compilern ist durch die Ziele
bezglich Entwicklungsaufwand, Testaufwand, und Zuverlssigkeit
(Anzahl der Bugs) begrenzt.

Oft kann man die eigentliche Optimierung vom Compiler durchfhren
lassen, und muss nur die Stolpersteine beseitigen.  Beispiel:

  for (i=0, best=0; i<n; i++)
    if (a[i]<a[best])
      best=i;
  return best;

Das luft auf vielen Prozessoren schneller, wenn man es so schreibt:

  for (p=a, bestp=a, endp=a+n; p<endp; p++)
    if (*p < *bestp)
      bestp = p;
  return bestp-a;

Das spart dem Prozessor das die Adressberechnung von a[i] und a[best]
in jedem Durchlauf.  Aber eigenlich knnen die meisten Compiler diese
Optimierung selbst, nur mssen sie weiterhin zustzlich i und best
mitberechnen, weil

1) best am Ende verwendet wird, und

2) (im Fall von gcc-3.0) die Ersetzung des Vergleichs i<n durch p<endp
nicht sicher korrekt ist (bei Arithmetik mit begrenzten ganzen Zahlen
folgt aus a<b nicht a+c<b+c; allerdings wagen viele Compiler diese
Transformation im Zusammenhang mit Zeigerarithmetik in C trotzdem,
wenn die entsprechenden Zeiger auch im Originalprogramm (implizit)
vorkommen; dann ergibt sich die Korrektheit aus den Regeln fr
Zeigerarithmetik in ANSI C, zusammen mit dem Wissen des Compilers ber
seine Implementierung dieser Regeln).

Das folgende Programm ist nher am Original, erlaubt dem Compiler aber
diese Optimierung:

  for (i=0, bestp=a; a+i<a+n; i++)
    if (a[i]<*bestp)
      bestp=a+i;
  return bestp-a;

Durch die Verwendung von bestp wurde das erste Problem behoben, und
durch Verwendung von "a+i<a+n" statt "i<n" das zweite.

Typische Stolpersteine fr Compiler:

- mgliche Aliase: das Schreiben in eine Speicherstelle und der
Zugriff auf eine andere Speicherstelle knnen nicht umgeordnet werden,
weil der Compiler nicht weiss, dass die beiden Zugriffe auf
verschiedene Speicherstellen erfolgen.  Viele Optimierungen
wollen viele Operationen umordnen.

- mgliche Seiteneffekte/Exceptions: Der Compiler kann nicht umordnen,
weil er nicht weiss, dass die Operation keine Seiteneffekte hat oder
Exceptions auslst.

- Schleifendurchlufe: Der Compiler zieht etwas nicht aus einer
Schleife heraus, weil es im Fall der 0-fachen Ausfhrung inkorrekt
oder ineffizient wre (und weil sich der Compiler gegen Loop Peeling
entscheidet, z.B. wegen der Codegre).

Manche Dinge, die Compiler knnen, sind auch fr den Fachmann
berraschend; so optimiert gcc beim Ausdruck

*s1==*s2 && *s1!=0 && *s2!=0

das "*s2!=0" komplett weg.  Wenn man das im Source-Code kommentarlos
weglassen wrde, wre er schlechter lesbar (dieses Fragment stammt aus
einer String-Vergleichsroutine; ohne "*s2!=0" ist es nicht
offensichtlich, dass die Routine terminiert, wenn s2 endet.
Alternativ: wegoptimierten Code als Kommentar im Source-Code
stehenlassen, wenn der Compiler diese Optimierung nicht schafft).

Ein wichtiger Vorteil der Compiler-Optimierung ist also, dass sie
erlaubt, klaren und wartbaren, und trotzdem effizienten Code zu
schreiben.

Inwieweit soll man sich auf den Compiler verlassen?

Einerseits: Mit einem anderen Compiler, in der nchsten Version des
gleichen Compilers, oder nach einer kleinen nderung am Programm
knnte der Compiler eine bestimmte Optimierung schon nicht mehr
schaffen, und herauszufinden, was ein bestimmter Compiler jetzt
schafft und wie, und was nicht, kostet u.U. mehr Zeit, als die
Optimierung von Hand durchzufhren.

Andererseits: Es gibt Leute, die noch immer ihren ganzen Code so
schreiben, wie das fr Optimierungszwecke fr bestimmte, heute im
Einsatzbereich der Programme unbliche Prozessoren im Zusammenhang
nicht-optimierenden Compilern zweckmssig war.


Hardware-Eigenschaften
----------------------

Ungefhre Kosten verschiedener Operationen auf in 2001 verkauften
Maschinen (ein Zyklus (Z) ist 0.5ns-2ns, aber das ndert sich sehr
schnell, whrend die folgenden Werte schon ein paar Jahre lang
halbwegs richtig sind):

 1Z   3-4 unabhngige Befehle
 1Z   Latenzzeit eines ALU-Befehls
 2-3Z Latenzzeit eines Load-Befehls (L1-Hit)
10Z   Latenzzeit eines Load-Befehls (L1-Miss, L2-Hit)
100ns Latenzzeit eines Load-befehls (L2-Miss, Main Memory access)
 30ns eine Cacheline (32-64B) zwischen Prozessor und Hauptspeicher bertragen
 1Z   korrekt vorhergesagter Sprung
10Z   falsch vorhergesagter Sprung (branch misprediction)
4-10Z Latenzzeit Integer-Multiplikation
 4Z   Latenzzeit FP-Addition/Multiplikation
50Z   Latenzzeit Division
100us IP-Ping ber Fast Ethernet (100Mb/s)
100us 1KB bertragung ber Fast Ethernet
10ms  Latenzzeit Plattenzugriff (seek & rotational delay)
10ms  400KB sequentieller Plattenzugriff (ohne delay)
100ms Latenzzeit CD-ROM (drehend; bei Stillstand mehrere Sekunden)
100ms 600KB sequentieller CD-ROM-Zugriff

Seit Bentley sein Buch schrieb, haben sich die relativen Kosten der
Operationen verschoben; insbesondere sind die Cache-Miss-Zeiten grer
geworden und branch prediction gab es damals noch berhaupt nicht.
Dafr ist Speicher viel billiger geworden.  Es gibt daher einige neue
Optimierungstechniken, die in Bentley's Buch nicht erwhnt sind.

Umgekehrt sind manche Optimierungen, die frher sinnvoll waren, heute
nicht mehr sinnvoll, weil der Flaschenhals woanders liegt: Z.B. wurde
in der Software-Implementierung von X-Grafikoperationen frher
komplexe Optimierungen angewandt, um die zahl der ausgefhrten Befehle
zu vermindern.  Bei der Neu-Implementierung vor ein paar Jahren wurde
dagegen relativ einfacher Code geschrieben, weil der Flaschenhals auf
heutigen Maschinen beim Speichersubsystem liegt, sodass ein
Wegoptimieren von Befehlen nur zur Folge htte, dass die CPU mehr Zeit
mit Warten auf den Speicher verbringt.


Algorithmen und Datenstrukturen
-------------------------------

Conventional Wisdom (aber trotzdem wahr): Wenn im kritischen Bereich
der falsche Algorithmus bzw. die falsche Datenstruktur gewhlt wird,
sind Gedanken zur effizienten Implementierung dieser Wahl
verschwendete Zeit (ausser vielleicht, um zu zeigen, dass es
tatschlich die falsche Wahl war und nicht nur eine ineffiziente
Implementierung einer guten Wahl).

Das verleitet leider manche Leute zur Behauptung, dass man sich nur um
den Algorithmus kmmern muss.  Aber wenn man eine gute Wahl getroffen
hat, dann kann die effiziente Implementierung noch einiges bringen.

Wie erkennt man eine gute Wahl?  Letztendlich an der Effizienz,
zusammen mit anderen Zielkriterien (Einfachheit).

Als Hilfestellung gibt es die algorithmische Komplexitt
(O(...)-Notation).  Dabei gibt es aber einige Fallen, die in die Irre
fhren knnen:

- Algorithmische Komplexitt betrachtet meist den
schlechtest-mglichen Fall, nicht den durchschnittlichen Fall (der
auch oft schwer bis gar nicht zu charakterisieren ist).

- Algorithmische Komplexitt beruht meist auf dem (abstrakten) Zhlen
von bestimmten Operationen, die aber nicht (mehr) unbedingt eine groe
Rolle fr die Laufzeit spielen (im Vergleich z.B. zu Cache Misses).

- Algorithmische Komplexitt ignoriert konstante Faktoren.  Konstante
Faktoren spielen oft eine grere Rolle als logarithmische Faktoren
u..

Beispiel: Peter Fenwick, "Some Perils of Performance Prediction: a
case study on Pattern Matching", Software - Practice and Experience,
Vol 31, pp 835-843 April 2001.

Suchen nach einem String in einem lngeren Text: Simple Methode hat
worst-case-Komplexitt von O(m*n), Knuth-Morris-Pratt O(n).  Trotzdem
schlgt dis simple Methode KMP in der Realitt, u.a., weil der
average-case der simplen Methode nher bei O(n) liegt als bei O(m*n),
und weil die simple Methode einen besseren Konstanten Faktor hat.


Die Rolle der Programmiersprache
--------------------------------

Eingebaute Ineffizienz

Idiomatische Ineffizienz

Effizienz durch Compiler

Effizienz durch Programmiereffizienz (mehr Zeit zum Tuning,
flexibleres Programm).

Beispiele:

Aliasing in C vs. Fortran (in Fortran sind verschiedene
Funktionsargumente keine Aliase des gleichen Datums).

Verschachtelte Objekte in Java vs. C++ (Indirektion in Java).

Skalieren bei Zeigerarithmetik in C vs. Forth (C skaliert per default).

0-terminierte Strings in C.

``C++ ist langsam''.

Bei Mikrobenchmarks fhren C- und Fortran-Compiler, bei
Programmierwettbewerben (z.B. Functional Programming Contest; die
Programmiersprache ist dabei nicht eingeschrnkt ist) dagegen nicht.

Flughafen von Riad: Mit Fortran und Assembler zu langsam, mit Forth
(implementiert per Interpreter) und Assembler schnell genug.

In manchen Fllen kann Assembler noch viel bringen, aber:
Spezialwissen erforderlich, oft Prozessorabhngig (z.B.: LODSD auf 386
vs 486).


Transformationen

Testfaelle

Programmplatz-Optimierung

Optimierungen
  von Bentley
  neu (fuer aktuelle Hardware)

Dieses Jahr gibt es nur die Folien mit
den Optimierungstransformationen.


Programmbeispiel
----------------

Ein einfacher suboptimaler Algorithmus fr das
Traveling-Salesman-Problem: tsp1.c

Dieser Algorithmus liefert Ergebnisse mit Weglngen, die um ca. 25%
ber dem Optimum liegen.  Dafr braucht er nur quadratische Zeit,
whrned ein optimaler Algorithmus exponentiell viel Zeit braucht (TSP
ist NP-vollstndig).

bung: berlegen Sie sich Optimierungsmglichkeiten in diesem Programm
und wieviel sie bringen knnen.


Messwerkzeuge
-------------

Auf Linux-Intel (expi2):

#gprof (function-level profiling):
gcc -pg -O ts.c
a.out 5000
gprof a.out

#basic block profiling (siehe (gcc)Debugging Options
gcc -O -a -lm ts.c
a.out 1000
cat bb.out
objdump -d a.out #disassemblieren, um die basic blocks zuordnen zu koennen

#cycle count timing:
perfex a.out 1000

#performance counters
perfex -e 4100c0 a.out 1000           #c0: instructions
perfex -e 4100c0 -e 0100c5 a.out 1000 #c5: branch mispredictions

#Intel-Doku ber Events
#Fr den Celeron (expi2) relevant sind Seiten 588-598 (A-20...A-30).
#erster counter immer mit 4xxxxx, zweiter immer mit 0xxxxx.

Auf Digital Unix (mips):

uprofile issues a.out 1000
#mgliche counter siehe "man uprofile", tabelle fr EV4
#sinnvollerweise kann man nur einen counter benutzen
# (sonst erhaelt man die Summe)
prof a.out umon.out


Beispiel fr Optimierung
------------------------

Angelehnt an Kapitel 2 von [Bentley82].  Der Algorithmus und die Idee
der Optimierungen sind gleich, aber die Details sind oft
unterschiedlich.

Das erste Programm ist unser usprngliches bungsbeispiel tsp1.c.

Wir messen die Effektivitt der Optimierungen auf der expi2 (Celeron
800) mit

perfex -e 4100c0 -e 0100c5 a.out 1000 >/dev/null

(also bei Lufen mit 1000 Stdten), wobei das Hauptaugenmerk auf die
Zyklen (tsc) gerichtet ist.

Ob wir bei der Optimierung einen Fehler eingebaut haben, berprfen
wir mit

diff tsp.eps tsp_ref.eps

nach einem Lauf ueber 1000 Stdte.

Wir fangen an mit gcc -O: 77.4M Zyklen.

1. Schritt: Bessere Optimierung: gcc -O3: 55.3M Zyklen.

2. Schritt: Common Subexpression Elimination von dist(cities, ThisPt, j),
sodass dieser Ausdruch nur einmal verwendet wird.
Ergebnis: tsp2.c, 54.8M Zyklen.

Der Geschwindigkeitsvorteil durch diese Optimierung ist gering, weil
der zweite Aufruf von dist in einem if ist, das im Durchschnitt
H(n)=1+1/2+1/3+..., also ca. ln(n) mal erfolgreich ist.

3. Schritt: Eliminieren von sqrt() im Aufruf von dist() in tsp().  Da
sqrt() fuer positive Argumente monoton ist, nur postive Argumente
vorkommen, und wir das Ergebnis nur fuer einen Grenvergleich
verwenden, kann man sqrt bei diesem Aufruf weglassen.

Wir machen das, indem wir eine Kopie von dist() namens DistSqrd()
erzeugen; diese Kopie rufen wir von tsp() aus auf.  Die
Originalversion von dist bleibt erhalten und kann von woanders
aufgerufen werden (und wird auch von main() aufgerufen), ohne dass wir
berprfen mssen, ob wir dort auch sqrt() weglassen drfen (wir
drfen nicht).

Ergebnis: tsp3.c, 26.0M Zyklen.

4. Schritt: Eliminieren von visited[].  Statt per visited[] zu
berprfen, ob wir eine Stadt schon besucht haben, verwenden wir
tour[], um nur ber die Stdte zu iterieren, die noch nicht dran waren
(z.B. im letzten Aufruf der inneren Schleife nur mehr eine Stadt statt
n, im Durchschnitt spart man die Hlfte der Iterationen der inneren
Schleife.  Das erfordert allerdings grere nderungen am Programm
(siehe "diff tsp3.c tsp4.c").

Ergebnis: tsp4.c, 20.2M Zyklen.

Ca. die Hlfte dieses Speedups beruht auf besserer Sprungvorhersage
(die "if (!visited[j])" sind nicht besonders gut vorhersagbar).

5. Schritt: Inlining von DistSqrd().

Ergebnis: tsp5.c, 19.5M Zyklen.

6. Schritt: Y-Distanz spter berechnen.  Die Distanz zwischen zwei
Punkten auf der X-Achse ist sicher kleiner als die Gesamtdistanz; Wenn
die X-Distanz zwischen der aktuellen Stadt und einer anderen Stadt
grer ist als die bisher krzeste Gesamtdistanz, und man braucht die
andere Stadt nicht weiter betrachten.  Nur in den Fllen, in denen die
X-Distanz kleiner ist (und das sind bei grossem n nicht so viele) muss
man auch noch die Y-Distanz berechnen, um die Gesamtdistanz zu
erhalten und vergleichen zu knnen.

Ergebnis: tsp6.c, 19.3M Zyklen.

(Der 7. Schritt bei Bentley ist die Verwendung von ganzen Zahlen statt
Gleitkommazahlen; diesen Schritt lassen wir hier aus, weil er die
Resultate ndert.  Ausserdem ist bei dieser Berechnung (mit einem
nicht unbetrchtlichen Anteil von Multiplikationen) auf modernen
Maschinen nicht unbedingt eine Verbesserung zu erwarten.)

8. Schritt: Direkte Umordnung der Stdte.  Statt ber ein Index-Array
tour[] zu indizieren, wird tour[] zu einem Array von Stdten, die
direkt umgeordnet werden.  Erspart indirekte Zugriffe ber das
Index-Array, dafr wird das Umordnen teurer (kommt aber nur in der
ueren Schleife vor).  Hauptnachteil hier ist, dass sich das
Interface von tsp() ndert, sodass alle Aufrufer gendert werden
mssen (knnte man umgehen, indem man das Index-array noch zustzlich
mitfhrt).

Ergebnis: tsp8.c, 18.1M Zyklen.

9. Schritt: Sentinel.  Die innere Schleife kann als Suchschleife
aufgefasst werden, die nach einer Stadt sucht, die nher ist als die
bisher gefundene.  Daher kann man die Sentinel-Technik anwenden, indem
man die aktuelle Stadt (die sich selbst natrlich mindestens so nahe
ist wie alle anderen) als Sentinel benutzt, um die Schleife
abzubrechen; dadurch erspart man sich die Abfrage im for-Teil der
inneren Schleife.  Da allerdings nicht bei der ersten nheren Stadt
abgebrochen wird wie bei anderen Suchschleifen, mu man eine Abfrage
nach dem Abbruch im inneren if-Statement einfgen, diese Abfrage kommt
aber wesentlich seltener vor (H(n) mal) als die Abfrage im for-Teil.

Ergebnis: tsp9.c, 18.9M Zyklen.

Die Ursache dieser Verlangsamung habe ich noch nicht nher untersucht.


Zusammenfassung und Vergleich mit Ergebnissen aus [Bentley82]:

Ergebnisse normalisiert auf die Version aus dem 6. Schritt:

Celeron  PDP-KL10  HP1000  # nach Optimierung
C        Pascal    C
4.01     5.73      4.39    1 -O (bei gcc)
2.87     -         -       1 -O3 (bei gcc)
2.84     5.56      4.27    2 Common Subexpression Elimination
1.35     2.95      2.78    3 Eliminieren von sqrt()
1.05     2.59      2.63    4 Eliminieren von visited[]
1.01     1.71      1.72    5 Inlining von DistSqrd()
1        1         1       6 Y-Distanz spter berechnen
-        0.91      0.86    7 Integers statt Floats
0.94     0.84      0.84    8 Direkte Umordnung statt Index-Array
0.98     0.83      -       9 Sentinel
