Die Levenshtein-Distanz (auch Editierdistanz) zwischen zwei Zeichenketten ist die minimale Anzahl von Einfüge-, Lösch- und Ersetz-Operationen, um die erste Zeichenkette in die zweite umzuwandeln. Die Laufzeit Komplexität liegt bei quadratisch. Wie schnell ist das? Getestet werden 1000 Sequencen mit 200 Zeichen Länge.
Die erste Implementierung von Wikipedia lasse ich im Debug Modus laufen und komme auf eine Laufzeit von 1700sec! Ein erster Blick in den Profiler zeigt, dass kein Speicher dynamisch allokiert wird, und 40% der Rechenzeit in der innersten doppelten Schleife auftritt. Sowohl von der Anzahl der Instruktionen als auch von den Branch Misses tritt diese Zeile hervor:
v1[j+1] = std::min(v1[j]+1, std::min(v0[j+1]+1, v0[j]+cost));
Die min() Funktion ist natürlich der Hauptgrund für die Branch Misses. So kann die CPU schlecht vorhersagen, wie die Sequenz editiert werden muss. Da hier nur mit Integer gearbeitet wird, kann std::min() durch eine andere Funktion ersetzt werden, welche keine Verzweigung beinhaltet. Dafür kostet sie mehr Rechenpower. Ob sich der Wechsel lohnt, sehen wir später.
Erstmal schalte ich auf Release Modus um, damit die std Funktionen geinlint werden und der Flaschenhals besser hervortritt. Jetzt beträgt die Laufzeit 97.2sec. Mehr als 10mal schneller als im Debug Modus. Und dabei ist nur mit O2 compiliert worden. Ich schalte erst später auf O3 um, wenn ich den Code gut kenne und paar Sachen schon verbessert habe.
Die fragliche Zeile wird jetzt mit 42% Instruktionen und 50% Branch Mispredict angezeigt. Die anderen 50% kommen von der Simplen Kopie von v1 nach v0. Diese Zeile wird in Wikipedia sogar als einfache swap Operation angezeigt. Das kann also besser Implementiert werden. Mit std::swap lassen sich zwei std::vectoren schnell swappen. Die Laufzeit beträgt jetzt 73.6sec ein deutlicher Gewinn!
Die innerste SChleife wird mit nahezu 100% Instruktionen und 96% Branch Mispredict angezeigt. Klar hier passiert ja die meiste Arbeit. Interessanterweise wird bei std::min kein einziger Branch Mispredict mehr angezeigt. Sondern nur beim Schleifenkopf. Nun die innerste Schleife wurde bisher 46901*200=9380200 mal ausgeführt. Und es gab 9380069 Mispredicts. Ist ja klar. Es wird angenommen, dass die Schleife immer läuft. Aber einmal ist sie zu Ende, dann gibt es den Mispredict. Da wir mit festen Sequencelängen rechnen, könnte man die Schleife komplett ausschreiben. Aber das ist in der Praxis wahrscheinlich dann nicht der Fall.
Von den Instruktionen fallen 12% auf den Schleifenkopf. Also die Variable j Vergleichen und Inkrementieren. Der Rest fällt auf den Schleifenkörper. Wenn man genau hinschaut, erkennt man 5 Additionen, 6 Array Zugriffe, 1 Vergleich und 2 mal die min() Funktionen. Plus ein paar Kopieraktionen. Macht zusammen mindestens 14 Operationen. Ob Valgrind pro Operation nun auch eine Instrktion zählt weiss ich nicht, aber man kann ja mal abschätzen. Valgrind hat knapp 26 Milliarden Instruktionen gezählt. Geschätzt komm ich auf 9380200*14= 131 Millionen. Also wird Valgrind wohl wirklich CPU Instruktionen zählen. Na, wär ja auch schlimm wenn nicht ;)
Außer eine Parallelisierung sehe ich jetzt keine großartiges Optimierungspotential. Man kann noch von Hand Richtung SSE arbeiten und auch die Compiler Optimierung O3 versuchen. Aber dynamik Programming Algorithmen sind nunmal von Natur aus langsam. Nur durch eine Sortierung der Sequenzen könnte man noch etwas reißen. Aber das kommt dann im dritten Teil.
Im Anhang der Code.
LevenshteinTerror1.zip