C++とcommon lispの実行速度比較(素数判定)

今日たまたま見つけた『(Sather を試そう) 1. Sather vs C++: 実行速度の比較』*1というページに触発され、lisp(sbcl-1.0.28)でも同様の比較を行ってみた。


C++ソースコードは、上記ページのものと同様だが、g++のオプションには'-O3'を渡している。
実行結果は以下の通り。

> time ./prime_cpp 10000000 > /dev/null
real	0m1.032s
user	0m0.992s
sys	0m0.004s


対するlispのコード。
※ 変数名などは、自分の好みに合わせて変えているが、アルゴリズム的にはC++のものと同様(のはず)。

;;;; 宣言などのため、C++のソースより長くなってしまっている
(declaim (optimize (debug 0) (safety 0) (speed 3) (compilation-speed 0))
         (inline primep))

(defun primep (n primes len)
  ;; inline化されるので、ここの宣言は(今回のケースでは)無くても大丈夫
  (loop FOR i FROM 0 BELOW len
        FOR p fixnum = (svref primes i) DO
    (when (> (the fixnum (* p p)) n) (return t))
    (when (zerop (mod n p))          (return nil))))

(defun nprime (limit)
  (format t "#Limit, N of primes~%0 0~%")
  (let ((primes (make-array (truncate (/ limit 2))))
        (len 0)  ; primesの長さは、プログラムで管理する
        (interval (- 500 2)))
    (declare (fixnum limit len interval)
             (simple-vector primes))
    (macrolet ((post-incf (n)    `(prog1 ,n (incf ,n)))
               (push-back (elem) `(setf (aref primes (post-incf len)) ,elem)))
      (push-back 2)
      (push-back 3)
      (loop FOR n FROM 5 TO limit BY 2 DO
        (when (primep n primes len) 
          (push-back n))
        (when (zerop (decf interval))
          (format t "~D ~D~%" n len)
          (setf interval 500))))))


実行結果。

>(let ((*standard-output* (make-broadcast-stream)))
   (time (nprime 10000000)))
Evaluation took:
  1.152 seconds of real time
  1.156072 seconds of total run time (1.156072 user, 0.000000 system)
  100.35% CPU
  3,655,271,262 processor cycles
  20,000,008 bytes consed

なかなか、悪くない結果だ。
lisp(sbcl)版は、C++版の1.15倍程度に収まっている*2

おまけ

宣言を外したり、primesの実装を変更した場合の処理速度の違いを以下にまとめる。

番号primes実装/宣言の有無実行時間(秒)
0simple-vector/宣言有(上の実装)1.152
1simple-vector/宣言無6.632
2fill-pointer-vector/宣言有9.576
3fill-pointer-vector/宣言無8.936
4fill-pointer-vector/primepのみ宣言無*312.943
5fill-pointer-adjustable-vector/宣言有*49.605
6list/宣言有1.167
7list/宣言無5.499
listでの実装(queueを使用)が意外に速く、fill-pointer付きvectorが遅かった。
多分、上記プログラムのボトルネックの一つは、primep関数内でのsequenceの各要素のイテレートなのだろうが、そこでのlistに対するcarとcdrが速く、fill-pointer-vectorに対するarefが(相対的に)遅いために、この様な結果になったのだと思う。


また、fill-pointer-vectorでは、何故か最適化宣言が有る場合の方が、無い場合よりも遅くなっている。
例えば、上の表の2番(宣言有)と3番(宣言無)の実行時間はあまり変わらないが、これは2番の場合、宣言によってfill-pointer-vector周りの処理で遅くなってprimep関数内での数値計算が速くなっているからだろう(両者が相殺)。
そのため、4番のようにprimep関数内の宣言だけを外した場合は、明らかに実行時間が延びている。


あと、adjustableは付けても付けなくても、それほど大きな影響がない感じだ。そもそも、今回は挿入回数が少なかったので、そのせいもあるだろう。

おまけ2

listでの実装が予想外に速かったので、このソースコードも載せておく。

(declaim (optimize (debug 0) (safety 0) (speed 3) (compilation-speed 0))
         (inline primep))

;; listによるqueue実装(必要な関数のみ)
(declaim (inline make-que push-que que-list))
(defun make-que ()    (let ((q (list nil))) (setf (car q) q)))
(defun push-que (x q) (setf (car q) (setf (cdar q) (list x))))
(defun que-list (q)   (cdr q))


(defun primep (n primes)
  (dolist (p (que-list primes))
    (declare (fixnum p))
    (when (> (the fixnum (* p p)) n) (return t))
    (when (zerop (mod n p))          (return nil))))

(defun nprime (limit)
  (format t "#Limit, N of primes~%0 0~%")
  (let ((primes (make-que))
        (len 2) ;; listのlengthはコストが高いので、長さは別に管理する
        (interval (- 500 2)))
    (declare (fixnum limit interval len))
    (push-que 2 primes)
    (push-que 3 primes)
    (loop FOR n FROM 5 TO limit BY 2 DO
      (when (primep n primes)
        (incf len)
        (push-que n primes))
      (when (zerop (decf interval))
        (format t "~D ~D~%" n len)
        (setf interval 500)))))

*1:Nまでの素数を探すプログラムをSather(?)とC++で実装・比較している

*2:ちなみに、後日、別のマシンで試してみたところ、そこでは1.5倍程度の差がでた

*3:primep関数定義内でのfixnum宣言を除去

*4:初期サイズは64