vector <bool>与数组之间的性能差距

Question

我试图解决C ++中的编码问题，该问题计算素数的数量小于非负数的数量n。

所以我首先想出了一些代码：

int countPrimes(int n) {
    vector<bool> flag(n+1,1);
    for(int i =2;i<n;i++)
    {
        if(flag[i]==1)
            for(long j=i;i*j<n;j++)
                flag[i*j]=0;
    }
    int result=0;
    for(int i =2;i<n;i++)
        result+=flag[i];
    return result;
}

这需要88毫秒，并使用8.6 MB的内存。然后，我将代码更改为：

int countPrimes(int n) {
    // vector<bool> flag(n+1,1);
    bool flag[n+1] ;
    fill(flag,flag+n+1,true);
    for(int i =2;i<n;i++)
    {
        if(flag[i]==1)
            for(long j=i;i*j<n;j++)
                flag[i*j]=0;
    }
    int result=0;
    for(int i =2;i<n;i++)
        result+=flag[i];
    return result;
}

这需要28毫秒和9.9 MB。我真的不明白为什么在运行时间和内存消耗上都存在这样的性能差距。我已阅读相类似的问题这一个和那一个，但我仍然困惑。

编辑：我的运行时间与11.5 MB的存储器替换之后减少至40毫秒vector<bool>与vector<char>。

Answer 1

std::vector<bool>不像其他任何载体。该文件说：

std::vector<bool>是std::vector该类型的可能节省空间的特殊化 bool。

这就是为什么它可能比数组占用更少的内存的原因，因为它可能表示一个字节的多个布尔值，例如位集。它还解释了性能差异，因为访问它不再那么简单了。根据文档，它甚至不必将其存储为连续数组。

Answer 2

std::vector<bool>是特例。它是专门的模板。每个值都存储在单个位中，因此需要位操作。这种内存结构紧凑，但是有一些缺点（例如无法bool在该容器内部使用指针）。

现在，bool flag[n+1];编译器通常将以与for相同的方式分配相同的内存，char flag[n+1];并且它将在堆栈而不是堆上进行分配。

现在，根据页面大小，缓存未命中和i值，一个可能比另一个更快。很难预测（较小的n阵列会更快，但是较大的n结果可能会改变）。

作为一个有趣的实验，您可以更改std::vector<bool>为std::vector<char>。在这种情况下，您将具有与数组类似的内存映射，但是它将位于堆而不是堆栈中。

Answer 3

我想在已经发布的好答案中添加一些评论。

• 在不同的库实现和向量的不同大小之间，std::vector<bool>和之间的性能差异std::vector<char>可能会变化（很大）。

  参见例如那些快速基准：clang ++ / libc ++（LLVM）与g ++ / libstdc ++（GNU）。

• 这：bool flag[n+1];声明了一个可变长度数组，即使某些（符合C99的）编译器提供了扩展功能，该数组也没有成为C ++标准的一部分（由于在堆栈中分配了蜂鸣声，因此具有一些性能优势）。

• 考虑到除2以外的所有素数都是奇数，提高性能的另一种方法是通过仅考虑奇数来减少计算量（和内存占用）。

如果您可以显示不太可读的代码，则可以尝试分析以下代码段。

int countPrimes(int n)
{
    if ( n < 2 )
        return 0;
    // Sieve starting from 3 up to n, the number of odd number between 3 and n are
    int sieve_size = n / 2 - 1;
    std::vector<char> sieve(sieve_size); 
    int result = 1;  // 2 is a prime.

    for (int i = 0; i < sieve_size; ++i)
    {
        if ( sieve[i] == 0 )
        {
            // It's a prime, no need to scan the vector again
            ++result;
            // Some ugly transformations are needed, here
            int prime = i * 2 + 3;
            for ( int j = prime * 3, k = prime * 2; j <= n; j += k)
                sieve[j / 2 - 1] = 1;
        }
    }

    return result;
}

编辑

正如彼得·科德斯（Peter Cordes）在评论中指出的那样，对变量使用无符号类型j

编译器可以尽可能便宜地实现j / 2。C的除以2的幂的除法运算（对于负红利）的舍入语义与向右移位的舍入语义不同，并且编译器并不总是传播足够的值范围证明以证明j总是非负的。

利用所有素数（过去2和3）都小于或大于6的倍数这一事实，也可以减少候选人的数量。