TU Wien:Effiziente Programme VU (Ertl)

Daten

Vortragende	Martin Ertl
ECTS	3,0
Alias	Efficient Programs (en)
Letzte Abhaltung	2024W
Sprache	English
Mattermost	effiziente-programme • Register • Mattermost-Infos
Links	tiss:185190 , Homepage

Zuordnungen

Masterstudium Data Science	Modul BDHPC/CO - Big Data and High Performance Computing - Core (Gebundenes Wahlfach)
Masterstudium Logic and Computation	Modul Programming Languages and Verification (Gebundenes Wahlfach)
Masterstudium Software Engineering & Internet Computing	Modul Computersprachen und Programmierung (Gebundenes Wahlfach)

Inhalt

Ist Effizienz nötig, Arten von Effizienz, Spezifikation und Effizienz, Design fuer Effizienz, die Rolle effizienter Algorithmen (konstante Faktoren), Hardwarecharakteristik (Cache, Blockgroessen, Register, Bandbreite), Mikrooptimierung, Werkzeuge.

Ablauf

Es gibt einige Vorlesungsheiten ohne Anwesenheitspflicht, in denen (sehr grundlegend) einige Richtlinien für effiziente Programme erläutert werden. Diese sind ungefähr nach der Hälfte des Semsters abgeschlossen. Anschließend wird in Kleingruppen (max. 3 Personen) ein Praxisbeispiel durchgeführt, in dem man entweder ein Standardbeispiel (im WS08 einen Löser für Mastermind) oder ein eigenes Programm optimieren und anschließend präsentieren muss.

Benötigte/Empfehlenswerte Vorkenntnisse

C/C++ programmieren (außer man wählt ein eigenes Beispiel für die Übung).

Zumindest im WS2016 ließen sich die benötigten C-Kenntnisse ohne Probleme "on-demand" erlernen.

Vortrag

Viele der vorgestellten Richtlinien und Tips sind imho selbstverständlich, wenn man nicht einfach blauäugig drauflos programmiert; wer also schon etwas erfahrener ist im Programmieren wird sich teilweise langweilen, da der Vortragsstil nicht unbedingt der spannendste ist. Es kommen aber immer wieder auch recht interessante Abschnitte, und wer im Vorlesungsteil halbwegs aufpasst weiß genau, was er im Übungsteil tun soll.

Übungen

Im WS25 gab es 4 Exercises. Diese wurden auf seiner Website veröffentlicht und sind hier öffentlich einsehbar. Sie beziehen sich zu den Themen (1) Profiling, (2) Loop-Profiling mit perf, (3) CPU cache sizes, (4) SIMD und Auto-Vectorization.

1. https://www.complang.tuwien.ac.at/anton/lvas/efficient/25/exercises1.html
2. https://www.complang.tuwien.ac.at/anton/lvas/efficient/25/exercises2.html
3. https://www.complang.tuwien.ac.at/anton/lvas/efficient/25/exercises3.html
4. https://www.complang.tuwien.ac.at/anton/lvas/efficient/25/exercises4.html

Es mussten eine Reihe von Fragen beantwortet werden und die Lösungen auf eine GitLab Instanz gepusht werden.

Ehemals, Veraltet, Jetzt Teil der Effiziente Programme PR

Der Übungsteil besteht aus der Optimierung eines Programms. Dazu werden Kleingruppen von max. 3 Personen gebildet. Man kann hier entweder ein Standardprogramm (im WS 08 ein Löser für Mastermind Mastermind) verwenden oder ein eigenes. Wählt man ein eigenes Programm ist man auch frei in der Wahl der Programmiersprache. Es muss nicht C/C++ sein. Die Optimierungen werden anschließend präsentiert.

Es sei hier erwähnt, dass - obwohl die Vorlesungsfolien sich oft auf Low-Level-Optimierungen fokussieren - die Übungsaufgabe auch seitens des Algorithmus verbessert werden kann. In meinem Fall wurden 4 von 5 Optimierungen durch Änderung der Datenstruktur und Abläufe erzielt.

Prüfung, Benotung

Mündliche Prüfung von 15 Minuten. Es werden zwei kurze Fragen zu den abgegebenen Übungen gestellt. Hier muss man erklären wie man z.B. optimiert hat, oder was man mit "perf" gemessen hat und was die Ergebnisse zeigen und warum.

Der größere zweite Teil der mündlichen Prüfung ist dann frei zum Inhalt der Vorlesung. Professor Ertl lässt sich dabei durchaus in eine bestimmte Richtung lenken. Er fragt gerne bei gegebenen Antworten ins Detail nach. Das kann man geschickt ausnutzen.

