std::bitset的性能如何?

68

我最近在程序员上发布了一个问题,询问使用原始类型手动位操作与std::bitset相比的优点。

从那次讨论中,我得出结论,主要原因是其相对较差的性能,尽管我不知道这种观点是否有任何实际依据。所以下一个问题是:

如果使用std::bitset而不是原始类型手动位操作,是否可能会遇到性能损失,如果有,它将有多大?

这个问题故意广泛,因为我在网上搜索后没有找到任何资源,所以我会尽量利用所能获得的信息。基本上,我需要一些关于使用GCC、Clang和/或VC++在某些常见机器架构上解决同样问题时,对比std::bitset和“前bitset”替代方案的性能分析资源。有一篇非常全面的论文试图回答这个问题,但是针对的是位向量(bit vectors):

http://www.cs.up.ac.za/cs/vpieterse/pub/PieterseEtAl_SAICSIT2010.pdf

不幸的是,它要么早于std::bitset,要么超出了其范围,因此它侧重于向量/动态数组实现。

我只想知道std::bitset是否比解决同样问题的其他方案更好。我已经知道它比在整数上进行位操作更易于理解和更清晰,但它是否同样快?


11
进行基准测试所需的时间不是和你撰写问题所花费的时间差不多吗? - Tony Delroy
36
@TonyD 如果要在不同的架构上制定一个全面的测试套件,以便在一般情况下有任何用处,可能需要大约一天的时间,即使如此,由于我不是专家,这个过程也容易出错。我认为询问是否已经有关于此方面的研究存在是合理的。 - quant
@TonyD,你是在说这是一道作业题吗? - quant
1
我认为@TonyD指的是第三种情况:关闭 -> 不相关,因为... ->要求我们推荐或查找书籍、工具、软件库、教程或其他场外资源的问题对于Stack Overflow来说是不相关的,因为它们往往会吸引不同意见的回答和垃圾邮件。相反,请描述问题以及已经采取的解决方法。 - Ivan Aksamentov - Drop
@TonyD 很好,投票关闭。 - quant
显示剩余6条评论
5个回答

37

更新

这篇文章已经发布很久了,但是:

我已经知道使用 bitset 比在整数上进行位操作更容易和清晰,但是它的速度比位操作快吗?

如果你确实使用 bitset 的方式使其更清晰、更易读,例如逐个检查一位而不使用位掩码,那么你将失去所有位运算提供的好处,例如能够针对掩码一次性检查 64 位是否被设置,或者使用 FFS 指令快速确定 64 位中哪一位被设置。

我不确定在所有可能的方式中使用bitset(例如:使用其位运算符&)是否会产生惩罚,但如果您像使用固定大小的布尔数组一样使用它,这基本上是我经常看到人们使用的方式,那么通常会失去上述所有优势。不幸的是,我们不能仅访问一个位并让优化器为我们找出所有位运算和FFS和FFZ等操作所进行的位运算,至少在我上次检查时是这样的(否则bitset将成为我最喜欢的结构之一)。

现在,如果您要像访问uint64_t bits[N/64]一样交替使用bitset<N> bits,则可以使用位运算符相同的方式进行访问(自古以来就没有检查过)。但是,那么您将失去使用bitset的许多好处。

for_each方法

过去我曾经提出过一个for_each方法用于遍历像vector、deque和bitset这样的东西,我想在那时候引起了一些误解。这样做的目的是利用容器的内部知识更有效地迭代元素,同时调用一个函数对象,就像一些关联容器提供了自己的find方法,而不是使用std::find进行更好的超线性搜索。
例如,如果您有关于这些容器的内部知识,您可以通过检查64位掩码来同时检查64个连续索引的占用情况,并在不是这种情况下使用FFS指令,以此遍历vector或bitset的所有设置位。

但是,一个需要在operator++中执行这种标量逻辑的迭代器设计,无论如何都不可避免地需要做一些更昂贵的事情,这是由于迭代器在这些特殊情况下的设计方式所决定的。 bitset根本缺乏迭代器,并且这经常使人们想要使用它来避免处理位逻辑,并在顺序循环中使用operator[]逐个检查每个位,只需找出哪些位被设置了。这也不像for_each方法实现可以做到的那么有效。

