[GSLL-devel] Why FFT tests are slow

[Sumant S. R. Oemrawsingh]

Hi Liam,

I recently realised that I completely forgot to submit the forms that
I used to check where the problem lies with the slow FFT tests.  So my
apologies, and hereby some very simple forms (should be run in package
:gsll).  I quickly re-ran them to verify that the timings are still
the same (with updated gsll and now using antik).


;;;; Check 1: Perform FFTs on 1000 different vectors, each with 1000
;;;; random complex elements (consisting of a real and a complex
;;;; random element).  Takes ~2 seconds on my old laptop.
(time
 (progn
   (loop for i from 0 below 1000
      do (forward-fourier-transform (make-urand-vector '(complex double-float) 1000)))
   nil))

;;;; Check 2: Same as 1, but without the FFTs.  Takes ~1.8 seconds.
(time
 (progn
   (loop for i from 0 below 1000
      do (make-urand-vector '(complex double-float) 1000))
   nil))


Here, it's clear that the time increases by an order of magnitude by
just generating random vectors.  1000 FFTs take less time:


;;;; Check 3: Generate only 1 random vector, FFT 1000 times. Takes ~
;;;; 0.14 seconds.
(time
 (let ((rand (make-urand-vector '(complex double-float) 1000)))
   (loop for i from 0 below 1000
      do (forward-fourier-transform rand))
   nil))


So let's see where the problems lie in making the random vector:


;;;; Check 4: Same as 2, but without making the vector.  Takes ~1 second.
(time
 (progn
   (loop for i from 0 below 1000
      do (loop for j from 0 below 1000
	    do (coerce (complex (urand) (urand)) '(complex double-float))))
   nil))

;;;; Check 5: Same as 4, but without coercing.  Takes ~0.6 seconds.
(time
 (progn
   (loop for i from 0 below 1000
      do (loop for j from 0 below 1000
	    do (complex (urand) (urand))))
   nil))


You can see that half the time of Check 1 is just spent generating and
coercing elements.  Then ~40% is making and setting the vectors
(non-optimized) and ~10% is the FFTs themselves.

I tried making an optimized version of make-urand-vector using
declarations, which only sped up things by a little bit (certainly not
an order of magnitude); we discussed this before on #lisp.  However,
since the transition to antik, I didn't manage to get this working in
a reasonable amount of time.  Regardless, the fact that it still
contained the form:
    
(coerce (complex (urand) (urand)) '(complex double-float))

is the reason for the fact that even the optimized version is slow.
Since the original GSL tests use random vectors a lot, this is a real
problem.  The second thing is that I suspect that setf-ing array
elements is slower than in C as well.  The GSL tests also use this a
lot, since they initialize the vectors with known numbers, to verify
that those elements were untouched when using the stride keyword.

It could be that optimized functions, using declarations and gsetf,
will cause those parts of the tests to go faster.  I will try that
when I have some more time, and when I get it working.

By the way, here's the defun for the attempt at an optimized version
of make-urand-vector for complex double-floats.  I tried many
different things (also without the let around) but couldn't get it to
run: I always get a type-error.

(defun make-urand-complex-double-float-vector (dimension &key (stride 1) init-offset)
  "Make a complex double-float vector with random elements."
  (let ((vec (make-and-init-vector '(complex double-float)
                                   (* stride dimension) :init-offset init-offset)))
    (declare (type grid:vector-complex-double-float vec))
    (loop for i from 0 below (* stride dimension) by stride
       do
	 (let ((value (coerce (complex (urand) (urand)) '(complex double-float))))
	   (declare (type (complex double-float) value))
	   (grid:gsetf (grid:aref* vec i) value)))
    vec))

Regards,
Sumant
    
-- 
Sumant Oemrawsingh