34

对这个类进行基准测试：

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适用于两个版本。当我用64 位和 32 位版本替换vector<bool>时，性能变得相同。vector<char>这是为什么？

以下是S(100000000)（发布模式，首先是 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 会议期间提出的，C++ 大师的主持小组评论了他们早期建议使用size_tfor indexing 和 as a return type of size()as 错误。他们说：“对不起，我们还年轻……”

这个问题的标题可以改写为：从 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.

4

3 回答 3

37

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;
}

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

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

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

于 2013-04-18T06:31:29.670 回答
25

我vector<bool>在 VS2010 中对此进行了测试：32 位需要 1452 毫秒，而 64 位需要 1264 毫秒才能在 i3 上完成。

VS2012中同样的测试（这次在i7上）需要700ms（32位）和2730ms（64位），所以VS2012中的编译器有问题。也许您可以将此测试用例作为错误报告给 Microsoft。

更新

问题是VS2012编译器在使用int作为迭代器时，内部for循环中的部分代码使用了临时堆栈变量。下面列出的组件部分是代码里面的一部分 ，<vector>在.+= operatorstd::vector<bool>::iterator

size_t 作为迭代器

用作迭代器时size_t，部分代码如下所示：

or  rax, -1
sub rax, rdx
shr rax, 5
lea rax, QWORD PTR [rax*4+4]
sub r8, rax

在这里，所有指令都使用非常快的 CPU 寄存器。

int 作为迭代器

当int用作迭代器时，相同的部分如下所示：

or  rcx, -1
sub rcx, r8
shr rcx, 5
shl rcx, 2
mov rax, -4
sub rax, rcx
mov rdx, QWORD PTR _Tmp$6[rsp]
add rdx, rax

在这里您可以看到正在使用的 _Tmp$6 堆栈变量，这会导致速度变慢。

将编译器指向正确的方向

有趣的是，您可以通过直接使用将编译器指向正确的方向vector<bool>::iterator。

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

  Sieve (int n = 1) {
    isPrime.assign(n + 1, true);

    std::vector<bool>::iterator it1 = isPrime.begin();
    std::vector<bool>::iterator end = it1 + n;
    *it1++ = false;
    *it1++ = false;
    for (int i = 2; i <= (int)sqrt((double)n); ++it1, ++i)
        if (*it1)
            for (std::vector<bool>::iterator it2 = isPrime.begin() + i * i; it2 <= end; it2 += i)
                *it2 = false;
  }
};
于 2013-04-17T21:18:57.023 回答
2

vector<bool>是一个非常特殊的容器，专门为每个项目使用 1 位，而不是提供正常的容器语义。我怀疑编译 64 位时位操作逻辑要昂贵得多（它仍然使用 32 位块来保存位或其他原因）。vector<char>行为就像一个正常vector的，所以没有特殊的逻辑。

您也可以使用deque<bool>which 没有专业化。

于 2013-04-17T21:13:48.027 回答