アルゴリズム
rust
FFT

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

More than 1 year has passed since last update.

概要

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