对此类进行基准测试:

struct Sieve {
  std::vector<bool> isPrime;

  Sieve (int n = 1) {
    isPrime.assign (n+1, true);
    isPrime[0] = isPrime[1] = false;

    for (int i = 2; i <= (int)sqrt((double)n); ++i)
      if (isPrime[i]) 
        for (int j = i*i; j <= n; j += i)
          isPrime[j] = false;
  }
};

当调用大量构造函数时，64 位二进制与 32 位版本(发布版本)的性能(CPU 时间)差 3 倍以上，例如

Sieve s(100000000);

我测试了 sizeof(bool)它是1两个版本。 当我替换 vector<bool>与 vector<char> 64 位和 32 位版本的性能相同。这是为什么呢？

这里是 S(100000000) 的运行时间( Release模式，先32位，后64位)):

vector<bool> 0.97s 3.12s vector<char> 0.99s 0.99s vector<int> 1.57s 1.59s

我还用 VS2010 进行了健全性测试(由 Wouter Huysentruit 的响应提示)，结果为 0.98s 0.88s。所以VS2012的实现有问题。

我向 Microsoft Connect 提交了错误报告

编辑

下面的许多答案评论了使用 int 的不足之处用于索引。这可能是真的，但即使是大巫师本人也在使用标准 for (int i = 0; i < v.size(); ++i)在他的书中，因此这种模式不应导致显着的性能损失。此外，这个问题是在 Going Native 2013 session 上提出的，C++ 大师的主持小组评论了他们早期使用 size_t 的建议。用于索引并作为 size() 的返回类型作为一个错误。他们说:“对不起，我们还年轻……”

这个问题的标题可以改写为:从 VS2010 升级到 VS2012 时，此代码的性能下降超过 3 倍。

编辑

我粗略地尝试查找索引的内存对齐 i和 j并发现这个检测版本:

struct Sieve {
  vector<bool> isPrime;

  Sieve (int n = 1) {
    isPrime.assign (n+1, true);
    isPrime[0] = isPrime[1] = false;

    for (int i = 2; i <= sqrt((double)n); ++i) {
      if (i == 17) cout << ((int)&i)%16 << endl;
      if (isPrime[i]) 
        for (int j = i*i; j <= n; j += i) {
          if (j == 4) cout << ((int)&j)%16 << endl;
          isPrime[j] = false;
        }
    }
  }
};

现在自动神奇地运行得很快(仅比 32 位版本慢 10%)。这种和 VS2010 的性能使得很难接受优化器理论在处理 int 时存在固有问题。索引而不是 size_t .

最佳答案

std::vector<bool>这不是直接的错。性能差异最终是由您使用带符号的 32 位 int 引起的。输入你的循环和编译器的一些相当糟糕的寄存器分配。例如，考虑您最内层的循环:

for (int j = i*i; j <= n; j += i)
    isPrime[j] = false;

这里，j是一个 32 位有符号整数。用于isPrime[j]时，但是，它必须提升(和符号扩展)为 64 位整数，才能执行下标计算。编译器不能只处理 j作为 64 位值，因为这会改变循环的行为(例如，如果 n 为负数)。编译器也无法使用 32 位数量执行索引计算 j ，因为这会改变该表达式的行为(例如，如果 j 为负数)。

因此，编译器需要使用 32 位 j 为循环生成代码那么它必须生成代码来转换 j为下标计算的 64 位整数。它必须对带有 i 的外循环执行相同的操作.不幸的是，在这种情况下，编译器似乎分配寄存器相当糟糕^(*)——它开始将临时变量溢出到堆栈中，从而导致您看到的性能下降。

如果您将程序更改为使用 size_t在任何地方(x86 上是 32 位，x64 上是 64 位)，您都会观察到性能与 x86 相当，因为生成的代码只需要使用一种大小的值:

Sieve (size_t n = 1)
{
    isPrime.assign (n+1, true);
    isPrime[0] = isPrime[1] = false;

    for (size_t i = 2; i <= static_cast<size_t>(sqrt((double)n)); ++i)
        if (isPrime[i]) 
            for (size_t j = i*i; j <= n; j += i)
                isPrime[j] = false;
}

无论如何你都应该这样做，因为混合有符号和无符号类型，尤其是当这些类型的宽度不同时，是很危险的，并且可能导致意外错误。

请注意，使用 std::vector<char>也“解决”了这个问题，但出于不同的原因:访问 std::vector<char> 的元素所需的下标计算比访问 std::vector<bool> 的元素要简单得多.优化器能够为更简单的计算生成更好的代码。

(*) 我不从事代码生成方面的工作，而且我几乎不是汇编或低级性能优化方面的专家，但从查看生成的代码来看，鉴于这里报告说 Visual C++ 2010 生成更好的代码，我猜编译器有改进的机会。我会确保将您打开的 Connect 错误转发给编译器团队，以便他们查看。

关于c++ - VS2012 在 64 位目标中 vector <bool> 的性能不佳，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/16070000/