Wäre das Kompilieren eines Regex in native Assembly schneller als PCRE oder andere Regex-Engines?

Question

Ich dachte über eine Verbesserung nach. Ich mache gerade viel Textverarbeitung von Protokolldateien.

Ich will nicht sagen, PCRE ist langsam/schnell oder irgendeine andere Implementierung für diese Angelegenheit.

Die Sprache, in der ich schreibe, ist in erster Linie Perl. Ich weiß, dass es eine leistungsstarke Regex-Engine hat und ich weiß, dass es expressiver ist als PCRE.

Ich habe diese Idee über eine kleine Regex-Engine in C++, die eine Regex auf rohe Nasm kompilieren würde.

Ich bin mir bewusst, dass PCRE ziemlich komplex ist, und ich gehe davon aus, dass ich viele Dinge, die von PCRE gemacht wurden, im Hinblick auf nicht notwendige Verarbeitung überspringen kann. Und ich könnte das sicherlich schneller machen als Perl, da es mit vm-ähnlichen Opcodes und allen möglichen Dingen arbeitet, die als Overhead betrachtet werden könnten.

Ich habe schon vor einiger Zeit eine Implementierung gestartet. Ich werde es hier nicht posten, da ich keine Probleme damit habe, ich könnte es bis zum Ende ausführen und eine Regex-Engine erhalten, die in der Lage ist, Captures zu machen, die in der Lage sind, Zeichenklassen zu interpretieren Ich habe den Teil nicht getan, wo ich die Regex in Assembler-Sprache umwandeln werde)

Wäre das eine gute Idee oder eine schlechte Idee? Was könnte schiefgehen, wenn es darum geht, eine gute Leistung zu erzielen?

tl; dr => könnte eine C++ - Mini-Regex-Engine, die eine native Assembly erzeugt, schneller sein als etablierte Regex-Implementierungen?

Answer 1

Ich denke, die Antwort zu diesem ist ziemlich offensichtlich. Im Idealfall, ja, könnte es sein. Aber selbst wenn Sie klug sind bei dieser Art von Sache, würde es einen sehr großen Entwicklungsaufwand erfordern, um zu einem Punkt zu kommen, an dem Sie größtenteils nur geringfügig besser als verfügbare Bibliotheken sind - und sogar noch länger zum Arbeiten alle Fehler aus. Es hat also nicht viel Sinn.

Answer 2

Perls Regexp ist schnell, aber nicht blitzschnell. Sehen Sie Russ Cox's analysis of Perl vs. Thompson-style regexp engines für eine Auge knallende Demonstration auf dem Unterschied in der Leistung und in der Theorie, wie man es richtig macht.

Wenn Sie das Schema von Thompson/Cox nicht implementieren möchten, sollten Sie in Betracht ziehen, ein sehr schneller Prozessor für reguläre Ausdrücke. Ragel erledigt die harte Arbeit des Aufbaus effizienter Automaten und generiert dann Code für Ziel-Compiler-Sprachen. Es ermöglicht dem Compiler die harte Arbeit, "Maschinencode" zu konvertieren.

Es ist wahrscheinlich der Motor, den Sie planen zu bauen.

Wenn diese nicht gut genug sind, sollten Sie die neuesten Arbeiten von IBM in extrem schnellen Stream-Matchern aufspüren. Ich denke Papiere von Davide Pasetto sind wahrscheinlich relevant.

Answer 3

Sie könnten wahrscheinlich erheblich mehr Leistung aus einem Regex kompromittieren, um Maschinenbefehle zu kompilieren. Ob es sinnvoll ist, hängt davon ab, wie Sie die Kosten amortisieren.

Wenn Sie versuchen, das spezifische Ziel der Analyse von Protokolldateien zu erreichen und eine Frist haben, könnte es dann nicht sinnvoll, auch diese zu betrachten, bis Sie bewährte haben, die vorhandenen Bibliotheken (einschließlich Google's RE2) zu langsam sind für Sie.Sich über Ihre RE-Leistung Sorgen zu machen, bevor Sie festgestellt haben, dass es sich um einen Engpass handelt, ist ein klassischer Fall einer vorzeitigen Optimierung.

Wenn Sie dies jedoch als eine Herausforderung und Lernübung tun wollen, und es keine Frist droht, dann versuchen Sie es auf jeden Fall. Bereite dich auf eine Menge Arbeit vor und vergiss nicht, viele Testfälle zu schreiben, weil es Bugs geben wird. Ihre Regex-Engine wird die entscheidende Grundlage des gesamten Arbeitsprodukts sein, und Sie können es sich nicht leisten, dass sie sich in der Produktion schlecht benimmt.

Viel Glück!

Answer 4

Machen Sie einfach einen Benchmark. Nehmen Sie eine Regexp, die ziemlich einfach ist, aber etwas, das Sie häufig verwenden würden. Dann erstellen Sie eine fest codierte Version dieser Regexp. Vergleichen Sie realistische Datenmengen, bei denen der Vorgang lange genug dauert, um die Beschleunigung zu beschleunigen.

Ich denke, jeder gute Regexp-Engine innere Schleife ist bereits ziemlich optimiert, mit beiden State-of-the-Art-Text-Matching-Algorithmen, und sind optimiert, um sie schnell zu tun. So viel Glück, schneller mit Ihrem eigenen Code, wenn Ausdruck nicht etwas Triviales ist (zB Char-Klassen).

Offensichtlich gibt es Overhead, Sie könnten hart-Code-Zeug tun es auf Ihre Weise und erreichen eine schöne lineare Beschleunigung, alles andere gleich. Aber das ist sekundär zu guten Algorithmen, und wenn Sie nicht vertraut sind mit Konzept der algorithmischen Komplexität, read up on that ersten.

---

Aber es gibt eine kritische Sache, die fast ein Showstopper für den realen Einsatz ist. Regexp-Engine muss korrekt sein. Es muss finden, was es soll, mit Null-Falsch-Positiven. Schlechte Dinge können passieren, wenn Sie eine falsche Übereinstimmung erhalten oder eine Übereinstimmung verpassen, z. B. Datenbeschädigung. Wie erreichen Sie ein hohes Vertrauen in Ihren Motor, um es zu wagen?

Erstellen Sie eine für Spaß, sicher. Für echte Produktionsanwendung ... umm ...

Wenn Sie möglicherweise ernsthafte sind, benötigen Sie einen automatisierten Test von Anfang an. Für etwas wie Regexp wollen Sie auch Code-Coverage-Analyse für Ihre Tests. Da Sie eine deterministische Eingabe und Ausgabe, keine Benutzereingaben oder irgendetwas haben werden, sollten Sie letztendlich eine 100% ige Abdeckung relevanter Teile des Codes anstreben, sowohl für die Engine als auch für den generierten Code Ihrer Test-Regexps. Oh, und vergessen Sie auch nicht automatische Benchmarks, wenn das Ziel Geschwindigkeit ist! Natürlich wollen Sie zuerst Kodierung und kümmern sich nicht darum, und das ist in Ordnung, aber richten Sie die Infrastruktur von Anfang an ein, und wenn Sie Ihren Code testen, schreiben Sie ihn als automatisierten Test, widerstehen Sie dem Ad-hoc-Test manuell (außer als Schritt zum Schreiben eines automatisierten Testfalls). Ihr Projekt hat viel höhere Erfolgsaussichten, wenn Sie die Dinge richtig machen.

Für generierten Code, LLVM ist wahrscheinlich, was Sie anstelle von Assembler von bestimmten CPU verwenden möchten.