Im dritten Teil geht es um die Parallelisierung mit OpenMP. Auf dem Arbeitsrechner werden 1000 zufällig gefüllte Strings in 71.6 sec. Der Algorithmus ist trivial über die äusserste Schleife zu parallelisieren, da ein String unabhänig der anderen Berechnet werden kann. Um eine schnelle Übersicht über die systime zu bekommen, wird das Programm mittels dem Hilfsprogramm […]
24.04.2018
23.04.2018
C++ Guns: branch free min() with Conditional Move CMOVcc
In der Regel wird die min() Funktion mittels Verzweigung implementiert. Ohne zusätzliche Optimierung führt dies zu einem Sprung im Code und damit zu Branchs Mispredicts. Dies ist gerade beim HPC Code ziemlich schlecht, da im Fall einer falscher Sprungvorhersage die CPU Pipeline wieder zurückgesetzt werden muss. Es gibt aber Alternativen: Conditional Move CPU Instruktionen. Je […]
22.04.2018
C++ Guns: Levenshtein-Distanz - Teil 2
Von der Compiler Optimierung O3 habe ich mir keine weiteren Geschwindigkeitsgewinn erhofft, aber dass das Programm doppelt so langsam! wurde, da stand mir dann doch der Mund offen ;) Das ist btw. auch das erste mal in meinem Programmiererleben, dass O3 die Laufzeit wirklich deutlich verschlechtert. Bisher hatte ich nur davon gehört. Ein schneller Blick […]
20.04.2018
C++ Guns: Levenshtein-Distanz - Teil 1
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 […]
11.04.2018
C++ Guns: Return function from function with same signature
Funktionen können Funktionen als Rückgabe Type/Wert haben, solange sie die selbe Signatur vorweisen. Also z.B. alles Binary Funktionen mit Argumenten von Type double.
08.04.2018
Python's 'Nase' + Python's 'Essen'
Lecker mjam mjam schmatz quetsch schluck satt. Python - what else did you think?
03.04.2018
C++ Guns: sort() mit Visitor
Wen hat es nicht schon einmal gestört, dass std::sort() so transparent arbeitet? Manchmal muss man wissen welche Elemente beim Sortieren wohin verschoben werden. Sozusagen eine Permutation. Manchmal ist es möglich, den zu sortierenden Daten eine ID mitzugeben. Aber oft nicht. Zum Beispiel arbeite ich mit 2D Punkten. Diese liegen natürlich schön dicht gepackt im std::vector, […]