Ich habe jetzt ein anderes implementiert SHA3-Kandidat, nämlich Grøstl. Dies ist immer noch in Arbeit (sehr), aber im Moment übergibt eine 224-Bit-Version alle KATs. So, jetzt frage ich mich über die Leistung (wieder: - & gt;). Der Unterschied liegt diesmal darin, dass ich die (optimierte) C-Implementierung genauer nachgebildet habe, also aus der ich einen Port gemacht habe C nach Haskell. Die optimierte C-Version verwendet Tabellen-Lookups, um den Algorithmus zu implementieren. Außerdem basiert der Code stark auf der Aktualisierung eines Arrays, das 64-Bit-Wörter enthält. Daher entschied ich mich dafür, in Haskell veränderbare ungepackte Vektoren zu verwenden.
Mein Grøstl-Code finden Sie hier: Ссылка
Kurze Beschreibung des Algorithmus: Es ist eine Merkle-Damgård-Konstruktion, die eine Komprimierungsfunktion ( f512M in meinem Code) wiederholt, solange 512-Bit-Blöcke von Nachrichten übrig sind. Die Komprimierungsfunktion ist sehr einfach: Sie führt einfach zwei verschiedene unabhängige 512-Bit-Permutationen durch P und Q ( permP und permQ in meinem Code) und kombiniert ihre Ausgabe. Es sind diese Permutationen, die durch Nachschlagetabellen implementiert werden.
Q1) Das erste, was mich stört ist, dass die Verwendung von veränderbaren Vektoren meinen Code wirklich fugig aussehen lässt. Dies ist das erste Mal, dass ich irgendeinen änderbaren Hauptcode in Haskell schreibe, also weiß ich nicht wirklich, wie ich das verbessern kann. Irgendwelche Tipps, wie ich den monadischen Code besser strukturieren könnte, wären willkommen.
Q2) Die zweite ist die Leistung. Eigentlich ist es nicht so schlimm, denn im Moment ist der Haskell Code nur 3 mal langsamer. Verwenden von GHC-7.2.1 und Kompilieren als solche:
ghc-O2-Odph -flllm -optlo-O3 -optlo-loop-reduce -optlo-loop-deletion
Der Haskell-Code verwendet 60s. bei einer Eingabe von ~ 1GB, während die C-Version 21-22s verwendet. Aber es gibt einige Dinge, die ich seltsam finde:
(1) Wenn ich versuche, rnd512QM einzubinden, dauert der Code 4-mal länger, aber wenn ich inline rnd512PM nichts passiert! Warum passiert dies? Diese beiden Funktionen sind praktisch identisch!
(2) Das ist vielleicht schwieriger. Ich habe damit experimentiert, die beiden Permutationen parallel auszuführen. Aber momentan ohne Erfolg. Dies ist ein Beispiel für das, was ich versucht habe:
%Vor%Beim Überprüfen der Laufzeitstatistiken und mithilfe von ThreadScope habe ich festgestellt, dass die richtige Anzahl von SPARKS erstellt wurde, aber fast keine wurde tatsächlich in nützliche parallele Arbeit umgewandelt. So habe ich an Beschleunigung nichts gewonnen. Meine Frage wird dann:
Vielen Dank für Ihre Zeit.
BEARBEITEN:
Entschuldigen Sie, dass Sie keine echten Benchmark-Tests durchgeführt haben. Der Testcode im Repo war nur für mich gedacht. Für diejenigen, die den Code testen möchten, müssen Sie main.hs kompilieren und dann wie folgt ausführen:
./ main "Algorithmus" "testvariant" "Byte ausgerichtet"
Zum Beispiel:
./ main groestl short224 Falsch
oder
./ main groestl e Falsch
( e steht für "Extreme". Es ist die sehr lange Nachricht, die mit dem NIST KATS geliefert wird).
Ich habe das Repo überprüft, aber es gibt keinen einfachen Benchmark, mit dem man einfach nur laufen und spielen kann, also sind meine Ideen nur daran, den Code zu sehen. Die Nummerierung hat nichts mit Ihren Fragen zu tun.
1) Ich bin mir ziemlich sicher, dass force nicht das tut, was Sie wollen - es zwingt tatsächlich eine Kopie des zugrunde liegenden Vektors.
2) Ich denke, die Verwendung von unsicherem Tau und unsicherem Gefriergut ist irgendwie merkwürdig. Ich würde einfach f512M in die ST-Monade setzen und damit fertig sein. Dann führe es so aus:
%Vor% 3) V.foldM' ist irgendwie albern - Sie können einfach eine normale (strikte) foldM über eine Liste verwenden - Faltung über den Vektor im zweiten Argument scheint nichts zu kaufen.
4) Ich bin zweifelhaft wegen der Pony in columnM und für die unsafeReads.
Auch ...
a) Ich vermute, dass das Xoring von ungepackten Vektoren wahrscheinlich auf einer niedrigeren Ebene als zipWith implementiert werden kann, indem Data.Vector-Internals verwendet werden.
b) Es ist jedoch besser, dies nicht zu tun, da dies die Vektorfusion beeinträchtigen könnte.
c) Bei Betrachtung sieht extractByte etwas ineffizient aus? Anstatt fromIntegral zum Abschneiden zu verwenden, verwenden Sie möglicherweise mod oder quot und dann eine einzelne vonIntegral, um Sie direkt zu einem Int. Zu bringen.
Stellen Sie sicher, dass Sie mit -threaded -rtsopts kompilieren und mit +RTS -N2 ausführen. Ohne dies haben Sie nicht mehr als einen Betriebssystem-Thread, um Berechnungen durchzuführen.
Versuchen Sie, Berechnungen zu generieren, auf die an anderer Stelle verwiesen wird, andernfalls könnten sie gesammelt werden:
_
%Vor%_
3) Wenn Sie die Dinge ändern, so akzeptiert parseBlock strikte Bytestrings (oder Chunks und packt faule Bytes, wenn nötig), dann können Sie Data.Vector.Storable verwenden und möglicherweise einige Kopien vermeiden.
Tags und Links haskell performance parallel-processing mutable