C++ 11 vector <bool>性能问题(带代码示例)

Question

我注意到在运行以下代码时,向量比bool数组慢得多.

int main() 
{
    int count = 0;
    int n = 1500000;
    // slower with c++ vector<bool>
    /*vector<bool> isPrime;
    isPrime.reserve(n);
    isPrime.assign(n, true);
    */
    // faster with bool array 
    bool* isPrime = new bool[n];

    for (int i = 0; i < n; ++i)
        isPrime[i] = true;


    for (int i = 2; i< n; ++i) {
        if (isPrime[i])
            count++;
        for (int j =2; i*j < n; ++j )
            isPrime[i*j] = false;
    }

    cout <<  count << endl;
    return 0;
}

有什么方法可以让我vector<bool>更快？顺便说一句,无论是std::vector::push_back和std::vector::emplace_back比速度更慢std::vector::assign.

Answer 1

std::vector<bool>可能有各种性能问题(例如,请查看https://isocpp.org/blog/2012/11/on-vectorbool).

一般来说,你可以:

• 使用std::vector<std::uint8_t>而不是std::vector<bool>(尝试std::valarray<bool>也).

  这需要更多内存并且对缓存不太友好,但是没有开销(以位操作的形式)来访问单个值,因此在某些情况下它可以更好地工作(毕竟它就像你的数组一样bool但是没有内存管理的麻烦)

• 使用std::bitset如果您在编译时知道你的布尔数组如何大的将是(或者,如果你至少可以建立一个合理的上限)
• 如果Boost是一个选项try boost::dynamic_bitset(可以在运行时指定大小)

但是对于速度优化,你必须测试......

根据您的具体示例,我只能在关闭优化时确认性能差异(当然这不是一种方法).

在Intel Xeon系统(-O3优化级别)上使用g ++ v4.8.3和clang ++ v3.4.5进行的一些测试给出了不同的图片:

                    time (ms)
                 G++      CLANG++
array of bool    3103     3010
vector<bool>     2835     2420    // not bad!
vector<char>     3136     3031    // same as array of bool
bitset           2742     2388    // marginally better

(答案中100次运行代码的时间已过去)

std::vector<bool>看起来不那么糟糕(源代码在这里).

Answer 2

vector<bool>可以具有模板特化,并且可以使用位阵列来实现以节省空间.提取并保存一点并将其转换为/ bool可能会导致您观察到的性能下降.如果你使用std::vector::push_back,你正在调整向量的大小,这将导致更糟糕的性能.下一个性能杀手可能是assign(最坏的复杂性:第一个参数的线性),而是使用operator [](复杂性:常数).

另一方面,bool []保证是阵列bool.

你应该调整大小n而不是n-1避免未定义的行为.

Answer 3

vector<bool> 可以是高性能，但并非必须如此。为了vector<bool>提高效率，它需要一次处理多个布尔值（例如isPrime.assign(n, true)），而实现者必须将关爱放在其中。将a中的单个布尔值编入索引vector<bool>很慢。

这是我一段时间后使用vector<bool>clang + libc ++ 编写的主要查找器（libc ++部分很重要）：

#include <algorithm>
#include <chrono>
#include <iostream>
#include <vector>

std::vector<bool>
init_primes()
{
    std::vector<bool> primes(0x80000000, true);
    primes[0] = false;
    primes[1] = false;
    const auto pb = primes.begin();
    const auto pe = primes.end();
    const auto sz = primes.size();
    size_t i = 2;
    while (true)
    {
        size_t j = i*i;
        if (j >= sz)
            break;
        do
        {
            primes[j] = false;
            j += i;
        } while (j < sz);
        i = std::find(pb + (i+1), pe, true) - pb;
    }
    return primes;
}

int
main()
{
    using namespace std::chrono;
    using dsec = duration<double>;
    auto t0 = steady_clock::now();
    auto p = init_primes();
    auto t1 = steady_clock::now();
    std::cout << dsec(t1-t0).count() << "\n";
}

这对我来说大约是28秒（-O3）。当我将其更改为返回a时vector<char>，执行时间最多约为44s。

如果使用其他std :: lib运行此程序，则可能不会看到这种趋势。在libc ++上，诸如的算法std::find已经过优化，可以一次搜索一个位的单词，而不是一次搜索一个位。

有关您的供应商可以优化哪些std算法的更多详细信息，请参见http://howardhinnant.github.io/onvectorbool.html。