15

受到 Herb Sutter 引人入胜的演讲Not your Father's C++的启发，我决定使用 Microsoft 的 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-element 向量，其中n是 2 的整数幂。任何寻找适用于任何人的快速 FFT 代码的人都n应该查看FFTW。

据我了解，xs[i]C 中用于索引 a 的传统语法vector不进行边界检查，因此不是内存安全的，并且可能成为内存错误的来源，例如非确定性损坏和内存访问违规。所以我xs.at(i)改用了。

现在，我希望这段代码“安全且快速”，但我不是 C++11 专家，所以我想要求改进这段代码，使其更加惯用或高效？

4

1 回答 1

14

我认为您在使用 at() 时过于“安全”。在大多数情况下，使用的索引很容易验证，因为它受到 for 循环中容器大小的限制。

例如

  for(unsigned int i=0; i<zs.size()-1; ++i) { 
    ...
    auto t = zs.at(i);

我唯一留下的 at()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 指令集可能会带来显着的提升（我确实按原样尝试过，并看到了轻微的减速）。

我认为重构以及在 cos 和 sin 调用中使用 MKL 之类的东西应该会带来更大、更不脆弱的改进。而且这些东西都不会依赖于语言（我知道这最初是与 F# 实现进行比较的）。

更新 2

我忘了提到预先计算 zs.size()确实有所作为。

更新 3

还忘了说（直到@xeo 在对 OP 的评论中提醒） i < j 检查之后的块可以归结为 std::swap。这更惯用并且至少具有相同的性能 - 在最坏的情况下应该内联到与编写相同的代码。事实上，当我这样做时，我发现性能没有任何变化。在其他情况下，如果移动构造函数可用，它可能会导致性能提升。

于 2012-04-12T10:58:14.083 回答