Schnellste Weg, um zu sehen, wie viele Bytes sind gleich zwischen fester Länge Arrays
https://stackoverflow.com/questions/116485
-
02-07-2019 - |
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
RussianFrage
Ich habe 2 Arrays von 16 Elementen (Zeichen), die ich brauche, um „Vergleichen“ und sehen, wie viele Elemente zwischen den beiden gleich sind.
Diese Routine wird ich millionenfach (ein üblicher Lauf beträgt etwa 60 oder 70 Millionen Mal) verwendet werden, so muß ich es so schnell wie möglich sein. Ich arbeite an C ++ (C ++ Builder 2007, für die Aufzeichnung)
Gerade jetzt, ich habe einen einfachen:
matches += array1[0] == array2[0];
wiederholt 16-mal (als Profilierungs es erscheint 30% schneller zu sein, als es mit einem for-Schleife zu tun)
Gibt es eine andere Art und Weise, die schneller arbeiten könnte?
Einige Daten über die Umwelt und die Daten selbst:
- Ich bin mit C ++ Builder, die keine Geschwindigkeitsoptimierungen zu berücksichtigen hat. Ich werde versuchen, schließlich mit einem anderen Compiler, aber im Moment bin ich mit diesem stecken.
- Die Daten werden anders sein die meisten der Zeit. 100% gleich Daten sind in der Regel sehr sehr selten (vielleicht weniger als 1%)
Lösung
UPDATE:. Diese Antwort modifiziert wurde auf meine Kommentare, den Quellcode unten bereitgestellt anzupassen
Es ist eine Optimierung zur Verfügung, wenn Sie die Fähigkeit haben, SSE2 und popcnt Anweisungen.
16 Bytes geschieht schön in einem SSE-Register passen. Verwendung von C ++ und Montage / intrinsics, laden die beiden 16-Byte-Arrays in XMM-Register, und sie cmp. Dies erzeugt eine Bitmaske, die die Wahr / Falsch-Bedingung des vergleichen. Sie dann eine movmsk Anweisung verwenden, um eine Bit-Darstellung der Bitmaske in ein x86-Register zu laden; dies wird dann ein Bit-Feld, in dem Sie alle 1'en zählen können, um zu bestimmen, wie viele wahren Werte, die Sie haben. Eine Hardware-popcnt Anweisung kann eine schnelle Art und Weise sein, all 1en in einem Register zu zählen.
Dies erfordert die Kenntnis der Montage / intrinsics und SSE im Besonderen. Sie sollten Web-Ressourcen für beide in der Lage zu finden.
Wenn Sie diesen Code auf einer Maschine laufen, die nicht entweder SSE2 oder popcnt nicht unterstützt, müssen Sie dann durch die Arrays durchlaufen und die Unterschiede mit Ihrem entrollten Schleife Ansatz zählen.
Viel Glück
Edit: Da Sie angegeben haben Sie nicht Versammlung wissen, ist hier einige Beispiel-Code meine Antwort zu veranschaulichen:
#include "stdafx.h"
#include <iostream>
#include "intrin.h"
inline unsigned cmpArray16( char (&arr1)[16], char (&arr2)[16] )
{
__m128i first = _mm_loadu_si128( reinterpret_cast<__m128i*>( &arr1 ) );
__m128i second = _mm_loadu_si128( reinterpret_cast<__m128i*>( &arr2 ) );
return _mm_movemask_epi8( _mm_cmpeq_epi8( first, second ) );
}
int _tmain( int argc, _TCHAR* argv[] )
{
unsigned count = 0;
char arr1[16] = { 0, 0, 0, 1, 0, 0, 0, 1, 0, 0, 1, 0, 0, 0, 0, 0 };
char arr2[16] = { 1, 0, 0, 1, 0, 0, 0, 0, 0, 0, 1, 0, 0, 1, 0, 0 };
count = __popcnt( cmpArray16( arr1, arr2 ) );
std::cout << "The number of equivalent bytes = " << count << std::endl;
return 0;
}
Einige Hinweise: Diese Funktion verwendet SSE2 Instruktionen und eine popcnt Anweisung in dem Phenom-Prozessor eingeführt (das ist die Maschine, die ich verwende). Ich glaube, die neuesten Intel-Prozessoren mit SSE4 auch popcnt haben. Diese Funktion überprüft nicht für den Unterricht Unterstützung mit CPUID; die Funktion ist nicht definiert, wenn es auf einem Prozessor verwendet, die nicht SSE2 haben oder popcnt (Sie werden wahrscheinlich einen ungültigen Operationscodebefehl erhalten). Das Erkennungscode ist ein eigener Thread.
Ich habe diesen Code nicht abgelaufen ist; der Grund, warum ich denke, dass es schneller ist, weil es 16 Bytes zu einer Zeit vergleicht, branchless. Sie sollten ändern diese Ihre Umgebung zu passen, und die Zeit, es selbst zu sehen, ob es für Sie arbeitet. Ich schrieb und getestet dies auf VS2008 SP1.
SSE bevorzugt Daten, die auf einer natürlichen 16-Byte-Grenze ausgerichtet ist; wenn du das dann sollten Sie zusätzliche Verbesserungen in der Geschwindigkeit garantieren können, und Sie können die _mm_loadu_si128 Anweisungen _mm_load_si128 ändern, die Ausrichtung erfordert.
Andere Tipps
Der Schlüssel ist, die Vergleiche zu tun mit der größten Ihre CPU unterstützt registrieren, Ausweich dann auf Bytes, falls erforderlich.
Der Code unten zeigt, bei der Verwendung von 4-Byte-Zahlen, aber wenn man auf einer SIMD-Architektur (all modernen Intel- oder AMD-Chip) laufen Sie beiden Arrays in einer Anweisung vergleichen können, bevor in eine Integer-basierten Schleife zurückzufallen. Die meisten Compiler haben in diesen Tagen intrinsische Unterstützung für 128-Bit-Typen wird so NICHT ASM erforderlich.
(Man beachte, dass für die SIMD Ihrer Arrays comparisions 16-Byte-ausgerichtet sein müßten, und einige Prozessoren (z MIPS) würden die Arrays erfordern 4 Byte für die int-basierten Vergleiche ausgerichtet sein.
z.
int* array1 = (int*)byteArray[0];
int* array2 = (int*)byteArray[1];
int same = 0;
for (int i = 0; i < 4; i++)
{
// test as an int
if (array1[i] == array2[i])
{
same += 4;
}
else
{
// test individual bytes
char* bytes1 = (char*)(array1+i);
char* bytes2 = (char*)(array2+i);
for (int j = 0; j < 4; j++)
{
same += (bytes1[j] == bytes2[j];
}
}
}
Ich kann mich nicht erinnern, was genau die MSVC-Compiler für SIMD unterstützt, aber man könnte so etwas wie tun;
// depending on compiler you may have to insert the words via an intrinsic
__m128 qw1 = *(__m128*)byteArray[0];
__m128 qw2 = *(__m128*)byteArray[1];
// again, depending on the compiler the comparision may have to be done via an intrinsic
if (qw1 == qw2)
{
same = 16;
}
else
{
// do int/byte testing
}
Wenn Sie die Möglichkeit haben, die Lage der Arrays zu steuern, in dem Speicher zum Beispiel ein Recht nach dem anderen zu setzen, könnte es dazu führen, dass in den Cache der CPU geladen werden, auf dem ersten Zugriff.
Es hängt von der CPU und seine Cache-Struktur und wird von einer Maschine zur anderen variieren.
Sie können über Speicherhierarchie und Cache in Henessy & Pattersons Computer Architecture lesen: A Quantitative Ansatz
Wenn Sie absolut niedrigsten Stellfläche benötigen, würde ich mit Assembler-Code gehen. Ich habe das nicht in einer Weile getan, aber ich werde MMX Wette (oder wahrscheinlicher SSE2 / 3) Anweisungen, die Sie aktivieren können, genau das in sehr wenige Anweisungen zu tun.
Wenn Übereinstimmungen sind der gemeinsame Fall dann versuchen, die Werte als 32-Bit ints Läden statt 16, so können Sie 2 vergleichen in einem Rutsch (und zählen als 2 Ursachen).
Wenn die beiden 32-Bit-Werte nicht das gleiche dann müssen Sie sie separat testen (und aus dem oberen und unteren 16-Bit-Werte).
Der Code wird komplexer sein, sollte aber schneller sein.
Wenn Sie zielt auf eine 64-Bit-System, das Sie den gleichen Trick mit 64-Bit-Ints tun könnte, und wenn Sie wirklich die Grenze drücken, dann sehen Sie fallen in Assembler und mit den verschiedenen Vektor-basierte Anweisungen möchten, die Sie würde arbeiten lassen mit 128 Bit auf einmal.
Magische Compiler-Optionen wird die Zeit stark variieren. Insbesondere macht es SSE Vektorisierung generieren werden Sie wahrscheinlich einen großen Speedup bekommen.
Hat diese Plattform unabhängig sein, oder wird dieser Code immer auf die gleiche Art von CPU laufen? Wenn Sie sich auf modernen x86 CPUs beschränken, können Sie in der Lage sein verwenden MMX Anweisungen der soll, können Sie auf einem Array von 8 Bytes in einem Taktzyklus betreiben. AFAIK, gcc können Sie Assembly in den C-Code zum Einbetten und der Intel-Compiler (IStGH) unterstützt Spezifika, die Wrapper sind, die es Ihnen ermöglichen, direkt bestimmte Montageanleitung zu rufen. Andere SIMD-Befehlssätze, wie SSE, können auch nützlich sein für diese.
Gibt es eine Verbindung zwischen den Werten in den Feldern? Sind einige Bytes eher die gleichen dann andere sein? Könnte es einige innere Ordnung der Werte sein? Dann könnten Sie für die wahrscheinlichste Fall optimieren.
Wenn Sie erklären, was die Daten darstellen tatsächlich dann könnte es eine ganz andere Art und Weise sein, die Daten im Speicher zu repräsentieren, die diese Art von brutaler Gewalt unnötig vergleichen machen würde. Pflege zu erarbeiten, was die Daten tatsächlich darstellt ??
Ist es schneller als eine Anweisung?
matches += (array1[0] == array2[0]) + (array1[1] == array2[1]) + ...;
Wenn das Schreiben, dass 16-mal schneller als eine einfache Schleife, dann wird Ihr Compiler entweder saugt, oder Sie haben nicht die Optimierung eingeschaltet.
Kurze Antwort: Es gibt keinen schnelleren Weg, es sei denn, Sie auf parallele Hardware-Vektor-Operationen zu tun
.Versuchen Zeiger anstelle von Arrays:
p1 = &array1[0];
p2 = &array2[0];
match += (*p1++ == *p2++);
// copy 15 times.
Natürlich müssen Sie gegen andere Ansätze messen, das zu sehen, was am schnellsten ist.
Und sind Sie sicher, dass diese Routine zu einem Engpass in der Verarbeitung ist? Sie beschleunigen Sie tatsächlich die Leistung Ihrer Anwendung als Ganzes nach oben durch diese Optimierung? Auch hier wird nur Messung sagen.
Gibt es eine Möglichkeit Sie die Art und Weise ändern, können die Arrays gespeichert werden? Vergleicht man 1 Byte zu einem Zeitpunkt ist extrem langsam Erwägen Sie sind wahrscheinlich ein 32-Bit-Compiler. Stattdessen, wenn Sie in 4 ganzen Zahlen Ihre 16 Byte gespeichert (32-Bit) oder 2 Long-Positionen (64-Bit), würden Sie müssen nur 4 bzw. 2 Vergleiche durchzuführen.
Die Frage, sich zu fragen, wie viel die Kosten für die Speicherung der Daten als 4-Integer-oder 2-lang-Arrays ist. Wie oft müssen Sie auf die Daten zugreifen, etc.
Es gibt immer die gute alte x86 REPNE CMPS Anweisung.
Eine zusätzliche mögliche Optimierung: Wenn Sie erwarten, dass die meisten der Zeit, die Arrays identisch sind dann könnte es etwas schneller sein, eine memcmp zu tun () als ersten Schritt, das Setzen von ‚16‘ als Antwort, wenn der Test true zurück . Wenn natürlich, wenn Sie die Arrays erwarten nicht identisch sein sehr oft, dass würde nur die Dinge langsam nach unten.