双重/嵌套迭代器

除了上面提出的for_each容器特定方法之外,另一种选择是使用双重/嵌套迭代器:即一个外部迭代器指向不同类型迭代器的子范围。客户端代码示例:

for (auto outer_it = bitset.nbegin(); outer_it != bitset.nend(); ++outer_it)
{
     for (auto inner_it = outer_it->first; inner_it != outer_it->last; ++inner_it)
          // do something with *inner_it (bit index)
}

虽然不符合标准容器现有的迭代器设计,但这可以允许一些非常有趣的优化。例如,想象一个像这样的情况:

bitset<64> bits = 0x1fbf; // 0b1111110111111;

在这种情况下,外部迭代器可以通过几个位运算((FFZ/or/complement))推断出要处理的第一个位范围是位[0,6),此时我们可以通过内部/嵌套迭代器非常便宜地迭代该子范围(它只需增加一个整数,使++inner_it等同于++int)。然后当我们增加外部迭代器时,它可以再次快速并且只需进行几个位操作即可确定下一个范围为[7,13)。在我们迭代完该子范围之后,我们就完成了。以此作为另一个例子:

bitset<16> bits = 0xffff;

在这种情况下,第一个和最后一个子范围将会是[0, 16),并且位集可以通过单一的按位指令确定这一点,然后我们就可以遍历所有设置的位,完成操作。
这种嵌套迭代器设计特别适用于vector<bool>dequebitset以及其他人们可能创建的数据结构,比如展开列表。
以一种超越纯粹的坐在椅子上推测的方式来说,我有一组数据结构,类似于deque,实际上与vector的顺序迭代相当(对于随机访问仍然明显较慢,特别是如果我们只存储一堆基元并进行微不足道的处理)。然而,为了实现与vector相当的顺序迭代时间,我必须使用这些类型的技术(for_each方法和双/嵌套迭代器),以减少每次迭代中发生的处理和分支数量。否则,我无法通过仅使用平面迭代器设计和/或operator[]来匹敌时间。我肯定不比标准库实现者聪明,但想出了一个类似于deque的容器,可以更快地进行顺序迭代,这强烈表明,在这种情况下,迭代器的标准接口设计存在一些开销,在这些特殊情况下,优化器无法优化掉。
旧答案:
我是那些会给你类似性能答案的人之一,但我会尝试给你一些更深入的东西,而不仅仅是"因为"。这是我通过实际的分析和计时发现的,而不仅仅是不信任和偏见。

bitsetvector<bool>的最大问题之一是它们的接口设计“太方便”了,如果你想像使用布尔数组那样使用它们。优化器非常擅长摧毁你建立的所有结构,以提供安全性、降低维护成本、减少更改对系统的影响等。它们尤其擅长选择指令并分配最小数量的寄存器来使这些代码运行得像不太安全、不太易于维护/更改的替代方法一样快。

使bitset接口“过于方便”的部分是随机访问operator[]以及vector<bool>的迭代器设计。当您在索引n处访问其中之一时,代码必须首先确定第n位属于哪个字节,然后确定该位在其中的子索引。这第一个阶段通常涉及除法/右移操作以及取模/位运算,这比您试图执行的实际位操作更昂贵。

vector<bool> 的迭代器设计面临着类似的尴尬困境,它要么必须在每次迭代时分支到不同的代码中,要么就要支付上述索引成本。如果选择前者,则会使逻辑在迭代之间不对称,而迭代器设计往往在这些罕见情况下性能受到影响。例如,如果 vector 有自己的 for_each 方法,您可以通过只针对 vector<bool> 的 64 位掩码屏蔽位来迭代一次 64 个元素的范围,而无需逐个检查每个位。它甚至可以使用 FFS 一次性确定整个范围。迭代器设计往往不可避免地必须以标量方式执行此操作或存储更多状态,每次迭代都必须进行冗余检查。

