Welche Art von Optimierungen nehmen moderne Compiler vor?

[niwax]

(19.02.2014 16:41)oreissig schrieb:  

(19.02.2014 14:53)niwax schrieb:  Ohne Unrolling hättest du enormen Overhead weil nach jeder Ausführung von zwei oder drei Instruktionen zuerst noch eine Manipulation an der Schleifenvariablen kommt dann ein GOTO, das dazu auch noch konditional ist.

die Schleifenvariable muss ja auch im entrollten Zustand zwischen den einzelnen Schritten noch iteriert werden

Nein, da das Unrolling meistens nur geht, wenn die Grenzen der Schleife schon bekannt sind, können einfach die entsprechenden Zahlen eingesetzt werden. In diesem Beispiel können zB sogar auch Speicherzugriffe in der Tabelle vereinfacht werden.

Spoiler anzeigen

Code:

for(x = 0; x < blocksize; x++)
                {
                    for(y = 0; y < blocksize; y++)
                    {
                        g += mb1.cb[i][j].data[x][y] * dctcos4[x][u][y][v];
                        g2 += mb1.cr[i][j].data[x][y] * dctcos4[x][u][y][v];
                        g3 += mb1.y[i][j].data[x][y] * dctcos4[x][u][y][v];
                    }
                }

wird zu

g += mb1.cb[i][j].data[0][0] * dctcos4[0][u][0][v];
g2 += mb1.cr[i][j].data[0][0] * dctcos4[0][u][0][v];
g3 += mb1.y[i][j].data[0][0] * dctcos4[0][u][0][v];
...
g += mb1.cb[i][j].data[8][8] * dctcos4[8][u][8][v];
g2 += mb1.cr[i][j].data[8][8] * dctcos4[8][u][8][v];
g3 += mb1.y[i][j].data[8][8] * dctcos4[8][u][8][v];

Dabei spart man sich zwei Dereferenzierungen pro Zugriff und der Compiler kann sogar im voraus kleinere Puffer aus den Konstanten vorberechnen. Am Ende liegen auch nur 192 Multiplikationen im Cache.

(19.02.2014 16:41)oreissig schrieb:  

(19.02.2014 14:53)niwax schrieb:  Von dem verbrauchten Cache ergibt sich kaum ein Unterschied, da Code bei dem sich das Unrolling lohnt meistens nur ein paar Instruktionen hat.

Wie viel Platz belegt wird, hängt auch von der Anzahl der Schleifendurchläufe ab.

Natürlich, aber durch die kleine Größe wird der Cache dadurch bei weitem nicht voll. 64x256 Bit sind immer noch erst 2 KByte. Damit das dem Cache gefährlich wird, musst du schon auf ner sehr alten Architektur arbeiten.

[Blue]

selbst ein pentium 1 hat 16kb l1 cache

[oreissig]

(19.02.2014 17:28)niwax schrieb:  

(19.02.2014 16:41)oreissig schrieb:  die Schleifenvariable muss ja auch im entrollten Zustand zwischen den einzelnen Schritten noch iteriert werden

Nein, da das Unrolling meistens nur geht, wenn die Grenzen der Schleife schon bekannt sind, können einfach die entsprechenden Zahlen eingesetzt werden.

achso ja in diesem Fall nicht, ich war in Gedanken noch in gandros beispiel, wo stattdessen die Anzahl der Iterationen dezimiert wird

(19.02.2014 17:28)niwax schrieb:  Damit das dem Cache gefährlich wird, musst du schon auf ner sehr alten Architektur arbeiten.

Interessanterweise hat sich der L1-Cache über die Zeit praktisch nie nennenswert erweitert. Die ganz allerersten CPUs, die überhaupt Caches hatten, hatten sowas kleines wie 512B, aber dann hat sich relativ schnell die Größenordnung 16-32kB für je Code und Daten etabliert.
Beim L2 war die Spanne zwar größer, aber auch da gabs vor 20 Jahren locker schon 2MB L2s. Das waren erst noch externe Chips, die erst im Laufe der Zeit aufs Package und dann aufs Die gewandert sind.

[friedrichheinze]

Ich muss hier gerade mal einen 180 pullen und oreissig recht geben: Auf Sandy Bridge und neuer sollte mal Loops wirklich nicht unrollen. Dort gibt es nämlich einen micro-op cache, der ca 1500 micro-ops speichert, und den sollte man echt sparsam einsetzen.

Wieder was gelernt

[thosch97]

(19.02.2014 22:49)friedrichheinze schrieb:  Ich muss hier gerade mal einen 180 pullen und oreissig recht geben: Auf Sandy Bridge und neuer sollte mal Loops wirklich nicht unrollen. Dort gibt es nämlich einen micro-op cache, der ca 1500 micro-ops speichert, und den sollte man echt sparsam einsetzen.

Wieder was gelernt

Gentoo Wiki über „Optimierung“ mit -funroll-loops