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 <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 > >
smime.p7s
Description: S/MIME cryptographic signature
_________________________________________________ For list-related administrative tasks: http://lists.racket-lang.org/listinfo/dev