Faster String GetHashCode (z. B. mit Multicore oder GPU)

Eine Möglichkeit, eine Funktion schneller zu machen, besteht darin, Sonderfälle zu berücksichtigen. Eine Funktion mit variablen Größeneingaben hat Sonderfälle basierend auf der Größe.

Parallel zu gehen macht nur dann Sinn, wenn es parallel läuft ist kleiner als die Verstärkung, und für diese Art der Berechnung ist es wahrscheinlich dass die Schnur ziemlich groß sein müsste, um die Kosten zu überwinden einen parallelen Faden zu forken. Aber das umzusetzen ist nicht schwer. im Grunde brauchen Sie einen Test dafür. Die Länge übersteigt empirisch bestimmte Schwelle und dann mehrere Threads zum Berechnen Gabeln Hashes auf Teilstrings, mit einem abschließenden Schritt, in dem die Subhashs zusammengefügt werden ein endgültiger Hash. Implementierung bleibt dem Leser überlassen.

Moderne Prozessoren haben auch SIMD-Anweisungen, die aufbereiten können zu 32 (oder 64) Bytes in einem einzelnen Befehl. Dies würde Ihnen erlauben um die Zeichenkette in 32 (16 Bit Zeichen) Chunks in eins-zwei zu verarbeiten SIMD-Anweisungen pro Chunk; und falte dann das 64-Byte-Ergebnis in ein einzelner Hashcode am Ende. Dies ist wahrscheinlich sehr schnell für Saiten jeder vernünftigen Größe. Die Umsetzung dieses aus C # ist schwieriger, weil man keine virtuelle Maschine erwartet Bereitstellung eines einfachen (oder tragbaren) Zugriffs auf die SIMD-Anweisungen das brauchst du. Die Umsetzung bleibt auch dem Leser überlassen. EDIT: Eine andere Antwort schlägt vor, dass Mono-System bietet SIMD-Befehlszugriff.

Nachdem das gesagt wurde, ist die gezeigte Implementierung ziemlich dumm. Die wichtigste Beobachtung ist, dass die Schleife das Limit zweimal bei jeder Iteration überprüft. Man kann dieses Problem lösen, indem man die Endzustandsfälle im Voraus prüft, und Ausführen einer Schleife, die die korrekte Anzahl von Iterationen durchführt. Man kann es besser machen, indem man benutzt Duffs-Gerät in eine entrollte Schleife von N Iterationen springen. Das wird los der Loop-Limit-Prüf-Overhead für N-1-Iterationen. Diese Änderung wäre sehr einfach und sicherlich die Mühe wert, um zu implementieren.

BEARBEITEN: Sie können auch die SIMD-Idee und die Loop-Abrollungsidee kombinieren, um die Verarbeitung vieler Blöcke von 8/16 Zeichen in einigen SIMD-Anweisungen zu ermöglichen.

Für Sprachen, die nicht in Schleifen springen können, kann man das Äquivalent von Duffs Gerät, indem er einfach die ersten Fälle ablöste. Ein Schuss auf Wie man den ursprünglichen Code mit dem Loop-Peeling-Ansatz umsetzt, ist folgender:

Ich habe diesen Code nicht kompiliert oder getestet, aber die Idee ist richtig. Es hängt davon ab, dass der Compiler eine vernünftige konstante Faltung durchführt und Adressarithmetik.

Ich habe versucht, das zu kodieren, um den genauen Hash-Wert des Originals zu erhalten, aber IMHO das ist nicht wirklich eine Anforderung. Es wäre noch einfacher und ein kleines bisschen schneller, wenn es nicht verwendet würde der num / num2-Stunt, aber einfach aktualisierte num für jedes Zeichen.

Korrigierte Version (von Brian) als statische Funktion:

Sie könnten dies parallelisieren, aber das Problem, mit dem Sie konfrontiert werden, ist, dass Threads, CUDA usw. mit Gemeinkosten verbunden sind. Auch wenn Sie einen Thread-Pool verwenden, wenn Ihre Strings nicht sehr groß sind, sagen wir, ein typischer String ist 128-256 Zeichen (wahrscheinlich weniger als dieser), werden Sie wahrscheinlich immer noch länger dauern als jedes Gespräch .

Wenn Sie jetzt mit sehr großen Saiten arbeiten, dann würde das ja Ihre Zeit verbessern. Der einfache Algorithmus ist "peinlich parallel".

Ich denke, dass alle von Ihnen vorgeschlagenen Ansätze im Vergleich zur aktuellen Implementierung sehr ineffizient sind.

Verwenden von GPU: Die String-Daten müssen an die GPU und das Ergebnis zurück übertragen werden, was viel Zeit in Anspruch nimmt. GPUs sind sehr schnell, aber nur beim Vergleich von Gleitkommaberechnungen, die hier nicht verwendet werden. Alle Operationen sind auf Ganzzahlen, für die x86-CPU-Leistung anständig ist.

Verwenden eines anderen CPU-Kerns: Dies würde beinhalten, einen separaten Thread zu erstellen, den Speicher zu sperren und den Thread zu synchronisieren, der den Hash-Code anfordert. Der anfallende Overhead überwiegt einfach die Vorteile der Parallelverarbeitung.

Wenn Sie Hash-Werte von Tausenden von Strings auf einmal berechnen möchten, sehen die Dinge vielleicht etwas anders aus, aber ich kann mir kein Szenario vorstellen, in dem dies die Implementierung eines schnelleren GetHashCode() rechtfertigen würde.

Jeder Schritt in der Berechnung baut auf dem Ergebnis des vorherigen Schritts auf. Wenn Iterationen der Schleife nicht in der richtigen Reihenfolge ausgeführt werden, erhalten Sie ein anderes Ergebnis (der Wert von num aus der vorherigen Iteration dient als Eingabe für die nächste Iteration).

Aus diesem Grund führt jeder Ansatz (Multithreading, massiv parallele Ausführung auf einer GPU), bei dem Schritte parallel ausgeführt werden, im Allgemeinen zu einer Verzerrung des Ergebnisses.

Ich würde mich auch wundern, wenn das zuvor besprochene Loop-Abrolling nicht bereits intern vom Compiler durchgeführt wird, so dass es tatsächlich einen Unterschied in der Ausführungszeit macht (Compiler sind heutzutage schlauer als der durchschnittliche Programmierer) und Loop Unrolling gibt es schon seit sehr langer Zeit als Compiler-Optimierungstechnik).

Angesichts der Tatsache, dass Strings unveränderlich sind, würde ich als erstes das Caching des Return-Ergebnisses in Betracht ziehen.