Är en for-sats långsammare än att skriva kodrader efter varandra?

Det kallas loop unrolling. Vektorisering är när instruktioner som opererar på flera värden samtidigt används.

Förr var loop unrolling en vanlig optimering programmerarna gjorde, men nu för tiden är processorerna "bredare" och smartare så loop-instruktionerna tenderar att kunna exekvera samtidigt som instruktionerna som gör själva jobbet. Kompilatorn kan även tänkas göra sin egen loop unrolling (eller ännu bättre, vektorisering) om du är tydlig med att det fungerar ("restrict" t ex).

Men om det är verkligt prestandakritisk kod så är det bästa att prova olika alternativ och se vad som är snabbast, eller om det inte spelar någon roll.

Nja, Loop Unrolling är fortfarande en högst relevant optimering, men kanske inte något man gör manuellt längre. En modern CPU med Out-of-Order-execution och spekulativ exekvering gör i stort sett loop unrolling i hårdvaran, men alla kompilatorer rullar upp loopar. Kör du exampelvis GCC på hög optimeringsnivå rullar den upp loopar ganska aggressivt. Det kan vara lärorikt att kika på den genererade koden i godbolt

Ursprungligen var tanken med unrolling att amortera av kostnaden för loop-overheaden på flera iterationer. Var det korta loopar med fix trip count kunde man bli av med loopvariabeln helt och hållet. Man fann dock snabbt att den stora finessen med loop unrolling var att unrolling exponerade flera kopior av loopkroppen och att detta öppnade för optimeringar mellan de olika iterationerna i loopen, exempelvis Common Subexpression Elimination, något som är svårt om kompilatorn bara ser en kopia av loopkroppen.

Vektorisering är en annan typ av optimering. Här handlar det om att kompilatorn upptäcker att de olika iterationerna i loopen är oberoende av varandra. Om accessmönstren stämmer kan kompilatorn lägga ut SIMD-instruktioner (AVX eller NEON/SVE) som köra flera iterationer av loopen parallellt. Sannolikheten för att kompilatorn ska kunna generera SIMD-kod ökar om du inte rullat upp loopen manuellt.

Det finns dock lägen när man vill göra en manuell loop unrolling. Exempelvis vid matrismultiplikationen kan man vilja göra en optimering som kallas Unroll-and-Jam om heuristiken i kompilatorn rullar upp fel loop.

Tag en skalär matrismultiplikation

for (i = 0, i < m; ++i) {
  for (j = 0, j < n; ++j) {
    tmp = c[i][j];
    for (x = 0, x < k; ++x) {
      tmp += a[i][x] * b[x][j];
    }
    c[i][j] = tmp;
  }
}

Här beror den innersta loopen bara på i och j så de olika iterationerna i j-loopen är oberoende av varandra. Efter Unroll:

for (i = 0, i < m; ++i) {
  for (j = 0, i < n; j += 8) {
    tmp[0] = c[i][j + 0];
    for (x = 0, x < k; ++x) {
      tmp[0] += a[i][x] * b[x][j + 0];
    }
    c[i][j + 0] = tmp[0];
    tmp[1] = c[i][j + 1];
    for (x = 0, x < k; ++x) {
      tmp[1] += a[i][x] * b[x][j + 1];
    }
    c[i][j + 1] = tmp[1];
    ...
    tmp[7] = c[i][j + 7];
    for (x = 0, x < k; ++x) {
      tmp[7] += a[i][x] * b[x][j + 7];
    }
    c[i][j + 7] = tmp[7];
  }
}

Nu är det dags för Jam. Alla dessa loopkroppar är oberoende av varandra så vi kan köra alla i samma loop:

for (i = 0, i < m; ++i) {
  for (j = 0, i < n; j += 8) {
    tmp[0] = c[i][j + 0];
    tmp[1] = c[i][j + 1];
    ...
    tmp[7] = c[i][j + 7];

    for (x = 0, x < k; ++x) {
      tmp[0] += a[i][x] * b[x][j + 0];
      tmp[1] += a[i][x] * b[x][j + 1];
      ...
      tmp[7] += a[i][x] * b[x][j + 7];
    }
    c[i][j + 0] = tmp[0];
    c[i][j + 1] = tmp[1];
    ...
    c[i][j + 7] = tmp[7];
  }
}

Nu har vi fått en loop som läser och skriver 8 konsekutiva element ur b och c. Denna loop lämpar sig väl för just verktorisering. (Att vektorisera x-accesserna kan kompilatorn klara av på egen hand.)

Ett sätt att mäta i är väl prestandaskillnad i ett gäng olika tester, som här: https://www.phoronix.com/review/gcc11-rocket-opts

Svaret då är att GCC 11 optimerar extremt mycket; -O0 ligger otroligt långt efter alla andra inställningar, ofta ger optimering 3x prestandan, men ibland långt mer ändå.

Det var en väldigt vettig motfråga. Den typ av motfråga vet vi ju alla vad det innebär. Det går inte att besvara din fråga på det sättet du önskar utan det beror helt enkelt på kompilator samt om kompilatorn har olika möjliga flaggor som kan ändra beteende hos den specifika optimeringen du söker samt vad som är standardinställning.

Vilken kompilator talar vi om? Är det gcc, LLVM, clang, intels egen eller Visual Studio? (Finns många fler!)
Folk har utvecklat bilar i 100 år, finns det ett svar på hur mycket fortare en bil går idag än i begynnelsen?
(Mäter vi hastighet eller restid, relevant då en del saker var bättre förr, innan trafikpropparna.)

Det finns switchar till kompilatorn som sparar den genererade assemblerkoden i läsbart skick. Det är väldigt givande att dyka ner där om man undrar vad de olika optimeringsstegen har för sig. Var beredd på att du inte kommer att känna igen din kod alls efter det att de högre optimeringsstegen har aktiverats.