Once upon a time in the evening in one programmer chat, some programmers felt boring. And I don’t remember why, but we started to compare programming languages performance using the Fibonacci algorithm in its recursive implementation. Many times passed since it happened. Only artifacts such as source code left on my hard drive and that’s why I decided to create this post.
Short Fibonacci number sequence description: F[n] = F[n-1] + F[n-2] where starting point could be F[0] = 0 and F[1] = 1 or F[1] = 1 and F[2] = 2.
Here is math description: https://en.wikipedia.org/wiki/Fibonacci_number
Here is different programming languages implementations: https://en.wikibooks.org/wiki/Algorithm_Implementation/Mathematics/Fibonacci_Number_Program
Let’s begin with PHP 7. Just because it’s my main language currently. And also it would be weaker one in speed with a recursive solution. For example, Javascript works much faster with a lot of functions calls by its nature. But Python 2.7 will be just a bit faster than PHP 7. These two languages stronger in different situations. That’s why objective and absolute performance comparison of languages isn’t a purpose of this post. The purpose of this post is fun and interest, nothing more.
Time measurement will be done in a console just with build in Linux command “time“.
PHP 7
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 |
<?php function fibonacci ($n) { if ($n == 1 || $n == 2) { return 1; } else { return fibonacci( $n - 1)+fibonacci( $n - 2 ); } } echo fibonacci(35) . "\n"; |
|
1 2 3 4 5 6 7 8 |
time php fibonacci.php 9227465 real 0m7.921s user 0m7.898s sys 0m0.009s |
I have used 35 as an argument. Just because PHP implementation works too long with argument value 40. But I will use 40 where it’s possible.
For PHP 5.6 results are slightly different. I don’t see drastically improvement in PHP 7.1…
|
1 2 3 4 5 6 7 8 |
time php fibonacci.php 9227465 real 0m9.217s user 0m9.189s sys 0m0.006s |
Python 2.7
|
1 2 3 4 5 6 7 8 9 10 11 |
def fib(n): if n == 1: return 1 elif n == 0: return 0 else: return fib(n-1) + fib(n-2) print fib(37) |
|
1 2 3 4 5 6 7 8 |
time python2.7 fibonacci.py 24157817 real 0m7.576s user 0m7.514s sys 0m0.001s |
Have used 37 as an argument for the same reason as with PHP. For number 38 timing will be 12s.
Python 3.5
Only one difference in code
|
1 2 3 |
print(fib(37)) |
And python3 is slower than python2. :)
|
1 2 3 4 5 6 7 8 |
time python3 fibonacci3.py 24157817 real 0m9.709s user 0m9.692s sys 0m0.002s |
Javascript Node 7.5.0
|
1 2 3 4 5 6 7 8 9 10 11 |
function fibonacci(n) { if (n < 2){ return 1; }else{ return fibonacci(n-2) + fibonacci(n-1); } } console.log(fibonacci(40)); |
|
1 2 3 4 5 6 7 8 |
time node fibonacci.js 165580141 real 0m1.340s user 0m1.336s sys 0m0.003s |
Js is pretty fast with recursion based solution by its nature as explained in the beginning.
Let’s try some compiled languages instead of interpreted.
Java 8
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 |
public class fibonacci { public static void main(String[] args) { int index = 40; System.out.println(fibonacci(index)); } public static int fibonacci(int n) { if(n == 0) return 0; else if(n == 1) return 1; else return fibonacci(n - 1) + fibonacci(n - 2); } } |
We need to compile it in class in order to run it.
|
1 2 3 4 5 6 7 8 9 10 |
javac fibonacci.java time java fibonacci 102334155 real 0m0.536s user 0m0.533s sys 0m0.008s |
Compiled beats any interpreted or script.
C++ (gcc version 5.4)
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 |
#include <iostream> using namespace std; int fib(int x) { if (x < 2) { return 1; } else { return fib(x-1)+fib(x-2); } } int main() { cout << fib(40) << endl; } |
Also, should be compiled.
|
1 2 3 4 5 6 7 8 9 10 |
g++ fibonacci.cpp time ./fibonacci.out 165580141 real 0m0.249s user 0m0.247s sys 0m0.000s |
It beats even Java implementation. Just great.
Well, let’s go deeper….
Assembler (NASM version 2.11.08)
Here I had problems to convert 32-bit version into 64-bit. I had a problem to run it then with nasm because hadn’t worked with assembly since university. That’s why I have created SO question and got some help here. So, the code is:
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 |
DEFAULT rel section .text GLOBAL _start _start: push qword 40 ; -> 1346269 call fibonacci add rsp, 8 call write_eax mov edi, 0 ; return 0 (success) mov eax, 60 ; sys_exit syscall fibonacci: push rbp push rbx mov rbp, rsp add rbp, 24 mov ebx, [rbp] cmp EBX,1 ; Check for base case jle base ; It is base if (n <= 1) lea ecx,[ebx-1] push rcx call fibonacci ; Calculate fibonacci for (EBX - 1) pop rcx push rax lea ecx,[ebx-2] push rcx call fibonacci ; Calculate fibonacci for (EBX - 2) pop rcx pop rcx add eax,ecx ; eax = fibonacci(N-2) + fibonacci(N-1) jmp end base: ; Base case mov EAX,1 ; The result would be 1 end: pop rbx pop rbp ret write_eax: mov rsi, rsp ; Keyword: Red Zone (https://en.wikipedia.org/wiki/Red_zone_%28computing%29) sub rsi, 1 mov byte [rsi], `\n` ; Line feed mov ecx, 10 ; Divisor .L1: xor edx, edx div ecx ; EDX:EAX / ECX -> EAX, remainder EDX or dl, 0x30 ; Convert remainder to ASCII sub rsi, 1 mov [rsi], dl ; Store remainder reversed on the stack test eax, eax jne .L1 mov rdx, rsp ; RDX: message string length sub rdx, rsi mov rdi, 1 ; RDI=1: stdout mov eax, 1 ; sys_write syscall ; /usr/include/x86_64-linux-gnu/asm/unistd_64.h ret |
And the fastest timing of course!
|
1 2 3 4 5 6 7 8 |
time nasm -f elf64 fibonacci_so.asm && ld -arch x86_64 fibonacci_so.o -o fab && ./fab real 0m0.003s user 0m0.003s sys 0m0.000s 165580141 |
Great, just great!
I will stop here. :) Maybe I would update this post later with versions and timing for some high-level languages like C# and Ruby and for some low level like C. Also, I’m interested in running functional languages like Haskel, Erlang and Scala.
A bit later I decided to add Ruby.
Ruby 2.3
|
1 2 3 4 5 6 7 |
def fibonacci( n ) return n if n <= 1 fibonacci( n - 1 ) + fibonacci( n - 2 ) end puts fibonacci( 39 ) |
|
1 2 3 4 5 6 7 8 |
time ruby fibonacci.rb 63245986 real 0m7.826s user 0m7.806s sys 0m0.003s |
Actually Ruby beats PHP and Python with argument value 39.
