Jon*_*rop 14 c++ performance fft c++11
灵感来自Herb Sutter引人注目的讲座不是你父亲的C++,我决定再使用微软的Visual Studio 2010来看看最新版本的C++.我特别感兴趣的是Herb断言C++"安全而快速",因为我写了很多性能关键代码.
作为基准,我决定尝试用各种语言编写相同的简单FFT算法.
我想出了以下使用内置complex类型和vector集合的C++ 11代码:
#include <complex>
#include <vector>
using namespace std;
// Must provide type or MSVC++ barfs with "ambiguous call to overloaded function"
double pi = 4 * atan(1.0);
void fft(int sign, vector<complex<double>> &zs) {
unsigned int j=0;
// Warning about signed vs unsigned comparison
for(unsigned int i=0; i<zs.size()-1; ++i) {
if (i < j) {
auto t = zs.at(i);
zs.at(i) = zs.at(j);
zs.at(j) = t;
}
int m=zs.size()/2;
j^=m;
while ((j & m) == 0) { m/=2; j^=m; }
}
for(unsigned int j=1; j<zs.size(); j*=2)
for(unsigned int m=0; m<j; ++m) {
auto t = pi * sign * m / j;
auto w = complex<double>(cos(t), sin(t));
for(unsigned int i = m; i<zs.size(); i+=2*j) {
complex<double> zi = zs.at(i), t = w * zs.at(i + j);
zs.at(i) = zi + t;
zs.at(i + j) = zi - t;
}
}
}
请注意,此函数仅适用于 - n元素向量,其中n是2的整数幂.任何寻找适合任何人的快速FFT代码的人都n应该关注FFTW.
据我了解,xs[i]C中用于索引a 的传统语法vector不进行边界检查,因此不具有内存安全性,并且可能是内存错误的来源,例如非确定性损坏和内存访问冲突.所以我用了xs.at(i).
现在,我希望这段代码"安全快速",但我不是C++ 11专家,所以我想要求对这段代码进行改进,以使其更具惯用性或效率？
phi*_*red 14
我认为你在使用at()方面过于"安全".在大多数情况下,使用的索引可以简单地验证为受for循环中容器的大小限制.
例如
for(unsigned int i=0; i<zs.size()-1; ++i) {
...
auto t = zs.at(i);
在()s中我唯一留下的是(i + j)s.它们是否总是受到约束并不是很明显(尽管如果我真的不确定我可能会手动检查 - 但我不熟悉FFT足以在这种情况下发表意见).
每次循环迭代都会重复一些固定计算:
int m=zs.size()/2;
pi * sign
2*j
并且zs.at(i + j)被计算两次.
优化器可能会捕获这些 - 但如果您将此视为性能关键,并且您让计时器测试它,我会将它们从循环中提升(或者,在zs.at(i + j)的情况下),只需参考第一次使用),看看是否会影响计时器.
谈论第二次猜测优化器:我确信对.size()的调用将被内联,至少是对内部成员变量的直接调用 - 但是考虑到你调用它多少次,我也会进行实验为zs.size()和zs.size() - 1引入局部变量.他们更有可能以这种方式进入寄存器.
我不知道所有这些对你的总运行时间有多大差异(如果有的话) - 其中一些可能已被优化器捕获,并且与所涉及的计算相比差异可能很小 - 但值得一试射击.
至于惯用语我的唯一注释,实际上,size()返回一个std :: size_t(通常是unsigned int的typedef - 但是使用该类型更加惯用).如果你确实想要使用auto但是避免警告你可以尝试将ul后缀添加到0 - 但不确定我会说这是惯用的.我想你在这里不使用迭代器已经不那么惯用了,但我明白为什么你不能这样做(很容易).
更新
我尝试了所有的建议,他们都有可测量的性能改进 - 除了i + j和2*j预处理 - 它们实际上导致了轻微的减速!我认为他们要么阻止编译器优化,要么阻止它使用寄存器来处理某些事情.
总的来说,我的性能提高了10%.改善这些建议.我怀疑如果第二个循环块被重构一点以避免跳转,我可能会有更多 - 并且这样做启用SSE2指令集可能会给出一个显着的提升(我确实按原样尝试并看到轻微的减速).
我认为重构,以及使用像MKL这样的cos和sin调用之类的东西应该会给出更大,更不易碎的改进.这些东西都不依赖于语言(我知道这最初是与F#实现进行比较).
更新2
我忘了提到预先计算zs.size()确实有所作为.
更新3
也忘了说(直到@xeo在对OP的评论中提醒)i <j check之后的块可以归结为std :: swap.这更具惯用性,至少在性能上 - 在最坏的情况下应该内联到与编写的相同的代码.确实,当我这样做时,我发现性能没有变化.在其他情况下,如果移动构造函数可用,则可以提高性能.