FFTs Using AltiVec on Linux and Mac OS X

GregAllen writes "After searching for a good open-source AltiVec implementation of the Fast Fourier Transform (FFT), I have put together the AltiVec FFT page. It has all of the source, some benchmarks, and runs on Mac OS X or LinuxPPC. I even compared it to the venerable (but scalar) FFTW."

Comments

Re:What's a FFT

[ndevice]

an fft is a fast fourier transform. It is commonly used to transform data from the time domain to the frequency domain.

What this means is that is if you have a time-varying signal like audio for example, you can run an fft on it and get a frequency analysis on the sound. i.e. from the sound in a waveform format, after an fft, you can pick out which are the dominant frequencies, and what the relationship between frequencies are.

Although the fft is strictly not necessary because it is, after all, just a transform, it turns out that many media compression techniques use them because humans aren't as discriminating in the frequency domain so if you do lossy compression in the frequency domain, we won't notice/mind as much.

fyi, you do an fft any time you view a .jpg, or listen to an .mp3, or watch a dvd, etc. Lots of uses for them, and that doesn't even get into the engineering/scientific uses...

Re:What's a FFT

[Anonymous Coward]

FFT = Fast Fourier Transform. It's used to convert a signal from time domain to frequency domain, which is closer to the way human perception works. For example: To record audio data, air pressure changes over time are sampled. An FFT of a sequence of samples gives the freqencies which are in that block. Most current media compression schemes make use of this transformation to identify the data components which are least noticeable when left out or encoded with reduced precision.

Re:What's a FFT

[nathanh]

fyi, you do an fft any time you view a .jpg, or listen to an .mp3, or watch a dvd, etc.

You use a FFT anytime you ENCODE a .jpg, or an .mp3, or a DVD. When you view or listen or watch you are using an Inverse FFT.

And to be very specific, I think all your examples use DCT (Discrete Cosine Transform) and not FFT. JPEG definitely does. Very good overview here

Not really for OSX unless you're porting to linux

[RalphBNumbers]

Note that MacOS X has a library called vDSP which is as much as twice as fast as vBigDSP on split data. Source code is not available, making it difficult to port to Linux.

So unless you're writing something for OSX and linux, want to use the same libs on both and are willing to sacrifice a 2x speed increase, you'd be well advised not to use this library package for FFTs on OSX.

Linux is faster than macosx

[dcstimm]

I use Gentoo Linux on my ibook and since I can compile all my code for my g3 cpu, I notice a huge speed increase between linux and macosx. Since My cpu doesnt take advantage of altivec apps that are compiled for altivec run slow on a g3. Apps that are directly compiled for a g3 will run 20-30% faster. Of course apple could make Macosx faster for g3 people if they recompiled the OS with out altivec support, but they cant do that. With My g4 system I dont see a huge speed difference in linux unless I use more aggressive gcc optimizations. Anyway, Linux on a g3 will always run faster than macosx on a g3.

Re:Not really for OSX unless you're porting to lin

[GregAllen]

It's important to point out that the "traditional way" to store complex numbers (and do an FFT) is with interleaved data. If your application uses interleaved data (and most do), then this library is for you. Split data is being used more because of the obvious performance improvements, but you have to change your code (and your mindset) to use it.

I've updated it to say: as much as twice as fast as vBigDSP on split data (but about the same on interleaved data).

I'd like to get an open-source split-data version to add to the site, so Linux users get good split-data FFTs, too.

Old story?

[MS_is_the_best]

I wonder when this benchmark was published, because the FFTW homepage already offers a 3.0beta for download, including SIMD support (SSE/SSE2/3DNow!/Altivec) support.

For applications where raw speed is not very important I recommend everyone to use the fftw library, it is already installed on a lot of systems and easy in use. Very fast are Intel's SDK version and DJ Bernstein's (only 256 points).

Further senseless nit-picking

[melquiades]

Although people often use the terms interchangably, strictly speaking the Fourier Transform is the mathematical operation (like "sort") and the FFT is a particular way of computing it (like "quicksort").

The FFT is a particularly FAST algorithm for computing Fourier Transforms, with O(n log n) instead of O(n^2) for the naive algorithm -- thus the name. I believe that there is a comparably fast and very similar algorithm for computing the DCT, which doesn't really have a separate name.

You use a FFT anytime you ENCODE a .jpg, or an .mp3, or a DVD. When you view or listen or watch you are using an Inverse FFT.

True, though an inverse Fourier tranform is simply the Fourier transform run through a complex complement and multiplication by a constant. The FFT and the IFFT are essentially the same algorithm.

And to be very specific, I think all your examples use DCT (Discrete Cosine Transform) and not FFT.

Right ... though again, the DCT and the FT are essentially the same operation -- the DCT is just the real part of the FT (the FT is complex).

Re:Further senseless nit-picking

[plastik55]

Right ... though again, the DCT and the FT are essentially the same operation -- the DCT is just the real part of the FT (the FT is complex).

No -- the DCT spaces its components at half-wavenumbers while the FT has components spaced at integer wavenumbers. So only every other DCT components would be equal to the real part of an FT component. (that isn't strictly true, either, since most DCTs have a half-sample offset compared to FT)

Interestingly enough it wasn't until the '90s that a "fast" or O(n log n) algorithm for calculating the DCT was found--this is well after it had become widely used in compression.

FFTW 3.0 beta has been released

[Dominic_Mazzoni]

Well, FFTW 3.0 beta has been released, and it includes Altivec support. I would be very surprised if this new FFTW wasn't extremely competitive with all the benchmarks presented on this page, if not better.

Anyone want to add it to the benchmark?

Have you already seen djbfft?

[twoflower]

Have you tried djbfft? You might want to, as it's quality software from a hardcore mathematician.

Re:Not really for OSX unless you're porting to lin

[GregAllen]

by using interleaved data, you are benchmarking a scalar vDSP against your other scalar algorithms

This is clearly not the case. On an 800 MHz G4, the peak scalar performance is 1600 MFLOPS. You're lucky to get 800 MFLOPS, just like the (very good) scalar FFTW. That's exactly why we have SIMD/AltiVec.

I'm using Apple's ctoz() and ztoc() to convert from interleaved to split and back, and getting "about the same as vBigDSP" -- that's 1-2 GFLOPS. Without these conversions, that curve peaks at about 4 GFLOPS.

You also could have checked your incorrect assumption if you had looked at the provided source code.

Re:What about Matlab?

[coult]

Umm...not sure what is meant by "OS X graphical version", but I'm running Matlab for OS X and its the full version, does everything that it does on other platforms, including fancy graphics. It works really well with Apple's X11 because then all the graphics are hardware accelerated.