How to do fast matrix-multiplication?
in [Lisp]
|
From: Karsten Wenzel on 7 Feb 2006 06:25 Hi, I need to operate on huge two-dimensional arrays. For example, a matrix-multiplication. For a first test, I tried to multiply two small arrays 500x500 (dimension hard coded, no error checking or whatever): (defun mult-array (a b) (let ((c (make-array '(500 500)))) (dotimes (i 500) (dotimes (j 500) (dotimes (k 500) (setf (aref c i j) (+ (aref c i j) (* (aref a i k) (aref b k j))))))) c)) (setf a (make-array '(500 500))) (setf b (make-array '(500 500))) (fill-array a) ; Not shown here (fill-array b) (mult-array a b) This was slow. The algorithm isn't very smart, but that's not the point. OK, these arrays should only contain integers. So I tried to define the arrays this way: (make-array '(500 500) :element-type 'fixnum) But I got no speed-up. I checked LispWorks and OpenMCL and both are slower this way. How to do it really fast? What should I do better? Are they faster ways to access elements other than aref? Thank you in advance, Karsten
From: Edi Weitz on 7 Feb 2006 06:56 On Tue, 07 Feb 2006 12:25:21 +0100, Karsten Wenzel <kwenzel(a)tfh-berlin.de> wrote: > I need to operate on huge two-dimensional arrays. For example, a > matrix-multiplication. > > For a first test, I tried to multiply two small arrays 500x500 > (dimension hard coded, no error checking or whatever): > > (defun mult-array (a b) > (let ((c (make-array '(500 500)))) > (dotimes (i 500) > (dotimes (j 500) > (dotimes (k 500) > (setf (aref c i j) (+ (aref c i j) > (* (aref a i k) (aref b k j))))))) > c)) > > (setf a (make-array '(500 500))) > (setf b (make-array '(500 500))) > (fill-array a) ; Not shown here > (fill-array b) > (mult-array a b) > > This was slow. The algorithm isn't very smart, but that's not the > point. > > OK, these arrays should only contain integers. So I tried to define > the arrays this way: > > (make-array '(500 500) :element-type 'fixnum) > > But I got no speed-up. I checked LispWorks and OpenMCL and both are > slower this way. > > How to do it really fast? What should I do better? Are they faster > ways to access elements other than aref? There are a couple of open questions here. First, what does "This was slow" really mean? Do you have something to benchmark against, or does it just /feel/ slow? Second, as you haven't posted here before: Did you compile the code? For implementations like LispWorks and OpenMCL that compile to native code that'd make a big difference. Apart from that, if this is really a bottleneck, you should add declarations to your code, i.e. within MULT-ARRAY there should be a DECLARE that declares the types of A, B, and C as accurately as possible. Declaring the element type in MAKE-ARRAY as you did above doesn't make a difference. You can also try various OPTIMIZE qualities, including implementation-dependent ones - for LispWorks for example you should check chapter nine of the LispWorks User Guide. HTH, Edi. -- Lisp is not dead, it just smells funny. Real email: (replace (subseq "spamtrap(a)agharta.de" 5) "edi")
From: Förster vom Silberwald on 7 Feb 2006 07:20 Karsten Wenzel wrote: > This was slow. The algorithm isn't very smart, but > that's not the point. > > OK, these arrays should only contain integers. > So I tried to define the arrays this way: I cannot comment on your code since my Lisp is zero. However, if you are really after some fast matrix-multiplication algorithms you should google around a bit. There exists some techniques for such kind of things (loop unrolling, cache size awareness, etc..). A good idea could be also to have a look at some specialized libraries and write a binding to your Lisp implemenation. Btw: profiling the code will alse lead to some better insight. Then you can quickly decide where most of the time is spent off (is it floating point performance, or memory). Schneewittchen
From: Alexander Schmolck on 7 Feb 2006 07:26 Karsten Wenzel <kwenzel(a)tfh-berlin.de> writes: > Hi, > > I need to operate on huge two-dimensional arrays. > For example, a matrix-multiplication. Assuming you want to do number crunching, for best performance you'll want to wrap atlas. There's very little chance you'll beat atlas performance with home-brewn matrix multiplication etc. routines in any language and if most of your arrays are large the FFI overhead should be negligible. Have a look at matlisp as a possibly not great starting point (doesn't work with most implementations, though). > For a first test, I tried to multiply two small > arrays 500x500 (dimension hard coded, no > error checking or whatever): > > (defun mult-array (a b) > (let ((c (make-array '(500 500)))) > (dotimes (i 500) > (dotimes (j 500) > (dotimes (k 500) > (setf (aref c i j) (+ (aref c i j) > (* (aref a i k) (aref b k j))))))) > c)) > > (setf a (make-array '(500 500))) > (setf b (make-array '(500 500))) > (fill-array a) ; Not shown here > (fill-array b) > (mult-array a b) > > This was slow. The algorithm isn't very smart, but > that's not the point. > > OK, these arrays should only contain integers. > So I tried to define the arrays this way: > > (make-array '(500 500) :element-type 'fixnum) See Edi's reply, also once you (declare (optimize (speed 3))), cmucl and sbcl will also give you hints where to put declarations. But integer matrix multiplication used to be one of the benchmarks in doug bagley's language shootout, so you should be able to find a lisp version that does that reasonably well floating around on the web somewhere. Are you sure you don't generally want floating point, though? 'as
From: Stephan Frank on 7 Feb 2006 16:23
Karsten Wenzel wrote: > Hi, > > I need to operate on huge two-dimensional arrays. > For example, a matrix-multiplication. > Hallo Karsten, apart from the other responses you already got, you might also want to have a look at Cyrus Harmon's clem-library [1]. I have not looked at it very deeply but according to the information given by its author it is designed to provide very high performance for matrix math making use of some macrology to make better use of the type information. Regs, Stephan [1] http://www.cyrusharmon.org/cl/blog/display/37 |