Ich versuche, diesen C-Code mit 4-Wege-Schleifenabwicklung zu optimieren

Question

Ich versuche, diesen C-Code mit einer Technik zu optimieren, die als Schleifenabrollung bezeichnet wird, aber in diesem Fall möchte ich eine vierfache Schleifenabrollung verwenden. Ich verstehe die Technik und das Konzept, ich weiß nur nicht, wie ich sie auf diesen Code anwenden soll. Muss ich ein paar zusätzliche Variablen hinzufügen? Muss ich nach jeder Schleife etwas Code einfügen oder nur am Ende aller Schleifen? Bei diesem Code handelt es sich um einen 8x8-Blockcode, bei dem es darum geht, Pixel zu nehmen und sie um 90 Grad gegen den Uhrzeigersinn zu drehen. Jede Hilfe würde sehr geschätzt werden. Vielen Dank!

/* 
 * rotate8 - rotate with 8x8 blocking
 */

char rotate8_descr[] = "rotate8: rotate with 8x8 blocking";

void rotate8(int dim, pixel *src, pixel *dst) 
{

int i, j, ii, jj;

for(ii = 0; ii < dim; ii += 8)
       for(jj = 0; jj < dim; jj += 8)
              for (i = ii; i < ii + 8; i++)   
                  for (j = jj; j < jj + 8; j++)
                      dst[RIDX(dim-1-j, i, dim)] = src[RIDX(i, j, dim)];
}

Answer 1

Sie können die innere Schleife durch 8 explizite Codezeilen ersetzen

          dst[RIDX(dim-1-jj, i, dim)] = src[RIDX(i, jj, dim)];
          dst[RIDX(dim-1-(jj+1), i, dim)] = src[RIDX(i, (jj+1), dim)];
          ...
          dst[RIDX(dim-1-(jj+7), i, dim)] = src[RIDX(i, (jj+7), dim)];

Sie ersetzen also die Schleifenvariable, indem Sie für jeden Wert, den sie annimmt, ausdrücklich eine Zeile schreiben.

Jetzt können Sie das für die 8 Werte der nächsten Schleife wiederholen, so dass Sie 8 x 8 Codezeilen haben, und so weiter.

Als etwas anderes als eine Übung in Verständnis, scheint dies ziemlich sinnlos zu mir, Compiler tun diese Art von Sachen wirklich effizient, sie werden optimieren, wo es Sinn macht. Hand-Rolling erzeugt selten optimalen Code.

Answer 2

Ich wollte sagen: "Profil" - aber dann habe ich es selbst getan. Das Erstaunliche ist, dass die innere Schleife am schnellsten mit genau Ihrem Layout - wenn man sie von Hand abrollt, ist sie sogar langsamer.

Der eigentliche Haken ist jedoch das RIDX-Makro. Das Umschalten des Speicherlayouts und das Umschalten der äußeren Schleifen hat eine bedeutsam Auswirkungen.

Hier ist meine schnellste Version mit Einrückung, um zu zeigen, wo sie sich von Ihrer Version unterscheidet. Es wird davon ausgegangen, dass das RIDX-Makro wie definiert ist.

#define RIDX(x,y,d) (x+(y)*(d))
typedef unsigned char pixel;
void rotate8(int dim, pixel *src, pixel *dst)
{
    int i, j, ii, jj;
        for(jj = 0; jj < dim; jj += 8)
    for(ii = 0; ii < dim; ii += 8)
              for (i = ii; i < ii + 8; i++)
                  for (j = jj; j < jj + 8; j++)
                      dst[RIDX(dim-1-j, i, dim)] = src[RIDX(i, j, dim)];
}

... Lektion gelernt: Immer ein Profil erstellen :-)

Answer 3

gcc -funrull-loops

Sie sollten Schleifen nicht selbst abrollen, es sei denn, GCC kann das nicht (sehen Sie sich die Assembler an) und Sie haben mit einem Profiler bewiesen, dass Sie diesen Teil des Codes beschleunigen müssen.

