Skip to content

Instantly share code, notes, and snippets.

@appkr
Last active April 16, 2022 06:01
Show Gist options
  • Star 2 You must be signed in to star a gist
  • Fork 0 You must be signed in to fork a gist
  • Save appkr/ced41a97796116bead6802d42002d3a0 to your computer and use it in GitHub Desktop.
Save appkr/ced41a97796116bead6802d42002d3a0 to your computer and use it in GitHub Desktop.
Performance Comparison for Dynamically-typed Non-compile Languages

Test Result

Language Execution time(sec)
JS with V8 (Node 8.11) 3.18
PHP 7.2 28.026075124741
PHP 7.0 28.537676095963
Ruby 2.5 37.355172
Python 2.7 70.2023770809
Python 3.6 99.59470009803772
PyPy 6 on Python 2.7 7.27390384674

FYI, Strictly-typed compile language

  • C 1.3 sec
  • Java 1.1 sec

Test Env

  • How to check version and run the REPL for each language
    • node -v; node
    • php -v; php -a
    • ruby -v; irb
    • python --version; python

asciicast

Test Code

const fib = (n) => {
    if (n <= 1) {
        return 0;
    }
    if (n === 2) {
        return 1;
    }
    return fib(n - 2) + fib(n - 1);
}

const startTime = new Date().getTime();
const range = [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];
range.forEach((i) => {
    console.log(i, fib(i));
});
console.log((new Date().getTime() - startTime) / 1000); 
// 3.18 @node v8.11.3
<?php // opcache.enable_cli => Off => Off
function fib(int $n) {
    if ($n <= 1) {
        return 0;
    }
    if ($n === 2) {
        return 1;
    }

    return fib($n - 2) + fib($n - 1);
}

$startTime = microtime(true);
foreach (range(1, 40) as $i) {
    echo $i, ' ', fib($i), PHP_EOL;
}
echo microtime(true) - $startTime; 
// 28.026075124741 sec @PHP 7.2.10
// 28.537676095963 sec @PHP 7.0.30
def fib(n)
  return 0 if n <= 1
  return 1 if n == 2
  return fib(n - 2) + fib(n - 1)
end

start_time = Time.now
(1..40).each do |i|
  puts "#{i.to_s} #{fib(i).to_s}"
end
puts (Time.now - start_time) 
# 37.355172 @ruby 2.5.0p0
import time

def fib(n):
  if n <= 1:
    return 0
  elif n == 2:
    return 1
  return fib(n - 2) + fib(n - 1)

if __name__ == "__main__":
  start_time = time.time() 
  for i in range(1, 40 + 1):
    print(i, fib(i))
  print(time.time() - start_time) 
  # 70.2023770809 sec @Python 2.7.10
  # 99.59470009803772 sec @Python 3.6.4
#include <stdio.h>
#include <time.h>

int fib(int n) {
    if (n <= 1) {
        return 0;
    }
    if (n == 2) {
        return 1;
    }

    return fib(n - 2) + fib(n - 1);
}

int main(void) {
    clock_t start_time, end_time;
    float exec_time;

    start_time = clock();
    for (int i = 1; i <= 40; i++) {
        printf("%d %d\n", i, fib(i));
    }
    end_time = clock();
    exec_time = (float)(end_time - start_time) / CLOCKS_PER_SEC;
    printf("%.3f\n", exec_time);
    return 0;
}
public class Fibonacci {
    public static void main(String[] args) {
        long startTime = System.currentTimeMillis();
        for (long i = 1; i <= 40; i++) {
            System.out.printf("%d %d \n", i, fib(i));
        }
        long endTime = System.currentTimeMillis();
        long exeTime = endTime - startTime;
        System.out.printf("%d ms\n", exeTime);
    }

    private static long fib(long n) {
        if (n <= 1) {
            return 0;
        }
        if (n == 2) {
            return 1;
        }

        return fib(n - 2) + fib(n - 1);
    }
}
@appkr
Copy link
Author

appkr commented Oct 28, 2018

I did this test to verify the authenticity of the following article.
https://hackernoon.com/django-vs-laravel-which-framework-should-you-choose-1d0f40049ec1

While the article benchmarks http transaction per second(tps) on framework, I've tested performance in language level. The reason being, there are so many optimization points in fully functioning web service, e.g., selection of web server, process manager, library, ..., and their settings. So I just wanted to know the baseline.

@appkr
Copy link
Author

appkr commented Oct 29, 2018

Recursions are inherently heavy. In this scenario one function call may generate additional subsequent two function calls, if the parameter does not fall into the exit condition. When fib(2) or fib(1) are called, the exit condition reaches and start to return.

Call Graph              Return Graph
-------------------------------------
fib(6)                          5
├── fib(4)                    2
│   ├── fib(2)              1
│   └── fib(3)              1
│       ├── fib(1)        0
│       └── fib(2)        1
└── fib(5)                    3
    ├── fib(3)              1
    │   ├── fib(1)        0
    │   └── fib(2)        1
    └── fib(4)              2
        ├── fib(2)        1
        └── fib(3)        1
            ├── fib(1)  0
            └── fib(2)  1
  • To depict it in a diagram

  • To get the 6th fibonacci number, there must be 15 function calls including the first call. And the number of function calls explode exponentially as the number grows.

