Code for FFT Timing Test


Further to my last two posts on FFTs in AS3, here’s the code I used to measure the speed. On my 2006 MacBook Pro (2GHz Core Duo), with a release build of the swf, this runs in ~660 ms using the most recently posted FFT code. That works out to 330 microseconds per FFT.  (Note that a debug run from within FlexBuilder will be much, much slower – 25x slower than release build for me).

Click below on the (nearly invisible) “show source” link to view the code:

package
{
	import flash.display.*;
	import flash.text.*;
	import flash.utils.getTimer;

	/**
	 * Simple program for testing the performance of an FFT implementation.
	 *
	 * Typical output be something like this:
	 *    1000 fwd-inv pairs of 1024 pt FFTs took 659 ms, or 0.330 ms per FFT.
	 */
	[SWF(width='500',height='30',backgroundColor='0x777777')]
	public class FFTTimingTest extends Sprite
	{
		private const LOG_N:uint = 10;			// Log2 of the FFT length
		private const N:uint = 1 << LOG_N;		// FFT Length (2^LOG_N)
		private const NUM_LOOPS:uint = 1000;	// Number of forward-inverse FFT iterations for timing test

		public function FFTTimingTest()
		{
			var i:uint;

			// Set up a text field to show the results
			stage.align = StageAlign.TOP_LEFT;
			stage.scaleMode = StageScaleMode.NO_SCALE;

			var textField:TextField = new TextField;
			textField.autoSize = TextFieldAutoSize.LEFT;
			textField.selectable = false;
			textField.defaultTextFormat = new TextFormat( 'Verdana', 12, 0xFFFFFF );
			textField.text = 'Performing FFTs...';
			addChild( textField );

			// Create vectors for the real & imaginary
			// components of the input/output data.
			var xRe:Vector.<Number> = new Vector.<Number>(N);
			var xIm:Vector.<Number> = new Vector.<Number>(N);

			// Initialize with some data.
			for ( i = 0; i < N; i++ )
			{
				xRe[i] = Math.cos(2*Math.PI*2*i/N);
				xIm[i] = 0.0;
			}

			// Create and initial the FFT class
			var fft:FFT2 = new FFT2;
			fft.init(LOG_N);

			// Do repeated forward & inverse FFTs
			var startTime:int = getTimer();
			for ( i = 0; i < NUM_LOOPS; i++ )
			{
				fft.run( xRe, xIm, FFT.FORWARD );
				fft.run( xRe, xIm, FFT.INVERSE );
			}
			var endTime:int = getTimer();

			// Compute and display the elapsed time
			var elapsed:int = endTime - startTime;
			var timePerFFT:Number = elapsed / (2.0*NUM_LOOPS);
			textField.text = NUM_LOOPS + " fwd-inv pairs of " + N + " pt FFTs took " + elapsed + " ms, or " + timePerFFT.toFixed(3) + " ms per FFT.";
		}
	}
}
Advertisements

About Gerry Beauregard

I'm a Singapore-based Canadian software engineer, inventor, musician, and occasional triathlete. My current work and projects mainly involve audio technology for the web and iOS. I'm the author of AudioStretch, an audio time-stretching/pitch-shifting app for musicians. Past jobs have included writing speech recognition software for Apple, creating automatic video editing software for muvee, and designing ASICs for Nortel. I hold a Bachelor of Applied Science (Electrical Engineering) from Queen's University and a Master of Arts in Electroacoustic Music from Dartmouth College.
This entry was posted in Audio, Flash, Programming and tagged . Bookmark the permalink.

