I’m performing my tests on a Motorola Cliq and HTC Hero. I’ve just started implementing my FFT code with Android’s NDK, but so far, my performance tests are looking much better….more like C-performance as expected.

However, what you can try to speed up the process is to use only fixed point arithmetic. Although this wouldn’t be as exact as floating point operation and therefore result in “noise”. Depending on your application, this might still be a suitable solution.

The really “nice” way to calculate the FFT would be to access the OMAPs DSP and do the calculation there. Although it might be a bit of a challenge to access the methods of Texas Instruments’ “dsplink” over JNI.

All in all I say the only way to go if you need speed is through the DSP. Our goal is create another post of how we managed to access it with dsplink but our method is still not complete (we struggle with the fixed point arithmetic) yet. Hopefully we will be able to post a complete “howto calculate a fft with dsplink on the beagleboard using android” by the end of the month.

May I ask what hardware platform you are using?

Cheers
Manuel

So the native solution is fast but not incredibly so: 256*21.9ms still equals 5.6 seconds. That means the native solution is only 2.5 times faster. Or perhaps there’s some start up overhead for that single native fft and the other 255 ffts would perform faster native than 5.6 seconds?

With our java implementation 256 ffts of the length 2048 take 14.3 seconds… so yeah … seems really slow

I’m a bit disappointed, I hoped the jvm was quicker.
It seems to me that you have to go the native way unless there is a trick to make the jvm faster.

It seems that basic operations are incredibly in the Dalvik VM used on mobile phones. For example, this VERY simple iteration over an empty method takes 1.4 seconds even though it doesn’t do anything:

public void performanceTest5() {
for (int i = 0; i < 2000000; i++) {
emptyMethod();
}
}

private int emptyMethod() {
return 0;
}

Doing something a little more complex like calculating the imaginary component of a complex conjugate 2 million times takes 3.2 seconds:

public void performanceTest7() {
for (int i = 0; i > 16) * ((c <> 16)) + (((a & 0X0000FFFF) * ((c <> 16)) >> 16);
y = -y;
y += ((b >> 16) * (c >> 16)) + (((b & 0X0000FFFF) * (c >> 16)) >> 16);

}
}

It appears the Dalvik VM has substantial overhead for even basic computational operations.

I’m curious though how fast these same operations take on the Beagle Board.

We have both implementations, one in Java and the other one in C (port of the kiss fft found here: http://sourceforge.net/projects/kissfft/) which we access over the Java Native Interface. For our application both implementations run fast enough on the Beagle Board.
Yet I am still pretty confident that the JVM should be able to handle the load

Cheers
Manuel

I’m guessing your kiss_fft is in C though…not Java. Or did you port the kiss_ft to Java? We rewrote our FFT code in Java but it’s currently too slow on Android’s JVM. We’re considering reverting back to our C FFT and running it using Android’s native interface.

I will be back in school tomorrow and perform an 2048 FFT with the kiss_fft library. 10 Seconds for 256 FFTs sounds a lot. I am pretty sure we are faster even with our Java implementation.

I will post some results and code here tomorrow.

Cheers
Manuel

I was curious if you’re performing your FFT using Android or not. We’re analyzing audio recorded from an Android phone’s microphone and then performing 256*2048 FFTs on it. The FFTs are taking 10 seconds to process in Java. We’ve considered reimplementing in native code to hopefully get better performance. It seems Android’s Dalvik VM is optimized for memory footprint rather than processing speed.

How fast would you expect your own FFT algorithm to run for 256*2048 FFT? Is it coded in Java or using JNI?

Thanks