Meine Aufgabe ist es zu prüfen (& gt; Billionen-Überprüfungen), enthalten zwei int irgendwelche vordefinierten Nibble-Paare (erstes Paar 0x2 0x7; zweites 0xd 0x8). Zum Beispiel:
%Vor%Also, für dieses Beispiel markiere ich zwei Offsets mit benötigten Paaren (Offsets sind 2 und 5; aber keine 7). Tatsächliche Offsets und die Anzahl der gefundenen Paare werden in meiner Aufgabe nicht benötigt.
Für zwei Ints lautet die Frage also: Enthält sie eines dieser Nibble-Paare mit demselben Offset?
Ich habe mein Programm überprüft, dieser Teil ist der heißeste Ort ( gprof bewiesen); und es wird ein sehr-sehr viele Male genannt ( gcov bewiesen). Eigentlich ist es die 3. oder 4. Schleife (am meisten verschachtelt) von verschachtelten Schleifen.
Mein aktueller Code ist langsam (ich schreibe ihn als Funktion um, aber es ist ein Code aus der inneren Schleife):
%Vor%Die andere Aufgabe besteht darin, diese Paare nicht nur bei Offsets von 0,4,8 Bits usw. zu finden, sondern auch bei Offsets von 0,2,4,8,10, ... Bits:
%Vor%Ist es möglich, diese Funktion und das Makro parallel neu zu schreiben?
Mein Compiler ist gcc452 und CPU ist Intel Core2 Solo im 32-Bit-Modus (x86).
Es gibt Tricks zum Testen auf ein Null-Byte in einem Wort (siehe z. B. Ссылка ); Eine schnelle Methode ist die Verwendung dieses Ausdrucks:
%Vor%, das einen Wert ungleich Null auswertet, wenn eines der vier Bytes innerhalb des 32-Bit-Worts 0 oder sonst 0 ist.
Diese Methode kann angepasst werden, um hier zu arbeiten:
%Vor%Die schnellste Lösung ist wahrscheinlich, eine Art Nachschlagetabelle zu verwenden.
Wie eingeschränkt sind Sie im Gedächtnis? Eine 16-Bit-Tabelle würde 64 KB groß sein und Sie könnten 4 Nibbles gleichzeitig testen. Also wäre 4 (1 für jedes Nibble) von ihnen 256K.
Wenn ich Ihr Problem verstehe, denke ich, dass es funktionieren wird. Es ist ein 8-Bit-Beispiel - Sie können es auf 16 Bits erweitern. :
%Vor%Hier ist eine bessere Implementierung:
%Vor%Haben Sie versucht, die Schleife abzurollen?
%Vor%Ich glaube, das Abwickeln der Schleife führt zu der gleichen Anzahl von bitweisen und Operationen und der gleichen Anzahl von Vergleichen, aber Sie sparen den Aufwand, alle richtigen Verschiebungen durchzuführen und die Ergebnisse zu speichern.
Bearbeiten : (als Antwort auf das Abrollen bei bedingten und nicht bedingten Sprüngen)
Dies würde Sprünge eliminieren, auf Kosten zusätzlicher Arbeit. Es ist eine Weile her, seit ich an etwas gearbeitet habe, das diese Art von Optimierung benötigt, aber das sollte zu keinerlei Sprüngen führen. (Wenn dies nicht der Fall ist, ersetzen Sie das & amp; & amp; mit & amp ;. Das & amp; & amp; kann den Compiler auslösen, um eine Kurzschlusslogik zu erzeugen, & & kann jedoch die zweite Hälfte immer ohne Sprünge auswerten .)
%Vor%Ein tabellenbasierter Ansatz könnte sein:
%Vor% Eine Idee besteht darin, eine Karte mit 65536 Werten vorzurechnen, die überprüft, ob eine 16-Bit-Zahl das Nibble 0000 enthält. Ich habe in meinem Beispiel eine Bit-Tabelle verwendet, aber möglicherweise ist eine Byte-Tabelle schneller, auch wenn sie größer und weniger Cache-freundlich ist.
Wenn Sie eine Tabellenprüfung haben, können Sie dann die erste 32-Bit-Ganzzahl mit einem wiederholten ersten Nibble und die zweite ganze Zahl mit einem wiederholten zweiten Nibble xorieren. Wenn das erste Nibble in der ersten Ganzzahl vorhanden ist, erhalten wir eine Null, und dasselbe wird in der zweiten Ganzzahl für das zweite Nibble vorkommen. Bei den beiden Ergebnissen ist eine Null nur möglich, wenn das gesuchte Paar vorhanden ist.
Die Suche wird dann abgeschlossen, indem sie für das andere Paar von Nibble-Werten wiederholt wird.
Beachten Sie jedoch, dass für einen König-König-Angriff in einem regulären Schachspiel (d. h. wo nur zwei Könige anwesend sind), meiner Meinung nach eine Überprüfung mit Koordinaten viel schneller sein könnte.
Tags und Links optimization c micro-optimization