Seminar „Effiziente Programmierung in C“

Beschreibung

In diesem Seminar geht es um konkrete Methode zum Zeitsparen beim Programmieren. Das bezieht sich sowohl auf die Zeit zum Debuggen und Weiterentwickeln, als auch auf die Laufzeit des Programms. Dabei sollen Informationen zu den verschiedenen Themen recherchiert werden, und anhand von konkreten Beispielen dargestellt werden. Es können auch die Ergebnisse kleiner vergleichender Untersuchungen zur Auswirkung verschiedener Konstrukte und Methoden gezeigt werden.

Es geht bei diesem Seminar explizit nicht um das einfache Vorstellen von Sprachkonstrukten, sondern um die Recherche & Bewertung von Nutzungsmöglichkeiten.

Organisatorisches

Wichtig: 3 Wochen vor dem Termin beim Betreuer melden!

Abzugeben sind:

  1. Präsentation als PDF Datei (wenn viel Farbe verwendet wird, bitte auch eine Druckversion)
  2. Ausarbeitung als PDF Datei
  3. Compilierfähiger Beispielcode als .tgz Archiv (mindestens für alle Beispiele, die in Präsentation und/oder Ausarbeitung verwendet wurden, gerne auch mehr)

Wenn im Rahmen dieses Seminars Performancemessungen gemacht werden, müssen diese auf den Knoten west1, … west10 unseres Lehre-Clusters durchgeführt werden. Sprecht einfach euren Betreuer an, dann geben wir euch eine Account.

Beachten Sie auch unsere allgemeinen organisatorischen Hinweise zu Seminaren.

Zielgruppe

Das Seminar eignet sich für Studierende der Informatik in den Diplom- und Bachelorstudiengängen. Studierende anderer Studiengänge müssen die Anrechnung mit dem jeweiligen Prüfungsausschuss klären.

Interessierte Zuhörer sind auch herzlich willkommen.

Voraussetzungen

Grundkenntnisse in C, C++ oder Objective-C.

Daten der Veranstaltung

Zeit Donnerstag, 10–12 Uhr
Ort DKRZ, Raum 034
Beginn 17.10.2013
Vorbesprechung 17.10.2012, 10–12 Uhr
Mailingliste EPC-1314

Dozenten

Themenliste

Die Themenliste hier gibt eine erste Übersicht über den Inhalt des Seminars, die Liste wird noch nach Absprache mit den Teilnehmern angepasst.

  • Compiler-Optimierung
    • Was kann der Compiler?
    • Was kann er nicht?
    • Und wie nutzt man es?
  • Die Keywörter “restricted”, “static” & “inline”
    • Was tun sie?
    • Was bringt das?
    • Und wie setzt man es sinnvoll ein?
  • Alignment
    • Wo wird es angewendet?
    • Was bewirkt es?
    • Wie kann man Overhead vermeiden?
  • Caches:
    • Wie funktionieren sie?
    • Was bedeuten Caches für die Programmierung?
    • Und wie nutzt man sie effizient?
  • Indirektion:
    • Welche Spielarten gibt es?
    • Was bringt sie, was kostet sie?
    • Wie kann man sie effizient einsetzen?
  • Datenstrukturen im Linux-Kernel:
    • Wie funktionieren sie?
    • Inwiefern unterscheiden sie sich von anderen Implementierungen von verlinkten Listen, Bäumen, etc.?
    • Was sind die Vor- & Nachteile dieses Ansatzes?
    • Wann sollte man sie verwenden?
  • Effizienz von Allokatoren
    • Welche Fragen stellen sich bei der Implementation von `malloc()`?
    • Welche Algorithmen kommen in Frage/wurden untersucht?
    • Welche fertigen Implementationen gibt es?
    • Wie ist die Performance dieser Implementationen?
  • Algorithmus Analyse:
    • Wie kann ich die Performance eines Algorithmus bewerten?
    • Ist O(n) immer besser als O(n^2)?
    • Wie hilft die Algorithmus Analyse bei der Optimierung?
    • Welche Art von Optimierungspotenzial kann man mit Algorithmus Analyse nicht erkennen?
  • Algorithmen:
    • Algorithmenstrukturen:
      • Für alle Unterthemen:
        • Was ist das Grundprinzip?
        • Welche Algorithmen wenden es an? (Nur ein bis drei Beispiele, aber die bitte mit ausreichend Tiefe!)
        • Was sind die typischen Merkmale?
        • Wann kann man es anwenden?
        • Wann ist es sinnvoll?
      • Teile & Herrsche
      • Greedy Algorithmen
      • Dynamische Programmierung
    • Hashing
      • Was ist ein Hashwert?
      • Wie funktioniert eine Hashtabelle?
      • Was bringt es, was kostet es?
      • Wie benutzt man typische Bibliotheksimplementationen?
      • Und was ist ein HTree?
  • Laufzeitkosten:
    • Was ist wie teuer?
      • Funktionsaufrufe
      • Berechnungen
      • Mathefunktionen
      • if-Konstrukte
      • switch-Anweisungen
      • Speicherzugriffe
      • Systemaufrufe

Weitere Themen können gerne vorgeschlagen werden.

Zeitplan

Materialien

Literaturhinweise

* http://smackerelofopinion.blogspot.de/2012/09/striving-for-better-code-quality.html

Ben Klemens: 21st Century C, ISBN-13:978-1-449-32714-9

Robert C. Martin: Clean Code / A Handbook of Agile Software Craftsmanship, ISBN-13:978-0-13-235088-4

1) , 3) , 8) , 12) , 17) , 19)
Michael Kuhn
2) , 6) , 11) , 13) , 15)
Konstantinos Chasapis
4) , 7) , 9) , 10)
Dr. Julian Kunkel
5) , 14) , 16) , 18)
Nathanael Hübbe