FAQ der Newsgroup de.comp.lang.assembler (d.c.l.a.)

Was ist "loop unrolling"?

Das Herunter- oder Hochzählen des Schleifenzählers und der Sprung kostet eine gewisse Anzahl von Taktzyklen. Dies kann reduziert werden, wenn die Tätigkeit innerhalb der Schleife z. B. 16-mal hintereinander steht, und so nur alle 16 Mal der Zähler aktualisiert und gesprungen werden muss. Zudem ist es möglicherweise leichter auf verschiedene Register zu parallelisieren, da nicht immer die gleichen Register genutzt werden müssen. Eine ausgerollte Schleife muss jedoch doppelt implementiert werden, da der Rest wieder einzeln abgearbeitet werden muss, da sich z.b. 100 nicht durch 16 teilen lässt, d. h. eine 16-fach ausgerollte Schleife muss in der ersten Schleife (6*16)-mal etwas machen, in der zweiten Schleife den Rest (Modulo) von 4, da: 6*16+4=100.

Ist der Code etwas größer, kann es sein, dass ein Ausrollen von nur 8 oder 4 mehr bringt. Das Ausrollen von 2er-Potenzen habe ich als praktisch empfunden, da der erste Zähler mit einem Schiebebefehl und der zweite mit einer UND-Verknüpfung ermittelt werden kann:

100 shr 4 = 6 und 100 and 15 = 4

Das nachfolgende Beispiel und ein Beispiel mit 2-Register-Zahlen (64 Bit im 32-Bit-Modus) gibt es auch als Delphi-Projekt zum Herunterladen (ZIP-Datei 340 kB).

Lazarus (FreePascal) 
uses SysUtils,StdCtrls,Forms,LResources,interfaces;

function RdTsc:int64;
asm
  db $0f, $31
end;

function Fibonacci01(n:integer):integer;
asm
  push ebx
  push ecx

  mov ecx, n
  jecxz @@Fertig

  mov eax, 0
  mov ebx, 1

@@lp01:
  add eax, ebx
  xchg eax, ebx
  dec ecx
  jnz @@lp01

@@Fertig:
  pop ecx
  pop ebx
end;

function Fibonacci04(n:integer):integer;
asm
  push ebx
  push ecx
  push edx

  mov ecx, n
  jecxz @@Fertig

  mov edx, ecx // Zähler in EDX sichern
  shr ecx, 2
  mov eax, 0
  mov ebx, 1
  jecxz @@Rest

@@lp01:
  add eax, ebx
  xchg eax, ebx
  add eax, ebx
  xchg eax, ebx
  add eax, ebx
  xchg eax, ebx
  add eax, ebx
  xchg eax, ebx
  dec ecx
  jnz @@lp01

@@Rest:
  and edx, 3
  mov ecx, edx
  jecxz @@Fertig

@@lp02:
  add eax, ebx
  xchg eax, ebx
  dec ecx
  jnz @@lp02

@@Fertig:
  pop edx
  pop ecx
  pop ebx
end;

function Fibonacci08(n:integer):integer;
asm
  push ebx
  push ecx
  push edx

  mov ecx, n
  jecxz @@Fertig

  mov edx, ecx // Zähler in EDX sichern
  shr ecx, 3
  mov eax, 0
  mov ebx, 1
  jecxz @@Rest

@@lp01:
  add eax, ebx
  xchg eax, ebx
  add eax, ebx
  xchg eax, ebx
  add eax, ebx
  xchg eax, ebx
  add eax, ebx
  xchg eax, ebx
  add eax, ebx
  xchg eax, ebx
  add eax, ebx
  xchg eax, ebx
  add eax, ebx
  xchg eax, ebx
  add eax, ebx
  xchg eax, ebx
  dec ecx
  jnz @@lp01

@@Rest:
  and edx, 7
  mov ecx, edx
  jecxz @@Fertig

@@lp02:
  add eax, ebx
  xchg eax, ebx
  dec ecx
  jnz @@lp02

@@Fertig:
  pop edx
  pop ecx
  pop ebx
end;

function Fibonacci16(n:integer):integer;
asm
  push ebx
  push ecx
  push edx

  mov ecx, n
  jecxz @@Fertig

  mov edx, ecx // Zähler in EDX sichern
  shr ecx, 4
  mov eax, 0
  mov ebx, 1
  jecxz @@Rest

