Kürzliche Entwicklungen
... [ Seminar Programmiersprachen und virtuelle Maschinen ] ... [ Google's V8 ] ...
[ << Schlüssel Elemente ] ... [ Fazit >> ] ...
Übersicht: Kürzliche Entwicklungen
Irregexp
Im Jahre 2009 hat Google eine neue Engine für reguläre Ausdrücke entwickelt, da sie für die bisher genutzte JSCRE-Bibliothek (Javascript Compatible Regular Expressions) Strings konvertieren mussten.
Die Irregexp Engine implementiert alle JavaScript Regulären Ausdrücke ohne auf fremde Bibliotheken zurückgreifen zu müssen und ist 10 mal schneller als die JSCRE.
Vorgehen
Die Irregexp Engine baut zunächst aus dem Regulären Ausdruck einen Automaten auf. Dieser wird erst analysiert und dann optimiert. Aus dem optimierten Automaten wird nun nativer
Maschinencode generiert. Dadurch werden alle Regulären Ausdrücke als nativer Maschinencode ausgeführt. Zudem benutzt die Irregexp ein paar Tricks, um Backtracking zu vermeiden, und sortiert
Operationen nach ihrem Aufwand.
Beispiele
- Masken
Aus einer alternativen Suche nach Dienstag oder Mittwoch, erzeugt die Irregexp die Maske ?i??????. Damit sucht sie zunächst nur Worte an dessen zweiter Stelle
ein i auftaucht. Ist dies nicht der Fall, kann abgebrochen werden, ansonsten wird mit Dienstag oder Mittwoch verglichen.
- Vergleich von Bit-Patterns
Die Irregexp vergleicht 4 Ascii-Zeichen in einer Anweisung über Bit-Patterns. Dadurch wird aus foobar ein Vergleich auf 0x666f6f62 und 0x6172. Dies bringt
enorme Geschwindigkeitsvorteile, da 4 Zeichen in einer Instruktion verglichen werden können. Wieder kann abgebrochen werden, wenn ein 'Byte' nicht passt.
- Sortieren nach Aufwand
Ein weiterer Punkt ist das Sortieren nach Aufwand. Die Irregexp führt dabei einfache Operationen zuerst aus, um eventuell abbrechen zu können, wenn ein Wort nicht passt. Zum Beispiel wird
die Suche nach ([fF]oo[bB]ar) wie folgt aufgeteilt. Zunächst vergleicht die Irregexp die Positionen 1 und 4 auf oo und ar. Ist dies der Fall, wird die 0.
Position auf f oder F verglichen. Ist auch dies der Fall, wird zuletzt die Position 3 auf b oder B verglichen. Wenn alles zutrifft, wird der Treffer
zurückgegeben, ansonsten wird abgebrochen.
Neue Compiler Infrastruktur
Der ursrpüngliche Kompiler war sehr simpel, führte keine statischen Analysen durch, allozierte keine Register und aus dem Code wurde ein abstrakter Syntax-Baum generiert. Der neue Compiler
kompiliert, wie der Alte, alles in einem Durchgang, auch Single-Pass-Compiler genannt. Er alloziert nun auch Register und gibt die Möglichkeit für zukünftige Optimierungen am Compiler.
... [ Seminar Programmiersprachen und virtuelle Maschinen ] ... [ Google's V8 ] ...
[ << Schlüssel Elemente ] ... [ Fazit >> ] ... [ nach oben ] ...