nth fibonacci number recursion count
1 0 1
2 1 1
3 1 3
4 2 5
5 3 9
6 5 15
7 8 25
8 13 41
9 21 67
10 34 109
11 55 177
12 89 287
13 144 465
14 233 753
15 377 1219
16 610 1973
17 987 3193
18 1597 5167
19 2584 8361
20 4181 13529
21 6765 21891
22 10946 35421
23 17711 57313
24 28657 92735
25 46368 150049
26 75025 242785
27 121393 392835
28 196418 635621
29 317811 1028457
30 514229 1664079
31 832040 2692537
32 1346269 4356617
33 2178309 7049155
34 3524578 11405773
35 5702887 18454929
36 9227465 29860703
37 14930352 48315633
38 24157817 78176337
39 39088169 126491971
40 63245986 204668309

The test was done on the same computer. Then, my next question is that where the difference come from? (Not an expert on computer internals though, I think there were no I/O with file, network, DB, etc...) Why Node and PyPy showed decent performance while others not?

@appkr
Copy link
Author

appkr commented Oct 29, 2018

Optimization

  • It only took around 0.01 sec after optimization.
  • The same technique can also be applied to other languages.
<?php
$cache = [];

function fib(int $n) {
	static $cache;
	if ($n <= 1) {
		return 0;
	}
	if ($n === 2) {
		return 1;
	}
	if (isset($cache[$n])) {
		return $cache[$n];
	}
    return $cache[$n] = fib($n - 2) + fib($n - 1);
}

$startTime = microtime(true);
foreach (range(1, 40) as $i) {
    echo $i, ' ', fib($i), PHP_EOL;
}
echo microtime(true) - $startTime;

// 0.0082170963287354
// 0.004504919052124
// 0.011820077896118
// 0.0066640377044678
// 0.0061328411102295
nth fibonacci number recursion count
1 0 1
2 1 1
3 1 3
4 2 5
5 3 7
6 5 9
7 8 11
8 13 13
9 21 15
10 34 17
11 55 19
12 89 21
13 144 23
14 233 25
15 377 27
16 610 29
17 987 31
18 1597 33
19 2584 35
20 4181 37
21 6765 39
22 10946 41
23 17711 43
24 28657 45
25 46368 47
26 75025 49
27 121393 51
28 196418 53
29 317811 55
30 514229 57
31 832040 59
32 1346269 61
33 2178309 63
34 3524578 65
35 5702887 67
36 9227465 69
37 14930352 71
38 24157817 73
39 39088169 75
40 63245986 77

References

@appkr
Copy link
Author

appkr commented Nov 2, 2018

함수를 실행하는 중간에 함수가 재귀적으로 호출되면, 함수의 복사본을 하나 더 만들어서 복사본을 실행하게된다.

위 문장의 내용은 재귀적인 형태의 함수 호출이 가능한 이유를 충분히 설명하고 있다. 실제로 함수를 구성하는 명령문은 CPU로 이동되어서(복사가 되어서) 실행이된다. 그런데 이 명령문은 얼마든지 CPU로 이동이(복사가) 가능하다. 따라서 함수의 중간쯤 위치한 명령문을 실행하다가 함수의 실행을 완료하지 않은 상태에서 다시 함수의 앞 부분에 위치한 명령문을 CPU로 이동시키는 것은 문제가 되지 않는다. 그래서 재귀적인 형태의 함수 호출이 가능한 것이다.

- 윤성우의 열혈 C 프로그래밍 중에서

@appkr
Copy link
Author

appkr commented Nov 23, 2018

  • (Java 제외) 모두 C/C++ 언어로 짠 언어
  • 프로그램을 실행할 때 기계 수준(메모리, 레지스터, CPU 등의 상호 동작)의 성능 차이는 없다고 가정하자. 다시 말해, 코드가 메모리에 올라가면, 위에서 분석한 함수 호출 횟수 등은 스크립트 언어든 컴파일 언어든 이미 기계 수준의 일이므로 같은 상수 시간이 걸린다고 가정할 수 있다.
  • 즉, "전체 실행 시간 = 스크립트 분석 및 컴파일 시간 + 프로그램 실행 시간" 식에서 프로그램 실행 시간은 Compile과 No-compile을 비교해도 차이가 없고, 스크립트 언어들 간에도 차이가 없다고 가정할 수 있다.
  • 그렇다면, 스크립트 언어간의 성능 차이는 컴파일(스크립트 -> 분석 트리, 추상 구문 트리, 심볼 테이블, 바이트 코드)까지 걸리는 시간 및 컴파일된 바이너리가 작동하는 VM의 성능 때문이라고 결론 지을 수 있을까?

@appkr
Copy link
Author

appkr commented Apr 16, 2022

Use loop instead of recursion

  • while fibonacci(47) in java, implemented using recursion takes 7sec see the link
  • the same operation takes 0ms when implemented using loop see the link

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment