Benutzer:TMg/autoFormatter/Performance

Im Januar 2013 hatten die 1000 längsten Artikel in der deutschsprachigen Wikipedia eine Durchschnittsgröße von 172 KiB. Auch in solchen Fällen – einen halbwegs modernen Webbrowser vorausgesetzt – soll der Auto-Formatter mit seinen rund 200 Regeln ohne spürbare Verzögerung ausgeführt werden. Einige meiner bei diesen Optimierungen gewonnenen Erfahrungen habe ich hier aufgeschrieben.

Meine Codekonventionen

• Geschweifte Klammern grundsätzlich untereinander, außer in JSON-Objekten.
• Bei sehr einfachen if sind die Klammern ausnahmsweise optional, sonst eigentlich Pflicht.
• Auf eine Zeile zusammengezogene if, while etc. sind normalerweise tabu, da die Lesbarkeit darunter leidet. Die Bedingung gehört immer auf eine eigene Zeile, die Anweisung eingerückt darunter. Um die Dateigröße zu reduzieren, weiche ich hier ausnahmsweise davon ab.
• Zum Einrücken verwende ich normalerweise streng 4, manchmal auch nur 2 Leerzeichen. Zugunsten der Dateigröße verwende ich hier ausnahmsweise Tabulatoren.
• Keine Leerzeichen in Klammern. Leerzeichen in ( a, b ) laufen jeder Lesegewohnheit zuwider und behindern die Lesbarkeit damit sogar.
• Leerzeichen um jeden Operator mit zwei Seiten, also bspw. a = b % 2, nicht jedoch bei den einseitigen Operatoren a++, !a etc.
• Unterscheidung zwischen Funktionen und Sprachelementen anhand eines Leerzeichens vor der öffnenden Klammer. Funktionen erhalten nie eine Klammer, if () usw. immer.

Variablennamen

Einzelbuchstaben sind normalerweise tabu, da sie den Quelltext schlecht lesbar machen und Konflikte vorprogrammiert sind. Aus Platzgründen weiche ich hier davon ab.

• a: Array, <a>-Element oder einfach nur der erste Parameter in einer Funktion.
• c: Character.
• e: Element oder Event.
• ex: Exception.
• i: Index in einem Array oder String, meist als Zählvariable in einer Schleife.
• k: Key.
• m: Match eines regulären Ausdrucks.
• p: Position oder Parameter.
• r: Resultat.
• re: Regulärer Ausdruck.
• s: String.
• t: Text.
• v: Value.

Stringverarbeitung

String-Builder-Prinzip

Das Skript schützt Dateinamen, <math>-Ausdrücke und vieles mehr vor ungewollten Änderungen, indem es diese gegen Platzhalter austauscht (in meinem Fall bspw. <file>1</file>) und diese Ersetzungen abschließend umkehrt (hier im Pseudocode).

for (i = 0; i < platzhalter.length; i++)
{
    text = text.replace(platzhalter[i], sicherung[i]);
}

Ohne Profiling würde man gar nicht vermuten, dass sich hier ein Flaschenhals versteckt. Wie kommt man diesem bei?

• In solchen Fällen besteht häufig die Möglichkeit, die Länge einmalig vorzuberechnen oder die Schleife sogar umzukehren. Das ist vor allem beim unfassbar langsamen count() in PHP wichtig. In JavaScript ist der Zugriff auf length jedoch billig.
• Das replace() lässt sich mit einem indexOf() und zwei substr(), substring() oder slice() nachbauen.

for (i = platzhalter.length; i--; )
{
    position = text.indexOf(platzhalter[i]);
    text = text.slice(0, position) + sicherung[i] + text.slice(position + sicherung[i].length);
}

Tatsächlich bringt das in dem einen oder anderen Webbrowser ein paar Prozentpunkte, jedoch keinen Durchbruch. Wie auch, denn letztlich tut auch replace() intern genau das. Durch die Zerlegung wird jedoch endlich der Flaschenhals klar: Für jede Fundstelle wird der String als ganzes neu aufgebaut und der bisherige verworfen. Die Laufzeitumgebung kann in beiden Implementierungen nichts Schlaueres tun, als jedes mal ein neues Stringobjekt zu erzeugen und die drei Teile dort hin zu kopieren.

