Vertretungsplan-Parser: Stack voll, Import zu langsam
Im Wahlpflichtfach Informatik der Klassenstufe 11 entwickelt ein Kurs von 19 Schülerinnen und Schülern eine Java-Anwendung, die den Vertretungsplan aus den täglich exportierten HTML-Dateien einliest und als PDF ausgibt. Das Modul PlanParser durchläuft die verschachtelten Tabellen rekursiv: Für jede gefundene Ebene ruft es sich selbst auf. Auf den Schulrechnern (2 GB RAM, Java 8) funktioniert der Import aller 1.200 Zeilen. Auf dem ausgemusterten Raspberry Pi im Sekretariat (512 MB RAM) bricht der Lauf bei Zeile 40 mit einem StackOverflowError ab. Ein Schüler schlägt vor, die JVM mit -Xss16m zu starten; die Lehrkraft möchte stattdessen mit einem expliziten Stack arbeiten. Zusätzlich ist der Import mit 9 Sekunden zu langsam, das Sekretariat erwartet höchstens 2 Sekunden. Eine Profiler-Messung zeigt, dass rund 80 Prozent der Laufzeit in einer Schleife entstehen, die Zeichenketten mit + aneinanderhängt. Der Kurs muss sich in der nächsten Doppelstunde entscheiden.
1. Beurteilen Sie beide Vorschläge zur Behebung des `StackOverflowError`. Welche Lösung setzen Sie auf dem Raspberry Pi um, und wie begründen Sie das mit dem Speicherverhalten und der Struktur des Problems?
Read the worked answer
Die beiden Vorschläge behandeln unterschiedliche Dinge.
-Xss16m vergrößert nur den Stack je Thread. Die Rekursionstiefe hängt aber von der Verschachtelungstiefe der eingelesenen HTML-Datei ab, also von der Eingabe, nicht vom Programm. Jeder Aufruf belegt einen Frame mit Rücksprungadresse, lokalen Variablen und Referenzen. Ein größerer Stack verschiebt den Schwellwert, an dem der Fehler auftritt – er behebt ihn nicht. Auf einem Gerät mit 512 MB RAM ist ein 16-MB-Thread-Stack zusätzlich riskant, weil der verbleibende Heap für die 1.200 Zeilen und die PDF-Erzeugung kleiner wird; der Fehler taucht dann als OutOfMemoryError an anderer Stelle wieder auf.
Iterativ mit explizitem Stack macht den Speicherbedarf sichtbar: Der Stack enthält genau die noch offenen Verschachtelungsebenen, also O(Tiefe) statt O(Tiefe) JVM-Frames mit unbeeinflussbarer Größe. Bei typischen Plänen sind das wenige Ebenen, und die Obergrenze lässt sich im Code prüfen und mit einer sauberen Fehlermeldung abfangen („Datei zu tief verschachtelt“). Das ist auf dem Pi reproduzierbar und unabhängig von JVM-Flags.
Entscheidung: iterative Variante. Sie ist zwar mehr Arbeit, beseitigt aber die Ursache, macht die Ressourcengrenze explizit und lässt sich mit einem Speicherlimit (-Xmx) testen, das den Pi nachbildet.
2. Erklären Sie die 9 Sekunden Laufzeit mit einem Komplexitätsargument und geben Sie die konkrete Änderung an. Schätzen Sie die Größenordnung des Gewinns ab.
Read the worked answer
Die Schleife hängt Zeichenketten mit + aneinander. In Java sind String-Objekte unveränderlich: Bei jedem s = s + teil entsteht ein neues Objekt, und der bisherige Inhalt wird vollständig kopiert. Bei k Teilstrings der Länge m werden also 1 + 2 + … + k Zeichen kopiert, das sind k·(k+1)/2, also O(n²) bei Gesamtlänge n.
Größenordnung: 1.200 Zeilen mit etwa 200 Zeichen ergeben n ≈ 240.000 Zeichen, thus rund 2,9·10¹⁰ kopierte Zeichen. Bei einigen Milliarden Kopiervorgängen pro Sekunde landet man genau in dem beobachteten Bereich von knapp 10 Sekunden – die Messung passt zur Theorie.
Änderung: StringBuilder verwenden, append in der Schleife, am Ende toString(). StringBuilder verdoppelt bei Bedarf die Kapazität, sodass amortisiert jedes Zeichen nur O(1) oft kopiert wird; insgesamt O(n). Bei bekannter Zielgröße zusätzlich new StringBuilder(300_000) als Startkapazität, um auch die Umspeicherungen zu vermeiden.
Erwartung: Der Kopieranteil fällt von ~9 s auf wenige Millisekunden; die Restzeit geht in Parsing und PDF-Erzeugung. Ob die 2-Sekunden-Vorgabe erreicht wird, muss danach erneut gemessen werden – das Argument liefert nur den Grund, nicht den Beweis.
3. Nennen Sie vier Testfälle, die Sie vor der Abgabe zwingend ausführen, und begründen Sie je, welche Fehlerklasse der Fall abdeckt.
Read the worked answer
- Tief verschachtelte Datei (z. B. 500 Ebenen). Deckt die alte Fehlerklasse ab: Der iterative Parser darf nicht abstürzen, sondern muss entweder korrekt parsen oder eine kontrollierte Meldung liefern. Ohne diesen Fall wäre die Regression unsichtbar, weil normale Pläne nur wenige Ebenen haben.
- Fehlerhafte Struktur (fehlendes schließendes
</table>, überzähliges</tr>). Prüft, ob der Parser einen definierten Fehlerzustand hat statt einerNullPointerException; genau hier zeigt sich, ob der explizite Stack korrekt aufgeräumt wird. - Große Realdatei mit 1.200 Zeilen und Umlauten (UTF-8). Prüft sowohl die Laufzeitvorgabe von 2 s als auch die Zeichenkodierung; ein falsch gesetzter Zeichensatz erzeugt sonst erst im PDF sichtbare Fehler.
- Leerer Plan (nur Kopfzeile). Randfall der Schleifen und der Zählerlogik: Ein leerer Plan ist gültig und darf nicht als Fehler gemeldet werden.
Zusätzlich sollte der Testlauf mit -Xmx256m erfolgen, um den Pi zu simulieren; ein Test auf dem Entwicklungsrechner mit 16 GB RAM beweist für die Zielumgebung nichts.