Crate phastft

PhastFT

PhastFT is a high-performance, “quantum-inspired” Fast Fourier Transform (FFT) library written in pure Rust.

Features

• Simple implementation using the Cooley-Tukey FFT algorithm
• Performance on par with other Rust FFT implementations
• Zero unsafe code
• Takes advantage of latest CPU features up to and including AVX-512, but performs well even without them
• Selects the fastest implementation at runtime. No need for -C target-cpu=native!
• Optional parallelization of some steps to 2 threads (with even more planned)
• 2x lower memory usage than RustFFT
• Python bindings (via PyO3)

Limitations

• Only supports input with a length of 2^n (i.e., a power of 2) – input should be padded with zeros to the next power of 2
• Requires nightly Rust compiler due to use of portable SIMD

Planned features

• Bluestein’s algorithm (to handle arbitrary sized FFTs)
• More multi-threading
• More work on cache-optimal FFT

How is it so fast?

PhastFT is designed around the capabilities and limitations of modern hardware (that is, anything made in the last 10 years or so).

The two major bottlenecks in FFT are the CPU cycles and memory accesses.

We picked an efficient, general-purpose FFT algorithm. Our implementation can make use of latest CPU features such as AVX-512, but performs well even without them.

Our key insight for speeding up memory accesses is that FFT is equivalent to applying gates to all qubits in [0, n). This creates the opportunity to leverage the same memory access patterns as a high-performance quantum state simulator.

We also use the Cache-Optimal Bit Reversal Algorithm (COBRA) on large datasets and optionally run it on 2 parallel threads, accelerating it even further.

All of this combined results in a fast and efficient FFT implementation competitive with the performance of existing Rust FFT crates, including RustFFT, while using significantly less memory.

Quickstart

Rust

use phastft::{
    planner::Direction,
    fft_64
};

let big_n = 1 << 10;
let mut reals: Vec<f64> = (1..=big_n).map(|i| i as f64).collect();
let mut imags: Vec<f64> = (1..=big_n).map(|i| i as f64).collect();
fft_64(&mut reals, &mut imags, Direction::Forward);

Python

Follow the instructions at https://rustup.rs/ to install Rust, then switch to the nightly channel with

rustup default nightly

Then you can install PhastFT itself:

pip install numpy
pip install git+https://github.com/QuState/PhastFT#subdirectory=pyphastft

import numpy as np
from pyphastft import fft

sig_re = np.asarray(sig_re, dtype=np.float64)
sig_im = np.asarray(sig_im, dtype=np.float64)

fft(a_re, a_im)

Normalization

phastft does not normalize outputs. Users can normalize outputs after running a forward FFT followed by an inverse FFT by scaling each element by 1/N, where N is the number of data points.

Output Order

phastft always finishes processing input data by running a bit-reversal permutation on the processed data.

Benchmarks

PhastFT is benchmarked against several other FFT libraries. Scripts and instructions to reproduce benchmark results and plots are available here.

Contributing

Contributions to PhastFT are welcome! If you find any issues or have improvements to suggest, please open an issue or submit a pull request. Follow the contribution guidelines outlined in the CONTRIBUTING.md file.

License

PhastFT is licensed under MIT or Apache 2.0 license, at your option.

PhastFT vs. RustFFT

RustFFT is another excellent FFT implementation in pure Rust. RustFFT and PhastFT make different trade-offs.

RustFFT made the choice to work on stable Rust compiler at the cost of unsafe code, while PhastFT contains no unsafe blocks but requires a nightly build of Rust compiler to access the Portable SIMD API.

RustFFT implements multiple FFT algorithms and tries to pick the best one depending on the workload, while PhastFT has a single FFT implementation and still achieves competitive performance.

PhastFT uses 2x less memory than RustFFT, which is important for processing large datasets.

What’s with the name?

The name, PhastFT, is derived from the implementation of the Quantum Fourier Transform (QFT). Namely, the quantum circuit implementation of QFT consists of the Phase gates and Hadamard gates. Hence, PhastFT.

Modules

• cobra
  This module provides several implementations of the bit reverse permutation, which is essential for algorithms like FFT.
• options
  Options to tune to improve performance depending on the hardware and input size.
• planner
  The planner module provides a convenient interface for planning and executing a Fast Fourier Transform (FFT). Currently, the planner is responsible for pre-computing twiddle factors based on the input signal length, as well as the direction of the FFT.

Functions

• fft_32
  FFT – Decimation in Frequency. This is just the decimation-in-time algorithm, reversed. This call to FFT is run, in-place. The input should be provided in normal order, and then the modified input is bit-reversed.
• fft_32_with_opts_and_plan
  Same as [fft], but also accepts Options that control optimization strategies, as well as a [Planner] in the case that this FFT will need to be run multiple times.
• fft_64
  FFT – Decimation in Frequency. This is just the decimation-in-time algorithm, reversed. This call to FFT is run, in-place. The input should be provided in normal order, and then the modified input is bit-reversed.
• fft_64_with_opts_and_plan
  Same as [fft], but also accepts Options that control optimization strategies, as well as a [Planner] in the case that this FFT will need to be run multiple times.