フィボナッチで各種言語をベンチマーク

AWK、Ada、Bash、Boo、C、C#C++Clojure、D、Erlang、Forth、Fortran、Go、Groovy、Haskell、Io、JavaJavaScriptLispLuaOCamlObjective-CPHPPascalPerl、Pike、PrologPython、R、RubyScalaSchemeSmalltalk、Tcl でフィボナッチ数を求める処理時間を計測してみました。

フィボナッチ数は漸化式で求められます。

F0 = 0
F1 = 1
Fn+2 = Fn+1 + Fn

フィボナッチ数を求めるアルゴリズムはいろいろありますが、今回は以下の再帰で求めるアルゴリズムで統一しました。

#include <stdio.h>

int fib(int n) {
    if (n < 2) return n;
    return fib(n - 2) + fib(n - 1);
}

int main(int argc, char *argv[]) {
    printf("%d\n", fib(38));
    return 0;
}

これはフィボナッチ数を求める実装としては最も単純な部類に属すると思います。すべての言語で 38 番目のフィボナッチ数を算出して、標準出力に表示して改行します。

すべての言語と処理系の実行環境は Ubuntu 10.04 が搭載された Let's Note Y4(Pentium M 778MHz、メモリ 1GB)です。時間計測には time の user を使用しています。

コンパイラが最適化オプションを提供していて、簡単に見つけられたものに関しては、最適化ありでも計測しています。また、ひとつの言語を複数の処理系で計測していたりもします。

それぞれの言語でできるだけ標準的な記法で書いたつもりですが、今回初めて触った言語もたくさんあるので、何かおかしい点があればご指摘ください。

それでは、まずは各言語の実装と実行方法から紹介します。

AWK

BEGIN {
    printf "%d\n", fib(38)
}

function fib(n) {
    if (n < 2) return n
    return fib(n - 2) + fib(n - 1)
}

結構古い言語であるはずなのに、関数が JavaScript と見間違うほどモダンです。

$ awk fib.awk

Ada

with Ada.Integer_Text_IO;

procedure Fib is
begin
    declare
    function fib(n : integer) return integer is
    begin
        if n < 2 then
            return n;
        else
            return fib(n - 2) + fib(n - 1);
        end if;
    end fib;

    begin
        Ada.Integer_Text_IO.Put(Item => fib(38), Width => 1);
    end;
end Fib;

これまた結構古い言語であるはずなのに、パッケージみたいな概念があるのに驚きました。

最適化なしはこちら。

$ gnat make fib.adb; ./fib

最適化ありはこちら。

$ gnat make -O2 fib.adb; ./fib

Bash

function fib() {
    if [ $1 -lt 2 ]; then
        return $1
    else
        fib `expr $1 - 2`
        local x=$?
        fib `expr $1 - 1`
        return `expr $x + $?`
    fi
}

fib 38
echo $?

$ bash fib.sh

追記:[2013/01/05]

コメントで「上記の書き方だとほとんどの時間が新しいプロセスの起動に費やされている」というコメントをいただき、以下のように改善できる旨を教えていただきました。

function fib() {
    if [[ $1 -lt 2 ]]; then
        return $1
    else
        fib $(($1 - 2))
        local x=$?
        fib $(($1 - 1))
        return $(($x + $?))
    fi	
}

fib 38
echo $?

確かにオリジナルのコードからバッククオートによる演算がなくなっているので、高速に動作することが期待できます。果たして結果は・・・。

Boo

def fib(n as int) as int:
    if n < 2:
        return n
    return fib(n - 2) + fib(n - 1)

print fib(38)

はい、そうです。Boo は型がある Python です。Mono で動作し、3D ゲーム開発環境 Unity で利用可能です。

インタプリタはこちら。

$ booi fib.boo

コンパイルする場合はこちら。

$ booc fib.boo; ./fib.exe

Ubuntu でも拡張子は .exe なんですね。

C

#include <stdio.h>

int fib(int n) {
    if (n < 2) return n;
    return fib(n - 2) + fib(n - 1);
}

int main(int argc, char *argv[]) {
    printf("%d\n", fib(38));
    return 0;
}

gcc はこちら。

$ gcc fib.c; ./a.out

最適化オプションをつけた場合はこちら。

$ gcc -O2 fib.c; ./a.out

clang はこちら。

$ clang fib.c; ./a.out

C#

using System;

class Fib {
    public static int fib(int n) {
        if (n < 2) return n;
        return fib(n - 2) + fib(n - 1);
    }

    static void Main() {
        Console.WriteLine(fib(38));
    }
}

$ gmcs fib.cs; ./fib.exe

C++

#include <stdio.h>

int fib(int n) {
    if (n < 2) return n;
    return fib(n - 2) + fib(n - 1);
}

int main(int argc, char *argv[]) {
    printf("%d\n", fib(38));
    return 0;
}

最適化なしはこちら。

$ g++ fib.cpp; ./a.out

最適化ありはこちら。

$ g++ -O2 fib.cpp; ./a.out