对于随机访问,优化器似乎无法优化掉索引开销以确定要访问哪个字节和相对位(可能有点过于依赖运行时),当不需要时,您倾向于使用更多手动处理位的代码,具有先进的知识,可以顺序处理字节/字/双字/四字。这有点不公平的比较,但是在std::bitset的困难之处在于,在这种情况下,代码知道它想要预先访问哪个字节,而且往往你提前就有这些信息。在随机访问的情况下,这是一个苹果与橙子的比较,但通常您只需要橙子。

如果接口设计涉及到bitset,其中operator[]返回一个代理,需要使用两个索引访问模式。在这种情况下,您可以通过编写bitset[0][6] = true; bitset[0][7] = true;来访问位8,并使用模板参数指示代理的大小(例如64位)。一个好的优化器可能能够采取这样的设计,并使其与手动、老派的方式相媲美,将其转换为:bitset |= 0x60;

另一个可能有帮助的设计是,如果bitsets提供了一种for_each_bit方法,传递一个位代理给您提供的函数对象。这样做可能实际上能够与手动方法相媲美。

std::deque存在类似的接口问题。它的性能在顺序访问方面不应该比std::vector太多。但不幸的是,我们使用operator[]进行顺序访问,而这个操作符被设计用于随机访问或通过迭代器进行访问,而deque的内部表示并不能很有效地映射到基于迭代器的设计中。如果deque提供了自己的for_each类型的方法,那么它就有可能开始接近std::vector的顺序访问性能。这些都是一些罕见的情况,其中序列接口设计带来一些效率开销,优化器通常无法消除。通常好的优化器可以使方便在生产构建中免费获得运行时成本,但不幸的是并非所有情况都是如此。

对不起!

同样抱歉,回过头来看,我在这篇文章中有点离题了,谈论了vector<bool>deque以及bitset。这是因为我们有一个代码库,在这个代码库中,使用这三个数据结构,特别是通过随机访问迭代它们,经常成为性能瓶颈。

无法比较

正如旧答案所强调的那样,将bitset的简单使用与低级位逻辑的原始类型进行比较就像是在比较苹果和橙子。这并不意味着bitset在其所做的事情上实现得非常低效。如果您真正需要访问一堆具有随机访问模式的位,并且由于某种原因需要检查和设置每次仅一个位,则可能最适合为此目的实现。但我的观点是,我遇到的几乎所有用例都不需要这样做,而当不需要时,涉及位运算的老派方式往往更有效率。


1
在我的测试中(www.plflib.org/colony.htm),如果您使用迭代器而不是 [ ] 运算符,deque 的迭代速度与 vector 非常相似。另外,不幸的是,有关 bitset 的声明从未附带基准测试。逻辑是正确的,但我所看到的唯一一次与 bitset 实现的比较得出了非常不同的结果: www.cs.up.ac.za/cs/vpieterse/pub/PieterseEtAl_SAICSIT2010.pdf - metamorphosis
棘手的部分是这些基准测试也可能变化很大:http://www.gotw.ca/gotw/054.htm(尽管有点老)。这是情况因案而异,取决于输入因素、内存、硬件、供应商实现等。我试图解决的问题更多地涉及概念层面。双端队列不提供连续要求,可能由多个块组成——自然而然地,符合STL的迭代器设计需要在增量/减量运算符中进行分支(它的廉价/昂贵程度因情况而异,但可以说从概念上讲,它比递增/递减指针/索引更昂贵)。 - user4842163
那么,使用直接针对deque内部实现的“for_each”设计,分支成本就会大大降低。bitset/vector<bool>比较并不是与像Qt版本这样的其他比较进行比较,而仅仅是与C中常见的按位逻辑代码进行比较。虽然我通常建议采用务实的方法,选择最简单的版本,以降低维护成本,然后反复进行剖析和测量,并根据需要进行优化(并始终测量这些优化,以确保它们确实有所改进)。 - user4842163
1
我认为将事物表述为概念并不真正有帮助 - 我的意思是,我知道分支并不会对迭代产生重大影响,因为现在CPU上的分支预测非常好。我的容器colony使用多个块,但这并不会对迭代产生重大影响。 此外,我认为您可能误解了迭代器的理解,认为它不使用容器的内部 - 实际上它们确实使用。因此,无论您是使用for_each还是使用带有迭代器的for循环,您都在使用迭代器。无论如何,bool似乎比std :: bitset更好,如下所示。 - metamorphosis
正如我所说,我已经实现了一个基于块的容器,检查块的结尾的分支开销不大。for_each在内部使用迭代器。 你并没有告诉我任何我不知道的东西,实际上你忽略了我说的话,所以我要结束对话了。 - metamorphosis
显示剩余11条评论

