24

我注意到在运行以下代码时，vector 比 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.

4

3 回答 3

20

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 是一个选项，请尝试boost::dynamic_bitset（可以在运行时指定大小）

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

通过您的具体示例，我只能在关闭优化时确认性能差异（当然这不是要走的路）。

在英特尔至强系统（-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>看起来还不错（源代码在这里）。

于 2016-04-29T08:29:28.393 回答
10

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

另一方面，bool []保证是数组bool。

并且您应该调整大小n而不是n-1避免未定义的行为。

于 2016-04-29T07:54:06.330 回答
7

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）内为我执行。当我将其更改为返回 avector<char>时，执行时间会上升到大约 44 秒。

如果您使用其他一些 std::lib 运行它，您可能不会看到这种趋势。在 libc++ 算法上，例如std::find已经优化为一次搜索一个字的位，而不是一次位。

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

于 2016-04-29T18:11:42.790 回答