Performance Comparison for Dynamically-typed Non-compile Languages

result.md

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

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);
    }
}

test_env.png

zfibonacci_recursion.png

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

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

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

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

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