更新
这篇文章已经发布很久了,但是:
我已经知道使用 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>
、
deque
、
bitset
以及其他人们可能创建的数据结构,比如展开列表。
以一种超越纯粹的坐在椅子上推测的方式来说,我有一组数据结构,类似于
deque
,实际上与
vector
的顺序迭代相当(对于随机访问仍然明显较慢,特别是如果我们只存储一堆基元并进行微不足道的处理)。然而,为了实现与
vector
相当的顺序迭代时间,我必须使用这些类型的技术(
for_each
方法和双/嵌套迭代器),以减少每次迭代中发生的处理和分支数量。否则,我无法通过仅使用平面迭代器设计和/或
operator[]
来匹敌时间。我肯定不比标准库实现者聪明,但想出了一个类似于
deque
的容器,可以更快地进行顺序迭代,这强烈表明,在这种情况下,迭代器的标准接口设计存在一些开销,在这些特殊情况下,优化器无法优化掉。
旧答案:
我是那些会给你类似性能答案的人之一,但我会尝试给你一些更深入的东西,而不仅仅是
"因为"
。这是我通过实际的分析和计时发现的,而不仅仅是不信任和偏见。
bitset
和vector<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
在其所做的事情上实现得非常低效。如果您真正需要访问一堆具有随机访问模式的位,并且由于某种原因需要检查和设置每次仅一个位,则可能最适合为此目的实现。但我的观点是,我遇到的几乎所有用例都不需要这样做,而当不需要时,涉及位运算的老派方式往往更有效率。