std :: bitset的性能是什么？

Question

我最近向程序员提出了一个关于使用原始类型的手动位操作的原因的问题std::bitset.

从这个讨论中我得出结论,主要原因是它的表现相对较差,尽管我不知道这种观点有任何可靠的依据.接下来的问题是:

什么是对性能的影响,如果有的话,有可能通过将发生std::bitset在一个原始的位操作？

这个问题有意广泛,因为在网上看后我找不到任何东西,所以我会拿走我能得到的东西.基本上我是在std::bitset使用GCC,Clang和/或VC++在一些常见的机器架构上提供一些资源来提供对''bit-bitset'替代相同问题的资源.有一篇非常全面的论文试图回答这个问题的位向量:

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

不幸的是,它要么超出范围std::bitset,要么被认为超出范围,因此它专注于向量/动态数组实现.

我真的只是想知道是否std::bitset是更好的比使用情况下,它是为了解决方案.我已经知道它比一个整数上的比特更容易和更清晰,但它是否同样快？

Answer 1

更新

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

我已经知道它比一个整数上的比特更容易和更清晰,但它是否同样快？

如果你的使用bitset方式实际上使它比bit-fiddling更清晰,更干净,比如一次检查一个位而不是使用位掩码,那么你不可避免地会失去按位操作提供的所有好处,比如能够检查是否一次针对掩码设置64位,或使用FFS指令快速确定在64位中设置哪个位.

我不确定是否bitset会以各种可能的方式使用惩罚(例如:使用它的按位operator&),但如果你像固定大小的布尔数组一样使用它,这几乎就是我总是看到人们使用它的方式,那么你通常会失去上述所有这些好处.遗憾的是,我们无法获得一次只访问一位的表达能力,operator[]并且让优化器弄清楚所有的按位操作以及FFS和FFZ等等,至少在我上次检查时没有(否则bitset将是我最喜欢的结构之一).

现在,如果您将使用相似的方式使用bitset<N> bits,例如,uint64_t bits[N/64]使用按位操作以相同的方式访问它,它可能是相同的(自从这个古老的帖子以来没有检查过).但是,你首先失去了许多使用的好处bitset.

for_each 方法

在过去,我钻进了一些误解,我想,当我提出一个for_each方法通过之类的东西进行迭代vector<bool>,deque和bitset.这种方法的关键是利用容器的内部知识在调用仿函数时更有效地迭代元素,就像一些关联容器提供find自己的方法而不是使用std::find比线性时间搜索更好.

例如,您可以遍历a的所有设置位,vector<bool>或者bitset如果您有这些容器的内部知识,则在64个连续索引被占用时使用64位掩码一次检查64个元素,并且当不是这样时,同样使用FFS指令案子.

但是,必须使用这种类型的标量逻辑的迭代器设计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 /或/补码)推断出要处理的第一个比特范围是位[0,6],此时我们可以迭代通过内部/嵌套迭代器非常便宜地子范围(它只会增加一个整数,++inner_it相当于刚才++int).然后当我们递增外部迭代器时,它可以非常快速地再次使用一些按位指令确定下一个范围是[7,13].在我们遍历该子范围之后,我们就完成了.以此为另一个例子:

bitset<16> bits = 0xffff;

在这种情况下,第一个和最后一个子范围将是[0, 16),并且bitset可以确定使用单个按位指令,此时我们可以迭代所有设置位,然后我们就完成了.

这种类型的嵌套迭代器设计将映射特别好地vector<bool>,deque以及bitset还有其他数据结构的人可能创造这样展开的列表.

我说的方式不仅仅是扶手椅的推测,因为我有一套类似于其中的数据结构deque实际上与顺序迭代相同vector(对于随机访问来说仍然明显较慢,特别是如果我们只是存储一堆基元并进行简单的处理).但是,为了实现vector顺序迭代的可比时间,我必须使用这些类型的技术(for_each方法和双/嵌套迭代器)来减少每次迭代中正在进行的处理和分支的数量.我无法与时间相媲美,否则只使用平面迭代器设计和/或operator[].而且我当然不比标准的库实现者更聪明,但是想出了一个类似deque容器,它可以更快地顺序迭代,这强烈告诉我,在这种情况下迭代器的标准接口设计是一个问题.在这些奇怪的情况下,优化器无法优化掉一些开销.

