Laufzeitanalyse (Runtime Analysis)

Motivation

Sobald ein Algorithmus entworfen ist, stellen sich verschiedene Fragen: Wird er funktionieren? Wird er immer korrekte Ergebnisse liefern? Gibt es redundante Teile? Haben meine Tests alle möglichen Fälle abgedeckt? Wie steht es um die Leistung – ist sie akzeptabel, liegt die funktionale Abhängigkeit von der „Problemgröße" im vorhergesagten Bereich? Wenn wir eine Optimierung des Codes in Betracht ziehen, wo sollten wir beginnen?

Laufzeitanalyse-Werkzeuge, die Daten während der Ausführung eines Algorithmus erfassen, können helfen, viele dieser Fragen zu beantworten. Deshalb bietet Structorizer jetzt mehrere spezifische Visualisierungsoptionen für die Analyse des Algorithmenverhaltens und der Teststrategie.

Testen ist ein wichtiger Ansatz zur Validierung eines Algorithmus. Ein wesentliches Kriterium für einen systematischen und erschöpfenden White-Box-Test ist die sogenannte Code-Abdeckung (code coverage) – d. h. sicherzustellen, dass jeder einzelne Pfad eines Algorithmus mindestens einmal durchlaufen wurde.

Neben der sorgfältigen Planung eines minimalen Satzes notwendiger Datentupel (Eingabe + erwartete Ausgabe) ist ein praktischer Weg erforderlich, um nachzuweisen und zu demonstrieren, dass alle Pfade durch die durchgeführten Tests tatsächlich ausgeführt (abgedeckt) wurden. Genau hier kommt Structorizer ins Spiel: Die Runtime Analysis ist eine Funktion innerhalb des Structorizer-Executors, die die Vollständigkeit eines Testsatzes demonstrieren kann.

Aktivieren der Runtime Analysis

Um die Runtime Analysis zu aktivieren, öffnen Sie den Executor. Im Executor-Steuerfeld befinden sich in der dritten Zeile ein Kontrollkästchen und eine Auswahlliste für die Art der visualisierten Daten:

[v] Collect Runtime Data: Schaltet die Erfassung von Ausführungszähldaten ein (oder aus).

Das Ändern des Kontrollkästchenzustands ist nur zwischen Tests möglich, niemals während einer Ausführung – unabhängig davon, ob diese läuft oder pausiert ist. Die Auswahlliste auf der rechten Seite ist nur verfügbar, wenn das Kontrollkästchen „Collect Runtime Data" aktiviert ist. (Das bedeutet, Sie können den Typ der angezeigten Daten während des Tests wechseln; die ausgewählte Visualisierung hat keinen Einfluss auf den Erfassungsprozess. Siehe „Wahlfreiheit" weiter unten.)

Hinweis: Wenn Sie das Kontrollkästchen abwählen, werden alle erfassten Daten sofort gelöscht und alle laufzeitdatenbezogenen Hervorhebungen ausgeschaltet. Wenn Sie die Hervorhebung nur unterdrücken, aber das Tracking und die Laufzeitdaten beibehalten möchten, wählen Sie stattdessen den Visualisierungsmodus „no coloring" aus.

Wenn die Runtime Analysis aktiviert ist, erfasst und zählt sie kumulativ verschiedene Daten über die Ausführung der Elemente. Sie haben dann die Möglichkeit, verschiedene Aspekte der erfassten Daten zu visualisieren:

• Test-Code-Abdeckung (wurde das Element mindestens einmal ausgeführt?)
• Ausführungszählung (wie oft wurde das Element während des Tests durchlaufen?)
• Anzahl der vom Element selbst durchgeführten Operationen (wie viele atomare Operationen hat das Element ausgeführt?)
• Aggregierte Anzahl der durchgeführten Operationen (wenn das Element zusammengesetzt ist: wie viele Operationen wurden als Teil dieser Struktur angewiesen?)

Da der Bereich der letzten beiden Annotationstypen enorm sein kann (von 0 bis zu vielen Millionen und mehr), ist sowohl eine lineare als auch eine logarithmische Skalierung wählbar. Entsprechend dem ausgewählten Visualisierungstyp ändert sich die Einfärbung der Elemente live während der Ausführung. So können Sie verfolgen, was passiert. Der Verzögerungsschieberegler ermöglicht es, den Prozess ausreichend zu verlangsamen, um den Änderungen zu folgen, oder die Verzögerung zu reduzieren, um schneller zu Ergebnissen zu gelangen.

