hardcore assembler: just in time loop unrolling

So ich habe mal angefangen mich mit assembler auseinanderzusetzen, aber habe noch keine große Ahnung. Mir ist dabei eine interessante Idee gekommen, von der ich gerne gewußt hätte, ob jemand sich schon daran probiert hat. Mir geht es hierbei um das loop unrolling. Ich kenne auch einigen libs, die dies per Hand machen, für verschiedene n, was ich als äußerste Platzverschwendung ansehe. Ich frage mich, ob man das mittles assembler auch nicht einfacher haben könnte.

Meine Schleife etwa:

for (i=0;i<n;++i) foo=bla(i);//blah ist Zuweisung oder was auch immer (un)abhängig von i

unrolling per Hand (Annahme n%4=0) etwa:

for (i=0;i<n;i+=4) {
foo=bla(i);
foo[i+1]=bla(i+1);
foo[i+2]=bla(i+4);
foo[i+3]=bla(i+3);
}

Meine Idee ist nun folgende: Es wird einmal die Schleife in assembler geschriebne und zwar mit maximalen unrolling, den man haben möchte. (Jetzt braucht man am besten einen nicht ganz so dummen assembler.) Vor jeder "unrollten" Zuweisung setzt man ein label.
Nun kann man in der Laufzeit anhand dieses Labels einfach herausfinden, welchen Befehl man mit einem jump Befehl überschreiben kann.

//maxmales unrollign mit labels, simuliert in pseudo c, das dem assembler näher kommt:
i=0;

start:
foo=bla(i);
ur1:
foo[i+1]=bla(i+1);
ur2:
foo[i+2]=bla(i+2);
ur3:
foo[i+3]=bla(i+3);
check:
i+=4;
if (i<n) goto start;
else goto end;

:end

Um nun etwa nur 2fach unrolling zu haben wirden die entsprechenden assmbler ROutinen überschrieben (bzw falls man doch wieder mehr braucht, die zu überschreibenden Routinen vorher gespeichert) und das Hochzählen von i angepaßt Ergebnis:

i=0;

start:
foo=bla(i);
ur1:
foo[i+1]=bla(i+1);
ur2:
i+=2;
if (i<n) goto start;
else goto end;
//nachfolg wird zum Teil durch obiges überschrieben
foo[i+2]=bla(i+2);
ur3:
foo[i+3]=bla(i+3);
check:
i+=4;
if (i<n) goto start;
else goto end;

:end


Hier steht nun nach dem "else goto end" zum Teil Müll im Speicher, was aber nicht wichtig ist, daß stätestens ab end wieder alles OK ist.

Ich hoffe meine Idee wurde klar. Zwar kosten die Kopieraktionen ein wenig overhead, aber da es sich um wenige byte handelt, könnte es schon einiges bringen. Ich sehe das doch richtig, daß ich wirkich nur kopieren muß, da ich die Sprungzeile nicht "verbiege". Wenn ich die Hochzählschritte von i auch noch in eine Variable packe, brauch ich selbst das nicht zu modifizeiren, sondern kann vorher den Wert einfach zuweisen. Hat das schon jemand realisiert? Insbesodnere bei größeren Funktionen kann mein Vorschlag sich sehr positiv auswirken, weil seperate Funktionen für jedes n schlicht zuviel SPeicher verbrauchen könnten. Man gucke etwa in OpenAL, wo man sehr viel per Hand unrolled hat für 1...16 etwa und dadurch die lib extrem aufgebläht ist.

Ich hab zwar keine Ahnung von Assembler - da warten wir lieber auf intel_hasser usw. - aber mich erinnert Dein Vorhaben stark an Duff's Device.

Ja, ich warte auch auf intel_hassers Aussage. Zum Verstehen brauchst du kein Assembler, nur denke ich, wird man unter assembler einfach die Adressen der labels bestimmen können, wodurch erst die Kopieraktionen möglich werden. So braucht man keinen mini-assembler compiler zu basteln...