@@lp01:
  add eax, ebx
  xchg eax, ebx
  add eax, ebx
  xchg eax, ebx
  add eax, ebx
  xchg eax, ebx
  add eax, ebx
  xchg eax, ebx
  add eax, ebx
  xchg eax, ebx
  add eax, ebx
  xchg eax, ebx
  add eax, ebx
  xchg eax, ebx
  add eax, ebx
  xchg eax, ebx
  add eax, ebx
  xchg eax, ebx
  add eax, ebx
  xchg eax, ebx
  add eax, ebx
  xchg eax, ebx
  add eax, ebx
  xchg eax, ebx
  add eax, ebx
  xchg eax, ebx
  add eax, ebx
  xchg eax, ebx
  add eax, ebx
  xchg eax, ebx
  add eax, ebx
  xchg eax, ebx
  dec ecx
  jnz @@lp01

@@Rest:
  and edx, 15
  mov ecx, edx
  jecxz @@Fertig

@@lp02:
  add eax, ebx
  xchg eax, ebx
  dec ecx
  jnz @@lp02

@@Fertig:
  pop edx
  pop ecx
  pop ebx
end;

function fibmich(Tiefe:integer): String;
const
  times=1000;
var
  t1,t2,t3,t4,t5:int64;
  ta,tb,tc,td:int64;
  i,j,k,m,o:integer;
  f1,f2,f3:integer;
  s1 : String;
begin
  s1 := 'Fibonacci-Zahlen:' + #13+#10;

  f1 := 0;
  f2 := 1;
  for i:=0 to Tiefe do
  begin
    s1 := s1 + IntToStr(i) + ', ' + IntToStr(f1) + #13+#10;
    f3 := f1 + f2;
    f1 := f2;
    f2 := f3;
  end;

  t1:=RdTsc;
  for i:=1 to times do
  begin
    j:=Fibonacci01(Tiefe);
  end;
  t2:=RdTsc;
  for i:=1 to times do
  begin
    k:=Fibonacci04(Tiefe);
  end;
  t3:=RdTsc;
  for i:=1 to times do
  begin
    m:=Fibonacci08(Tiefe);
  end;
  t4:=RdTsc;
  for i:=1 to times do
  begin
    o:=Fibonacci16(Tiefe);
  end;
  t5:=RdTsc;

  ta:=(t2-t1) div times;
  tb:=(t3-t2) div times;
  tc:=(t4-t3) div times;
  td:=(t5-t4) div times;

fibmich := s1 + 'Funktionsergebnisse: '
  + IntToStr(j) + ', ' + IntToStr(k) + ', ' + IntToStr(m) + ', ' + IntToStr(o)
  + #13 + #10
  + 'Taktverbrauch der einzelnen Funktionen:'
  +  IntToStr(ta) + ', ' + IntToStr(tb) + ', ' + IntToStr(tc) + ', ' + IntToStr(td);

end;

type
  TForm1 = class(TForm)
    Button1: TButton;
    Memo1: TMemo;
    procedure Button1Click();
  end;

var
  Form1: TForm1;

procedure TForm1.Button1Click();
const
  Tiefe=46;
begin
  Memo1.Clear;
  Memo1.Lines.Add(fibmich (Tiefe));
end;

begin
  LazarusResources.Add('TForm1','FORMDATA',['TPF0'
    +#6'TForm1'#5'Form1'
    +#5'Width'#3#88#2
    +#6'Height'#3#224#1
    +#7'Caption'#6#23'Loop Enrolling Beispiel'
    +#0
    +#7'TButton'#7'Button1'
    +#4'Left'#2#24
    +#3'Top'#2#16
    +#5'Width'#2#75
    +#6'Height'#2#25
    +#7'Caption'#6#10'Klick mich'
    +#7'OnClick'#7#12'Button1Click'+#0
    +#0
    +#5'TMemo'#5'Memo1'
    +#4'Left'#2#120
    +#3'Top'#2#16
    +#5'Width'#3#194#1
    +#6'Height'#3#194#1
    +#10'ScrollBars'#7#6'ssBoth'+#0
    +#0#0
  ]);
  Application.Initialize;
  Application.CreateForm(TForm1, Form1);
  Application.Run;
end.

Hubert Seidel Aug 2008 in d.c.l.a. (g8ur6c$sf2$03$1@news.t-online.com)