Clojure

(defn fib [n]
  (if (< n 2)
     n
     (+ (fib (- n 2)) (fib (- n 1)))))

(println (fib 38))

$ clojure fib.clj

D

import std.stdio;

int fib(int n) {
    if (n < 2) return n;
    return fib(n - 2) + fib(n - 1);
}

void main() {
    writef("%d\n", fib(38));
}

$ gdc fib.d; ./a.out

追記:[2013/01/09]

DMD(Digital Mars の本家コンパイラと処理系)でも計測して欲しい、ということで以下のオプションで試してみました。

$ dmd -O -release -inline fib.d; ./fib

Erlang

-module(fib).
-export([fib/1, main/1]).

main([]) -> 
   Res = fib:fib(38),
   io:fwrite("~w~n", [Res]).

fib(0) -> 0; 
fib(1) -> 1; 
fib(N) when N > 0 -> fib(N - 2) + fib(N - 1). 

ちょっと実装のアルゴリズムが違うけど、妥協しました。

インタプリタはこちら。

$ escript fib.erl

コンパイルする場合はこちら。

$ erlc fib.erl; escript fib.beam

Forth

: fib ( n -- f )
    dup 2 u< if exit then
    1- dup recurse swap 1- recurse + ;
 
38 fib . cr
bye

初見でこれが読める人がいるのでしょうか。例えば最後から 2 番目の行は、「38 をスタックに積んで、fib を実行、結果を出力して、改行を出力」、という手続きです。

インタプリタはこちら。

$ gforth fib.fs

高速版インタプリタはこちら。

$ gforth-fast fib.fs

Fortran

program main
    implicit none
    interface 
        function fib(n)
            integer, intent(in) :: n 
            integer :: fib
        end function fib
    end interface

    print *, fib(38)
end program main

recursive function fib (n) result (fnum) 
    integer, intent(in) :: n
    integer :: fnum
    if (n < 2) then 
        fnum = n
    else
        fnum = fib(n - 2) + fib(n - 1)
    endif
end function fib

宣言がやたら多いという印象を受けます。古い言語なのでしょうがないですが。

$ gfortran fib.f90; ./a.out

追記:[2013/01/09]

コメントで以下のような書き方を教えてもらいました。

program test
    implicit none
    print *, fib(38)
    contains
    recursive integer function fib(i) result(ires)
        integer, intent(in) :: i
        if (i < 2) then
            ires = i
        else
            ires = fib(i - 2) + fib(i - 1)
        end if
    end function fib
end program test

わざわざ program と function をわけなくても良いということなんですね。

Go

package main

import "fmt"

func fib(n int) int {
    if (n < 2) { return n }
    return fib(n - 2) + fib(n - 1)
}

func main() {
    fmt.Println(fib(38))
}

if の後の return をブロックに入れなければならないのが残念。

直接実行はこちら。

$ go run fib.go

コンパイルして実行ならこちら。

$ go build fib.go; ./fib

Groovy

def fib(n) {
    if (n < 2) return n
    return fib(n - 2) + fib(n - 1)
}

print fib(38) + "\n"

シンタックスは今回の言語の中では一番好きかも。

$ groovy fib.groovy

追記:[2013/01/04]

コメントで引数に型を指定すると高速になると教えていただきました。

def fib(int n) {
    if (n < 2) return n
    return fib(n - 2) + fib(n - 1)
}

print fib(38) + "\n"

型指定なしと型指定ありの結果をあわせて集計してみます。Java 系の結果まとめ部分に反映されているので、そちらを参照ください。

Haskell

fib n 
 | n < 2 = n
 | otherwise = fib (n - 2) + fib (n - 1)

main = print $ fib 38

GHC はこちら。

$ ghc fib.hs; ./a.out

GHCi はこちら。


$ ghci fib.hs
GHCi, version 6.12.1: http://www.haskell.org/ghc/ :? for help
Loading package ghc-prim ... linking ... done.
Loading package integer-gmp ... linking ... done.
Loading package base ... linking ... done.
Ok, modules loaded: Main.
Prelude Main> main
39088169
Prelude Main> :quit
Leaving GHCi.

Hugs はこちら。


$ hugs fib.hs
__ __ __ __ ____ ___ _________________________________________

__ Hugs 98: Based on the Haskell 98 standard
___ __ __ __ Copyright (c) 1994-2005
--- ___ World Wide Web: http://haskell.org/hugs
Bugs: http://hackage.haskell.org/trac/hugs
Version: September 2006 _________________________________________

Haskell 98 mode: Restart with command line option -98 to enable extensions

Type :? for help
Main> :main
39088169

Main> :quit
[Leaving Hugs]

バッチ実行の方法がわかりませんでした。

Jhc はこちら。

$ jhc fib.hs; ./hs.out

追記:[2012/12/30]

今回の fib 38 は Int の範囲内であり、関数の型宣言を省略した場合は Integer が使用され、要するに型宣言を明示的に行ったほうが速いということ、ghc には -O2 という最適化オプションがあることをコメントで教えていただきました。

