Hatena::ブログ(Diary)

satosystemsの日記 このページをアンテナに追加 RSSフィード

2012-12-28

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

AWK、Ada、Bash、Boo、C、C#、C++、Clojure、D、Erlang、Forth、Fortran、Go、Groovy、Haskell、Io、Java、JavaScript、Lisp、Lua、OCaml、Objective-C、PHP、Pascal、Perl、Pike、Prolog、Python、R、Ruby、Scala、Scheme、Smalltalk、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(多分 SpiderMonkey か TraceMonkey)と 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
Ada1.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
Pike25.186
Lua (luac)26.866
Lua (lua)26.91
Groovy40.751
Clojure41.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
PHP85.417
Python (Jython)86.637
Scheme (Gambit: gsi)86.665
Perl109.103
AWK114.235
Scheme (sscm)117.707
Lisp (GNU CLISP)211.802
Ruby (CRuby)213.185
Scheme (elk)214.245
R669.911
Scheme (tinyscheme)671.202
Bash (without back quote)10036.583
Tcl1039.129
Haskell (hugs)1104.557
Io1358.093
Bash (with back quote)-
Prolog-

Benchmark

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

Bash と Prolog は結果がありません。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 系の最適化ビルドが続くのは順当として、Haskell の GHC ではないコンパイラ 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
Clojure41.691
Ruby (JRuby 1.4.0)41.959
JavaScript (Rhino)43.967
Groovy (型指定あり)48.003
Python (Jython)86.637

Java が速いので、バイトコードにコンパイルする Scala も速いです。もし Scala が Java より速かったら、「おおっ、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
Clojure41.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 でもいいんだよなぁ・・・。

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

言語処理系バージョンインストール方法
Adagnat-4.4sudo apt-get install gnat
AWKGNU Awk 3.1.6sudo apt-get install awk
BashGNU bash, version 4.1.5(1)sudo apt-get install bash
Booboo 0.9.2sudo apt-get install boo
Cgcc (Ubuntu 4.4.3-4ubuntu5.1) 4.4.3sudo apt-get install build-essential
Cclang version 1.1sudo apt-get install clang
C#Mono C# compiler version 2.4.4.0sudo apt-get install mono-gmcs
C++g++ (Ubuntu 4.4.3-4ubuntu5.1) 4.4.3sudo apt-get install g++
ClojureClojure 1.0.0sudo apt-get install clojure
Dgdc (Ubuntu 1:1.046-4.3.4-3ubuntu1) 4.3.4sudo apt-get install gdc
Ddmd (2.061)http://www.digitalmars.com/d/download.html
ErlangV5.7.4sudo apt-get install erlang
ForthGforth 0.7.0sudo apt-get install gforth
FortranGNU Fortran (Ubuntu 4.4.3-4ubuntu5.1) 4.4.3sudo apt-get install gfortran
Gogo version go1.0.2sudo apt-get install golang
GroovyGroovy Version: 1.6.4 JVM: 1.6.0_26sudo apt-get install groovy
HaskellJhc Haskell Compiler 0.8.0http://repetae.net/computer/jhc/
HaskellGHC 6.12.1sudo apt-get install ghc6
HaskellHugs Version September 2006sudo apt-get install hugs
IoIo 20110905http://github.com/stevedekorte/io
JavaOpenJDK Runtime Environment 1.6.0_24sudo apt-get install java-sdk
Javagcj 4.4sudo apt-get install gcj-jdk
JavaScriptnode.js v0.8.16http://nodejs.org
JavaScriptXULRunner 1.9.2.28sudo apt-get install xulrunner
JavaScriptRhino 1.7R2-3sudo apt-get install rhino
LispGNU CLISP 2.44.1sudo apt-get install clisp
LispSBCL 1.0.29.11.debiansudo apt-get install sbcl
LuaLuaJIT 2.0.0beta2sudo apt-get install luajit
LuaLua 5.1.4sudo apt-get install lua
Objective-CThe GNU Objective-C compiler 4.4.3sudo apt-get install gobjc
OCamlocaml 3.11.2-1sudo apt-get install ocaml
PascalFree Pascal Compiler 2.4.0sudo apt-get install fpc
PerlPerl v5.10.1sudo apt-get install perl
PHPPHP 5.3.2-1ubuntu4.18sudo apt-get install php
PikePike v7.6sudo apt-get install pike7.6-core
PrologGNU Prolog 1.3.0sudo apt-get install gprolog
Pythonpypy 1.9.0http://pypy.org
PythonPython v2.6.5sudo apt-get install python
PythonJython 2.2.1 on java1.6.0_24sudo apt-get install jython
RR version 2.10.1 (2009-12-14)sudo apt-get install r-base
Rubyjruby 1.4.0sudo apt-get install jruby
Rubyruby 1.8.7sudo apt-get install ruby
ScalaScala code runner version 2.7.7finalsudo apt-get install scala
SchemeIkarus Scheme version 0.0.3sudo apt-get install ikarus
SchemeGambit 4.2.8-1.1sudo apt-get install gambc
SchemeYpsilon 0.9.6-update3sudo apt-get install ypsilon
SchemeGauche scheme interpreter, version 0.8.13sudo apt-get install gauche
SchemeScheme48 1.8sudo apt-get install scheme48
Schemescm 5e5sudo apt-get install scm
Schemeguile-1.8sudo apt-get install guile-1.8
SchemeGambit 4.2.8-1.1sudo apt-get install gambit
Schemesigscheme 0.8.3-4sudo apt-get install sigscheme
Schemeelk 3.99.7-1sudo apt-get install elk
Schemetinyscheme 1.37sudo apt-get install tinyscheme
SmalltalkGNU Smalltalk version 3.0.3sudo apt-get install gnu-smalltalk
TclTcl 8.5sudo apt-get install tcl

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

