Seminar „Effiziente Programmierung in C“

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.

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.

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.

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

• Nathanael Hübbe
• Michael Kuhn
• Dr. Julian Kunkel
• Konstantinos Chasapis
• Thomas Ludwig

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

• Kommentierung:
  • Welche Denkschulen gibt es?
  • Welche Antworten finden sie auf die Fragen
    • Was ist ein hilfreicher Kommentar?
    • Was sollte man kommentieren?
    • Was sollte man nicht kommentieren?
  • Welche Hinweise sind allgemein gültig, worin unterscheiden sie sich?
  • Und was heißt das für mich als Programmierer?
  • Siehe auch: http://queue.acm.org/detail.cfm?id=1053354
• Umgang mit Buffern:
  • Was kann man tun, um Indexfehler zu vermeiden?
  • Allokation auf dem Heap ↔ Allokation auf dem Stack
  • Siehe auch:
    • https://developer.apple.com/library/mac/#documentation/security/conceptual/SecureCodingGuide/Articles/BufferOverflows.html
    • http://www.ibm.com/developerworks/linux/library/l-sp4/index.html
• Umgang mit Pointern
  • Wie nutzt man sie sinnvoll?
  • Was sind die Performance-Aspekte?
  • Und wie vermeidet man Fehler?
  • Einige Stichworte: Uninitialisierte Pointer, Falsche Typen, dangling pointer, NULL pointer, Alloziierungsfehler, Aliasfehler.
• Mehrdimensionale Arrays
  • Wie funktionieren sie?
  • Wie kann man sie typsicher übergeben?
  • Wie kann man sie korrekt casten?
  • Im Gegensatz zu den anderen Themen geht es hierbei explizit um die korrekte, detailierte und verständliche Darstellung eines Sprachfeatures, mit dem Ziel, dass die Zuhörer es wirklich verstehen; nicht um die Frage, wo und wie es sinnvoll einzusetzen ist. Der Grund ist, dass es ein komplexes Feature ist, das nur selten angewendet wird weil es noch viel seltener verstanden wird.
  • Siehe auch:
    • http://stackoverflow.com/questions/18361111/are-a-a-a-a0-a0-and-a00-identical-pointers
    • http://stackoverflow.com/questions/381542/in-c-arrays-why-is-this-true-a5-5a
    • http://stackoverflow.com/questions/1461432/what-is-array-decaying
    • http://c-faq.com/aryptr/index.html
• Undefined Behavior:
  • Was ist Undefined Behavior?
  • Wie schlägt der Compiler Kapital aus Undefined Behavior?
  • Was sind die Gefahren?
  • Worauf sollte man achten?
  • Siehe auch: http://blog.llvm.org/2011/05/what-every-c-programmer-should-know.html
• Präprozessor:
  • Was kann man damit machen?
  • Wie geht das?
  • Wo ist es sinnvoll?
  • Bringt es Performance?
  • Und wo sind die Fallen?
• Objektorientierung in C
  • Geht das?
  • Und wenn ja, wie?
  • Und was ist mit “private” und “public”?
• Die Programmiersprache Vala
  • Sprachweiterentwicklung von C
  • Objektorientierung
  • Welcher C Code entsteht dabei?
• Polymorphie in C:
  • Welche Ansätze gibt es dafür?
  • Lohnt sich der Aufwand?
  • Was bedeuten die verschiedenen Ansätze für die Performance?
• Reference Counting:
  • Was ist das?
  • Was bringt es?
  • Wie setzt man es ein?
  • Wieviel Rechenzeit kostet es?
  • Und welche Gefahren gibt es?
  • Siehe auch: https://developer.apple.com/library/mac/#documentation/Cocoa/Conceptual/MemoryMgmt/Articles/MemoryMgmt.html
• C11
  • Was ist neu?
  • In welchen Situationen kann man es sinnvoll einsetzen?
  • Was sollte man sich unbedingt merken?
• Zu den Themen bezüglich Objektorientierung, siehe auch:
  • http://www.eventhelix.com/realtimemantra/basics/object_oriented_programming_in_c.htm
  • http://www.planetpdf.com/codecuts/pdfs/ooc.pdf

• 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.

• 7. 11. 2013: C11 – Daniel Martens ¹⁾ – Präsentation Ausarbeitung
• 14. 11. 2013: Präprozessor – Henrik Friedrichsen ²⁾ – Präsentation Ausarbeitung
• 14. 11. 2013: Buffer – Stefan Bruhns ³⁾ – Präsentation Ausarbeitung Materialien
• 21. 11. 2013: Pointer – Hannes Röbe-Oltmanns ⁴⁾ – Präsentation Materialien
• 21. 11. 2013: Mehrdimensionale Arrays – Florian Wilkens ⁵⁾ – Präsentation AusarbeitungMaterialien
• 28. 11. 2013: Undefined Behavior – Dennis Sobczak ⁶⁾ – Präsentation Ausarbeitung
• 28. 11. 2013: Objektorientierung – Alexander Droste ⁷⁾ – Präsentation Code
• 5. 12. 2013: Reference Counting – Moritz Gaack ⁸⁾ – Präsentation Ausarbeitung Code
• 12. 12. 2013: Vala – Julian Schmid ⁹⁾ –
• 12. 12. 2013: Compiler Optimierung – Göhkan Kalender ¹⁰⁾ –
• 19. 12. 2013: restricted, static & inline – Markus Fasselt ¹¹⁾ – Präsentation Ausarbeitung
• 19. 12. 2013: Laufzeitkosten – Tobias Fechner ¹²⁾ – Präsentation Ausarbeitung Materialien
• 9. 1. 2014: Alignment – Sven Hendrik Haase ¹³⁾ – Präsentation Ausarbeitung
• 9. 1. 2014: Algorithmus Analyse – Johann Basnakowski ¹⁴⁾ – Präsentation Ausarbeitung Code
• 16. 1. 2014: Achtung: Wir sind in Raum 023
• 16. 1. 2014: Allokatoren – Marcel Ellermann ¹⁵⁾ – Präsentation Ausarbeitung
• 16. 1. 2014: Algorithmen – Marcel Hellwig ¹⁶⁾ – Ausarbeitung Materialien
• 23. 1. 2014: Fehlertoleranz – Anna Fuchs ¹⁷⁾ – Präsentation Bericht
• 30. 1. 2014: Caches – Christian Duße ¹⁸⁾ – Präsentation Druckversion Ausarbeitung Materialien
• 30. 1. 2014: Hashing – Paulus Böhme ¹⁹⁾ – Präsentation Ausarbeitung Code

* 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