fib :: Int -> Int
fib n 
 | n < 2 = n
 | otherwise = fib (n - 2) + fib (n - 1)

main = print $ fib 38

$ ghc fib.hs; ./a.out

全体的に結果が変わってくると思うので、全部の処理系で計測しなおして、結果に反映してみます。

Io

fib := method(n,
  if(n < 2,
    n,
    fib(n - 2) + fib(n - 1)
))

fib(38) println

今回試した言語の中で、唯一はてなシンタックスハイライトに対応していません。また、apt-get でインストールできなかった数少ない処理系のひとつでもあります。マイナー of マイナー言語。ですが、超マイナー言語はもっともっとたくさんあるので、それらに比べればメジャーでしょう。僕も名前は知っていたし。

$ io fib.io

Java

public class fib {
    static int fib(int n) {
        if (n < 2) return n;
        return fib(n - 2) + fib(n - 1);
    }
	
    public static void main(String[] args) {
        System.out.println(fib(38));
    }
}

OpenJDK はこちら。

$ javac fib.java; java fib

gcj はこちら。

$ gcj --main=fib fib.java; ./a.out

JavaScript

function fib(n) {
    if (n < 2) return n;
    return fib(n - 2) + fib(n - 1);
}

print(fib(38));

XULRunner はこちら。

$ /usr/lib/xulrunner-1.9.2.28/run-mozilla.sh /usr/lib/xulrunner-1.9.2.28/xpcshell fib.js

node.js はこちら。

$ node fib.js

node.js の場合、print の代わりに console.log を使用します。

Rhino はこちら。

$ rhino fib.js

XULRunner と node.js の JavaScript エンジンは、それぞれ「なんとか」Monkey(多分 SpiderMonkeyTraceMonkey)と V8 です。

Lisp

(defun fib (n)
  (if (< n 2)
    n
    (+ (fib (- n 2)) (fib (- n 1)))))

(print (fib 38))

clisp はこちら。

$ clisp fib

sbcl はこちら。

$ sbcl --script fib.lisp

Lua

function fib(n)
    if n < 2 then return n end
    return fib(n - 2) + fib(n - 1)
end

print(fib(38))

if の後の return を then end で囲まなければならないのが残念。

Lua はこちら。

$ lua fib.lua

コンパイルするならこちら。

$ luac fib.lua; lua luac.out

LuaJIT はこちら

$ luajit fib.lua

OCaml

open Pervasives

let rec fib n =
    if n < 2
    then n
    else fib(n - 2) + fib(n - 1);;

print_int(fib 38);
print_string("\n");

インタプリタはこちら。

$ ocaml fib.ml

コンパイルするならこちら。

$ ocamlc fib.ml; ./a.out

最適化コンパイルするならこちら。

$ ocamlopt fib.ml; ./a.out

Objective-C

#import <stdio.h>

int fib(int n) {
    if (n < 2) return n;
    return fib(n - 2) + fib(n - 1);
}

int main(int argc, char *argv[]) {
    printf("%d\n", fib(38));
    return 0;
}

最適化なしならこちら。

$ gcc fib.m; ./a.out

最適化ありならこちら。

$ gcc -O2 fib.m; ./a.out

PHP

<?php
function fib($n) {
    if ($n < 2) return $n;
    return fib($n - 2) + fib($n - 1);
}

print fib(38);
print "\n";

php タグって、閉じてなくてもいいんだ・・・。

$ php fib.php

Pascal

program fib;

function fib(n:longint): longint;
begin
    if (n < 2) then
        fib := n
    else
        fib := fib(n - 2) + fib(n - 1);
end;

begin
    writeln(fib(38));
end.

最適化なしならこちら。

$ fpc fib.pas ./fib

最適化ありならこちら。

$ fpc -O2 fib.pas ./fib

Perl

sub fib($) {
    return $_[0] if ($_[0] < 2);
    return fib($_[0] - 2) + fib($_[0] - 1);
}

print fib(38), "\n";

$ perl fib.pl

Pike

int fib(int n) {
    if (n < 2) return n;
    return fib(n - 2) + fib(n - 1);
}
int main() {
    write(fib(38) + "\n");
    return 0;
}

ほとんど C です。いや、D に近いかな。

$ pike fib.pike

Prolog

fib(0, 0).
fib(1, 1).
fib(N, NF) :-
    A is N - 2, B is N - 1,
    fib(A, AF), fib(B, BF),
    NF is AF + BF.

goal :-
    fib(38, NF), 
    write([NF]), nl.

これも実装のアルゴリズムを妥協しました。

$ gplc fib.pro; ./fib; ... (snip)

Python

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

print(fib(38))

Fortran の流れをくむ言語の end をインデントで省略するというアイデアは、いろいろな言語を見て改めて秀逸だと思いました。

CPython はこちら。

$ python fib.py

Jython はこちら。

$ jython fib.py

PyPy はこちら。

$ pypy fib.py

R

