Hacker News Reader

Comment by tsomctl | Hacker News Reader

How does it compare to the two giants, FFTW and Intel IPP? (http://www.fftw.org/speed/CoreDuo-3.0GHz-icc64/). In particular, I don't see any mention of cache awareness. I don't know much about FFTW, but all the parts of Intel IPP that I've used are ridiculously fast, and I'm sure Intel is using all the tricks they can to speed up the cache (ie proper layout, cache prefetch). For example, Intel's fft forward transform on complex floats is about as fast as memcpy with a cold cache.

View on HN

It's not going to compare well. The assembly is a pretty simple port of a basic C implementation of radix 2 Cooley-Tukey FFTs. The author gets ~2x speedup from writing this in assembly.

In contrast, highly optimized FFT implementations that use higher radix transforms and other FFT algorithm optimizations, along with SIMD and good C (not necessarily assembly) will get speedups of 10-40x over basic C implementations with a radix 2 implementation: http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.153... (Implementing FFTs in practice by Frigo and Johnson, of FFTW)

FWIW, it is possible to significantly beat FFTW, if you highly optimize for particular cases: https://github.com/halide/Halide/pull/977. I don't have data handy, but I've seen similar results comparing against IPP.

Probably a massive difference. The generic X86 IPP implementation of 1 dimensional FFT is around 8x faster than the naive FFT variants I've tried. Intel also claims an effective 5.5x improvement over that when targeting AVX2 (so Haswell and later). Essentially, a 40x is not unusual.

When it comes to insanely optimized code, most of Intel's libraries (MKL, VSL, IPP, DAAL) are hard to beat.

FFTW is one of the seminal examples of the importance of cache awareness, if I remember my history correctly. As I understand it, the reason the fftw authors (Matteo Frigo and Steven G. Johnson) won the Wilkinson prize was essentially because fftw exemplified the importance of cache-aware algorithms, as opposed to blindly optimizing number of operations.

I don't know, but I would guess that intel's implementation post-dates fftw?

Reply on news.ycombinator.com