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 <cleme...@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 < > 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 > > > > > >
_________________________________________________ For list-related administrative tasks: http://lists.racket-lang.org/listinfo/dev