fib <- function(n) {
    if (n < 2) return(n)
    return(fib(n - 2) + fib(n - 1))
}

print(fib(38))

$ R --vanilla < fib.R

Ruby

def fib(n)
    return n if (n < 2)
    return fib(n - 2) + fib(n - 1)
end

puts fib(38)

CRuby はこちら。

$ ruby fib.rb

JRuby 1.4 はこちら。

$ jruby fib.rb

JRuby 1.7.1 はこちら。

$ java -jar jruby-complete-1.7.1.jar fib.rb

JRuby は間違えてふたつの異なるバージョンで計測してしまったのですが、結果がかなり違ったので、そのまま計測結果に含めることにしました。

Scala

def fib(n: Int): Int = n match {
    case 0 | 1 => n
    case _ => fib(n - 2) + fib(n - 1)
}

println(fib(38))

構造化言語と関数型言語のハイブリット。試みとしては良いんじゃないでしょうか。

scala fib.scala

追記:[2012/12/31]

コメントで教えていただいた scalac を試してみました。

object fib {
    def fib(n: Int): Int = n match {
        case 0 | 1 => n
        case _ => fib(n - 2) + fib(n - 1)
    }

    def main(args: Array[String]) {
        println(fib(38))
    }
}

scalac するためには object か class 定義内に処理を記述しなければならず、いっきに Java くさくなってしまいました。スクリプトっぽく書けるのがいい感じなのに。

$ scalac fib.scala
$ scala fib

追記:[2013/01/04]

コメントで丁寧な追試をして頂いて、書き方に若干問題があるという事に気が付きました。

def fib(n: Int): Int = {
    if (n < 2) n
    else fib(n - 2) + fib(n - 1)
}

println(fib(38))

case ではなく if-else を使ったほうが高速です。詳細は Java 系のまとめを参照ください。

Scheme

(define (fib n)
  (if (< n 2)
    n
    (+ (fib (- n 2)) (fib (- n 1)))))

(write (fib 38))
(newline)

Gauche はこちら。

$ gosh fib.scm

MzScheme はこちら。

$ mzscheme -f fib.scm

Guile はこちら。

$ guile fib.scm

Gambit インタプリタはこちら。

$ gsi fib.scm

Gambit コンパイラ(C トランスレータ)はこちら。

$ gsc -c fib.scm; gsc -link fib; gcc fib_.c fib.c -lgambc -lm -ldl -lutil; ./a.out

Gambit コンパイラ(C トランスレータ)を最適化したものはこちら。

$ gsc -c fib.scm; gsc -link fib; gcc -O2 fib_.c fib.c -lgambc -lm -ldl -lutil; ./a.out

Ikarus はこちら。

$ ikarus fib.scm exit.scm

exit.scm には以下が書かれています。

(exit)

MIT-Scheme はこちら。

$ mit-scheme --load fib.scm --eval “(quit)”

MIT-Scheme のもうひとつのインタプリタはこちら。

$ mit-scheme-native --load fib.scm --eval “(quit)”

Scheme48 はこちら。


$ scheme48
Welcome to Scheme 48 1.8 (made by vernadsky on Fri Jul 24 18:05:33 UTC 2009)
Copyright (c) 1993-2008 by Richard Kelsey and Jonathan Rees.
Please report bugs to scheme-48-bugs@s48.org.
Get more information at http://www.s48.org/.
Type ,? (comma question-mark) for help.
> ,load fib.scm
39088169
> ,exit

Scheme48 のコンパイラはこちら。


$ scheme48
Welcome to Scheme 48 1.8 (made by vernadsky on Fri Jul 24 18:05:33 UTC 2009)
Copyright (c) 1993-2008 by Richard Kelsey and Jonathan Rees.
Please report bugs to scheme-48-bugs@s48.org.
Get more information at http://www.s48.org/.
Type ,? (comma question-mark) for help.
> (define fib (let loop )((n 38))( (if (< n 2) n (+ (loop (- n 2)) (loop (- n 1))))))
; no values returned
> ,build fib fib.image
Writing fib.image
> ,exit
$ scheme48 -i fib.image

Scheme48 は多分バッチ実行はできないんだと思います。

SCM はこちら。

$ scm -lfib.scm "-e(exit)"

TinyScheme はこちら。

$ tinyscheme fib.scm

Ypsilon はこちら。

$ ypsilon fib.scm

elk はこちら。

$ elk -l fib.scm

SigScheme はこちら。

$ sscm fib.scm

Scheme には思い入れがあるので、apt-get で入れられるものは全部入れてみました。これ以外に Scheme2c というおそらく C トランスレータもあったのですが、使い方がわからなくて計測を断念。

スクリプトを渡してそのまま終了せず、REPL に残る処理系が結構あって、こういう動作は使いにくいと感じてしまうんだけど、どうなんでしょう。(exit) や (quit) は処理系依存なのでスクリプトには書けない(書きたくない)。

Smalltalk

