MISTライブラリのFFT、遅いと感じたわけではないのだけれどFFTWと比べてみようかと思った。

C++, using GeSHi 1.0.8.8
#include <iostream>
#include <wrp/diagnostics.hxx>
#include <ppl.h>
 
#include <mist/mist.h>
#include <mist/fft/fft.h>
 
int main()
{
	const auto N = 16777216;
	typedef double TValue;
	typedef std::complex<TValue> TComplex;
	typedef mist::array1<TComplex> TArray;
 
	auto data = TArray(N);
 
	Concurrency::parallel_for(0, N, [&](size_t n){
		const auto c = M_PI / N;
		data[n].real(sin(c * n));
	});
 
	auto src = data;
	decltype(src) dst;
 
	auto sw = wrp::diagnostics::StopWatch();
 
	sw([&]{ mist::fft(src, dst); });
	std::cout<<sw.GetResultInSec()<<std::endl;
 
	sw([&]{ mist::ifft(dst, src); });
	std::cout<<sw.GetResultInSec()<<std::endl;
}
Parsed in 0.024 seconds at 26.57 KB/s

StopWatchはQueryPerformanceCounterで時間間隔測るクラス(crono対応とかHPET無い環境とかLinuxとか未対応)。operator()で受け取った関数オブジェクトの所要時間を測ったり、GetResultInSec()で計測した時間間隔を秒単位で返します。

parallel_forの中で元データとして1半周期分の正弦波を作っています。データはN件、mist::array1<std::complex<double>>型で作っています。MISTライブラリのFFTはcomplex<double>でもdoubleでも扱える。

FFTは27行目のmist::fft、30行目のmist::ifftとシンプル。このコードの結果は以下の通り。

2.1442 [sec] (FFT)
2.02586 [sec] (iFFT)

※Phenom II 940、Windows 7、VS2010、x64

FFTWも出来合いのDLLなり、ソースコードとVS2010のソリューションファイルを拾ってビルドするだけなので導入の手間はそれほどかからない。でも、FFTWはC言語向けにつくられている事もあり、C++に慣れているとちょっと使い勝手は悪い気がする。FFTW++というのもあるようだけど今回はスルー。

C++, using GeSHi 1.0.8.8
	auto src = static_cast<fftw_complex*>(fftw_malloc(sizeof(fftw_complex) * N));
	auto dst = static_cast<fftw_complex*>(fftw_malloc(sizeof(fftw_complex) * N));
 
	auto pf = fftw_plan_dft_1d(N, src, dst, FFTW_FORWARD, FFTW_ESTIMATE);
	auto pb = fftw_plan_dft_1d(N, dst, src, FFTW_BACKWARD, FFTW_ESTIMATE);
 
 	fftw_execute(pf);
	fftw_execute(pb);
 
	fftw_destroy_plan(pf);
	fftw_destroy_plan(pb);
	fftw_free(src);
	fftw_free(dst);
 
Parsed in 0.017 seconds at 25.57 KB/s

メモリ確保、FFT、iFFT、メモリ解放の部分だけ抜粋。fftw_plan_dft_1dてのがMISTでいうfftにarray1dを突っ込みますよに相当、プランのFFTW_FORWARDとFFTW_BACKWARDがFFTとiFFTに対応。正規化してくれないので変換結果がデカくなるのもMISTより不便。それはそうと、同様に変換速度を測ってみた。

3.59038 [sec] (FFT)
3.56843 [sec] (iFFT)

(´・ω・`)

FFTW使ったらMIST付属のFFTより速いかもとか思ってたのでしょぼーん…とも一概に言えなくい。MISTの方が使いやすいし、まあいっかー…と。

＜追記＞

MIST内蔵のFFTエンジンはこの界隈ではお馴染み Ooura's Mathematical Software Packages のアルゴリズムが実装されています。