15

我做了一个简短的测试,对比了使用std::bitset和bool数组进行顺序访问和随机访问的性能 - 你也可以这样做:

#include <iostream>
#include <bitset>
#include <cstdlib> // rand
#include <ctime> // timer

inline unsigned long get_time_in_ms()
{
    return (unsigned long)((double(clock()) / CLOCKS_PER_SEC) * 1000);
}


void one_sec_delay()
{
    unsigned long end_time = get_time_in_ms() + 1000;

    while(get_time_in_ms() < end_time)
    {
    }
}



int main(int argc, char **argv)
{
    srand(get_time_in_ms());

    using namespace std;

    bitset<5000000> bits;
    bool *bools = new bool[5000000];

    unsigned long current_time, difference1, difference2;
    double total;

    one_sec_delay();

    total = 0;
    current_time = get_time_in_ms();

    for (unsigned int num = 0; num != 200000000; ++num)
    {
        bools[rand() % 5000000] = rand() % 2;
    }

    difference1 = get_time_in_ms() - current_time;
    current_time = get_time_in_ms();

    for (unsigned int num2 = 0; num2 != 100; ++num2)
    {
        for (unsigned int num = 0; num != 5000000; ++num)
        {
            total += bools[num];
        }
    }   

    difference2 = get_time_in_ms() - current_time;

    cout << "Bool:" << endl << "sum total = " << total << ", random access time = " << difference1 << ", sequential access time = " << difference2 << endl << endl;


    one_sec_delay();

    total = 0;
    current_time = get_time_in_ms();

    for (unsigned int num = 0; num != 200000000; ++num)
    {
        bits[rand() % 5000000] = rand() % 2;
    }

    difference1 = get_time_in_ms() - current_time;
    current_time = get_time_in_ms();

    for (unsigned int num2 = 0; num2 != 100; ++num2)
    {
        for (unsigned int num = 0; num != 5000000; ++num)
        {
            total += bits[num];
        }
    }   

    difference2 = get_time_in_ms() - current_time;

    cout << "Bitset:" << endl << "sum total = " << total << ", random access time = " << difference1 << ", sequential access time = " << difference2 << endl << endl;

    delete [] bools;

    cin.get();

    return 0;
}
请注意:输出总和是必要的,这样编译器就不会优化掉for循环,有些编译器会优化掉未使用循环结果的循环。
在具有以下标志的GCC x64下:-O2;-Wall;-march=native;-fomit-frame-pointer;-std=c++11; 我得到了以下结果:
布尔数组: 随机访问时间=4695,顺序访问时间=390
位集: 随机访问时间=5382,顺序访问时间=749

4
单个数据点无法评估渐近成本。它是线性的吗?二次方的?还是其他什么? - sp2danny

10

这里并没有一个很好的答案,但是有一个相关的轶事:

几年前,我在做实时软件时遇到了调度问题。有一个模块超时预算很多,这非常令人惊讶,因为这个模块只负责将一些映射和位的打包/解包到32位字中。

后来发现这个模块使用了std::bitset。我们用手动操作替换它后,执行时间从3毫秒降至25微秒。那是一个重大的性能问题和重大的改进。

结论是,由于这个类引起的性能问题可能非常真实。


