Interview mit Core-Developer Gustavo Lopes

Feinjustierung im PHP-Core: strtr() gegen str_replace()
Kommentare

PHP-Core-Entwickler Gustavo Lopes hat mit uns über eine der jüngsten Neuerungen im PHP-Core gesprochen: Er hat strtr() generalüberholt. Jetzt arbeitet die Funktion für Zeichenketten-Manipulation viel schneller. Lopes erklärt uns, was das im Alltag bedeutet und wie der Boost möglich wurde.

PHP Magazin: Vor wenigen Tagen hast du einen Benchmark zu strtr() vs. str_replace() veröffentlicht. Dabei wurde die strtr()-Implementierung in einigen Tests um Größenordnungen schneller als bisherige Versionen. Was bedeutet das für den Entwickler im Alltag?

Gustavo Lopes: strtr() (mit zwei Argumenten) war in manchen Fällen unverwendbar langsam. Das habe ich jetzt behoben, und auch in den meisten anderen Fällen sollte es jetzt viel schneller laufen.

strtr() is now a better option performance-wise [than str_replace()]

Gustavo Lopes

strtr() war besonders langsam, wenn es Muster sehr unterschiedlicher Länge verarbeiten sollte. Gehen wir also von einem Input-Text mit einer bestimmten Länge aus, wurde der Algorithmus in einer Zeit durchlaufen, die proportional war zur strlen(„längster String im Muster“)strlen(kürzester String im Muster“).

Die neue Implementierung könnte etwas langsamer laufen, wenn man nur mit kurzen Strings arbeitet. Grund dafür ist ein neuer Vorberechnungsschritt, der zusätzliche Rechenzeit erfordert.

Ich will anmerken, dass strtr() in der Form strtr(string $str, string $from, string $to) nicht betroffen ist, da es einen anderen Algorithmus nutzt. Ihm liegt eine 256-Byte-Lookup-Tabelle T zu Grunde, in der T(i) (i = [0…255]) den Charakter bezeichnet, der (unsigned char)i ersetzt.

Auf Anwendungsebene bedeutet das, dass das neue strtr() aus Performancesicht verglichen mit str_replace() die bessere Wahl ist. Ausnahmen stellen hier Ersetzungen einzelner Strings dar. Ebenfalls nicht zu empfehlen ist strtr(), wenn man auf das Verhalten von str_replace() angewiesen ist, und beim Ersetzen der Strings die Reihenfolge derselben beibehalten will.

PM: Wie hast du den Leistungssprung erreicht?

Lopes: Das war nicht schwer. Der ursprüngliche Algorithmus war ziemlich dürftig. Im Grunde hatte es einen Vorberechnungsschritt, bei dem eine Hashtabelle erstellt wird mit den Mustern als Keys und den Ersetzungen als Values. So weit so gut. Aber dann würde es über jede Stelle des Textes iterieren, und für jede Stelle den Text zwischen dieser Position und n betrachten, und n sind alle(!) Werte zwischen strlen(längster String des Musters) und strlen(kürzester String des Musters). Hätte man also zwei Muster mit den Längen 1 und 1000, dann würde der Algorithmus an jeder Stelle im Text 1000 Substrings ausprobieren, obwohl nur zwei davon (1 oder 1000) passen könnten. Schlimmer noch: Um jeden dieser Substrings mit den Hashtabellenkeys (den Mustern) abzugleichen, musste es den Substring hashen. Jeder dieser Hashes wurde einzeln berechnet. Das ist verschwenderisch. Wenn man, so wie dort, einen Rolling Hash verwendet, gibt es Methoden mit weit weniger Rechenaufwand, um den Hash des Substrings A[a…a+n-1] vom Substring A[a…a+n] zu berechnen.

Also habe ich ein paar Optimierungen vorgenommen. Ich habe nur Substrings der Größe betrachtet, die in der Pattern-Liste vorkommen. Und ich lasse den errechneten Hash für jede betrachtete Substring-Größe speichern und ihn in der nächsten Iteration wennmöglich updaten, anstatt ihn komplett neu zu berechnen. Im Grunde war es ein Rabin-Karp-Algorithmus, angepasst auf Muster unterschiedlicher Größe (und so, dass er an jeder Stelle n Substrings hasht anstatt nur einen, wobei n die Zahl unterschiedlicher Mustergrößen sei).

Danach war ich noch nicht zufrieden mit der Leistung, also habe ich mich nach anderen Algorithmen umgeschaut. Am Ende habe ich den implementiert, der in diesem Bericht erläutert wird.

A Fast Algorithm For Multi-Pattern Searching (1994)

Meine Implementierung ist eng an den Bericht angelehnt. Die einzigen Kniffe, die ich anwenden musste, waren Anpassungen, sodass er mit Ersetzungen zurechtkommt, und dass die Muster nicht nur nach dem Hashwert sortiert werden, sondern bei Gleichheit auch nach absteigender Stringlänge.

PM: Wann wird das Feature implementiert?

Lopes: Im nächsten Release von PHP 5.4. [Anm. d. Red.: PHP 5.4.12 sollte Mitte Februar 2013 erscheinen]

Gustavo Lopes stammt aus Portugal, lebt aber seit Dezember 2011 in Utrecht. In Lissabon hatte er Biomedical Engineering studiert. Schon seit Ende 2010 hat er an der PHP-Runtime mitentwickelt. Dabei hat er sich hauptsächlich mit den Modulen ext/standard, ext/intl und ext/sockets sowie mit der Streams-Komponente beschäftigt. Des Weiteren pflegt er die PECL-Pakete rar, intl und markdown. Beruflich entwickelt er aktuell Java Middleware. Doch schon in naher Zukunft wird sein derzeitiges Projekt zum Abschluss kommen, sodass er eventuell ins PHP Userland Coding zurückkehrt.
Unsere Redaktion empfiehlt:

Relevante Beiträge

Meinungen zu diesem Beitrag

X
- Gib Deinen Standort ein -
- or -