Während die Runtime Analysis aktiv ist, erscheinen und wachsen in der oberen rechten Ecke jedes Elements zwei Zahlen (Zähler), getrennt durch einen Schrägstrich. Die erste Zahl stellt den Ausführungszähler dar, die zweite die Anzahl der lokalen (oder aggregierten) atomaren Operationen, die vom Element angewiesen werden.

Test-Code-Abdeckung

Wenn Sie in der Auswahlliste shallow test coverage (flache Testabdeckung) oder deep test coverage (tiefe Testabdeckung) wählen, werden alle Elemente, die während der jüngsten Testreihe mindestens einmal ausgeführt wurden, hervorgehoben. Die Hervorhebungsfarbe dieser „testabgedeckten" Elemente ist leuchtendes Grün.

Abdeckungsregeln

Die Regeln sind recht einfach:

• Einfache Anweisungen und Sprünge (Jumps) werden nach ihrer ersten vollständigen Ausführung markiert. Leere Elemente (z. B. leere FALSE-Zweige von IF-Anweisungen) müssen ebenfalls durchlaufen worden sein, bevor sie grün werden.
• Strukturierte Verzweigungselemente (IF-Anweisungen, CASE-Selektionen und PARALLEL-Abschnitte) werden nur dann markiert, wenn alle ihre Zweige vollständig abgedeckt, d. h. grün geworden sind.
• CASE-Selektionen ohne Default-Zweig: Da ein fehlender Default-Zweig nicht bedeutet, dass ein Diskriminatorwert, der keinem der angegebenen Selektorkonstanten entspricht, ein Fehler ist – sondern nur übergangen wird –, ist diese Struktur äquivalent zu einer CASE-Selektion mit leerem Default-Zweig. Im Shallow-Coverage-Modus wird eine CASE-Selektion als abgedeckt markiert

  

  , sobald alle expliziten (d. h. sichtbaren) Zweige abgedeckt sind; eine Deep Coverage kann dagegen erst erreicht werden, nachdem auch der versteckte Default-Zweig mindestens einmal durchlaufen wurde.
• Schleifenelemente werden beim Verlassen grün, wenn ihr jeweiliger Schleifenrumpf vollständig abgedeckt wurde; eine kopfgesteuerte Schleife wird also nicht grün, wenn der Schleifenrumpf umgangen wurde.
• Bei Unterroutinen-CALLs gibt es einen Deep- und einen Shallow-Modus. Im Deep-Modus ist die aufgerufene Unterroutine selbst Teil des Tests und muss erst vollständig abgedeckt sein, bevor das CALL-Element, das sie aufruft, ebenfalls grün werden darf. Der Shallow-Modus geht dagegen davon aus, dass aufgerufene Unterroutinen zuvor getestet und als korrekt erwiesen wurden – das CALL-Element kann also grün werden, ohne dass die aufgerufene Routine vollständig abgedeckt sein muss.
• Im Shallow-Modus werden alle Unterroutinen als abgedeckt behandelt; Sie können jedoch auch bestimmte Unterroutinen selektiv als formal abgedeckt markieren, die im Arranger abgelegt sind, und für die verbleibenden Unterroutinen den Deep-Modus beibehalten.
• Verwenden Sie die Schaltfläche „Set Covered" in der Arranger-Symbolleiste (oder das Kontextmenü-Element „Test-covered on/off" im Arranger-Index), um ein ausgewähltes Diagramm als abgedeckt zu markieren. (Die Schaltfläche ist nur im Testabdeckungs-Tracking-Modus aktiviert.) Ein so markiertes Unterroutinen-Diagramm ist an seinem grünen Außenrahmen erkennbar.
• Rekursive CALLs: Wenn im Deep-Modus verfolgt, könnte eine rekursive Routine nie abgedeckt werden (da das Grünwerden erfordern würde, dass der enthaltene rekursive CALL grün ist, was wiederum erfordert, dass die Routine grün ist, usw.). Daher wird ein als rekursiv erkannter CALL IMMER im Shallow-Modus verfolgt.

Hinweise

Abdeckungsmarkierungen werden beim Speichern eines Diagramms nicht gespeichert. Gleiches gilt für die Zählwerte.

Das Bearbeiten eines Diagramms löscht alle erfassten Laufzeitdaten und Markierungen, aber die Zahlen werden in der Undo-Liste zwischengespeichert. Wenn Sie die Änderungen rückgängig machen, wird der vorherige Abdeckungszustand wiederhergestellt.

Komplexes Beispiel