6 Responses to Code for FFT Timing Test

  1. rigondo says:

    Hello Jerry,

    First of all, thank you for your excellent FFT class.

    I have translated it to HaXe and compiled it to both swf and js. It is possible to compile it for all other HaXe targets, for example PHP or neko, but I was lazy to do that )))

    See my results:
    http://rigondo.com/gerrybeauregard.wordpress.com/FFTTT.swf
    is it faster/slower than yours? HaXe tends to optimize the swf code, due to its language specific features like type inference, but I am not sure if it can be applied to a heavy computing code.

    It is also interesting to see the JS timing, I am sure you’ll be surprised:
    http://rigondo.com/gerrybeauregard.wordpress.com/ffttt_js.html

    Get the hx sources here:
    http://rigondo.com/gerrybeauregard.wordpress.com/fft_haxe.zip

    Looking forward for your opinion.

    • Hi Rigondo, thanks for doing the translation and sharing the results! When I run your JS test (in Safari 5.1 on my mid-2010 MB Pro), the report says “1000 fwd-inv pairs of 1024 pt FFTs took 711 ms”, vs. 289ms for the HaXe-compiled swf. So Javascript is pretty quick – not as fast as an SWF at the moment, but still fast enough for some interesting application. When/if there’s support for Javascript dynamic audio generation in shipping versions of browsers, it might make a good target platform for me 🙂

  2. rigondo says:

    Hello Gerry,

    Did you test the haXe->swf on the same computer, where you had “~660 ms” result? If yes, then HaXe is much better than I could ever imagine :))) Twice as faster, on the same AWM2? Unbelievable, please confirm that it was the same machine :)))

    Well, JS results are vary: it runs dramatically fast on modern browsers, but in older browsers it hangs forever :)))
    For instance I had to reduce the number of runs to 20 to make IE7 finish the test. The result was: “20 fwd-inv pairs of 1024 pt FFTs took 1047 ms, or 26.175 ms per FFT”.
    26 ms! I wonder, were are all my precious CPU cycles gone? Seems like IE interpreter toggles “sleep()” after each expression :)))
    Anyway, as for me, I will never code in JS again, even if someday it will run x10 faster than an FFT written in a pure asm – I had enough of this dynamic prototyping nightmare in my past :))))

    What does really excite me, is thinking about HaXe->CPP->exe conversion – if compiled FFT speed will approach to your original C++ FFT code… We can easily use any sound API available in C++, for example VST. WIth tiny latency or zero with ASIO and similar (compared to 200-1000ms latency in swf). If it is all possible (most likely it is, as far as I tested HaXe->C++ in other applications), then we will have a great opportunity to write one code and make it portable for browser and desktop usage. Looks inspiring, doesn’t it? I am going to research it in the nearest future.

    One more question regarding your FFT code, recently edited line
    if ( inverse == false )
    ??? I haven’t seen such an expressions for ages 🙂 I suppose you did it to accent the fix?

    • I upgraded to a faster laptop last December; the “660 ms” figure was on my previous slower laptop. My latest tests are on a 15″ MacBook Pro 2.66 GHz i7 with 4GB, running OS 10.7, and using Flash Player 10.1.53.64 (not the content debugger version, and not running in a browser).

      On my current laptop, the difference between the original SWF and your haXE->SWF version (FFTTT.swf) is not all that dramatic: 236 ms vs. 206 ms. Still, it’s odd that one could improve performance at all by going through a couple of extra stages of translation! Regardless, both are very slow compared to a compiled C++ FFT implementation running on the same platform, and ridiculously slow compared to highly-optimized DSP libraries (e.g. Accelerate/vDSP on Mac, Intel Integrated Performance Primitives on Windows).

      Using HaXe to translate my FFT from ActionScript to C++ would be kind of amusing given that I based my AS FFT on a C++ one I wrote. 😉

      For high-performance desktop application code, ActionScript basically isn’t a good starting point, even if HaXE could translate it to C++. In AS, one has to write things in unusual ways to get around its frustrating performance bottlenecks and language limitations. For example, in C++ stepping through elements of a vector is extremely fast, and thanks to clever compilers, it’s often as fast to use the natural array indexing notation (x[k]) as it is to use pointers (*px). In AS, by contrast, for maximum performance in sequential access of a bunch of numbers, vectors are OK but linked lists are best… but unfortunately awkward code-wise and bulkier!

      Much as I’d love to be able to write code in just one language, and target many platforms (web, desktop, phone), the reality seems to be that if you want good performance and a good UI, you need to write in whatever the most natural and best-supported language/IDE exists for the target platform. For desktop apps, that means Xcode Objective-C / C++ if you’re targeting for Mac, and probably VisualStudio and C# for Windows.

      That “if (inverse == false)” line is deliberately verbose, in part because it’s a fix, but also because it’s all-too-easy to miss the “!” Boolean “not” operator, especially when squeezed in between other characters, e.g. “if (!inverse)”.

  3. rigondo says:

    I couldn’t resist compiling your FFT Timing Test to C++ 🙂
    Here is the result:
    http://rigondo.com/gerrybeauregard.wordpress.com/fft_cpp.zip
    Launch “cpp/FFTTimingTest.exe” from shell, it’s a command line program.
    You can find your class in
    “cpp/include/le/au/analyze/beauregard/FFT.h”
    and
    “cpp/src/le/au/analyze/beauregard/FFT.cpp”
    and compare it to your original C++ code. See any resemblance? 🙂

    On my machine, it runs only 2.4x faster than swf version. Not too much. I think I need to try your original, non linked list version of FTT – who knows, maybe haxe compiler converts flash.Vector to C++ vectors template system, then our results will be better, but you are right, in this case it means we don’t have an ideal “one language -> many targets” model I was dreaming of.

  4. rigondo says:

    I have translated your original vector-based FFT class to HaXe, compiled to C++ – it executes even slower than linked-list version. Looks like HaXe C++ environment is based on flash architecture somehow…

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s