Der Highlighter basiert auf einem RegExp-Lexer und einem State-Stack, der das Nesting abbildet. Kurz: Er erkennt bestimmte Muster, z.B.
<?php, legt diese Information auf einen Stapel und behandelt nachfolgenden Code in diesem Kontext. Trifft er dann auf gleicher Ebene auf ein
?>, entfernt er die Info wieder vom Stapel und nimmt den darunterliegenden State (z.B. HTML) als neuen Kontext. So weit, so trivial.
Reguläre Ausdrücke sind zwar ein extrem mächtiges Werkzeug zur Mustererkennung in Zeichenketten, dafür sind sie nicht so performant wie z.B. ein linearer Parser. An jeder Stelle im Code gibt es zudem eine Reihe möglicher Fortsetzungen, abhängig vom Kontext, die alle geprüft werden müssen. Der wahrscheinlichste Treffer gewinnt. Das ist einfach der mit der niedrigsten Position. Erst die folgende Optimierung macht den Einsatz von RegExp für größere Texte überhaupt brauchbar:
Zunächst nummeriere ich jeden einmaligen regulären Ausdruck durch, unabhängig von dessen Kontext. Wird dieser ausgeführt und nicht als Treffer gekrönt, speichere ich dessen Nummer zusammen mit der Fundstelle. So kann ich im weiteren Verlauf schauen, ob bereits eine Fundstelle vorliegt, bevor ich ein teures RegExp ausführe. Je nach Code reduziere ich damit den Rechenaufwand auf ca. ein Sechstel.
Damit liege ich bereits in einem Bereich, der mehr als praktikabel ist. Auf meinem durchschnittlichen Entwicklungsrechner erreiche ich bei "normalen" Templates/Komponenten Werte von 1-5 ms für das reine Parsing. Meine Template-Engine mit 5.000 Zeilen Quellcode wird in 50-80 ms verarbeitet. Zudem sorgt ein Debouncing dafür, dass nur in Eingabepausen neu geparst wird. Viel mehr Zeit kostet dagegen das DOM-Update, also die Umsetzung des Highlighting durch den Browser, sowie die Wiederherstellung einer möglichen Textauswahl.
Ursprünglich hatte ich bei der Entwicklung die Ausführungszeit der einzelnen Abschnitte gemessen, aber später wieder vergessen. Mit 350 ms bei 5.000 Zeilen für den Gesamtvorgang (Parsing + DOM + Selection Restore) war es viel zu langsam für die produktive Arbeit. Da vergessliches Ich annahm, dass der Bottleneck im RegExp-Parsing liegt, wollte ich das Problem durch partielles Parsing lösen, also nur die Teile neu parsen, die sich auch geändert haben. Klingt logisch, oder?
Dazu muss man allerdings erstmal herausfinden, was sich geändert hat. Um das zu bestimmen, vergleiche ich den Anfang und das Ende des alten und neuen Textes, bis ich jeweils auf ein anderes Zeichen stoße. Das bedingt zwei Loops, die insgesamt jedes Zeichen einmal vergleichen müssen. Bei meinen 5.000 Zeilen sind das immerhin etwa 228 Tsd. Zeichen. Scheint viel, ist aber für einfache Zeichenvergleiche ziemlich billig... dachte ich. Zumindest billiger als RegExp.
Die andere Voraussetzung für das partielle Parsing ist die Speicherung aller State-Stacks für jede Highlighting-Position. Der Anfang lässt sich einfach überspringen, aber um das Ende des zu parsenden Bereichs festzustellen, muss ich prüfen, ob und wo der State-Stack mit dem vorherigen Parsing konvergiert. Ist der Zustand exakt gleich, bleibt der Kontext ab da konsistent, und ich kann das alte Highlighting verwenden. Jetzt muss ich nur noch die Parts zusammenkleben. Voila!
Das Ergebnis war für mich überraschend. Anstatt Zeit einzusparen, kostete der ganze Aufwand für das partielle Caching einige Millisekunden mehr – völlig unabhängig von der Textgröße. Nach einigen Stunden Gefrickel, die mich das gekostet hat, ein frustrierendes Outcome. Jeder Entwickler weiß, dass ein großer Teil der Motivation darin besteht, am Ende des Tals der Tränen das gelobte Land zu finden. Cold Turkey.
Eine weitere Stunde Prüfung auf einen möglichen Bug später machte ich alle Änderungen wieder rückgängig. Viel gelernt, nichts gewonnen. Immerhin stellte ich dabei fest, dass der Bottleneck gar nicht an der vermuteten Stelle saß. Der wahre Zeitfresser war das Einfügen des neuen Highlightings in das innerHTML des Contenteditable und zu 2/3 davon sogar die Wiederherstellung der Selection Range. Ein simples display none vor den DOM-Operationen reichte schon aus, um die Zeit dafür um 2/3 zu verkürzen. Doh!
Zwar ergab sich dabei noch ein anderes Problem, nämlich dass das dadurch kollabierende Elternelement die Scrollposition verlor, aber das ließ sich mit einem Extraelement austricksen, das über eine passende Mindesthöhe (Anzahl der Zeilen multipliziert mit der Zeilenhöhe) die Stellung hält. Im Ergebnis hatte ich damit mein Ziel erreicht, anders als geplant, aber am Ende kam ich doch in das gelobte Land des Programmierer-Bliss.
Das 5.000 Zeilen Script kaut mein Highlighter nun in durchschnittlich 150 ms durch, inkl. Ausgabe und Selection Restore. Das ist natürlich schon ein extremes Beispiel. Bei üblichem Codeumfang zuckt der Highlighter nicht mal mit der Wimper (1-3 ms). Mit gerade mal 250 Zeilen (plus CSS) erreiche ich die Performance gängiger Lösungen ohne den Overhead, den diese mit sich bringen. Dafür darf man sich schon ein wenig auf die Schulter klopfen.
0 Kommentar(e)