Benchmarks

[Thaddy]

Not a tail recursion.

Fibonacci's code is tail recursion.

[alpine]

Not a tail recursion.

Fibonacci's code is tail recursion.

Would be if the last line was:

Code: Pascal  [Select][+][-]

1. Fibonacci := n + Fibonacci(n - 1);

but it is:

Code: Pascal  [Select][+][-]

1. Fibonacci := Fibonacci(n - 1) + Fibonacci(n - 2);

Edit: A typo, * instead of +.

[Thaddy]

Anyway, not using recursion is much much faster and will be inlined:

Code: Pascal  [Select][+][-]

1. program fib;
2. {$mode objfpc}{$optimization level4}{$i-}
3. uses cmem,sysutils;
4. // non-recursive, iterative
5. function Fibonacci(n: cardinal): cardinal;inline;
6. var
7.   a, b, temp, i: cardinal;
8. begin
9.   if n <= 1 then
10.     Exit(n);
11.   a := 0;
12.   b := 1;
13.   for i := 2 to n do
14.   begin
15.     temp := a + b;
16.     a := b;
17.     b := temp;
18.   end;
19.   Result := b;
20. end;
21.  
22. var
23.   code:integer;
24.   i,u:cardinal;
25.   r:cardinal = 0;
26.   start:int64;
27. begin
28.   val(paramstr(1),u,code);
29.   start := gettickcount64;
30.   if code = 0 then
31.   for i := 1 to u do
32.     r := r+fibonacci(u);
33.   writeln(r);
34.   writeln(gettickcount64-start);
35. end.

If this is allowed, it beats all of the others.
That is also because recursion is exponentionally slower. It has to grow the stack all the time.
A combined test with my code and fibonacci's code:

Code: Bash  [Select][+][-]

1. D:\>fib 5
2. 25
3. 0
4. 25
5. 0
6.  
7. D:\>fib 10
8. 550
9. 0
10. 550
11. 0
12.  
13. D:\>fib 20
14. 135300
15. 0
16. 135300
17. 0
18.  
19. D:\>fib 30
20. 24961200
21. 0
22. 24961200
23. 359
24.  
25. D:\>fib 40
26. 4093366200
27. 0
28. 4093366200
29. 65500

[Thaddy]

I also compared the above to GNU C

Code: C  [Select][+][-]

1. /* recursive */
2. int fibonacc1i(int n) {
3.     if (n <= 1) return n;
4.     return fibonacci1(n - 1) + fibonacci1(n - 2);
5. }
6. /* iterative  */
7. int fibonacci2(int n) {
8.     if (n <= 1) return n;
9.     int a = 0, b = 1, temp;
10.     for (int i = 2; i <= n; i++) {
11.         temp = a + b;
12.         a = b;
13.         b = temp;
14.     }
15.     return b;
16. }

the results are neigh on equal between C and FreePascal for the iterative function and with similar optimizations.
I did not test rust yet, but both C and Freepascal beat all the other languages.

[bytebites]

It is not acceptable. Requirement was to use recursion.

[Warfley]

It is not acceptable. Requirement was to use recursion.

As I said previously this benchmark is terrible. The requirement from the github:

Emphasizes function call overhead and recursion.

But LLVM optimizes the tail recursion away away:

Code: C  [Select][+][-]

1. unsigned fib(unsigned n) {
2.     if (n==0) return 0;
3.     if (n==1) return 1;
4.     return fib(n-1) + fib(n-2);
5. }

Clang -O3:

Code: ASM  [Select][+][-]

1. fib(unsigned int):
2.         push    rbp
3.         push    rbx
4.         push    rax
5.         mov     ebx, edi
6.         xor     ebp, ebp
7.         cmp     edi, 2
8.         jb      .LBB0_3
9.         xor     ebp, ebp
10. .LBB0_2:
11.         lea     edi, [rbx - 1]
12.         call    fib(unsigned int)
13.         add     ebx, -2
14.         add     ebp, eax
15.         cmp     ebx, 1
16.         ja      .LBB0_2
17. .LBB0_3:
18.         add     ebp, ebx
19.         mov     eax, ebp
20.         add     rsp, 8
21.         pop     rbx
22.         pop     rbp
23.         ret

So if the goal is to measure the overhead of function calls, using code where the compiler optimizes half of the function call away is completely missing the point.

Again this is probably the most terrible benchmark I have seen, which does not measure anything. So why follow rules they don't follow themselves really

[alpine]

Clang -O3:

What a smartass! It discovered it is an iterative algorithm by itself. Impressive /oo\

Again this is probably the most terrible benchmark I have seen, which does not measure anything. So why follow rules they don't follow themselves really

+1

[Thaddy]

But LLVM optimizes the tail recursion away away:

then the fpc llvm backend should do that too?
(I have to build that again)

In that case, do the speed test with the llvm backend. 

[Warfley]

Probably. It's on my list of things to test out for some time now, but any code that does not use like Pascal specific functionality (managed types, classes, Exceptions, etc.) so basically the C compatible subset, should probably not be any different performance wise to C code when build with LLVM

[turrican]

Again, thanks for your valuable help!