老答案

我是那些会给你类似性能答案的人之一,但我会尝试给你一些更深入的东西"just because".这是我通过实际剖析和计时而遇到的,而不仅仅是不信任和偏执.

其中与最大的问题bitset,并vector<bool>为他们的界面设计是"太方便了",如果你想使用它们像boolean数组.优化器可以很好地消除您建立的所有结构,从而提供安全性,降低维护成本,减少更改的干扰等.通过选择指令并分配最少数量的寄存器,使这些代码运行速度与不那么安全,不那么容易维护/改变替代品.

使得bitset接口"太方便"而牺牲效率的部分是随机访问operator[]以及迭代器设计vector<bool>.当您在索引处访问其中一个时n,代码必须首先确定第n位属于哪个字节,然后确定该位中的位的子索引.第一阶段通常涉及对lvalue的分割/缩减以及模/按位,并且比您尝试执行的实际位操作更昂贵.

迭代器设计vector<bool>面临着类似的尴尬困境,它必须每隔8次以上分支到不同的代码中,或者支付上述的索引成本.如果前者完成,它会使迭代中的逻辑不对称,并且迭代器设计往往会在极少数情况下受到性能影响.举例来说,如果vector有for_each自己的方法,你可以通过仅对64位掩码屏蔽位来同时迭代一系列64个元素,vector<bool>如果所有位都设置好而不单独检查每个位.它甚至可以使用FFS一次性计算出范围.迭代器设计往往不得不以标量方式进行,或者存储更多状态,每次迭代都需要对其进行冗余检查.

对于随机访问,优化器似乎无法优化此索引开销,以确定在不需要时访问哪个字节和相对位(可能有点过于依赖于运行时),并且您倾向于看到显着的性能提升手动编码处理位,并具有对其正在处理的字节/字/双字/ qword的高级知识.这有点不公平的比较,但困难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[]它来设置随机访问或通过迭代器,并且deques的内部rep不能非常有效地映射到基于迭代器的设计.如果deque提供了for_each一种自己的方法,那么它可能会开始更接近std::vector's顺序访问性能.这些是一些罕见的情况,其中Sequence接口设计带来了优化器通常无法消除的一些效率开销.通常,优秀的优化器可以在生产构建中节省运行时的成本,但遗憾的是并非在所有情况下都如此.

抱歉!

同样遗憾,回想起来我徘徊了一下这条信息中谈论vector<bool>和deque除bitset.这是因为我们有一个代码库,使用这三个代码库,特别是通过它们进行迭代或使用随机访问,通常是热点.

苹果到橘子

正如旧答案所强调的那样,将bitset原始类型的直接用法与低级按位逻辑进行比较是将苹果与橙子进行比较.bitset对于它所做的事情而言,它的效果并不是非常低效.如果你真的需要访问具有随机访问模式的一堆比特,由于某种原因,由于某种原因需要检查和设置一次,那么它可能理想地实现了这样的目的.但我的观点是,我遇到的几乎所有用例都不需要,并且当不需要时,涉及按位操作的旧学校方式往往效率更高.

Answer 2

是否有一个简短的测试分析std :: bitset vs 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; 我得到以下结果:

Bool数组:随机访问时间= 4695,顺序访问时间= 390

位集:随机访问时间= 5382,顺序访问时间= 749

Answer 3

除了其他答案所说的关于访问性能的内容之外，还可能存在大量空间开销：典型的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

如您所见，我的编译器分配了高达 64 位来存储单个位，使用位域方法，我只需要四舍五入到 8 位。

如果您有很多小位集，那么空间使用的这个因素八可能会变得很重要。

Answer 4

这里不是一个很好的答案，而是一个相关的轶事：

几年前，我正在研究实时软件，我们遇到了调度问题。有一个模块超出了时间预算，这非常令人惊讶，因为该模块只负责将位映射和打包/解包到 32 位字/从 32 位字。

事实证明，该模块正在使用 std::bitset。我们将其替换为手动操作，执行时间从 3 毫秒减少到 25 微秒。这是一个重大的性能问题和重大改进。

关键是，此类引起的性能问题可能非常真实。

Answer 5

反问：为什么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 都生成相同的代码。

另一个地方是setand []，第一个是安全的，这意味着你永远不会得到 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