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))

(time (fft-complex-radix2-forward v1))
(define v2 (vector-copy v))

(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

John Clements

> On Thu, Oct 14, 2010 at 4:34 PM, John Clements <cleme...@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

Attachment: smime.p7s
Description: S/MIME cryptographic signature

  For list-related administrative tasks:

Reply via email to