[racket-dev] expected timing difference between fft-complex-forward and fft-complex-radix2-forward?

On my laptop:

#lang racket

(require "fft.rkt")

(define v (build-vector 16384 (lambda (i) (random))))

(define v1 (vector-copy v))

(collect-garbage)
(collect-garbage)
(collect-garbage)
(time (fft-complex-radix2-forward v1))

(define v2 (vector-copy v))

(collect-garbage)
(collect-garbage)
(collect-garbage)
(time (fft-complex-forward v2))

(for/and ([i (in-range (vector-length v))])
 (< (magnitude (- (vector-ref v1 i) (vector-ref v2 i))) 1e-4))

==>

cpu time: 94 real time: 94 gc time: 0
cpu time: 79 real time: 78 gc time: 0
#t

I'll look at the rsound/fft implementation and see if I see the problem.

On Mon, Oct 18, 2010 at 10:32 PM, John Clements
<clements at brinckerhoff.org>wrote:

>
> On Oct 18, 2010, at 9:25 AM, Doug Williams wrote:
>
> > When I first ran with vectors of 8192, I got exactly the opposite - the
> radix-2 version was much slower (although still < 500ms). But, when I
> looked, the longer time was almost exclusively GC - it just happen to hit
> that particular call. When I put a (collect-garbage) before each call, they
> were all < 50ms on my machine. So, the GC penalty is likely what you're
> seeing.
> >
> > The other thing is to make sure you aren't calling one of the dft
> routines instead of the fft routines. Those are the only ones that get
> anywhere near 24s on my machine - they are about 20s on my machine. The dft
> routines are the 'straight' mathematical discrete Fourier transform and do
> not use the FFT algorithms at all. [They're really only useful for a sanity
> check on results.]
>
> Right, got it. No, the times I'm seeing are not GC.  I bumped it up to an
> 8192-point fft, and now the radix-2 version is about 400x faster.
>
> Here's my code:
>
> #lang racket
>
> (require (planet clements/rsound/fft))
>
> (define v (build-vector 16384 (lambda (i) (random))))
>
> (define v1 (vector-copy v))
>
> (collect-garbage)
> (collect-garbage)
> (collect-garbage)
> (time (fft-complex-radix2-forward v1))
>
> (define v2 (vector-copy v))
>
> (collect-garbage)
> (collect-garbage)
> (collect-garbage)
> (time (fft-complex-forward v2))
>
> (for/and ([i (in-range (vector-length v))])
>  (< (magnitude (- (vector-ref v1 i) (vector-ref v2 i))) 1e-4))
>
> =>
>
> cpu time: 208 real time: 211 gc time: 0
> cpu time: 81357 real time: 82502 gc time: 8337
> #t
>
> John Clements
>
> > On Thu, Oct 14, 2010 at 4:34 PM, John Clements <
> clements at brinckerhoff.org> wrote:
> > On a vector of length 8192 (a power of 2, natch),
> fft-complex-radix2-forward takes about 1/8 of a second (lost in the noise,
> essentially), but fft-complex-forward takes more than 24 seconds, a
> difference of about 200x.  They do produce the same answers, up to
> differences of 1e-4 in the magnitude (didn't check the phase).
> >
> > 1) Is this expected? I thought the non-radix2 one was still fairly clever
> about subdividing when the number of points is divisible by 2.
> > 2) If so, would it make sense to test for powers of 2?
> >
> > John Clements
> >
> >
>
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.racket-lang.org/dev/archive/attachments/20101019/bd6fbf60/attachment.html>