Fibonacci Number via Inline Assembly in Delphi

Delphi is a power RAD under Win32. I think one of the main strengths is that you can write inline assembly easily, which makes it very powerful and flexible. In Delphi, you can include assembly code with the structure asm and end. For example,

procedure test; assembler; register;
asm
  mov eax, 1
  add eax, 2
end;

The keyword assembler is to tell the compiler the function or procedure contains assembly code and the register is to tell the compiler, if possible, use as many registers as possible, which can yield performance gains.

Basically, you can use the standard WIN32 32-bit registers such as EAX, EBX, ECX, EDX. Also, AX, BX, CX, DX the 16-bit registers are available. Each 16-bit registers can be treated as two 8-bit registers. For example, the AX register can be considered as AH and AL.

The following will demonstrate three versions of Fibonacci functions, with two implemented in inline assembly and one in standard pascal.

The Fibonacci number is defined as follows.

Fibonacci

The Delphi source code is presented as follows, which times each version of Fib number. (Also available at https://github.com/DoctorLai/Algorithms/blob/master/Fib/TestASM.dpr

program TestASM;
(*
  https://helloacm.com
  TestASM.pas
  Example Usage of Inline-Assembly in Delphi
  Compares Performance of Three Implementation of Fib Numbers
*)

{$APPTYPE CONSOLE}

uses
  Windows,
  SysUtils;

function Fib1(n: LongWord): LongWord; assembler; register;
asm
  PUSH EBX
  TEST EAX, EAX
  JZ @M
  MOV ECX, EAX
  XOR EAX, EAX
  MOV EDX, 1
@L:
  MOV EBX, EDX
  ADD EDX, EAX
  MOV EAX, EBX
  LOOP @L
@M:
  POP EBX
end;

function Fib2(n: LongWord): LongWord; assembler; register;
asm
  PUSH EBX
  XOR ECX, ECX
  TEST EAX, EAX
  JZ @L
  MOV EDX, 1
@M:
  MOV EBX, EDX
  ADD EDX, ECX
  MOV ECX, EBX
  DEC EAX
  JNZ @M
@L:
  MOV EAX, ECX
  POP EBX
end;

function Fib3(n: LongWord): LongWord;
var
  i, a, b, c: LongWord;
begin
  a := 0;
  b := 1;
  for i := 1 to n do
  begin
    c := b;
    b := a + b;
    a := c;
  end;
  Result := a;
end;

var
  i: integer;
  k: array [0..150000] of LongWord;
  start : cardinal;

begin
  for i := 0 to 20 do
  begin
    Writeln(Fib1(i), ' ', Fib2(i), ' ', Fib3(i));
  end;
  start := GetTickCount;
  for i := 0 to 150000 do
  begin
    k[i] := Fib1(i);
  end;
  Writeln(GetTickCount - start);
  start := GetTickCount;
  for i := 0 to 150000 do
  begin
    k[i] := Fib2(i);
  end;
  Writeln(GetTickCount - start);
  start := GetTickCount;
  for i := 0 to 150000 do
  begin
    k[i] := Fib3(i);
  end;
  Writeln(GetTickCount - start);
  Readln;
end.

The timings is shown at the following output:

From this, we can see that even short algorithm can be implemented differently in the aspect of assembly language. The Delphi compiler is very efficient and it produces highly-optimised Win32 assembly code. Unless you know what are doing, for example, you use assembly to write SIMD, it is not recommended to optimise every single piece of code in assembly.

In Delphi IDE, you can use Ctrl + Alt + D to invoke the de-assembly view in the debug mode. For example, the following shows how Delphi compiler translates the pascal code.

Comparing the three approaches, the Delphi standard Pascal version of Fib is efficient. Despite many approaches in the view of assembly level, these approaches vary on performances i.e. different instructions cost different CPU cycles and are of different sizes.

For example, to clear EAX register to zero, the following is not optimal.

mov eax, 0

And it is often replaced by the following more-efficient instruction,

xor eax, eax

or,

sub eax, eax

By default, the first parameter of procedure/function is passed by register EAX and the result (integer, longword) is returned by the same register.

The implementation Fib2 is very similar to Fib3 (standard pascal version), they both give similar performance. However, the Fib1 implementation is not. Maybe using ECX loop is not as efficient as simply decrementing the register EAX.

–EOF (The Ultimate Computing & Technology Blog) —