Integer extend [
    fib [
        self < 2
        ifTrue: [ ^self ]
        ifFalse: [ ^(self - 2) fib + (self - 1) fib ].
    ]
]

38 fib printNl.

今回試した言語の中で、よくわからない言語のひとつです。最後の行は多分、「38 を fib にメッセージパッシングして、その結果を printNl にメッセージパッシング」という感じなのでしょうか。でも + オペレータの部分は普通に中置記法だしなぁ。

$ gst fib.st

Tcl

proc fib {n} {
    if {$n < 2} { return $n }
    set a [expr $n - 2]
    set b [expr $n - 1]
    set x [fib $a]
    set y [fib $b]
    return [expr $x + $y]
}

set z [fib 38]
puts $z

処理結果をいちいち変数に入れなきゃならないので、ちょっと面倒ですね。僕がわかってないだけかもしれません。

$ tclsh fib.tcl

ベンチマーク結果

言語(処理系) 時間
Scheme48 (build) 0.004
Haskell (jhc) 0.540
Java (OpenJDK) 0.732
OCaml (ocamlopt) 0.98
Scala (if-else) 1.024
C (gcc -O2) 1.18
C++ (g++ -O2) 1.18
Objective-C (gobjc -O2) 1.18
D (dmd -O inline) 1.316
Ada (-O2) 1.384
Go (build) 1.388
Pascal (fpc -O2) 1.46
C (gcc) 1.492
C++ (g++) 1.508
Objective-C (gobjc) 1.516
Haskell (ghc -O2) 1.576
D (gdc) 1.624
C# 1.648
Ada 1.648
Scala (case scalac) 1.748
Pascal (fpc) 1.848
C (clang) 1.872
Scala (case) 1.896
Fortran (gfortran) 1.92
Go (run) 1.956
Haskell (ghci) 1.992
Scheme (ikarus) 2.068
JavaScript (node.js) 2.62
Boo (compile) 2.674
Java (gcj) 2.88
Lisp (sbcl) 3.292
Boo (interpret) 3.56
Scheme (Gambit: gcs -O2) 4.524
Scheme (Gambit: gcs) 7.132
Forth (gforth-fast) 7.388
OCaml (ocaml) 7.528
OCaml (ocamlc) 7.528
Forth (gforth) 8.385
Lua (luajit) 8.9353
Erlang (erlc) 9.969
Erlang (escript) 9.977
Scheme (ypsilon) 14.493
Python (pypy) 18.369
Smalltalk (gst) 18.905
Ruby (JRuby 1.7.1) 22.773
Scheme (gosh) 24.75
Pike 25.186
Lua (luac) 26.866
Lua (lua) 26.91
Groovy 40.751
Clojure 41.691
JavaScript (XULRunner) 41.743
Ruby (JRuby 1.4.0) 41.959
JavaScript (Rhino) 43.967
Scheme (scheme48) 53.215
Python (CPython) 53.651
Scheme (scm) 56.076
Scheme (guile) 71.404
PHP 85.417
Python (Jython) 86.637
Scheme (Gambit: gsi) 86.665
Perl 109.103
AWK 114.235
Scheme (sscm) 117.707
Lisp (GNU CLISP) 211.802
Ruby (CRuby) 213.185
Scheme (elk) 214.245
R 669.911
Scheme (tinyscheme) 671.202
Bash (without back quote) 10036.583
Tcl 1039.129
Haskell (hugs) 1104.557
Io 1358.093
Bash (with back quote) -
Prolog -

Benchmark

1 秒で終わる処理系もあれば、10 分、20 分かかる処理系もあり、チャートとしてはグダグダですが、ありのまま載せることにします。チャートは Google Image Chart というサービスを使用して作成しました。これ以上縦に大きくできないので、見にくくてすみません。

BashProlog は結果がありません。Bash は 4 時間待っても終わらず計測不可能としました(追記:[2013/01/05] Bash を効率化したところ、約 2 時間 47 分で完了するようになりました)。Prolog はメモリとスタックが足りなくなって途中で終了します。環境変数を指定することでメモリやスタックを指定できるのですが、利用可能な 600MB をどのような割合で分配しても(それほどは試していませんが)、途中でどちらかが足りなくなるので、これも計測不可能としました。

さて、ぶっちぎりで速いのが Scheme48 のコンパイルバージョン。なんと 0.004sec。ただこれはタネがあって、コンパイル時に関数を評価してフィボナッチ数を算出しているためです。したがって、コンパイルインタプリタで実行するのと同程度の時間がかかります。ただ、コンパイル時に評価できる関数は評価してしまうというアプローチは関数型言語の特性をうまく生かした良い方法だと思います。

Scheme48 を除いたら、Java がトップでした(追記:[2012/12/30] Haskell の型宣言を指定したら、Jhc に抜かれてしまいました)。JIT が効いているのは当然として、Java VM の動作や実装を熟知している身としては、よくこんな短時間でブートストラップクラスを初期化できるものだと感心してしまいます。Oracle の最新の Java VM を使えばもっと速くなるんじゃないでしょうか。いやはや。