send(to, from, count)
register short *to, *from;
register count;
{
register n=(count+7)/8;
switch(count%8){
case 0: do{ *to = *from++;
case 7: *to = *from++;
case 6: *to = *from++;
case 5: *to = *from++;
case 4: *to = *from++;
case 3: *to = *from++;
case 2: *to = *from++;
case 1: *to = *from++;
}while(--n>0);
}
}

Zum Vergrößern anklicken....

Ich verstehe es ehrlich gesagt nicht ganz. Wenn count%8=0 ist, verstehe ich es, aber wenn nicht, wie kann es funkt? Etwa im Bsp count=17. Der coder möchte doch, daß die Schleife 8,8,1 mal kopiert. Doch switch(count%8) sagt doch immer 1, und n=(count+7)/8=3, also wird doch statt 17 mal nur 1+1+1 mal kopiert. Oder sehe ich was falsch? Nein, jetzt verstehe ich das...er springt nur am Anfang richtig rein und dann wird die Schleife immer von 0 agbefahren. Nicht schlecht, aber *nicht* dasselbe wie bei mir, da bei ihm das unrolling konstant groß ist.

Ich weiß, daß mein Bsp schlecht ist (aber soll ja nur erläutern), aber bei mir geht es darum das unrolling dynamisch einzustellen. Sinn: Wenn ich etwa eine gegebene # von Audiotracks mischen möchte. Dann wäre es wünschenwert, etwa das unrolling genauso groß zu wählen wie die # der tracks.

Jetzt muss ich erstmal gucken, dass ich da durchblicke .

Selbstmodifizierender Code bringt aber allgemein erstmal das Problem, dass du vor dem 1. Ausführen vom veränderten Code erstmal die Prefetch Queue leermachen musst. Das machst du idR durch einen FAR Jump, der die CPU sehr viel Zeit kostet (und jede Pipeline wird erstmal geleert -> dauert ewig).
Desswegen gilt selbstmodifizierender Code auch als unsauber, moderne CPUs können den nicht ad hoc ausführen (das gilt so ungefähr ab 386er, der hat schon eine etwas längere Prefetch Queue).


... ah, jetzt steig ich so langsam durch .
Also die Schleife tritt bei dir sagen wir 20mal auf, mit verschieden vielen Durchläufen - und du willst vermeiden, dass der Compiler 20mal die Schleife unrollt, sondern stattdessen eine Schleife immer etwas umschreibt. Richtig?
Gut, das ginge auch einfacher ohne Selbstmodifizierenden Code:



Wenn du sagen wir 20 Labels hast (die Labels ergeben übrigens keinen Assemblercode - in Maschienencode gibts nämlich keine Labels, die werden vom Assembler in Offsets umgewandelt und aus einem JMP L1 wird ein JMP 0x1234) du 10 Durchläufe willst machst du einfach ein JMP L10.
Allerdings musst du da wissen wie viele Durchläufe die Schleifen haben müssen... andererseits kannst du aber auch die Labels alle in einer Tabelle speichern (mit NASM dank des guten Präprozessors zb. kein Problem) und dann während der Laufzeit für die entsprechende Anzahl der Durchläufe die Sprungmarke auslesen.


Aber LOOP Unrolling bringt allgemein nicht mehr sooo viel, weil heutige CPUs eine Vorhersagegenauigkeit von 98% und mehr haben. Der Unterschied von GCC -O2 (alle Optimierungen ohne Inline-Funktionen und ohne Loop Unrolling) zu GCC -O3 (kleinere Funktionen werden gleich inline realisiert, kleine Schleifen werden "ungerollt") ist oft nichtmal messbar.

Ich glabue ehrlich gesagt auch nicht daran, daß ein unrolling von mehr als 4 viel bringt, aber testen wollte ich das mal schon.

Ich weiß, daß die labels nur für den compiler bestimmt sind. Aber deine Idee ist ja auch sehr interessant, nur müßte man ja die letzten statements entsprechend anpassen, da es ja i.a. nicht dasselbe ist, wenn du die El 1-10 resp. 11-20 iterativ abarbeitest. Aber deinen Vorschlag könnte man ja schon in C probieren. Very well. Werde mich beizeiten mal dran probieren. Hmm ich denke sogar, so wie du es aufgeschribene hast,also mit dem andaurnden Inkrementieren statt w ie ich absolute offsets angegeben habe, sollte es in der tat einfach sein, 11-20 statt 1-10 auszuführen. Da habe ich wohl nicht zuende gedacht. Naja, bin ja auch assembler Anfänger. Letztendlich hängt das ber von dem zugrunde liegnden Problem ab...


