Skrivet av iXam:
Det heter "Loop Unrolling" (https://en.wikipedia.org/wiki/Loop_unrolling) och jag tror det var LÄNGE sen det ansågs som en optimering. Numera har CPUer cache (mer cache) och både CPUer och kompilatorer är smartare. Känns dumt att fylla upp kodcache med exakt samma instruktioner.
Men det finns säkert specialfall som någon annan kan fylla i här.
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.)