続いて OCaml の最適化ビルド。最適化した場合としない場合のギャップ萌え(追記:[2012/12/30] ocamlc と ocamlopt は、名前からして最適化の有無だと思ったのですが、バイトコードかネイティブかの違いであるとコメントで教えていただきました)。

後続に C 系の最適化ビルドが続くのは順当として、HaskellGHC ではないコンパイラ Jhc とか(追記:[2012/12/30] Haskell を計測しなおして、Jhc はトップに君臨しました)、Ada の最適化ビルド、Go の最適化ビルド、Pascal の最適化ビルドなどは、かなり健闘していると思います。Ada って名前しか聞いたことなかったんですが、実力はあるのかも。でもなんで拡張子が .adb なの?

clang が意外と振るわなかった印象。なんか gcc から clang にコンパイラと処理系を置き換えたら、それだけでハッピーになれる、みたいに思っていたので。

今回計測したなかで一番びっくりしたのが Ikarus という Scheme 処理系の速さ。動的言語では僕の予測を裏切って JavaScript の V8 を押さえ最速でした。

カテゴリに分けて見てみます。

Java

言語(処理系) 時間
Java (OpenJDK) 0.732
Scala (if-else) 1.024
Scala (case scalac) 1.748
Scala (case) 1.896
Java (gcj) 2.88
Ruby (JRuby 1.7.1) 22.773
Groovy (型指定なし) 40.751
Clojure 41.691
Ruby (JRuby 1.4.0) 41.959
JavaScript (Rhino) 43.967
Groovy (型指定あり) 48.003
Python (Jython) 86.637

Java が速いので、バイトコードコンパイルする Scala も速いです。もし ScalaJava より速かったら、「おおっ、Java の文法的制約を超越してバイトコードのポテンシャルを 100% 引き出しているっ」みたいな感動があったのですが、なかなかそこまでは行かないようです。

追記:[2012/12/31]

scalac を計測してみました。若干速くはなったものの、コードは小さいですし、処理は重いので、見違えて効果があったという結果にはなりませんでした。事前コンパイルするために、スクリプトっぽい書き方ができなくなるのが、しょうがないですが痛いですね。

追記:[2013/01/04]

コメントで教えていただいた Groovy のメソッド引数の型指定は、かえって遅くなるという結果になりました(型指定なしと型指定ありを交互に繰り返し計測したので、たまたまということではなさそうです)。使っている処理系が古い(私の環境は 1.6.4、コメントを頂いた方の環境は 2.0.6)のが原因でしょうか。

追記:[2013/01/04]

Scala は case で書くとバイトコード的には tableswitch にコンパイルされるようです。このせいで Java が 0.7 秒のところを 1.7 秒かかってしまっていました。case を if-else に直したところ、1.0 秒まで短縮しました。scalac をすると更に 0.1 秒短縮し、0.952 秒でした。Java との約 200ms の違いは、Scala のライブラリロードで 150ms、invokevirtual の呼び出しのオーバーヘッドで残りの 50ms ということだと思います。実際の運用ではライブラリロードの時間は無視でき、126491971 回のメソッド呼び出しで 50ms のオーバーヘッドしかないということは、Java とほぼ同じと考えてよいと思います。

gcj がそれなりに速かったのが意外と言えば意外。かつては AOT の方が圧倒的に高速だった時代があったのですが、JIT が優秀になりすぎて、逆転して久しいです。

Groovy から Rhino までが接戦なんですが、Jython はダブルスコアをつけられています。

Haskell

言語(処理系) 時間
Haskell (jhc)(Int) 0.540
Haskell (ghc -O2)(Int) 1.576
Haskell (jhc)(Integer) 1.268
Haskell (ghci)(Int) 1.992
Haskell (ghc)(Integer) 15.801
Haskell (ghci)(Integer) 17.225
Haskell (hugs)(Int) 1025.9.557
Haskell (hugs)(Integer) 1104.557
追記:[2012/12/30] (Int) が型宣言あり、(Integer) が型宣言なしの結果です。

Jhc という処理系の成績がとても良い。

今回ベンチマークを行うにあたり「Haskell の処理系、なんかないかな〜」とググって見つけたものなのですが、まさか GHC よりも高速とは。しかも生成されるバイナリのサイズも極小で、GHC が 546KB に対し、Jhc は 20KB しかありません。Haskell で実装されていて、処理系のビルドに GHC が必要です。

逆に GHC は 15 秒と振るわなかった印象です(追記:[2012/12/30] すみません、GHC 見くびっていました。型宣言を行った場合、C 系に匹敵するパフォーマンスが出ることが判明しました。なお、型宣言を行なって最適化なしでも、型宣言を行わずに最適化ありでも、型宣言を行なって最適化ありでも、ほとんど同じ結果になりました。ghci も型宣言を行ったことで圧倒的に高速になりました)。GC がかなり動いてるのかな、という気がします(追記:[2012/12/30] Integer が使われるか Int が使われるかの違いのようでした)。

