Speed comparison C vs Common Lisp

Mon 08 Aug 2011 10:28:17 PM CST

昨天看到有人轉噗一則 StackOverflow 上面的問題，內容是問他分別用 C, python, erlang 與 haskell 寫了 Project Euler 的第十二題，但是 haskell 版本慢得不像話，該如何改進？

以下是苦主的原始 C 語言版：

#include <stdio.h>
#include <math.h>
int factorCount (long n)
{
    double square = sqrt (n);
    int isquare = (int) square;
    int count = isquare == square ? -1 : 0;
    long candidate;
    for (candidate = 1; candidate <= isquare; candidate ++)
        if (0 == n % candidate) count += 2;
    return count;
}
int main ()
{
    long triangle = 1;
    int index = 1;
    while (factorCount (triangle) < 1001)
    {
        index ++;
        triangle += index;
    }
    printf ("%ld\n", triangle);
}

我的執行時間約為 5.48s

% gcc -lm -o euler12.bin euler12.c
% time ./euler12.bin 
842161320
./euler12.bin  5.48s user 0.00s system 99% cpu 5.484 total

手癢想看看據說可以編譯出不錯的機器碼的 Common Lisp 速度怎麼樣，於是第一個版本如下 (用 sbcl 執行)：

(defun factor-count (n)
  (let* ((square (sqrt n))
         (squaref (floor square))
         (count (if (eql squaref square) -1 0)))
      (loop
         for cand from 1 to squaref
         count (eql 0 (rem n cand)) into c
         finally (return (+ count c c)))))
(defun first-triangle-over (n)
    (loop
       for idx from 1
       sum idx into triangle
       until (>= (factor-count triangle) n)
       finally (return triangle)))
;; (time (first-triangle-over 1000))
;; Evaluation took:
;;   11.192 seconds of real time
;;   11.184699 seconds of total run time (11.184699 user, 0.000000 system)
;;   99.94% CPU
;;   30,135,882,489 processor cycles
;;   32,912 bytes consed
;;   
;; 842161320

還不錯，11.192s，這個版本採用原文中給 haskell 的建議，使用 rem 而不是 mod，可以加快一點速度。再給一點關於型別的提示，然後把第一個 function inline，第二版可以跑出和 C 版本差不多的成績 5.563s :-)

(declaim (inline factor-count)) ;; <----
(defun factor-count (n)
  (let* ((square (sqrt n))
         (squaref (floor square))
         (count (if (eql squaref square) -1 0)))
      (loop
         for cand from 1 to squaref
         count (eql 0 (rem n cand)) into c
         finally (return (+ count c c)))))
(defun first-triangle-over (n)
    (loop
       for idx of-type fixnum from 1 ;; <----
       sum idx into triangle of-type fixnum  ;; <----
       until (>= (factor-count triangle) n)
       finally (return triangle)))
;; (time (first-triangle-over 1000))
;; Evaluation took:
;;   5.563 seconds of real time
;;   5.556347 seconds of total run time (5.556347 user, 0.000000 system)
;;   99.87% CPU
;;   14,970,270,903 processor cycles
;;   32,768 bytes consed
;;
;; 842161320

純粹湊個熱鬧而已，有興趣的人可以試試看把 loop 改成和原文其他語言一樣使用遞迴來實做，大部分 Lisp 都有做 TCO，速度應該差不多...

結論：Common Lisp is awesome ;-)