使用布尔值向量是否比动态位集慢？

Question

使用布尔值向量是否比动态位集慢？

我刚刚听说了 boost 的动态位集，我想知道这是否值得。我可以只使用布尔值向量吗？

原文由 user2381422 发布，翻译遵循 CC BY-SA 4.0 许可协议

Answer 1

这里很大程度上取决于您使用的布尔值的数量。

bitset 和 vector<bool> 通常都使用打包表示，其中布尔值仅存储为单个位。

一方面，这会以位操作的形式施加一些开销来访问单个值。

另一方面，这也意味着您的更多布尔值将适合您的缓存。

如果您使用大量布尔值（例如，实现 Eratosthenes 的筛子），在缓存中安装更多的布尔值几乎总是会获得净收益。内存使用的减少将比位操作损失更多。

大多数反对 std::vector<bool> 的论据都回到了它不是标准容器的事实（即它不符合容器的要求）。 IMO，这主要是一个期望问题——因为它说 vector ，许多人希望它是一个容器（其他类型的向量是），他们经常对以下事实做出负面反应 vector<bool> 不是容器。

如果您以确实需要将其作为容器的方式使用向量，那么您可能想要使用其他一些组合 deque<bool> 或 vector<char> 可以正常工作。不过，在您这样做之前请 _三思_——有很多（糟糕的，IMO）建议通常应该避免 vector<bool> ，很少或根本没有解释为什么应该避免，或者在什么情况下应该避免这对你来说真的很重要。

是的，在某些情况下，其他方法会更好。如果您处于其中一种情况，使用其他东西显然是一个好主意。但是，请确保您确实首先处于其中一种情况。任何告诉你（例如）“Herb 说你应该使用 vector<char> ”而没有对所涉及的权衡做出大量解释的人都不应该被信任。

让我们举一个真实的例子。既然评论中提到了，让我们考虑一下埃拉托色尼筛法：

 #include <vector>
#include <iostream>
#include <iterator>
#include <chrono>

unsigned long primes = 0;

template <class bool_t>
unsigned long sieve(unsigned max) {
    std::vector<bool_t> sieve(max, false);
    sieve[0] = sieve[1] = true;

    for (int i = 2; i < max; i++) {
        if (!sieve[i]) {
            ++primes;
            for (int temp = 2 * i; temp < max; temp += i)
                sieve[temp] = true;
        }
    }
    return primes;
}

// Warning: auto return type will fail with older compilers
// Fine with g++ 5.1 and VC++ 2015 though.
//
template <class F>
auto timer(F f, int max) {
    auto start = std::chrono::high_resolution_clock::now();
    primes += f(max);
    auto stop = std::chrono::high_resolution_clock::now();

    return stop - start;
}

int main() {
    using namespace std::chrono;

    unsigned number = 100000000;

    auto using_bool = timer(sieve<bool>, number);
    auto using_char = timer(sieve<char>, number);

    std::cout << "ignore: " << primes << "\n";
    std::cout << "Time using bool: " << duration_cast<milliseconds>(using_bool).count() << "\n";
    std::cout << "Time using char: " << duration_cast<milliseconds>(using_char).count() << "\n";
}

我们使用了一个足够大的数组，我们可以预期它的很大一部分会占用主内存。我也有点痛苦，以确保在一个调用和另一个调用之间 唯一 改变的是使用 vector<char> 与 vector<bool> 。以下是一些结果。首先使用 VC++ 2015：

 ignore: 34568730
Time using bool: 2623
Time using char: 3108

…然后是使用 g++ 5.1 的时间：

 ignore: 34568730
Time using bool: 2359
Time using char: 3116

显然， vector<bool> 在这两种情况下都获胜——使用 VC++ 大约 15%，使用 gcc 超过 30%。另请注意，在这种情况下，我选择了以非常有利的方式显示 vector<char> 的大小。例如，如果我将 number 从 100000000 减少到 10000000 ，则时间差会变得 _更大_：

 ignore: 3987474
Time using bool: 72
Time using char: 249

虽然我没有做很多工作来确认，但我猜在这种情况下，使用 vector<bool> 的版本节省了足够的空间，使数组完全适合缓存，而 vector<char> 大到足以溢出缓存，并且涉及大量的主存访问。

原文由 Jerry Coffin 发布，翻译遵循 CC BY-SA 3.0 许可协议

Answer 2

您通常应该避免 std::vector<bool> 因为它不是标准容器。这是一个打包版本，因此它打破了通常由 vector 提供的一些有价值的保证。一个有效的替代方法是使用 std::vector<char> 这是 Herb Sutter 推荐的。

您可以在他的 GotW 中阅读有关该主题的更多信息。

更新：

正如已经指出的那样， vector<bool> 可以使用效果很好，因为打包表示可以提高大型数据集的局部性。根据情况，它很可能是最快的选择。但是，默认情况下我仍然不推荐它，因为它违反了 std::vector 建立的许多承诺，并且打包是速度/内存的权衡， 可能 对速度和内存都有好处。

如果您选择使用它，我会在针对您的应用程序的 vector<char> 进行测量后这样做。即便如此，我还是建议使用 typedef 通过一个似乎无法保证它不具备的名称来引用它。

原文由 Agentlien 发布，翻译遵循 CC BY-SA 3.0 许可协议