Hugs はメンテナンスされていない処理系(だったと思う)ので、仕方がないかな。

JavaScript

言語(処理系) 時間
JavaScript (node.js) 2.62
JavaScript (XULRunner) 41.743
JavaScript (Rhino) 43.967

node.js の V8 は流石の一言。アプリにスクリプト言語を組み込むなら、V8 を組み込みたい、と思わされてしまう。

Python

言語(処理系) 時間
Boo (compile) 2.674
Boo (interpret) 3.56
Python (pypy) 18.369
Python (CPython) 53.651
Python (Jython) 86.637

PyPy が振るわなかったという印象を受けた。そして Boo が速かった。Jython はもうちょっと頑張れ。

Ruby

言語(処理系) 時間
Ruby (JRuby 1.7.1) 22.773
Ruby (JRuby 1.4.0) 41.959
Ruby (CRuby) 213.185

JRuby のバージョンの違いで、2 倍速くなっているのが印象的。使用している環境が Ubuntu 10.04 LTS なので、処理系もいささか古く、最新の環境で試みたらまた違う結果になっていたのかも知れない。各処理系のバージョンは本エントリの最後にまとめます。

CRuby はやっぱり遅かった(いやいや、今回使った 1.8.7 よりも 1.9 系で速くなっているはず)。

Lua

言語(処理系) 時間
Lua (luajit) 8.9353
Lua (luac) 26.866
Lua (lua) 26.91

今回ベンチマークを計測してみようと思ったきっかけは、実は Lua 処理系に興味を持ったからでした。

LuaJIT がすこぶる速い、という噂を聞いて、「一体どれほど?」と思って試してみた、というわけです。V8 とまではいかないけれど、確かに速いということがわかって満足。VM で動作する lua もそれなりに速いのがわかったのも収穫です。

luac と lua がほとんど同じなのは、luac は単に Lua VM の内部構造をファイルにダンプするだけなので、パースの時間程度しか違わないためです。

OCaml

言語(処理系) 時間
OCaml (ocamlopt) 0.98
OCaml (ocamlc) 7.528

もう一度言いますが、最適化でこんなに速くなっていいんでしょうか。すげーな。

追記:[2012/12/30]

繰り返しですが、ocamlc はバイトコード、ocamlopt はネイティブコードです。

$ ocamlc fib.ml
$ file a.out
a.out: a /usr/bin/ocamlrun script text executable

$ ocamlopt fib.ml
$ file a.out
a.out: ELF 32-bit LSB executable, Intel 80386, version 1 (SYSV), dynamically linked (uses shared libs), for GNU/Linux 2.6.15, not stripped

ocamlopt で生成されるネイティブコードは gcc -O2 よりも速いので、コンパイラがかなり優秀なんだろうと思われます。

Lisp

言語(処理系) 時間
Scheme (ikarus) 2.068
Lisp (sbcl) 3.292
Scheme (Gambit: gcs -O2) 4.524
Scheme (Gambit: gcs) 7.132
Scheme (ypsilon) 14.493
Scheme (gosh) 24.75
Clojure 41.691
Scheme (scheme48) 53.215
Scheme (scm) 56.076
Scheme (guile) 71.404
Scheme (Gambit: gsi) 86.665
Scheme (sscm) 117.707
Lisp (GNU CLISP) 211.802
Scheme (elk) 214.245
Scheme (tinyscheme) 671.202

Ikarus が速すぎです。Wikipedia によると、マシン語コンパイルされるという事らしく、要するに V8 と同じということなら(それだけではないとは思いますが)納得です。Gambit が生成する C を最適化したものよりも圧倒的に高速なので、かなり優れたネイティブコードを生成するんだろうなぁ。GPL3 なので、時間があるときにコードを見てみたい。

インタプリタでは Ypsilon、Gauche が善戦しています。もうひとつの代表的な国産実装 Mosh も試したかったけど、ソースからビルドしなきゃいけないので・・・、省略しました。

やっぱり Scheme は処理系が多い。

追記:[2013/01/04]

コメントで Lisp の処理系である SBCL (Steel Bank Common Lisp) を教えていただきました。Common Lisp は仕様が大きいため、なかなか Scheme のように処理系が実装されず、商用じゃないとダメなのかな、と思っていたのですが、これは速いです。

D 系

言語(処理系) 時間
D (dmd -O inline) 1.316
D (gdc) 1.624

gdc が思いの外速かった、dmd は apt-get でインストールできない、という理由で dmd を試していませんでしたが、コメントで計測のリクエストを受けたので試してみました。

ちなみに僕は、8 年程前に最も期待を寄せていた言語は D でした。結構時間を投入して勉強していました。こんないい言語がなんで流行らないんだろう、とか、C/C++ が D で置き換わればいいのに、とか本気で思っていました。今なお流行っているとは言いがたい状況である理由はよくわかりませんが、処理系にバグが多い(多かった、僕も何個も遭遇した)、そんな状況にも関わらず互換性のないライブラリを再設計した、というようなところでユーザがついて来なかったというのが僕の想像です。

