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

Question

我试图解决一个C++编程问题，它计算非负整数n之前的质数数量a coding problem in C++。

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

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>后，将运行时间降低至40毫秒，内存消耗为11.5 MB。

- Qin Heyang

---

你如何编译你的代码？使用了哪些编译器选项？此外，“vector<bool>”是特别的。 - Jesper Juhl

小心，std::vector<bool> 是一个奇怪的特化，更像是一个位集(bitset)而不是一个向量(vector)。 - Martin Morterol

您可以稍微修改一下循环：for(int i = 2; i * i <n;i++)，这样做可以节省一些时间，因为如果i * i >= n，那么下一次循环将不会有任何作用。请注意，修改后的内容应保持与原文意思一致，同时更通顺易懂。 - Marek R

这并没有回答问题，但当你处理布尔类型时，请使用true和false而不是1。所以：vector<bool> flag(n+1, true);和if (flag[i])。这并不影响结果，但可以让你的操作更加清晰易懂。 - Pete Becker

在进行基准测试之前，请确保启用编译器优化选项来编译您的代码。 - Jesper Juhl

Answer 1

std::vector<bool> 不像其他的向量。根据文档：

std::vector<bool> 是一个专门为类型 bool 设计的可能具有空间效率的 std::vector 特化版本。

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

- Blaze

Answer 2

std::vector<bool> 是一个特殊情况。它是一个专门的模板。每个值都存储在单个位中，因此需要进行位操作。这样可以节省内存，但也有一些缺点（例如没有办法在该容器内部拥有指向bool的指针）。

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

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

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

- Marek R

Answer 3

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

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

  例如，参见这些快速工具：clang++ / libc++(LLVM) vs. 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的倍数以下或以上的事实来减少候选人数。

- Bob__

---

哇，C99发布20年后，甚至没有最基本的可变长度数组（VLA）……看起来C++越来越落后于C了;-) 据我所知，曾经有一个提案，可以使int array[length];在C++中合法，但是即使这个提案也不允许多维数组，无论是在堆栈上(int array2d[height][width])还是在堆上(int (*array2d)[width] = new int[height][width];)。显然，即使20年前C已经允许多维情况(int (*array2d)[width] = malloc(height * sizeof(*array2d));)，该提案也从未获得批准... - cmaster - reinstate monica

@cmaster 嗯，这是有争议的 ;) - Bob__

是的，我知道。特别是因为很少有人真正理解 C99 语法的威力 - 你链接的问题的两个得分最高的答案都完全低估了它的价值。因为你看，C99 可变长度数组不仅存在于堆栈上，还可以在堆上分配。我已经举了一个例子，就是最后一个例子。真正的威力来自于任何 C99 数组类型都可以具有运行时长度，可以被指向或 typedefed。而且 C99 不关心你嵌套了多少运行时长度的数组类型，索引计算总是正确的。 - cmaster - reinstate monica

长话短说：总的来说，我非常喜欢使用C++进行编程，但是当涉及到操作多维数组的纯数据（如图像、体积、模拟）时，我会退回到C99，因为它具有VLA语法。 - cmaster - reinstate monica

gcc在这里显示出了差异，因为它使用有符号的int实际上效果更差。总体而言，它能生成更快的代码，但是你可以看到它使用sar/ sub/ movslq来进行符号扩展回到64位。我建议使用size_t重新扩展到指针宽度是不必要的。（虽然在x86-64上零扩展是免费的；写入32位寄存器会将其零扩展为64位，但64位使其可以在地址模式中使用-1。）无论如何，使用unsigned long比unsigned在gcc中确实提供了额外的加速。http://quick-bench.com/4t9DE9nsT-oQYSNo0leeyYZ8GvY。( long int 也相同。) - Peter Cordes

Answer 4

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

• vector<bool>：0.038秒，3344 KiB内存，IPC3.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;
}

- atomsymbol