Es ist eine kleine "Programmbibliothek" gegeben
welche sehr einfache Vektor Operationen implementiert
und Werte-Semantik verwendet.
Diese wird von einem Testprogramm verwendet,
beim Optimieren ist nur die Veränderung der Bibliothek zulässig.
Die gesamte original Aufgabenstellung ist
Unsere Gruppe führte folgende Optimierungen durch:
- Lazy Evaluation mit Reference Counting
- Erkennen von speziellen Mustern zur Situationsspezifischen Optimierung
- Memory Management - Malloc/Free Wrappers
- Hinweise an den Compiler
- Compiler Optionen
Besonders Interessant dabei ist, das unsere ersten Optimierungsansätze
(Assembly, Datenumstrukturierung) sehr schlecht verlaufen sind.
Erst nachdem wir das Programm durch eine andere Implementierung zuerst sehr stark
verschlechtert hatten konnten wir darauf basierend andere Optimierungen anwenden
die dann tatsächlich zu einer Verbesserung führte.
| Verbesserung |
Cycles Absolut |
Cycles Relativ |
Instructions Absolut |
Instructions Relativ |
| Original |
1.790.767.358 |
100% |
4.571.583.802 |
100% |
| + Lazy Evaluation |
6.918.121.173 |
386,3% |
14.822.838.134 |
324,2% |
+ Mathematische Zusammenfassung |
3.501.391.479 |
195,5% |
7.975.040.428 |
174,4% |
| + Memory Management |
868.780.341 |
48,5% |
1.613.760.109 |
35,3% |
| + Compiler |
767.622.685 |
42,9% |
1.413.462.136 |
30,9% |
Im Endeffekt konnten wir auf der Testmachine die Laufzeit
von
2,41s auf
0,54s verringern,
also einen Speedup von etwa
2,25 erzielen.
Unsere Implementierung (in vectors.c):
Directory
Unsere Präsentation:
PDF