追記:[2013/01/04]

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

tnodatnoda 2012/12/28 15:01 FYI: https://github.com/shenfeng/fibonacci-game

nobsunnobsun 2012/12/28 21:04 ghcの最適化オプションは -O2 くらいを指定すればよさそう.それと38番目のフィボナッチ数はIntの範囲なので, fib :: Int -> Int という型シグネチャをつければ速くなります.Haskellでは整数はシグネチャーがないときはInteger任意倍長整数になるのでかなり遅いです.

cocoatomococoatomo 2012/12/29 21:36 Lisp の節と Lua の節がくっついてしまっているようです.

AlexAndRiteAlexAndRite 2012/12/29 23:27 ocamlcとocamloptの違いは最適化じゃなくて
バイトコードかネイティブかの違い。
ocamlcはバイトコードなので数段遅いのは当然かな。

satosystemssatosystems 2012/12/30 06:36 > tnoda
github に置くというのはいいアイディアだと思いました。時間ができた時に僕も自分の github に置いてみようと思います。

> nobsan
計測しなおしてみました。Haskell 全体でパフォーマンスが向上しました。

> cocoatomo
報告ありがとうございます。修正しました。

> AlexAndRite
確かにそのとおりでした。ご教示ありがとうございました。

nanashi-sannanashi-san 2012/12/30 16:30 これってコンパイル時間も込みで計測しているのですか?
そうじゃないなら、Scalaはscalacでコンパイルしてから計った方が良いですよ。

MATSUZAKIMATSUZAKI 2012/12/30 18:38 scalac してもクラスメソッドで invokevirtual されるので Java より若干遅いですね
もう少し大きいフィボナッチ数を ServerVM で実行すると大体 Java と同じになりますが

satosystemssatosystems 2012/12/31 00:59 > nanashi-san
> MATSUZAKI

コメントありがとうございます。scalac で計測してみました。fsc は生成されるクラスファイル scalac と全く同じなので省略しました。

