Loop Splitting Performance Problem

Question

Ich implementierte das Gaussian-Elimination-Verfahren über GF (2). Ich benutzte ein zweidimensionales 64-Bit-Integer-Array, um die Matrix in einer Reihe-Haupt-Darstellung zu speichern (Zeilen der Matrix werden in einem zusammenhängenden Array gespeichert). I implementiert, um die Gaußsche Eliminations auf den Zeilen der Matrix in der folgenden Weise:

wobei (A)^i die i-te Zeile von A. bezeichnet I realisiert dann, dass, wenn i Splitt die Schleife an 5-6 Zeilen wie folgt erhalte ich eine etwas bessere Leistung:

ich würde erwarten, etwas schlechter Leistung zu bekommen, weil ich bin die ganze äußere Schleife wieder Iterieren ... hat jemand dafür eine Erklärung Verhalten? Trifft der Compiler einige knifflige Optimierungen, ist das bei der geteilten Variante einfacher? (Kompiliert mit g ++ O3)

(Wenn Pseudo-Code nicht auf die Antwort führt, i ein minimales Beispiel-Code zur Verfügung stellen kann)

Answer 1

Es gibt keinen Grund schlechter Leistung aus Ihrem zweiten Lösung zu erwarten - beide Algorithmen sind in haben sie sogar die gleiche Konstante: in der ersten Lösung ist Ihre äußere Schleife in , in der zweiten haben Sie zwei Schleifen in .

In der Praxis hat Ihre zweite Lösung möglicherweise bessere CPU-Caching-Eigenschaften oder ist besser für die Compileroptimierung geeignet. Insbesondere, da Ihre Operationen über GF (2)/Z (2) sind, können sie als binäre Operationen über Wörter ausgedrückt werden - was zu einer großen Beschleunigung führen würde. Abhängig von Ihrer Implementierung (und den Einschränkungen für n) kann der Algorithmus am Ende auf optimiert werden. Wir können es nicht wirklich sagen, ohne einen Blick auf Ihren Code zu werfen, obwohl :).