Optimizing vectorized calcs in Lisp

[Harvey Stein]

I spent a good chunk of today experimenting with optimizing vectorized calcs.  It took a lot of trial and error, but I finally found a way to write an element-wise vector multiply so that it's about 10x faster than stock cls & antik when the arguments are vectors of double-floats.

Here's some test code:

(defun testgenericantik (n m)
  (declare (type (integer 1 10000000) n m))
  (let ((v1 (cls:iseq m))
    (v2 (cls:rseq 0 .1 m)))
    (time (progn (dotimes (i n)
           (setq v1 (antik:* v1 v2)))))
    (reduce #'+ v1)))

(defun testgenericantikv2 (n m)
  (declare (type (integer 1 10000000) n m))
  (let ((v1 (coerce (cls:* 1d0 (cls:iseq m)) '(vector double-float)))
    (v2 (coerce (cls:rseq 0 .1 m) '(vector double-float))))
    (time (progn (dotimes (i n)
           (setq v1 (antik:* v1 v2)))))
    (reduce #'+ v1)))

Compiling declaration:

(eval-when (:compile-toplevel)
  (declaim (optimize (speed 3) (safety 1) (space 0) (debug 0))))


Performance:

CL-USER> (testgenericantikv2 50 1000000)
Evaluation took:
  5.973 seconds of real time
  5.980181 seconds of total run time (5.769374 user, 0.210807 system)
  [ Run times consist of 0.829 seconds GC time, and 5.152 seconds non-GC time. ]
  100.12% CPU
  16,090,477,530 processor cycles
  4,400,105,248 bytes consed
 

CL-USER> (testgenericantik 50 1000000)
Evaluation took:
  6.087 seconds of real time
  6.085726 seconds of total run time (5.761059 user, 0.324667 system)
  [ Run times consist of 2.989 seconds GC time, and 3.097 seconds non-GC time. ]
  99.98% CPU
  16,397,993,739 processor cycles
  1,600,006,576 bytes consed

Disappointingly, using arrays of double-floats doesn't help. 

But, because Antik implements vectorized multiplication via generic functions, I can insert a specialized version of *. Unfortunately, I can't add a generic based on the complex type (simple-array double-float (*)) because it's not a class.  But I can at least make a special version for vectors & specialize at run-time based on types:

(defmethod antik::*i ((a vector) (b vector))
  (assert (eq (length a) (length b)) (a b)
      "Sequence arguments are not of the same length.")
  (cond ((and (typep a '(simple-array double-float (*)))
          (typep b '(simple-array double-float (*))))
     (let ((a a) (b b) (c (make-array (length a) :element-type 'double-float)))
       (declare (type (simple-array  double-float (*)) a b c))
       (dotimes (i (length a))
         (setf (aref c i) (* (aref a i) (aref b i))))
       c))
    (t (map '(vector) #'antik::*i a b))))


CL-USER> (testgenericantikv2 50 1000000)
Evaluation took:
  0.443 seconds of real time
  0.441042 seconds of total run time (0.363605 user, 0.077437 system)
  [ Run times consist of 0.309 seconds GC time, and 0.133 seconds non-GC time. ]
  99.55% CPU
  1,193,347,167 processor cycles
  400,001,472 bytes consed

Over a factor of 10x faster.  This is with sbcl.  I'm finding similar results with ccl, but sbcl is about 2x faster. In any case, the numerics can be sped up by about a factor of 10 on arrays if we special case the code for arrays where we know the types of the elements.  Incidentally, antik and cls in sbcl are about the same speed as xlispstat.

For big calculations, it'd be important to also do them in place so as to avoid a lot of memory allocation, copying, gcing, and polluting of cache.

[A.J. Rossini]

Dear Harvey -

Could you add your code (and notes, as comments) into a file in the
examples directory? From there, it can be refactored into various
places where it belongs (unit testing, to continue to confirm
speedups, etc).

In general, if you have code (real or wished for) that you want to
run, put it there (top level examples directory) and then we can
refactor into various places. I made the mistake early of trying to
do too much without experimenting first, and ran into chaos.

best,
-tony

> --
> You received this message because you are subscribed to the Google Groups
> "Common Lisp Statistics" group.
> To unsubscribe from this group and stop receiving emails from it, send an
> email to lisp-stat+...@googlegroups.com.
> To post to this group, send email to lisp...@googlegroups.com.
> Visit this group at http://groups.google.com/group/lisp-stat.
> For more options, visit https://groups.google.com/d/optout.



--
best,
-tony

blind...@gmail.com
Muttenz, Switzerland.
"Commit early,commit often, and commit in a repository from which we
can easily roll-back your mistakes" (AJR, 4Jan05).

Drink Coffee: Do stupid things faster with more energy!