From: Doug Williams (m.douglas.williams at gmail.com)Date: Tue Oct 19 08:17:34 EDT 2010 |

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>

Posted on the dev mailing list. |