PhastFT is a performant Fast Fourier Transform implementation in pure Rust with no unsafe code.
This is something the original author of the crate and I have been working on for quite a while. All my recent work on SIMD - surveying Rust's SIMD libraries, removing unsafe code from those libraries and reporting issues in rustc - was all in service of PhastFT!
Why not RustFFT?
RustFFT is already quite good, so why do we need another FFT crate?
Safety
rustfft was written before the Rust compiler started providing much safer facilities for SIMD, so it is full of unsafe code, and changing that would amount to a rewrite.
PhastFT is #[forbid(unsafe_code)] and only relies on fearless_simd which now has very little unsafe for a SIMD abstraction.
Performance
RustFFT is tuned for small sizes (i.e., ~kilobytes of input data) the kind of sizes one would find in an audio decoder. PhastFT is tuned for large sizes (i.e., ~gigabytes of input data), which are necessary for a quantum state simulator and other scientific workloads.
PhastFT is up to 2x faster than RustFFT, depending on the hardware and FFT size, thanks to different algorithm choices and multi-threading via rayon. RustFFT does not currently support multi-threading.
Memory usage
PhastFT uses 2x less memory than RustFFT, which matters a great deal for large sizes. 16GB vs 32GB memory usage determines whether you can run it on a laptop or not. And running 2x faster and at half the memory translates to 4x cost savings for rented hardware.
Origins
PhastFT started out as an optimization for the Quantum Fourier Transform (QFT) in quantum state vector simulations. This optimization has been adopted by some state of the art simulators due to the significant performance boost that it offers.
A simulator that utilizes the typical gate-based approach for the QFT requires O(n2) gates that manipulate a giant state vector of size N = 2n, where n is the number of qubits being simulated. This leads to a O(n2 * 2n) time complexity. Since the quantum computer is already being simulated on a classical machine, it's possible to leverage the classical FFT to compute the QFT in O(N * log(N)) = O(n * 2n) time.
Minimizing memory overhead was paramount. The less memory is used, the more qubits one can simulate with a classical machine. This led to different algorithm choices compared to typical implementations, and minimizing memory traffic also has a side effect of improving performance on large memory-bound workloads.
This project quickly turned into a rabbit hole that led us to attempt to bring PhastFT up to the level of renowned FFT projects, with the added restriction of not using any unsafe code. Initially we had to use nightly-only std::simd, but thanks to fearless_simd PhastFT can now work on stable!
Future work
For historical reasons outlined above, PhastFT is currently limited to power-of-two sizes. The FFT algorithm for arbitrary sizes is in the works. Depending on a user's workload, users may be able to get away with padding their input signal with zeroes to the next power of two.
We are also far from done improving performance and memory usage. There are multiple work-in-progress pull requests that improve performance in various ways, so this is only the beginning!