kmizushimakmizushima 2012/12/31 04:05 はじめまして。Scalaの結果が自分の知る限りのscalacによるコンパイル後の
バイトコードから推測される性能と一致しないので、ちょっと追試してみました
(以下、やや長文になります。すいません)。

環境は
OS: Ubuntu 12.04 LTS
CPU: AMD A8-3870 3.0GHz
SSD: Intel SSD 520 Series(Cherryville) 180GB
JVM(Oracle JVM):
java version "1.7.0_10"
Java(TM) SE Runtime Environment (build 1.7.0_10-b18)
Java HotSpot(TM) 64-Bit Server VM (build 23.6-b04, mixed mode)
Scala: Scala 2.9.1.final
です。

結果は

Java
$ time java Fib1
java Fib1 0.36s user 0.03s system 103% cpu 0.375 total
$ time scala Fib2 # if(n < 2) n else fib(n - 1) + fib(n - 2) にしたバージョン
scala Fib2 0.63s user 0.02s system 104% cpu 0.626 total
$ time scala Fib3 # このエントリとほぼ同じコード
scala Fib3 0.69s user 0.05s system 104% cpu 0.710 total
$ time scala Fib4.scala # scalac 使わない版
scala Fib4.scala 0.71s user 0.05s system 65% cpu 1.148 total

さて、Scalaの方が一見2倍程度遅いように見えます。ただ、生成されたバイトコードをみる限り、足引っ張りそうなのはinvokevirtualくらいで、しかも、これだけ同じメソッド
呼び出しが多発すれば脱仮想化が働くと考えられるので、差がついた部分は
scala-library.jar(Scala標準ライブラリのjarファイル)のロード時間部分ではないかと
思います。

裏付けをとるために、n=38ではなくn=40にしてみたところ、ほぼ予想どおりの
結果が出ました。

time java Fib1
java Fib1 0.81s user 0.04s system 101% cpu 0.839 total

$ time scala Fib2
scala Fib2 1.06s user 0.03s system 102% cpu 1.067 total

$ time scala Fib3
scala Fib3 1.12s user 0.05s system 101% cpu 1.146 total

$ time scala Fib4.scala
scala Fib4.scala 1.17s user 0.04s system 81% cpu 1.491 total

ポイントは、Fib1(Java版)とFib2(Scala版)でn = 38 から n = 40に上げた
とき、user timeの「差」はほぼそのまま(0.25sec)で変わっていない点です。仮に
scalacがjavacより数倍程度遅くなるバイトコードを吐いていたとしたらこのような
結果にはならないので、scala-library.jarを最初にロードする時間で差が付いた
だけかと思います。Java環境がOpenJDKかOracle JDKかという違いはあります
が、OpenJDK自体がSun時代のJDKがオープンソース化されたもので、その時代、既に
Java 6になっていましたから、脱仮想化のような最適化機構はOpenJDKにも入って
います。おそらくsatosystemsさんの環境でもn = 40くらいにして計測して
みると同じような現象が観測できるかと思います。

このように、1回だけ実行で単位がmsの場合、処理系の実行速度ではなく、初期
ライブラリのロードで差が付くことはJVMのような環境では珍しくないので、処理系
が吐くコードの質の問題と混同しないように注意が必要かなと思いました。

実験に使ったJavaコードおよびScalaコードを以下に示しておきます。

$ cat Fib1.java
public class Fib1 {
public static int fib(int n) {
if (n < 2) return n;
return fib(n - 1) + fib(n - 2);
}

public static void main(String[] args) {
fib(38);
}
}

$ cat Fib2.scala
object Fib2 {
def fib(n: Int): Int = {
if (n < 2) n
else fib(n - 1) + fib(n - 2)
}
def main (args: Array[String]) {
fib(38)
}
}

$ cat Fib3.scala
object Fib3 {
def fib(n: Int): Int = n match {
case 0|1 => 1
case _ => fib(n - 1) + fib(n - 2)
}
def main(args: Array[String]) {
fib(38)
}
}

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

fib(38)

mike_neckmike_neck 2012/12/31 05:30 Groovyについてですが…

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

