获得比特值的BitArray比使用按位移位的简单结合更快吗？

Question

1). var bitValue = (byteValue & (1 << bitNumber)) != 0;

2).使用System.Collections.BitArray与Get(int index)方法

• 什么更快？
• 在.NET项目的什么情况下,BitArray比按位移的简单连接更有用？

Answer 1

BitArray将能够处理任意数量的布尔值,而a byte只能容纳8,int只有32等.这将是两者之间的最大差异.

而且,BitArray实现IEnumerable,其中整数类型显然不是.所以这一切都取决于你的项目的要求; 如果你需要一个IEnumerable类似于数组的接口,那就去吧BitArray.

我实际上会使用一个bool[]解决方案,只是因为它更清楚你要跟踪的是什么类型的数据.Ť

BitArray或bitfield将使用大约1/8的空间,bool[]因为它们将8个布尔值"打包"到一个字节中,而a bool本身将占用整个8位字节.使用位域或空间的优势BitArray是不会尽管事,直到你被储存大量的bools.(数学留给读者:-))

基准

结果:我的原始测试环境,似乎BitArray是有点快,但幅度作为自己与一体型做的同样的量级.还测试了一个bool[],这是最快的毫不奇怪.访问存储器中的单个字节将比访问不同字节中的各个位复杂得多.

Testing with 10000000 operations:
   A UInt32 bitfield took 808 ms.
   A BitArray (32) took 574 ms.
   A List<bool>(32) took 436 ms.

码:

class Program
{
    static void Main(string[] args)
    {
        Random r = new Random();
        r.Next(1000);

        const int N = 10000000;

        Console.WriteLine("Testing with {0} operations:", N);

        Console.WriteLine("   A UInt32 bitfield took {0} ms.", TestBitField(r, N));
        Console.WriteLine("   A BitArray (32) took {0} ms.", TestBitArray(r, N));
        Console.WriteLine("   A List<bool>(32) took {0} ms.", TestBoolArray(r, N));

        Console.Read();
    }


    static long TestBitField(Random r, int n)
    {
        UInt32 bitfield = 0;

        var sw = Stopwatch.StartNew();
        for (int i = 0; i < n; i++) {

            SetBit(ref bitfield, r.Next(32), true);
            bool b = GetBit(bitfield, r.Next(32));
            SetBit(ref bitfield, r.Next(32), b);
        }
        sw.Stop();
        return sw.ElapsedMilliseconds;
    }

    static bool GetBit(UInt32 x, int bitnum) {
        if (bitnum < 0 || bitnum > 31)
            throw new ArgumentOutOfRangeException("Invalid bit number");

        return (x & (1 << bitnum)) != 0;
    }

    static void SetBit(ref UInt32 x, int bitnum, bool val)
    {
        if (bitnum < 0 || bitnum > 31)
            throw new ArgumentOutOfRangeException("Invalid bit number");

        if (val)
            x |= (UInt32)(1 << bitnum);
        else
            x &= ~(UInt32)(1 << bitnum);
    }



    static long TestBitArray(Random r, int n)
    {
        BitArray b = new BitArray(32, false);     // 40 bytes

        var sw = Stopwatch.StartNew();
        for (int i = 0; i < n; i++) {

            b.Set(r.Next(32), true);
            bool v = b.Get(r.Next(32));
            b.Set(r.Next(32), v);
        }
        sw.Stop();
        return sw.ElapsedMilliseconds;
    }



    static long TestBoolArray(Random r, int n)
    {
        bool[] ba = new bool[32];

        var sw = Stopwatch.StartNew();
        for (int i = 0; i < n; i++) {

            ba[r.Next(32)] = true;
            bool v = ba[r.Next(32)];
            ba[r.Next(32)] = v;
        }
        sw.Stop();
        return sw.ElapsedMilliseconds;
    }
}

Answer 2

@Jonathon Reinhart,

不幸的是,你的基准是不确定的.它没有考虑可能的延迟加载,缓存和/或预取(由CPU,主机OS和/或.NET运行时)的影响.

随机测试的顺序(或多次调用测试方法),您可能会注意到不同的时间测量.

我使用"任何CPU"平台目标和.NET 4.0客户端配置文件构建了原始基准测试,在我的机器上运行i7-3770 CPU和64位Windows 7.

我得到的是这个:

Testing with 10000000 operations:
   A UInt32 bitfield took 484 ms.
   A BitArray (32) took 459 ms.
   A List<bool>(32) took 393 ms.

这几乎与你的观察一致.

但是,在UInt32测试之前执行BitArray测试产生了这样的结果:

Testing with 10000000 operations:
   A BitArray (32) took 513 ms.
   A UInt32 bitfield took 456 ms.
   A List<bool>(32) took 417 ms.

通过查看UInt32和BitArray测试的时间,您会注意到测量的时间似乎与测试本身无关,而是与测试的运行顺序相关.

为了至少缓解这些副作用,我在每个程序运行中执行了两次测试方法,结果如下.

测试订单UInt32,BitArray,BoolArray,UInt32,BitArray,BoolArray:

Testing with 10000000 operations:
   A UInt32 bitfield took 476 ms.
   A BitArray (32) took 448 ms.
   A List<bool>(32) took 367 ms.

   A UInt32 bitfield took 419 ms.  <<-- Watch this.
   A BitArray (32) took 444 ms.    <<-- Watch this.
   A List<bool>(32) took 388 ms.

测试订单BitArray,UInt32,BoolArray,BitArray,UInt32,BoolArray:

Testing with 10000000 operations:
   A BitArray (32) took 514 ms.
   A UInt32 bitfield took 413 ms.
   A List<bool>(32) took 379 ms.

   A BitArray (32) took 444 ms.    <<-- Watch this.
   A UInt32 bitfield took 413 ms.  <<-- Watch this.
   A List<bool>(32) took 381 ms.

看一下测试方法的第二次调用,看来至少在具有最新.NET运行时的i7 CPU上,UInt32测试比BitArray测试更快,而BoolArray测试仍然是最快的.

(我很抱歉,我必须将我对Jonathon基准测试的回复作为答案,但作为新的SO用户,我不能发表评论......)

编辑:

在调用第一个测试之前,您可以尝试使用Thread.Sleep(5000)或类似的权限,而不是改变测试方法的顺序......

此外,原始测试似乎使UInt32测试处于不利地位,因为它包括边界检查" if(bitnum <0 || bitnum> 31) ",执行了3000万次.其他两个测试都没有包含这样的边界检查.然而,这实际上并非全部,因为BitArray和bool数组都在内部进行边界检查.

虽然我没有测试,但我希望消除边界检查会使UInt32和BoolArray测试的表现相似,但这对公共API来说不是一个好主意.