Die folgenden drei Bilder zeigen Phasen einer Code-Abdeckungsanalyse mit Structorizer. Das Hauptprogramm ist ein Testrahmen (Diagramm in der unteren rechten Ecke des Arranger-Fensters) für einen rekursiven QuickSort-Algorithmus mit mehreren verschachtelten Unterroutinen (Diagramme im übrigen Arranger-Bereich). Das erste Bild zeigt einen laufenden Test (beachten Sie, dass mehrere Unterroutinen-CALLs gleichzeitig auf verschiedenen Ebenen offen sind, erkennbar an der orangefarbenen Elementfarbe). Die verbleibenden zwei Bilder zeigen die Situation nach weiteren ausgeführten Tests.

Nach dieser letzten Phase im Deep-Modus sind alle Unterroutinen vollständig abgedeckt. Dies gilt jedoch nicht für das Testprogramm „SORTIERUNG_RAHMEN3", da der Sortieralgorithmus stets korrekt arbeitete, sodass der Fehlerpfad (mit der rosafarbenen Ausgabeanweisung) nie durchlaufen wurde. Um eine Inversionserkennung (d. h. einen Sortierfehler) zu provozieren, könnte die Routine „QuickSort" durch einen Dummy (mit demselben Namen, der aber nicht wirklich sortiert) ersetzt werden, bevor der nächste Test läuft. Damit würde die Abdeckung vollständig.

Ausführungszählung (Execution Counts)