print fib(38) + "\n"

となっているメソッドfibの引数の型を指定してあげて下さい。

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

print fib(38) + "\n"

半端なく速くなります。

なお、僕の環境
Mac (2011) : OS10.8.2/1.8GHz core-i7/4GB 1333MHz DDR3
Groovy : version 2.0.6
Java : 1.7.0.7
においては、

OLD版
groovycなし
$ time groovy fb.groovy
Picked up _JAVA_OPTIONS: -Dfile.encoding=UTF-8
39088169

real 0m13.069s
user 0m13.956s
sys 0m0.399s

groovycあり
$ time java -classpath $GROOVY_HOME/embeddable/groovy-all-2.0.6.jar: fb
Picked up _JAVA_OPTIONS: -Dfile.encoding=UTF-8
39088169

real 0m12.384s
user 0m12.830s
sys 0m0.364s

NEW版
groovycなし
$ time groovy fb.groovy
Picked up _JAVA_OPTIONS: -Dfile.encoding=UTF-8
39088169

real 0m5.769s
user 0m6.463s
sys 0m0.206s

groovycあり
$ time java -classpath $GROOVY_HOME/embeddable/groovy-all-2.0.6.jar: fb
Picked up _JAVA_OPTIONS: -Dfile.encoding=UTF-8
39088169

real 0m4.707s
user 0m4.974s
sys 0m0.132s

と大体38%ほどまでに時間が短縮されます。

nanasi-sannanasi-san 2013/01/03 22:38 clojure1.2以降なら40秒はかからずに5秒程度になるとおもいますが、Ubuntu10.04用の公式パッケージはないようです。
DLしてきて実行するとしたら、
wget 'http://search.maven.org/remotecontent?filepath=org/clojure/clojure/1.4.0/clojure-1.4.0.jar'
java -cp clojure-1.4.0.jar clojure.main fib.clj
という感じでしょうか。

nanasi-sannanasi-san 2013/01/03 22:49 ついでに、下記のようにするとチョビっと速くなります。
intをlongにかえるともう少しなります。
(defn fib [n]
(let [n (int n)]
(if (< n 2)
n
(+ (fib (- n 2)) (fib (- n 1))))))
(println (fib 38))

また、下記のようにclojureのtime関数を使うと関数の実行は2、3秒ぐらいであって、
お使いのPC環境で初期化に2秒ぐらいかかってるのが分かると思います。
(time (println (fib 38)))

nanasi-sannanasi-san 2013/01/03 23:45 CL系ではclispが遅いことで有名ですので、実際によく使われているsbclの結果も入れてもらえるとバランスがいいと思います。
ubuntu 10.4にもパッケージがあるようです。
http://packages.ubuntu.com/oneiric/sbcl

簡易的に比較できるように自分の環境でclispとsbclを測定したものを貼っときます。
clisp fib.l
real 1m50.760s
sbcl --script fib.l
real 0m2.013s

nanasi-sannanasi-san 2013/01/04 00:19 clojure1.3以降の場合、下記の書き方をすれば初期化時間を除いた処理時間がjavaと同じぐらいになるようです。
http://dev.clojure.org/display/doc/Documentation+for+1.3+Numerics

(defn fib ^long [^long n]
(if (< n 2)
n
(+ (fib (- n 2)) (fib (- n 1)))))
(time (println (fib 38)))

satosystemssatosystems 2013/01/04 07:30 > kmizushima
コメントありがとうございます。
気になったので javap でバイトコードを見てみました。

以下は Java です。

static int fib(int);
Code:
0: iload_0
1: iconst_2
2: if_icmpge 7
5: iload_0
6: ireturn
7: iload_0
8: iconst_2
9: isub
10: invokestatic #2; //Method fib:(I)I
13: iload_0
14: iconst_1
15: isub
16: invokestatic #2; //Method fib:(I)I
19: iadd
20: ireturn

以下が Scala です。

