RustでFFT (3)自作クレートchfftの紹介

概要

FFTを実装し、チューニングを施していた所、要素数によってはFFTW3やrustfftより速くなったため、クレートとした。

使い方

Cargo.tomlにnumクレート及びchfftクレートを追加する。

Cargo.toml

[dependencies]
num = "*"
chfft = "*"

サンプルコードは次の通り。

extern crate chfft;
extern crate num;
use num::Complex;
use chfft::CFft1D;

fn main() {
    let input = [Complex::new(2.0, 0.0), Complex::new(1.0, 1.0),
                 Complex::new(0.0, 3.0), Complex::new(2.0, 4.0)];

    let mut fft = CFft1D::<f64>::with_len(input.len());

    let output = fft.forward(&input);

    println!("the transform of {:?} is {:?}", input, output);
}

その他backwardメソッドや、スケーリング処理を同時に行うメソッドを用意している。
ただし、現状では1次元の複素数FFTしか実装されていない。

パフォーマンス計測結果

測定環境

MacBook Pro (Retina, 13-inch, Mid 2014)
Processor 2.6GHz Intel Core i5 (Haswell)
Memory 8GB 1600MHz DDR3

RUSTFLAGS='-C target-cpu=native'
rustc 1.19.0 (0ade33941 2017-07-17)

FFTW3の計測はfftwクレートを使用

測定内容

順方向に変換した結果を逆変換する処理を1,000回実施。
総所要時間を2,000で除したものを結果とした。

測定結果

単位はns(ナノ秒)

要素数	chfft	FFTW3	rustfft
2	39	40	65
4	46	47	69
8	68	67	79
16	97	107	129
32	191	214	331
64	363	513	620
128	782	1,084	1,277
256	1,649	2,451	2,183
512	3,732	5,963	5,989
1,024	7,948	13,469	10,802
2,048	19,286	30,287	29,665
4,096	64,376	79,114	60,930
8,192	157,663	188,274	150,720

これより大きい要素数となると、L3キャッシュに乗らなくなる事から非常に遅くなる。
マルチスレッド化、及びロジックの切り替えを行い、高速化を測る必要がある。

ソースコード

githubの次のページを参照
https://github.com/chalharu/chfft