言語仕様はかなり好みで、おそらく当時よりももっと良くなっているんだとは思いますが、現在取り組んでいるアプリはなぜか C++ で書き始めてしまいました・・・。始めたばかりだから D でもいいんだよなぁ・・・。

処理系のバージョンとインストール方法

言語 処理系バージョン インストール方法
Ada gnat-4.4 sudo apt-get install gnat
AWK GNU Awk 3.1.6 sudo apt-get install awk
Bash GNU bash, version 4.1.5(1) sudo apt-get install bash
Boo boo 0.9.2 sudo apt-get install boo
C gcc (Ubuntu 4.4.3-4ubuntu5.1) 4.4.3 sudo apt-get install build-essential
C clang version 1.1 sudo apt-get install clang
C# Mono C# compiler version 2.4.4.0 sudo apt-get install mono-gmcs
C++ g++ (Ubuntu 4.4.3-4ubuntu5.1) 4.4.3 sudo apt-get install g++
Clojure Clojure 1.0.0 sudo apt-get install clojure
D gdc (Ubuntu 1:1.046-4.3.4-3ubuntu1) 4.3.4 sudo apt-get install gdc
D dmd (2.061) http://www.digitalmars.com/d/download.html
Erlang V5.7.4 sudo apt-get install erlang
Forth Gforth 0.7.0 sudo apt-get install gforth
Fortran GNU Fortran (Ubuntu 4.4.3-4ubuntu5.1) 4.4.3 sudo apt-get install gfortran
Go go version go1.0.2 sudo apt-get install golang
Groovy Groovy Version: 1.6.4 JVM: 1.6.0_26 sudo apt-get install groovy
Haskell Jhc Haskell Compiler 0.8.0 http://repetae.net/computer/jhc/
Haskell GHC 6.12.1 sudo apt-get install ghc6
Haskell Hugs Version September 2006 sudo apt-get install hugs
Io Io 20110905 http://github.com/stevedekorte/io
Java OpenJDK Runtime Environment 1.6.0_24 sudo apt-get install java-sdk
Java gcj 4.4 sudo apt-get install gcj-jdk
JavaScript node.js v0.8.16 http://nodejs.org
JavaScript XULRunner 1.9.2.28 sudo apt-get install xulrunner
JavaScript Rhino 1.7R2-3 sudo apt-get install rhino
Lisp GNU CLISP 2.44.1 sudo apt-get install clisp
Lisp SBCL 1.0.29.11.debian sudo apt-get install sbcl
Lua LuaJIT 2.0.0beta2 sudo apt-get install luajit
Lua Lua 5.1.4 sudo apt-get install lua
Objective-C The GNU Objective-C compiler 4.4.3 sudo apt-get install gobjc
OCaml ocaml 3.11.2-1 sudo apt-get install ocaml
Pascal Free Pascal Compiler 2.4.0 sudo apt-get install fpc
Perl Perl v5.10.1 sudo apt-get install perl
PHP PHP 5.3.2-1ubuntu4.18 sudo apt-get install php
Pike Pike v7.6 sudo apt-get install pike7.6-core
Prolog GNU Prolog 1.3.0 sudo apt-get install gprolog
Python pypy 1.9.0 http://pypy.org
Python Python v2.6.5 sudo apt-get install python
Python Jython 2.2.1 on java1.6.0_24 sudo apt-get install jython
R R version 2.10.1 (2009-12-14) sudo apt-get install r-base
Ruby jruby 1.4.0 sudo apt-get install jruby
Ruby ruby 1.8.7 sudo apt-get install ruby
Scala Scala code runner version 2.7.7final sudo apt-get install scala
Scheme Ikarus Scheme version 0.0.3 sudo apt-get install ikarus
Scheme Gambit 4.2.8-1.1 sudo apt-get install gambc
Scheme Ypsilon 0.9.6-update3 sudo apt-get install ypsilon
Scheme Gauche scheme interpreter, version 0.8.13 sudo apt-get install gauche
Scheme Scheme48 1.8 sudo apt-get install scheme48
Scheme scm 5e5 sudo apt-get install scm
Scheme guile-1.8 sudo apt-get install guile-1.8
Scheme Gambit 4.2.8-1.1 sudo apt-get install gambit
Scheme sigscheme 0.8.3-4 sudo apt-get install sigscheme
Scheme elk 3.99.7-1 sudo apt-get install elk
Scheme tinyscheme 1.37 sudo apt-get install tinyscheme
Smalltalk GNU Smalltalk version 3.0.3 sudo apt-get install gnu-smalltalk
Tcl Tcl 8.5 sudo apt-get install tcl

JRuby の例にあるように、古いバージョンから新しいバージョンにアップデートすることによって、劇的に処理速度が向上している可能性があるので、今さらですが、今回の結果を真に受けずに、参考程度にとどめておいてしてください。

追記:[2013/01/04]

有用なコメントをいくつもいただいています。時間があればコメント欄も参照ください。