Die erste der beiden kleinen Zahlen in der oberen rechten Ecke der Elemente stellt die Anzahl dar, wie oft das Element während der Tests durchlaufen wurde. (Alle Elemente mit Ausführungszählung größer als null sind zumindest im flachen Sinne „testabgedeckt".) Die Ausführungszählung wird erst inkrementiert, wenn der Kontrollfluss das Element verlassen hat.

Wenn Sie in der Anzeige-Auswahlliste execution counts (Ausführungszählungen) auswählen, werden die Elemente entsprechend dieser ersten Zählzahl in einem Spektralbereich von tiefem Blau bis leuchtendem Rot eingefärbt, wobei Tiefblau für 0 und Leuchtendes Rot für den höchsten Zählwert über alle beteiligten Diagramme steht.

Wie zu sehen ist, wurde die WHILE-Schleife nur einmal betreten und verlassen, aber der Schleifenrumpf musste 6-mal wiederholt werden. Somit ist 1 der kleinste und 6 der höchste vorhandene Zähler, dazwischen gibt es nichts. Daher treten nur zwei Farben auf. (Da innerhalb des Bereichs 0…5 ein Schritt von 1 relativ grob ist, ist das Blau nicht so dunkel, wie man bei Wert 1 erwarten könnte.)

Diese Analyse zeigt beispielsweise, wo eine Code-Optimierung wesentlich wäre (rote Bereiche) und wo sie nicht in Betracht gezogen werden müsste (blaue Bereiche).

Operationslast (Operation Load)

Die zweite der beiden kleinen Zahlen in der oberen rechten Ecke eines Elements stellt die Last der „atomaren" Operationen dar (rechts vom Schrägstrich).

Wenn Sie done operations lin. oder done operations log. auswählen, wird die Einfärbung der Diagrammelemente entweder durch lineare oder logarithmische Skalierung der Anzahl der „atomaren" Operationen vorgenommen. Die logarithmische Skala ist sinnvoller, wenn der Zahlenbereich sehr weit gestreut ist.

Zuordnungsregeln

Die Operationslasten für die verschiedenen Elementtypen sind:

• Instruction-Element: Anzahl der Anweisungszeilen innerhalb des Elements. Hinweis: Ein leeres Element zeigt immer 0, egal wie oft es durchlaufen wurde! Bloße Typdefinitionen tragen ebenfalls nicht zu den Operationslasten bei.
• EXIT-Element: 1;
• CALL-Element (für sich allein): 1 (das Organisieren des Stack-Abstiegs kostet Zeit);
• IF-Element: 1 für die Auswertung der Bedingung;
• CASE-Selektion: 1 für die Auswertung des verteilenden Ausdrucks;
• FOR-Schleife: 1 + n (Initialisierung und erster Test als eine Operation, Inkrement und Test bei jeder Wiederholung);
• WHILE-Schleife: 1 + n (erster Test und dann ein weiterer Test bei jeder Wiederholung);
• REPEAT-Schleife: n (Test nach jeder Rumpfausführung);
• ENDLESS-Schleife: 0 (kein Test);
• PARALLEL-Abschnitt: 0 (der Synchronisationsaufwand wurde hier vernachlässigt);
• TRY-Block: 0.

Wenn ein Element mehrfach durchlaufen wird, multiplizieren sich die oben genannten Werte entsprechend.

Diese Lasten beinhalten nicht die Lasten der Unterstrukturelemente – es ist nur der eigene Beitrag des jeweiligen Elements. Nur das Programm- (oder Funktions-)Element (d. h. der äußere Rahmen) zeigt die aggregierte Last der Operationen, die während des gesamten Programms / der Routine durchgeführt wurden (in Klammern). Die Einfärbung des Programm- bzw. Routinenelements spiegelt jedoch nicht die aggregierte Last wider, sondern basiert auf der eigenen Operationslast, die üblicherweise null beträgt (tiefblau im obigen Bild).

Aus dieser Einfärbung lässt sich ablesen, wo der größte Teil der Zeit verbraucht wird.

Hinweis: Bei Elementen vom Typ Alternative sind Benutzer manchmal verwundert, wenn eine hohe Zählzahl bei der Bedingung erscheint, aber sehr niedrige Operationslasten auf beiden Zweigen. Diese Situation tritt typischerweise auf, wenn einer der Zweige leer ist – ein leeres Element führt nichts aus, sodass seine Operationslast stets bei null bleibt! (Schauen Sie in solchen Fällen auf den Durchlaufzähler.)

Hinweis zu rekursiven Algorithmen: Bei rekursiven Algorithmen geben die Operationslasten nur einen Hinweis auf die Zeitverteilung auf der obersten Ebene (bzw. der aktuellen Ebene bei Unterbrechung). Andernfalls wäre die Gesamtsumme nicht korrekt, da die Operationslast der analogen Elemente auf aufgerufenen Ebenen bereits in den rekursiven CALLs aggregiert wurde. Dadurch kann es vorkommen, dass der Ausführungszähler einer Anweisung in einer rekursiven Routine größer ist als die angezeigte Operationslast.

Wenn Sie ein strukturiertes Element einklappen, erhöht sich seine angezeigte Operationslast um die Operationslasten der enthaltenen Elemente – als wären sie zusammengeschmolzen. Die Einfärbung des Elements ändert sich dabei jedoch nicht.

Für Folgen deklarativer Elemente im Anzeigemodus „Hide mere declarations?" gilt ähnliches wie für eingeklappte strukturierte Elemente – allerdings unterscheidet sich die Hintergrundfarbe vom normalen Anzeigemodus. Das Darstellungssurrogat für die Deklarationsfolge erscheint als deren Zusammenschmelzung (und wird wie im Modus Gesamtoperationslast eingefärbt).

Gesamtoperationslast (Total Operations Load)

Wenn Sie einen der Visualisierungsmodi total operations lin. oder total operations log. auswählen, wird die Einfärbung der Diagrammelemente durch entweder lineare oder logarithmische Skalierung der aggregierten Operationslast vorgenommen, d. h. die Last strukturierter Elemente umfasst rekursiv auch die Lasten ihrer jeweiligen Unterstruktur. Die aggregierten Operationszahlen bei strukturierten Elementen werden in Klammern eingeschlossen, um daran zu erinnern, dass es sich um zusammengesetzte Daten handelt.

Dieser Modus eignet sich gut zur Visualisierung der hierarchischen Aggregation und Lastverteilung. Das Programmelement gibt die Gesamtzahl der (fiktiven) Einheitsoperationen zur Durchführung der Berechnung an und kann als Schätzung für die Zeitkomplexität dienen, wenn Sie die funktionale Beziehung zur Anzahl oder Größe der zu verarbeitenden Daten finden.

Komplexes Beispiel

Die Einfärbung wird auch am komplexen Beispiel eines rekursiven QuickSort-Algorithmus mit mehreren verschachtelten Routinenebenen veranschaulicht.

Wahlfreiheit

Sobald die Runtime Analysis begonnen hat, können Sie frei zwischen den verschiedenen Visualisierungsmodi wechseln, die eingefärbten Diagramme in verschiedene Grafikformate exportieren, drucken, im Arranger anordnen usw. – bis Sie das Kontrollkästchen „Collect Runtime Data" abwählen, wodurch alle erfassten Daten gelöscht und die Anzeige in den Standardmodus zurückversetzt wird.

Wie bereits für den Testabdeckungsmodus erwähnt, speichert das Speichern eines Diagramms im nativen Dateiformat keine der gesammelten Ergebnisse. Wenn Sie die Ergebnisse dokumentieren möchten, müssen Sie das/die Diagramm(e) als Bild exportieren.