Die Lösung wirkt kompliziert, die Idee ist jedoch simpel: Wir motivieren die Laufzeitumgebung, intern mit einem String-Builder zu arbeiten, der kontinuierlich anwächst, anstatt dauernd große Stringobjekte neu zu erzeugen und wieder zu verwerfen.

neuerText = '';
vorherigePosition = 0;
for (i = 0; i < platzhalter.length; i++)
{
    position = text.indexOf(platzhalter[i], vorherigePosition);
    neuerText += text.slice(vorherigePosition, position) + sicherung[i];
    vorherigePosition = position + sicherung[i].length;
}
neuerText += text.slice(vorherigePosition);

Verwirrend ist, dass die Laufzeitumgebung eigentlich nicht wissen kann, dass sie einen String-Builder nutzen soll, da es keinen Konstruktor dafür gibt. Das ergibt sich implizit nur aufgrund der Art und Weise, wie mit der Variable umgegangen wird, in diesem Fall durch die ausschließliche Verwendung von += und +.

Eine wichtige Einschränkung ist, dass nun keine Funde vor bereits gemachten Funden mehr möglich sind. Die Reihenfolge der Platzhalter im Text muss zwingend aufsteigend sein.

Reguläre Ausdrücke

Backtracking vermeiden

…

In der Kürze liegt die Würze

• Die Zeichenklassen \d, \s und \w sowie ihre negierten Gegenstücke \D, \S und \W sollte man ebenso kennen wie die Sequenzen \b und \B, die für eine Wortgrenze und das Gegenteil davon stehen. Beispielsweise findet /\Ba\B/ alle „a“ innerhalb von Wörtern, nicht jedoch am Anfang oder Ende eines Wortes.
• Ein einfaches Oder ist auch ohne Klammern möglich: /a|b/. Das funktioniert in allen Browsern.
• Eine schließende eckige Klammer in einer Zeichenklasse muss logischerweise maskiert werden, die öffnende dagegen nie: /[[\]]/.
• Die Maskierung des Bindestrichs in einer Zeichenklasse kann man sich sparen, wenn man ihn ans Ende setzt: /[abc-]/.
• Genau genommen muss innerhalb von eckigen Klammern so gut wie gar nichts maskiert werden, außer der schließenden eckigen Klammer (logisch), dem Schrägstrich (sowieso), evtl. dem Bindestrich, wenn er nicht am Ende steht, sowie dem Backslash selbst.
• Geschweifte Klammern müssen eigentlich nicht maskiert werden, wenn gar keine Zahl darauf folgt. Es gibt allerdings einige nicht ganz so alte Browserversionen (Safari 5.0, Chrome 13), die darüber stolpern, deshalb sollte man zumindest die öffnenden Klammern immer maskieren: /\{\{a}}/.

Fallstricke und Kuriositäten

• Der Zugriff auf die Zeichen eines Strings per s[i] funktioniert bis einschließlich Internet Explorer 7 nicht. Es ist deshalb noch eine ganze Weile empfehlenswert, auf s.charAt(i) zu vertrauen, zumal der Arrayzugriff verwirrenderweise rein lesend ist. Bei der Funktion stellt sich diese Frage nicht.
• In JavaScript sind aus Performancegründen keine Look-behinds definiert, (?<=…) und (?<!…) können also nicht funktionieren. Look-aheads können dagegen bedenkenlos eingesetzt werden, sie funktionieren in allen Webbrowsern einschließlich Internet Explorer 6.
• Inline-Modifikatoren wie (?i…) gibt es nicht, außer in Konqueror. Na wenn das keine Kuriosität ist.
• Die Regex-Sequenzen \Q und \E funktionieren in keinem Browser, außer in … richtig, Konqueror. Er scheint einfach die Regex-Bibliothek von Perl zu nutzen und sich nicht um den ECMAScript-Standard zu scheren.
• Der Modifikator /s ist in JavaScript leider nicht definiert und wird – abgesehen von ein paar voreiligen Chrome- und Safari-Versionen – nirgends unterstützt.
• Für die Regex-Sequenzen $&, $' und $` habe ich in all den Jahren noch nie eine naheliegende Verwendung gefunden. Abgesehen von älteren WebKit-Versionen funktionieren sie zwar überall, aber wozu, wenn man dasselbe kompatibler und besser lesbar mit Klammern und $1 etc. erreichen kann?
• ECMAScript kennt kein $0.
• Google Chrome bis Version 12 meint, der typeof eines RegExp-Objekts wäre eine "function".