vector<bool> 和 array 之间的性能差距

Question

我试图解决 a coding problem in 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。我真的不明白为什么运行时间和内存消耗都有这样的性能差距。我已经阅读了诸如 this one and that one 之类的相关问题，但我仍然感到困惑。

编辑：在将 vector<bool> 替换为 vector<char> 后，我将运行时间减少到 40 毫秒，内存为 11.5 MB。

Answer 1

std::vector<bool> 不同于任何其他向量。 documentation 表示：

std::vector<bool> is a possibly space-efficient specialization of std::vector for the type bool.

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

Answer 2

std::vector<bool> 是特例。它是专门的模板。每个值都存储在单个位中，因此需要进行位操作。这个内存紧凑但有几个缺点（比如没有办法在这个容器内有一个指向 bool 的指针）。

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

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

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

Answer 3

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

std::vector<bool> 和 std::vector<char> 之间的性能差异可能因不同的库实现和不同大小的向量而异（很多）。

参见例如那些快速的长凳：clang++ / libc++(LLVM) vs. g++ / libstdc++(GNU).
这：bool flag[n+1]; 声明了一个可变长度数组，它（尽管由于在堆栈中分配而具有一些性能优势）从未成为 C++ 标准的一部分，即使提供了作为一些（C99 兼容）编译器的扩展。
另一种提高性能的方法可能是通过只考虑奇数来减少计算量（和内存占用），因为除了 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

the compiler can implement j/2 as cheaply as possible. C signed division by a power of 2 has different rounding semantics (for negative dividends) than a right shift, and compilers don't always propagate value-range proofs sufficiently to prove that j will always be non-negative.

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

Answer 4

在 Ryzen 5 1600 CPU:

上使用 g++-7.4.0 -g -march=native -O2 -Wall 和运行编译时，我得到的时间和内存使用情况与问题中提到的不同

vector<bool>: 0.038 秒, 3344 KiB 内存, IPC 3.16
vector<char>：0.048 秒，12004 KiB 内存，IPC 1.52
bool[N]：0.050 秒，12644 KiB 内存，IPC 1.69

结论：vector<bool> 是最快的选项，因为它具有更高的 IPC（每时钟指令数）。

#include <stdio.h>
#include <stdlib.h>
#include <sys/resource.h>
#include <vector>

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

int main() {
    {
        const rlim_t kStackSize = 16*1024*1024; 
        struct rlimit rl;
        int result = getrlimit(RLIMIT_STACK, &rl);
        if(result != 0) abort();
        if(rl.rlim_cur < kStackSize) {
            rl.rlim_cur = kStackSize;
            result = setrlimit(RLIMIT_STACK, &rl);
            if(result != 0) abort();
        }
    }

    printf("%zu\n", countPrimes(10e6));
    return 0;
}

vector<bool> 和 array 之间的性能差距

Performance gap between vector<bool> and array

c++

arrays

performance

vector

std