luajit vs pypy

luajitがアツイという話を聞きつけたのでpypyと比較してみた。
luajitは id:pcl:20100203 を参考に。

-- prime.lua
function isprime(n, primes)
    nsqrt = n ^ 0.5
    for i = 1, #primes do
        if nsqrt < primes[i] then break end
        if n % primes[i] == 0 then return false end
    end
    return true
end

primes = {}

for i = 2, arg[1] * 1 do
    if isprime(i, primes) then primes[#primes + 1] = i end
end

print(primes[#primes]) --確認用

$ time lua5.1 prime.lua 10000000
99999991

real 2m39.759s
user 2m30.641s
sys  0m0.148s

$ time luajit-2.0.0-beta5 prime.lua 10000000
9999991

real 0m15.089s
user 0m14.261s
sys  0m0.028s

pythonに移植してみる

# prime.py
import sys
import math

def isprime(n, primes):
    nsqrt = math.sqrt(n)
    for x in primes:
        if nsqrt < x:
            break
        if n % x == 0:
            return False
    return True

def main(argv):
    primes = []
    num = int(argv[1])
    for x in xrange(2, num):
        if isprime(x, primes):
            primes.append(x)
    print primes[-1]

if __name__ == '__main__':
    main(sys.argv)

$ time python prime.py 10000000
99999991

real 2m32.655s
user 2m29.357s
sys  0m0.120s

$ time pypy prime.py 10000000
9999991

real 0m13.596s
user 0m9.277s
sys  0m0.728s

微妙にだがpypyの方が早い。それにしてもどっちもすごい速度upだ。

追記

参考までにC++でも書いてみた。

// prime.cpp
#include <vector>
#include <math.h>
#include <stdio.h>
#include <stdlib.h>

bool isprime(int n, const std::vector<int>& primes)
{
    float nsqrt = sqrtf(n);
    for(size_t Li = 0; Li < primes.size(); ++Li){
        if(nsqrt < primes[Li]){
            break;
        }
        if(n % primes[Li] == 0){
            return false;
        }
    }
    return true;
}

int main(int argc, const char** argv)
{
    std::vector<int> primes;
    int num = atoi(argv[1]);
    for(int Li = 2; Li < num; ++Li){
        if(isprime(Li, primes)){
            primes.push_back(Li);
        }
    }
    printf("%d\n", primes.back());
    return 0;
}

$ g++ -o prime -O3 prime.cpp
$ time ./prime 10000000
99999991

real 0m7.565s
user 0m7.396s
sys  0m0.012s

さらに倍早い。さすが。C++最強。

追記２

cythonでもやってみる。

# cython_prime.pyx
cimport libc.math
from libcpp.vector cimport vector
from cython.operator import dereference, preincrement

cdef bint isprime(int n, vector[int]* primes):
    cdef double nsqrt = libc.math.sqrt(n)
    cdef vector[int].iterator x = primes.begin()
    cdef vector[int].iterator end = primes.end()
    cdef int xx
    while x != end:
        xx = dereference(x)
        if nsqrt < xx:
            break
        if n % xx == 0:
            return False
        preincrement(x)
    return True

cpdef main(int num):
    cdef int x
    cdef vector[int] primes
    for x in xrange(2, num):
        if isprime(x, &primes):
            primes.push_back(x)
    print primes.back()

# cython_prime_main.py
import sys
import cython_prime
cython_prime.main(int(sys.argv[1]))

$ cython --cplus cython_prime.pyx
$ g++ -shared -O3 -I/usr/include/python2.7 -o cython_prime.so cython_prime.cpp
$ time python cython_prime_main.py 10000000
9999991

real 0m8.378s
user 0m8.077s
sys  0m0.016s

cythonもかなり早い。しかしvectorをpythonのlistに変えただけで2sくらい遅くなる。細かいことを考えないと早くならないのはしんどいなぁ。