Optimierung für den Substitution-Solver

PHP ist nicht gerade sehr performant, wenn es um Zugriffe auf Arrays geht. Für normale Web-Anwendungen ist das nicht bemerkbar, aber für den Substitution-Solver ist dies eine arge Last. Viele viele tausend mögliche Schlüssel werden pro Sekunde durchprobiert, und sowohl der Schlüssel als auch der Geheimtext und der daraus resultierende Klartext werden in Arrays abgespeichert.

Trotzt intensiver Recherche konnte ich im Netz keine befriedigende Lösung finden. Die PHP-interne Implementierung kennt nämlich gar keine Arrays wie man sie z.B. klassisch von C oder anderen Programmiersprachen her kennt. Die Position eines Array-Elementes im Speicher wird nicht direkt aus dem Index berechnet. Stattdessen werden Arrays über Hashes implementiert. Beim Zugriff auf ein Array-Element wird der Index einer Hash-Funktion zugeführt, und mit dem so errechneten Hashwert werden die internen Datenstrukturen nach dem Array-Element durchsucht.

Für den PHP-Programmierer bleibt diese Implementierung verborgen, um diese Interna braucht er sich nicht kümmern. Für den Substitution-Solver allerdings macht sich das in einer verlängerten Laufzeit bei der Ausführung bemerkbar.

Daher wurde kurzerhand der C-Compiler ausgepackt und der Kern des Algorithmus' entsprechend aus PHP ausgelagert.

Eine grobe Vergleichsmessung ergibt, dass die C-Implementierung gegenüber PHP ungefähr um den Faktor 15 schneller ist.

Ich denke, das hat sich gelohnt.

Zurück