v0.7.3<\/code>. This post is a full measurement of where it stands: against FFTW3, against the other Go FFT libraries, at powers of two and at the lengths that are actually awkward, with and without its assembly.<\/p>\n\n\n\n\n\n\n\nHow this was measured<\/h2>\n\n\n\n
The numbers come from go-fft-bench<\/a>, a harness that runs five FFT libraries over the same lengths in one process:<\/p>\n\n\n\n\n- algo-fft<\/strong> \u2014 this library, both precisions.<\/li>\n
- FFTW3<\/strong>, through cgo bindings. The reference implementation of “fast”, and the baseline everything else is divided by. It is C with generated codelets and decades of tuning; the distance to it is the honest measure.<\/li>\n
- gonum<\/strong> (
dsp\/fourier<\/code>) \u2014 the pure-Go library most Go projects actually reach for.<\/li>\n- go-dsp<\/strong> \u2014 pure Go, arbitrary lengths via Bluestein, no reusable plan.<\/li>\n
- takatoh\/fft<\/strong> \u2014 a compact radix-2 implementation, power-of-two only.<\/li>\n<\/ul>\n\n\n\n
Five methodological points, because a benchmark you cannot criticise is a benchmark you cannot trust:<\/p>\n\n\n\n
\n- Steady state, plan reused.<\/strong> Every library that has a plan object gets one, built outside the timing loop. go-dsp and takatoh have no such API and allocate on every call \u2014 that is their design, and it shows up as a fixed tax rather than as a measurement artefact.<\/li>\n
- Libraries are interleaved per length<\/strong>, not run in five long blocks. This is a 15 W laptop part that throttles under sustained load, so absolute numbers drift downward over a sweep. Interleaving puts that drift on every library at a given length equally, which is what makes the ratios<\/em> trustworthy even where the absolute figures are a laptop’s.<\/li>\n
- The runner refuses to start on a busy machine.<\/strong> It reads the load average and declines above a threshold derived from the core count. Nothing downstream can distinguish a throttled result from a slow library, so the check has to happen before the run rather than in a caveat afterwards.<\/li>\n
- Correctness is a precondition, not a footnote.<\/strong> Every non-power-of-two length is cross-checked against gonum’s transform of the same input before it is allowed into the benchmark. A fast wrong answer is not a result, and this is exactly where FFT libraries quietly fail: hand a radix-2 implementation n = 1000 and it will cheerfully return something.<\/li>\n
- The y-axis on the throughput charts is pseudo-MFLOPS<\/strong>, the
5\u00b7n\u00b7log₂n \/ t<\/code> convention from the FFTW benchmarks. Nobody executes exactly that many operations. Its only job is to divide out the O(n log n) growth so that n = 8 and n = 32768 can share an axis: a flat curve means “scaling as the algorithm says it should”, and a dip means a length fell off a fast path.<\/li>\n<\/ol>\n\n\n\nEverything below is one machine \u2014 an i7-1255U, Go 1.26.1, Linux, GOAMD64=v3<\/code> \u2014 and one machine is not a benchmark suite. Treat the ratios as real and the absolute figures as indicative.<\/p>\n\n\n\nPowers of two<\/h2>\n\n\n\n![\"Throughput](\"\/wordpress\/wp-content\/uploads\/algo-fft-throughput-pow2.png\")
Complex128 forward transforms, powers of two. Higher is better.<\/figcaption><\/figure>\n\n\n\nTwo groups, and the gap between them is the whole story of writing numerical code in Go. algo-fft and FFTW3 are in one; gonum, go-dsp and takatoh are in the other, a factor of ten to fifty below. As a ratio against FFTW3 across all thirteen lengths, geometric mean: algo-fft 1.37\u00d7, gonum 0.09\u00d7, go-dsp 0.02\u00d7, takatoh 0.03\u00d7<\/strong>.<\/p>\n\n\n\n![\"Speed](\"\/wordpress\/wp-content\/uploads\/algo-fft-speedup-vs-fftw.png\")
The same data as a ratio against FFTW3. Note the log scale: the lower three libraries are one to two orders of magnitude down, not a few lines down.<\/figcaption><\/figure>\n\n\n\nalgo-fft is at or above FFTW3 across the whole power-of-two ladder. It wins by a lot below n = 64 \u2014 5.3\u00d7 at n = 8<\/strong>, where the transform is 6 ns and FFTW3’s 34 ns is mostly the cost of dispatching through a plan at all \u2014 and then tracks it within about \u00b110% from 128 upward, dipping to 0.91\u00d7 at n = 1024 and rising to 1.27\u00d7 at 8192.<\/p>\n\n\n\nAgainst the rest of the Go field it was never close. At n = 1024, one forward complex128 transform costs 1.35 \u00b5s in algo-fft, 22.0 \u00b5s in gonum, 45.0 \u00b5s in go-dsp and 76.9 \u00b5s in takatoh<\/strong>, against FFTW3’s 1.24 \u00b5s.<\/p>\n\n\n\nWhat the assembly buys<\/h2>\n\n\n\n
algo-fft ships 229 registered codelets \u2014 kernels bound to one specific transform length, so that a length like 1024 runs straight into a routine that knows it is 1024 and skips every dispatch decision. They are distributed unevenly on purpose:<\/p>\n\n\n\n
![\"Speedup](\"\/wordpress\/wp-content\/uploads\/algo-fft-simd-vs-purego.png\")
![\"The](\"\/wordpress\/wp-content\/uploads\/algo-fft-purego-vs-competitors.png\")
![\"Geometric](\"\/wordpress\/wp-content\/uploads\/algo-fft-nonpow2-by-class.png\")
![\"Every](\"\/wordpress\/wp-content\/uploads\/algo-fft-nonpow2-detail.png\")
![\"Single](\"\/wordpress\/wp-content\/uploads\/algo-fft-precision.png\")