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実装/宣言の有無 | 実行時間(秒) |
| 0 | simple-vector/宣言有(上の実装) | 1.152 |
| 1 | simple-vector/宣言無 | 6.632 |
| 2 | fill-pointer-vector/宣言有 | 9.576 |
| 3 | fill-pointer-vector/宣言無 | 8.936 |
| 4 | fill-pointer-vector/primepのみ宣言無*3 | 12.943 |
| 5 | fill-pointer-adjustable-vector/宣言有*4 | 9.605 |
| 6 | list/宣言有 | 1.167 |
| 7 | list/宣言無 | 5.499 |
多分、上記プログラムのボトルネックの一つは、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)))))