Ihr Beispielcode sieht wie ein perfekter Kandidat für die automatische Schleifenabwicklung aus.

Einige andere nützliche Flaggen:

\-O3                          // turns on a lot of optimizations (almost all)
-ftree-vectorize -msse2      // vectorizes automatically some loops

Answer 4

http://www.relisoft.com/book/lang/pointer/2ptrarr.html

Wenn Ihr Compiler nicht in der Lage ist, die für den Menschen lesbare, wartbare Version des Algorithmus zu optimieren, und Sie sich als menschlicher Compiler verdoppeln müssen - kaufen Sie einen neuen Compiler! Niemand kann sich mehr menschliche Compiler leisten. Haben Sie also Erbarmen mit sich selbst und Ihren Programmiererkollegen, die sich Ihren Code ansehen müssen.

Answer 5

Die Rotation um 8x8 wird effizienter durch SIMD- oder SWAR-Techniken durchgeführt, die mindestens 64 Bits gleichzeitig lesen können.

Rot90Left(X) = flip_vertical(transpose(X))
Rot90Right(X) = transpose(flip_vertical(X))

Die vertikale Umkehrung ist eine Null-Kosten-Operation, da sie nur das Speichern/Lesen vom anderen Ende der temporären Variablen bedeutet. Wenn die SSE/SIMD-Implementierung der Transponierung nicht verwendet werden kann, hat sich dieser Kernel auf x64 und arm64-v8 als recht schnell erwiesen.

inline void transpose_u8(uint64_t *a, uint64_t *b) {
     uint64_t A = *a, B = *b, C = B ^ (A>>8)) & 0x00ff00ff00ff00ffull;
     *a = A ^ (C << 8);
     *b = B ^ C;
}
inline void transpose_u16(uint64_t *a, uint64_t *b) {
     uint64_t A = *a, B = *b, C = B ^ (A>>16)) & 0x0000ffff0000ffffull;
     *a = A ^ (C << 16);
     *b = B ^ C;
}
inline void transpose_u32(uint64_t *a, uint64_t *b) {
     uint64_t A = *a, B = *b, C = B ^ (A>>32)) & 0x00000000ffffffffull;
     *a = A ^ (C << 32);
     *b = B ^ C;
}
void transpose8x8(uint8_t *src, int skip0, uint8_t *dst, int skip1) {
     uint64_t d[8];
     for (int x = 0; x < 8; x++)
         memcpy(d+(x ^ LEFT), src + x * skip0);
     transpose_u8(d+0, d+1);
     transpose_u8(d+2, d+3);
     transpose_u8(d+4, d+5);
     transpose_u8(d+6, d+7);
     transpose_u16(d+0, d+2);
     transpose_u16(d+1, d+3);
     transpose_u16(d+4, d+6);
     transpose_u16(d+5, d+7);
     transpose_u32(d+0, d+4);
     transpose_u32(d+1, d+5);
     transpose_u32(d+2, d+6);
     transpose_u32(d+3, d+7);
     for (int x = 0; x < 8; x++)
         memcpy(dst + x * skip1, d + (x ^ RIGHT));
}

• Hier erfolgt die Rechtsdrehung durch die Einstellung LEFT=0, RIGHT=7

• Linksdrehung == LEFT=7, RIGHT = 0

• Transponieren = LINKS=0, RECHTS=0

Meine Hypothese ist, dass jeder anständige Compiler alle internen Speicherlesungen in der transpose_uXX Funktionen durch direkte Änderung der in Registern gespeicherten Variablen und ersetzt die memcpy durch einzelnes 64-Bit-Lesen oder -Schreiben in den Speicher - dies sollte zumindest bei 64-Bit-Architekturen geschehen. Auf pre-x86-Architekturen gibt es nicht genügend Register, und die praktische Alternative besteht darin, jeden verfügbaren SIMD-Register- und Befehlssatz zu verwenden.