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.orgwrote:
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
