Re: [Flashcoders] A fast FFT in Flash?
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 >>> Flashcoders@chattyfig.figleaf.com >>> http://chattyfig.figleaf.com/mailman/listinfo/flashcoders >>> >> >> ___ >> Flashcoders mailing list >> Flashcoders@chattyfig.figleaf.com >> http://chattyfig.figleaf.com/mailman/listinfo/flashcoders >> >> >> > > ___ > Flashcoders mailing list > Flashcoders@chattyfig.figleaf.com > http://chattyfig.figleaf.com/mailman/listinfo/flashcoders ___ Flashcoders mailing list Flashcoders@chattyfig.figleaf.com http://chattyfig.figleaf.com/mailman/listinfo/flashcoders
Re: [Flashcoders] A fast FFT in Flash?
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 Flashcoders@chattyfig.figleaf.com http://chattyfig.figleaf.com/mailman/listinfo/flashcoders ___ Flashcoders mailing list Flashcoders@chattyfig.figleaf.com http://chattyfig.figleaf.com/mailman/listinfo/flashcoders ___ Flashcoders mailing list Flashcoders@chattyfig.figleaf.com http://chattyfig.figleaf.com/mailman/listinfo/flashcoders
Re: [Flashcoders] A fast FFT in Flash?
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 > Flashcoders@chattyfig.figleaf.com > http://chattyfig.figleaf.com/mailman/listinfo/flashcoders ___ Flashcoders mailing list Flashcoders@chattyfig.figleaf.com http://chattyfig.figleaf.com/mailman/listinfo/flashcoders
Re: [Flashcoders] A fast FFT in Flash?
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 Flashcoders@chattyfig.figleaf.com http://chattyfig.figleaf.com/mailman/listinfo/flashcoders
Re: [Flashcoders] A fast FFT in Flash?
Maybe check this http://blog.inspirit.ru/?p=405 > From: Gerry Beauregard > Reply-To: Flash Coders List > Date: Mon, 2 Aug 2010 09:59:05 +0800 > To: Flash Coders List > Subject: [Flashcoders] A fast FFT in Flash? > > > Does anyone know of a really good, fast FFT implementation in AS3? > > I write a lot of audio signal processing code in AS3, and some of it uses FFTs > (Fast Fourier Transforms) which can be pretty CPU intensive. I have my own > AS3 FFT which is pretty good (about 15x faster than the one in as3mathlib), > but is nonetheless ~7x slower than my own C++ FFT on which I based my AS3 > version, and over 20x slower than highly optimized native FFT implementations > (e.g. the one in Intel IPP). > > I've looked into Alchemy, but unfortunately it doesn't appear to have any > efficient means to pass Vectors of Numbers :-( I've come across a few blogs > where people discuss the possibility of doing FFTs with PixelBender, but I > haven't found any implementations yet. > > -Gerry Beauregard > > > ___ > Flashcoders mailing list > Flashcoders@chattyfig.figleaf.com > http://chattyfig.figleaf.com/mailman/listinfo/flashcoders This e-mail is intended only for the named person or entity to which it is addressed and contains valuable business information that is proprietary, privileged, confidential and/or otherwise protected from disclosure. If you received this e-mail in error, any review, use, dissemination, distribution or copying of this e-mail is strictly prohibited. Please notify us immediately of the error via e-mail to disclai...@tbwachiat.com and please delete the e-mail from your system, retaining no copies in any media. We appreciate your cooperation. ___ Flashcoders mailing list Flashcoders@chattyfig.figleaf.com http://chattyfig.figleaf.com/mailman/listinfo/flashcoders
[Flashcoders] A fast FFT in Flash?
Does anyone know of a really good, fast FFT implementation in AS3? I write a lot of audio signal processing code in AS3, and some of it uses FFTs (Fast Fourier Transforms) which can be pretty CPU intensive. I have my own AS3 FFT which is pretty good (about 15x faster than the one in as3mathlib), but is nonetheless ~7x slower than my own C++ FFT on which I based my AS3 version, and over 20x slower than highly optimized native FFT implementations (e.g. the one in Intel IPP). I've looked into Alchemy, but unfortunately it doesn't appear to have any efficient means to pass Vectors of Numbers :-( I've come across a few blogs where people discuss the possibility of doing FFTs with PixelBender, but I haven't found any implementations yet. -Gerry Beauregard ___ Flashcoders mailing list Flashcoders@chattyfig.figleaf.com http://chattyfig.figleaf.com/mailman/listinfo/flashcoders