public int fib(int);
Code:
0: iload_1
1: istore_2
2: iload_2
3: tableswitch{ //0 to 1
0: 42;
1: 42;
default: 24 }
24: aload_0
25: iload_1
26: iconst_2
27: isub
28: invokevirtual #31; //Method fib:(I)I
31: aload_0
32: iload_1
33: iconst_1
34: isub
35: invokevirtual #31; //Method fib:(I)I
38: iadd
39: goto 43
42: iload_1
43: ireturn

Scala は case で書いた部分が tableswitch にコンパイルされていて、結果を見ればそりゃそうだ、という感じなんですが、ここが単純にオーバーヘッドになっているようです。case の書き方が関数型言語っぽくていい感じなんですが、if-else で書いたほうが javac のバイトコードに近いようです。

以下は if-else で書いた Scala です。

public int fib(int);
Code:
0: iload_1
1: iconst_2
2: if_icmpge 9
5: iload_1
6: goto 24
9: aload_0
10: iload_1
11: iconst_2
12: isub
13: invokevirtual #26; //Method fib:(I)I
16: aload_0
17: iload_1
18: iconst_1
19: isub
20: invokevirtual #26; //Method fib:(I)I
23: iadd
24: ireturn

invokevirtual でメソッド呼び出しが行われるのは Scala の特徴のようなので、そのための aload_0 を差し引くと ireturn するか goto するかの違いだけで(厳密には goto して ireturn より直接 ireturn したほうが無駄がないですが)、コンパイラの出力という面では遜色ないと思います。部分的には javac より優れているところもあるんでしょうね。

さて、結果は以下の通りです。

Java: 0.732
Scala (case): 1.896
Scala (if-else): 1.024

Java と Scala (if-else) で 300ms ほど差があるのですが、内訳は Scala ライブラリのロードで 150ms、コンパイルで 100ms、invokevirtual のオーバヘッドで 50ms、という感じの結果でした。

Scala は書き方が悪かったということなんだと思います。Java も switch-case で書けば 1.844 で、Scala より遅いぐらいでした。

satosystemssatosystems 2013/01/04 07:35 > mike_neck

教えていただいた通り、引数に型指定をして計測してみたのですが、逆に遅くなってしまいました。

型指定なし: 40.751
型指定あり: 48.003

バージョンのせい(Groovy 1.6.4)なんでしょうか?

型指定して遅くなるというのが考えづらいのですが、こういう結果になりました。

satosystemssatosystems 2013/01/04 08:01 > nanasi-san

教えていただいた情報で Clojure を追試してみました。

** 新しいバージョンを使う

$ wget -O clojure-1.4.0.jar 'http://search.maven.org/remotecontent?filepath=org/clojure/clojure/1.4.0/clojure-1.4.0.jar'
$ time java -cp clojure-1.4.0.jar clojure.main fib.clj

結果は、以下の通りで、5 秒という事にはなりませんでした。

Clojure 1.0.0: 41.691
Clojure 1.4.0: 37.718

** let でちょびっと速くなる

Clojure 1.0.0 の結果は以下のとおりです。

let なし: 41.691
int 版: 47.723
long 版: 44.691

Clojure 1.4.0 の結果は以下のとおりです。

let なし: 37.718
int 版: 16.665
long 版: 14.597

Clojure 1.4.0 はかなり違いますね。

long の方が高速というのがどういう理屈なのか全くわかりません。

** javaと同じぐらいになる

Clojure 1.4.0 で試してみました。

オリジナル: 37.718
高速版: 4.720

劇的に速くなりました。Clojure 1.0.0 では動作しませんでした。

satosystemssatosystems 2013/01/04 08:03 > nanasi-san
SBCL の情報提供、ありがとうございました。

計測して記事に反映させました。かなり高速な処理系ですね。

kariya_mitsurukariya_mitsuru 2013/01/06 17:04 bash がちょっとかわいそうなので。
この記事の書き方だと bash と言うより新規プロセス起動にほとんどの時間が費やされてしまうので、以下のような書き方のほうが良いかと。

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