Professor Ertl asks you before the interview if you would like to speak German or English, of course.

Fragen zum Vorlesungsinhalt

Die folgenden Fragen wurden im WS25 in der mündlichen Prüfung zum zweiten Teil gestellt.

• Welche Arten von Effizienz gibt es? (Geschwindigkeit/Zeit, Speicher, Energieeffizienz)
• Wie teilt man die Programmzeit auf (Realtime, Usertime, Systemtime) Was ist das alles? Was zählt zur Systemtime?
• Angenommen ein Programm hat hohe Systemtime, woher kommt das Problem (Zu viele Syscalls) Wie kann man es optimieren? (Zum Beispiel keine Allocations in Hot-Loops)
• Was sind die Basiskosten eines Syscalls (Context-Switch des CPUs)
• Was kann io_uring hier verbessern? (Event-loop, Aufgabe eines Tasks im Userspace-Programm kostet fast nichts; einfach in einen Buffer schreiben. Nur Syscall wenn man die erledigten Events will)
• Wann ist ein Programm schnell genug? (Command Line -> 300ms; Music -> 20ms; ...)
• Wie würdest du ein Programm schneller machen? (mit "time, gprof, gcov, perf stat" benchmarken -> Hot Loops optimisieren -> überprüfen ob output noch immer korrekt ist -> benchmarken wiederholen)
• Was ist abgesehen von Effizienz wichtig? (Programmierzeit des Programmierers)
• What is the role of the programming language in programs efficiency ? (inherent vs idiomatic efficiency, compiler makes different optimizations)
• Why can humans optimize better than compilers ? (compilers have to keep the same output, humans only stick to the specifications)

Prüfungsbericht vom 21.01.2026 (Prüfung war auf Deutsch)

Zuerst sind wir die Abgaben durchgegangen. Hier sind wir nur durch die 3. Aufgabe gegangen. Q3, Q8, Q9. Hatte da paar Fehler drinnen, die haben wir besprochen. Er hat dann noch bisschen zus

• Was ist Parallelisierung, SIMD. Dann Konzepte beispielhaft besprochen (Reduction, er wollte noch weitere wissen aber mir ist keins direkt eingefallen)
• What is the role of the programming language in programs efficiency ? (inherent vs idiomatic efficiency, compiler makes different optimizations)
• Was kann man neben runtime optimieren -> Memory efficiency.
  • Hier wollte er paar Beispiele. Data files -> compressing.
  • Was verbraucht noch Speicherplatz neben Daten -> Programme
  • Dann wollte er noch Packing hören (Slide 69 und 70)

Benotung war sehr fair.

23.01:

1. Why can't I just leave the efficiency to the compiler?

2. What is latency and what is Through-put?

3. From which hardware features do these two benefit from?

Dauer der Zeugnisausstellung

Sehr schnell (<1 Woche nach den letzten Präsentationen)

Zeitaufwand

Wenn man fit im C/C++ Programmieren ist eher wenig. Eine Handvoll VO-Einheiten á 1,5 Stunden. Für die Übung 1-3 Tage, je nach Ehrgeiz.

WS2016: Der Zeitaufwand hängt vom persönlichen Ehrgeiz ab. Es lässt sich wohl in 1-2 Tagen eine mittelmäßige Optimierung und Präsentation vorbereiten. Wer bessere Ergebnisse erzielen will muss sich aber doch einige Tage mehr Zeit lassen. Das tolle an der Aufgabe ist ja, dass es der Gruppe freisteht, wie viel Aufwand investiert werden soll.

Unterlagen

• Empfohlenes Buch
• Etwas gewöhnungsbedürftige, aber ausreichende Notizen (über LVA-Homepage erreichbar)
• Aufgabe aus WS2016 sowie Links zu Beispielen aus früheren Jahren.

Tipps

• Wie immer bei Kleingruppen ist etwas Vorsicht bei der Auswahl der Leute geboten - nicht alle machen die LVA wirklich zu Ende oder bringen kaum Coding-Wissen mit.
• Sich die Notizen einmal durchzublättern, bevor man an die Optimierungen geht lohnt sich. Mit den Tips dort kommt man schon recht weit.

Highlights / Lob

noch offen

Verbesserungsvorschläge / Kritik

Das Beispiel im WS10 konnte kaum verstanden werden, es war ein Ausschnitt aus einem Compiler in C. Dadurch kann man fast nur Optimierungen auf syntaktischer Ebene machen.

Materialien

Neues Material hinzufügen

I

• Interview-questions