C ++ 11 vector< bool>性能问题（带代码示例） [英] C++11 vector<bool> performance issue (with code example)

问题描述

我注意到，当运行下面的代码时，vector比bool array慢得多。

I notice that vector is much slower than bool array when running the following code.

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> 更快？ Btw， std :: vector :: push_back 和 std :: vector :: emplace_back 甚至比 std :: vector :: assign 。

Is there some way that I can do to make vector<bool> faster ? Btw, both std::vector::push_back and std::vector::emplace_back are even slower than std::vector::assign.

推荐答案

std :: vector< bool> 可能会有各种性能问题（例如，查看 https://isocpp.org/blog/2012/11/on-vectorbool ）。

std::vector<bool> can have various performance issues (e.g. take a look at https://isocpp.org/blog/2012/11/on-vectorbool).

一般来说，您可以：




• 使用 std :: vector< std :: uint8_t> c $ c> std :: vector< bool> （尝试 std :: valarray< bool> ）。

• use std::vector<std::uint8_t> instead of std::vector<bool> (give a try to std::valarray<bool> also).

少缓存友好，但没有开销（以位操作的形式）访问单个值，所以有一些情况下，它的工作更好（毕竟它就像你的数组 bool ，但没有内存管理的麻烦）

This requires more memory and is less cache-friendly but there isn't a overhead (in the form of bit manipulation) to access a single value, so there are situations in which it works better (after all it's just like your array of bool but without the nuisance of memory management)

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

But for speed optimizations you have to test...

用你的具体例子，我可以确认性能差异只有当优化被关闭（当然这不是走的路）。

With your specific example I can confirm a performance difference only when optimizations are turned off (of course this isn't the way to go).

有些测试使用g ++ v4 .8.3和clang ++ v3.4.5在英特尔至强系统（ -O3 优化级别）给出不同的图片：

Some tests with g++ v4.8.3 and clang++ v3.4.5 on an Intel Xeon system (-O3 optimization level) give a different picture:

                    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次运行代码所用的时间）

(time elapsed for 100 runs of the code in the answer)

std :: vector< bool> 看起来很糟糕（源代码此处）。

std::vector<bool> doesn't look so bad (source code here).

这篇关于C ++ 11 vector< bool>性能问题（带代码示例）的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！