To good to be true?

No, it wasn't!

I've wrote about implementing Karatsuba multiplication in previous post (sorry it's in Japanese). So I wanted to make all internal bignum multiplication to use it. Now I've modified expt to use it. Then next step is of course benchmark :)

Actually, it didn't make any performance better and it's quite difficult to compare because of the bug. So I've decided to compare with Mosh and Ypsilon, especially Mosh which is using GMP internally. So I wrote this piece of code;
(import (rnrs) (time))
(define-syntax dotimes
  (syntax-rules ()
    ((_ (var i res) . body)
     (do ((limit i)
          (var 0 (+ var 1)))
         ((>= var limit) res)
       . body))
    ((_ (var i) . body)
     (do ((limit i)
          (var 0 (+ var 1)))
         ((>= var limit))
       . body))
    ((_ . other)
     (syntax-violation 'dotimes
                       "malformed dotimes"
                       '(dotimes . other)))))

;; To avoid compile time constant folding
;; Sagittarius' compiler is a bit smarter than
;; the others :)
(define v (make-vector 1 512))

(time (dotimes (i 5000) 
        (let ((e (vector-ref v 0)))
          (expt #x123456789ABCDEF12 e))))

(display 'done) (newline)
And for Mosh, this was also required;
;; file name time.mosh.sls
(library (time)
    (export time)
    (import (mosh)))
Now, it's good to go. It took a bit time to figure out that Sagittarius compiler computes constant variable in compile time even though I implemented it. (That causes benchmark time always 0.00ms, so it was indeed 'too good to be true'. well but true though :-P)

The result was like this;
% ./build/sash.exe num.scm

;;  (dotimes (i 5000) (let ((e (vector-ref v 0))) (expt 20988295479420645138 e)))
;;  3.160898 real    3.2290000915527344 user    0.000000 sys

% ypsilon num.scm

;;  4.47794 real    4.524029 user    0.0 sys

% mosh num.scm

;;4.463438034057617 real 4.18 user 0.234 sys
As usual, I was very surprised with Ypsilon. It doesn't use GMP but the same time as Mosh. Anyway, Sagittarius' expt is faster than any others now. (could be before as well but incorrectly.)

After I wrote this post, I checked Mosh's expt code. It actually didn't use GMP but simply multply the given arguments... Well, it could be too good to be true then...

No comments:

Post a Comment