那是什么编译器? - user1319829
我认为msvc 12是来自于Visual Studio 2008。 - Stewart
“我们用手动操作替换了这个”,是指您重写了std::bitset,还是对其进行了修改?我在std::bitset处也遇到了瓶颈。 - cppBeginner

10
除了其他答案提到的关于访问性能的问题之外,还可能存在显著的空间开销:典型的bitset<>实现只使用最长的整数类型来支持它们的位。因此,下面的代码:
#include <bitset>
#include <stdio.h>

struct Bitfield {
    unsigned char a:1, b:1, c:1, d:1, e:1, f:1, g:1, h:1;
};

struct Bitset {
    std::bitset<8> bits;
};

int main() {
    printf("sizeof(Bitfield) = %zd\n", sizeof(Bitfield));
    printf("sizeof(Bitset) = %zd\n", sizeof(Bitset));
    printf("sizeof(std::bitset<1>) = %zd\n", sizeof(std::bitset<1>));
}

在我的机器上,它的输出如下:
sizeof(Bitfield) = 1
sizeof(Bitset) = 8
sizeof(std::bitset<1>) = 8

你看,我的编译器为了存储一个单独的1,需要分配整整64位,但是使用位域方法,我只需要舍入到8位。

如果你有很多小的位集合,那么这种空间利用率的因素8就变得非常重要。


9

修辞问句:为什么std::bitset被写成那种低效的方式? 回答:它不是。

另一个修辞问句:以下两者有何区别:

std::bitset<128> a = src;
a[i] = true;
a = a << 64;

并且

std::bitset<129> a = src;
a[i] = true;
a = a << 63;

答案:性能相差50倍 http://quick-bench.com/iRokweQ6JqF2Il-T-9JSmR0bdyw

你需要非常小心地询问,bitset支持很多东西,但每个东西都有自己的代价。通过正确的处理,您将拥有与原始代码完全相同的行为:

void f(std::bitset<64>& b, int i)
{
    b |= 1L << i;
    b = b << 15;
}
void f(unsigned long& b, int i)
{
    b |= 1L << i;
    b = b << 15;
}

两者生成相同的汇编代码:https://godbolt.org/g/PUUUyd(64位GCC)

另一件事是bitset更具可移植性,但这也有代价:

void h(std::bitset<64>& b, unsigned i)
{
    b = b << i;
}
void h(unsigned long& b, unsigned i)
{
    b = b << i;
}

如果i > 64,则位设置将为零,在无符号的情况下,我们会有UB。
void h(std::bitset<64>& b, unsigned i)
{
    if (i < 64) b = b << i;
}
void h(unsigned long& b, unsigned i)
{
    if (i < 64) b = b << i;
}

使用检查来防止UB,两者生成相同的代码。

另一个地方是set[],第一个是安全的,意味着您永远不会遇到UB,但这将花费一个分支。如果您使用错误的值,则[]会有UB,但速度与使用var |= 1L<< i;一样快。当然,如果std::bitset不需要比系统上可用的最大整数位更多的位,因为否则您需要拆分值以获取内部表中的正确元素。这意味着对于std::bitset<N>,大小N对于性能非常重要。如果比最优大小更大或更小,您将为此付出代价。

总的来说,我发现最好的方法是使用类似以下内容:

constexpr size_t minBitSet = sizeof(std::bitset<1>)*8;

template<size_t N>
using fasterBitSet = std::bitset<minBitSet * ((N  + minBitSet - 1) / minBitSet)>;

这将删除超出位数限制的修整成本: http://quick-bench.com/Di1tE0vyhFNQERvucAHLaOgucAY


minBitSet * ((N + minBitSet - 1) / minBitSet) == N + minBitSet - 1 - moongoal
1
@AlQafir / 使值被裁剪,这意味着该方程不成立。左侧始终为 minBitSet * k,其中两个数字都是整数,但右侧可以有任何您想要的值,例如 13 + 32 - 1。而我想要的是 32 * k - Yankes
现在我明白你做了什么。谢谢你的解释! - moongoal

网页内容由stack overflow 提供, 点击上面的
可以查看英文原文,
原文链接