どこまで早くなるかわかりませんが・・・

Scheme48のコンパイルがアリならScheme48のコンパイルがアリなら 2013/01/06 21:23 C++11
constexpr int fib(int n) {
return n < 2 ? n : fib(n - 2) + fib(n - 1);
}

Scheme48のコンパイルがアリならScheme48のコンパイルがアリなら 2013/01/06 21:29 あ、トラックバックで既出だったorz

satosystemssatosystems 2013/01/07 02:24 > kariya_mitsuru
コメントありがとうございます。

計測したところ結果が出るようになりました。バッククオートによる演算方法しか知らなかったので、勉強になりました。

> Scheme48のコンパイルがアリなら
constexpr は全く知らなかったので、トラックバック先含め、勉強になりました。私の環境では C++11 はまだサポートされていないようです(どうやら 4.6 かららしいです)。

Scheme48 がコンパイル時に計算するというのは事前には知らなくて、関数型言語だからそれもありだろうと思ったのですが、手続き型言語の代表格でもある C++ でもそうした試みがあるのですね。キーワードをつけてプログラマが副作用がないことを保証?しなければならないのでしょうか。ググったのですが、今ひとつよくわかりませんでした。

はげはげ 2013/01/08 09:59 Fortranだと内部関数にするとインライン最適化が効く場合もある。
再帰を末尾再帰最適化する処理系もある。
普通は再帰そのものが忌み嫌われて使うと馬鹿にされるがww
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

野生野生 2013/01/08 13:14 gdcはD言語最新の処理系では無いので、dmd -O -release -inlineでも計測して頂きたいです。
また、D言語にもC++11同等以上のCTFEが存在します。

http://www.kmonos.net/alang/d/dmd-linux.html#switches
http://dlang.org/download.html
http://www.kmonos.net/alang/d/function.html#interpretation

satosystemssatosystems 2013/01/09 03:19 > はげ
コメントありがとうございます。
使用している処理系が gfortran で、それ自体が 1.92 秒と速いのですが、教えてもらったコードも処理時間としてはほとんど変わりませんでした。特別な最適化はおこなっていないのでしょうね。

> 野生
記事にも書いた通りなのですが、gdc がそれなりに高速だったので、dmd は「ま、いっか」「すべての処理系で最新版の導入なんてやってられん」と省略しました。

私の D の知識は数年前で止まってしまっているのですが、D の言語仕様はかなり好きです。記事本文では D を dis っているわけでは決してないんです、でもすみません。

はげはげ 2013/01/09 11:16 下品なコメで失礼しました。
最適化の件ですが、gfortranはdefaultでは最適化をしていないようなので、-O3のオプションをつけていただければ良かろうかと思います。こちらで試してみたところ、3倍くらいは早くなりました。なお、書き方での差は誤差の範囲内で無いようでした。

ZimotoZimoto 2013/01/26 00:32 Prologの結果が無かったので、記載します。CPUはAMD A10-5800Kです。オーバークロックはしていません。CPU性能は多分Corei3なみです。
GNU Prologは使ったことはないので、知っている複数の処理系ですが
Visual Prolog 1.444s
SWI Prolog 18.707s
LPA Prolog 28.295s

Visual Prologは型定義のあるPrologで、処理速度はPrologの中でも早いほうに入ると思います。SWI Prologはフリーソフトです。LPA Prologの場合は、fib(38)はintegerの範囲ですが、もっと大きなintegerを超える値の場合も問題なく計算ができます。

ytqwertyytqwerty 2013/02/21 16:48 Adaのコンパイラはgccでしょうか。であればCと全く変わらない数値が出るはずです。-gnatpあたりを付けてみてください。
あ、拡張子が.adbなのは、ADa Bodyです。.ads(ADa Spec)もあります。

TclerTcler 2013/05/30 19:16 Tclは[]を入れ子にできるし、加減算だけならincrにすれば8倍くらい速い。

