矢量之间的性能差距 和数组

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和that one这样的相关问题，但我仍然感到困惑。

编辑：用vector<bool>替换vector<char>后，我用11.5 MB内存将运行时间缩短到40 ms。

Answer 1

std::vector<bool>不像任何其他矢量。 documentation说：

std::vector<bool>是std::vector类型的bool可能具有空间效率的专业化。

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

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)与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

编译器可以尽可能便宜地实现j / 2。以2的幂表示的C签名除法具有与右移不同的舍入语义（对于负除数），并且编译器并不总是足以传播值范围证明以证明j将始终是非负的。

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

Answer 4

在使用g++-7.4.0 -g -march=native -O2 -Wall进行编译并在Ryzen 5 1600 CPU上运行时，我得到的时间和内存使用量与问题中提到的不同：

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