On 2010-08-03 , at 22:21 , Glen Pike wrote: > You should maybe look using "twiddle" factors and creating these in the > init too - so you are not doing cosine / sin math in the butterfly loops?
Thanks for the suggestion. I've tried both ways, and it's actually a tiny bit faster to compute the twiddle factors on the fly, at least compared to pre-computing all of them and storing them in a Vector. (In C++, it's definitely faster to pre-compute the twiddle factors. Slowness is language dependent). In any case, the total number of calls to sin and cos is actually quite small - only one each per stage, the number of stages being log2 of the FFT length (e.g. 10 for a 1024 pt FFT). Successive twiddle factors are computed by complex multiply of a rotated unit vector, which is pretty quick (4 multiplies & 2 adds). Turns out the really speed killer is accessing elements of Vectors. In an email a few hours ago, Andre Michelle (author of core stuff for the amazing audiotool.com) gave me an excellent suggestion: use linked lists instead of Vectors. For accessing elements in sequence, it's much faster to follow a link to the next element than to access using a Vector of elements and an incrementing index into that Vector. Using that tip, plus a few other optimizations, I've now got a new FFT that runs at *double* the speed of my previous one. It's nearly 30x as fast as the FFT in as3mathlib. It's still 3.5x slower than my C++ code, but I guess that's the price one pays for using a virtual machine. I'll post the new code in my blog soon... -Gerry On 2010-08-03 , at 22:21 , Glen Pike wrote: > Hi, > > You should maybe look using "twiddle" factors and creating these in the > init too - so you are not doing cosine / sin math in the butterfly loops? > > There are some FFT algorithm optimisations about which init these and just > do multiplication / addition in the main loop - you might have to google > around for "fft twiddle" and "fft bitrev" to find them.. > > HTH > > Glen > > On 03/08/2010 15:10, Karim Beyrouti wrote: >> Just a thought - try moving the variable declarations out of the loops: >> >> >> http://www.rozengain.com/blog/2007/05/01/some-actionscript-30-optimizations/ >> http://osflash.org/as3_speed_optimizations >> >> http://gamedevjuice.wordpress.com/2008/02/15/seven-tips-about-performance-optimization-in-actionscript-3/ >> >> Might help a little... do you have some test code lying about so we can >> compare / optimise?.... >> >> >> Best >> >> >> - karim >> >> On 3 Aug 2010, at 04:40, Gerry Beauregard wrote: >> >> >>> On 2010-08-03 , at 06:07 , Patrick Matte wrote: >>> >>>> Maybe check this http://blog.inspirit.ru/?p=405 >>>> >>> Hey Patrick, thanks for the link (to Eugene Zatepyakin's "Fast Fourier >>> Transform for Flash"). It looks like an interesting implementation, but it >>> uses Alchemy. I've been reading up more on Alchemy, and according to Adobe >>> it's pre-release, and they advise that it "not be used to generate code for >>> use in production". In any case, the Alchemy APIs make passing arbitrary >>> data to/from the FFT a bit clunky, e.g. passing a Vector of Numbers >>> requires conversion to a ByteArray first. >>> >>> For what it's worth, I've posted my pure-AS3 FFT implementation here: >>> http://gerrybeauregard.wordpress.com/ >>> >>> >>> >>> _______________________________________________ >>> Flashcoders mailing list >>> [email protected] >>> http://chattyfig.figleaf.com/mailman/listinfo/flashcoders >>> >> >> _______________________________________________ >> Flashcoders mailing list >> [email protected] >> http://chattyfig.figleaf.com/mailman/listinfo/flashcoders >> >> >> > > _______________________________________________ > Flashcoders mailing list > [email protected] > http://chattyfig.figleaf.com/mailman/listinfo/flashcoders _______________________________________________ Flashcoders mailing list [email protected] http://chattyfig.figleaf.com/mailman/listinfo/flashcoders