proc fib {n} {
if {$n<2} {return $n}
set m [fib [incr n -1]]
incr m [fib [incr n -1]]
return $m
}

puts [fib 38]

sakamotosakamoto 2013/06/11 09:22 SmallTalk の文法は [ a b c d.] となっていたら、 a というオブジェクトに b というメッセージを送り、返ってきたオブジェクトに c というメッセージを送り、さらに返ってきたオブジェクトに d というメッセージを送る...というものです。で、基本型が無くて、数とか論理値とかもオブジェクトです。メッセージに引数を持たせるときはメッセージの最後にコロンが付きますが、演算子はコロンなしで一個引数を持ちます。
1 + 2 * 3 は 1 というオブジェクトに引数 2 を持つ + メッセージを送り、返ってきたオブジェクト(この場合は3)に3という引数を持つ * メッセージを送るので、 9というオブジェクトが返ってきます。[38 fib printNl.]は38というオブジェクトに fib というメッセージを送り、返ってきたオブジェクトに printNl というメッセージを送ります。作成されているプログラムは Integerクラスにメソッドを拡張しています。
実験結果は非常に興味深いものでしたが、これ、横軸を対数目盛にすることはできませんかね?

inokinok 2014/09/24 00:28 ごめんなさいね、悪気は無いんですよ、これアルゴリズムがだめです。
1 ずつ足していって, 2 つずつスタック(引数につんで)、再帰呼び出ししてください。もちろん、末尾再帰呼び出しで。たぶん, Lisp 類は、これで圧倒的に速くなります。

あと、Scheme は、write じゃなくて display でやったほうが早いです。
ついでですが, Scheme の R5RS には exit があったと思いますけど ... たぶん R7RS の処理系なら、確実にあるはずです。それを使えば exit できます。

satosystemssatosystems 2014/12/02 22:17 > Zimoto
コメントありがとうございます。Prolog は全く精通していなくて、大変参考になります。

> ytqwerty
拡張子はそういう理由だったんですね。
教えていただいた引数をつけて再計測したいところなのですが、あいにく当時の環境がもうないので・・・。機会があれば、また新しい環境で計測しなおしてみたいと思います。

> Tcler
コメントありがとうございます。Tcl も全く精通していないので、大変参考になります。再計測の機会があれば、教えていただいたコードで行ってみようと思います。

> sakamoto
Smalltalk に対する知見が少しだけ増えました。
結果のグラフは、Google のウェブサービスか何かを使用していて、細かくカスタマイズできない(できるかも知れないけどわからない)ので、再計測の機会があれば対数目盛にしてみようと思います。

> inok
コメントありがとうございます。
アルゴリズムに関しては、冒頭に記載している通り漸化式をそのままコードにしたもので、全言語できるだけこのアルゴリズムを採用するようにしています。

Scheme の write と display の違いは:
 write は機械可読な出力を生成するためにあり,display は人間可読な出力を生成するためにある。
ということらしく、どちらがより速いとか、そうした速度の保証はないと思います。

exit は R7RS にはありますが、R5RS にはないようです。R6RS からライブラリ関数として定義されるようになったようですね。

tealsenstealsens 2015/02/02 04:26 sbclはコンパイルも出来るので、できればそれも計測して欲しいですね。

enoeno 2016/01/31 17:25 面白い比較ありがとうございます。mawkはgawkよりも高速です。手元ではgawkでは33秒,mawkでは12秒でした。

hyotang666hyotang666 2016/07/12 18:09 lispですが、コンパイル時計算が許されるなら採用してほしいですねw
(print #.(fib 38))

また、そうでなくても、最適化オプションをつけるとまだ速くなります。
https://gist.github.com/hyotang666/b4385eaa724a4a527a9fdbbd8dbb4f9d

スパム対策のためのダミーです。もし見えても何も入力しないでください
ゲスト

コメントを書くには、なぞなぞ認証に回答する必要があります。

リンク元