Speed comparison C vs Common Lisp

昨天看到有人轉噗一則 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 😉