An die prefetch queue habe ich nicht gedacht. Stimmt schon, daß diese wohl entleert wird, aber solange ich in naheliegenden Bereichen kopiere wird das zumindest vom L1 cache abgefangen und der overhead hält sich in Grenzen.

Mir ist noch was sinvolleres eingefallen. Schreib die Zugriffe einfach rückwärts in Assembler auf, ohne INCs oder DECs.

Also


Usw. - das ist für die CPU entspannender, weil ECX sonst Abhängigkeiten erzeugt.

Verstehe nicht, wo der Unterschied sein soll. Soll ich absolute offsets verwenden, deiner Meinung nach?

Das INC ECX erzeugt Abhängigkeiten, weil die danachfolgende Anweisung ja ECX als Argument nimmt.
Das heist in der CPU muss erst das INC fertiggerechnet werden, damit die CPU dann den eigentlichen Befehl rechnen kann. Besser ist es das dann direkt in dem Befehl anzugeben, weil dann wirklich keinerlei Abhängigkeiten entstehen.

Also in C:

foo[5]=bar[5]
foo[4]=bar[4]
foo[3]=bar[3]
foo[2]=bar[2]
foo[1]=bar[1]
foo[0]=bar[0]

Das ist besser als

x=0
foo[x]=bar[x]
x=1
foo[x]=bar[x]
x=2
foo[x]=bar[x]

usw.


Wenn du das rückwärts erledigst (5..0 statt 0..5) kannst du eben trotzdem vor jede Anweisung ein Label setzen und dann je nach Bereich die eine oder andere anspringen.

Ah OK, jetzt hats halbwegs klick gemacht. Nur muß es ja trotzdem ein offset sein, und keine Zahl, denn sonst würde ich ja immer dieselben Werte überschreiben bzw ich müßte foo und bar (als pointer gesheen) entsprechend erhöhen, damit ich wieder Zahlen benutzen kann.

Ja, die Offsets kannst du vorher aber in die Register packen - die werden ja dann nicht mehr verändert und damit gibts auch keine Abhängigkeiten.

Wenn du mit Assembler schneller sein willst als mit einem ordentlichen Compiler darfst du dich bei der Umsetzung vom Alg keinesfalls an einer Hochsprache orientieren, denn so macht der Compiler das auch - und der kennt bei der Optimierung auf eine CPU idR mehr Regeln als du .

Ja ja, ich muß mich noch etwas mit den Registern anfreunden... Kann ich eigentlich edi und esi so nutzen wie ich will? Oder muß ich irgendetwas beachten?

Hast du ne AHnung wie man unter dem gcc inline assembler die jumptable mit den labels als Werten initialiert? In dem art of assembly wird ja nur hla benutzt und dort geht das in einer c ähnl Notation.

Mit NASM dürfte das gehen, den bekommst du auch in ein GCC Prog rein. Frag mich aber nicht wie

Ich mag den AT&T Assembler Syntax nicht, daher hab ich den auch wo es ging gemieden (und NASM ist eben ein sehr leistungsfähiger Assembler mit Intel Syntax).

Ich weiß nur, daß man nasm output mit gcc output verlinken kann, aber soweit wie ich es verstanden habe, wird gas als inline assembler benutzt. Werde mal was suchen...

Wie würde es denn mit nasm und den sprunglabels gehen?

So habe mal etwas rumgesucht und es scheint doch so, daß ich nasm *nicht* als inline assembler nutzen kann. Dh. ich müßte die assmbler ROutinen seperat schreiben, was ich nicht unbedingt möchte, da ich eigentlich soweit wie möglich weiterhin C(++) nutzen wollte. herrje, muß also einen GAS Experten finden.

So würd ich das machen:



Hoffe ich bin im NASM Syntax nicht ganz eingerostet, das letzte mal ist schon eine Weile her.