使用VS2012的64位目标中的矢量<bool>性能不佳

Question

对这个课程进行基准测试:

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

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

Sieve s(100000000);

我测试了sizeof(bool)它,它适用1于两个版本.当我vector<bool>用vector<char>64位和32位版本替换性能时,它会变得相同.这是为什么？

以下是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.98秒0.88秒.所以VS2012实施有问题.

我向Microsoft Connect提交了一个错误报告

编辑

下面的许多答案都评论了使用int索引的不足之处.这可能是真的,但即使是伟大巫师本人for (int i = 0; i < v.size(); ++i)也在他的书中使用标准,所以这样的模式不应该导致显着的性能损失.此外,这个问题是在Going Native 2013会议期间提出的,并且C++专家组的主持人评论了他们早期使用size_t索引的建议以及作为size()错误的返回类型.他们说:"我们很抱歉,我们还年轻......"

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

编辑

我在寻找索引内存对齐由粗的尝试i和j并发现这种Instrumented版本:

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.

Answer 1

std::vector<bool>这里没有直接的错.性能差异最终是由于int在循环中使用带符号的32位类型以及编译器的一些相当差的寄存器分配造成的.例如,考虑一下你最内层的循环:

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>"解决"问题,但由于不同的原因:访问a的元素所需的下标计算std::vector<char>比访问元素的元素要简单得多std::vector<bool>.优化器能够为更简单的计算生成更好的代码.

(*)我不做代码生成,我不是汇编或低级性能优化的专家,而是从查看生成的代码,并且鉴于此处报告Visual C++ 2010生成更好代码,我猜在编译器中有改进的机会.我将确保您打开的Connect错误转发给编译器团队,以便他们可以查看.

Answer 2

我vector<bool>在VS2010中进行了测试:32位需要1452ms,而64位需要1264ms才能在i3上完成.

VS2012中的相同测试(此时在i7上)需要700ms(32位)和2730ms(64位),因此VS2012中的编译器出现了问题.也许您可以将此测试用例报告为Microsoft的错误.

UPDATE

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

size_t作为迭代器

使用size_tas iterator时,代码的一部分如下所示:

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

这里,所有指令都使用非常快的CPU寄存器.

int作为迭代器

当使用intas iterator时,相同的部分如下所示:

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