在C#中,BitArray获取比特值的速度是否比使用逐位移位的简单组合更快
本文关键字:组合 简单 速度 BitArray 获取 是否 | 更新日期: 2023-09-27 18:12:50
1(。var bitValue = (byteValue & (1 << bitNumber)) != 0;
2( 。使用System.Collections.BitArray
和Get(int index)
方法
- 什么更快
- 对于.NET项目BitArray来说,在什么情况下比简单地结合按位移位更有用
@Jonathon Reinhart,
不幸的是,您的基准测试没有结论。它没有考虑可能的延迟加载、缓存和/或预取(由CPU、主机操作系统和/或.NET运行时(的影响。
打乱测试的顺序(或多次调用测试方法(,您可能会注意到不同的时间测量。
我用"Any 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来说,这不是一个好提议。
BitArray
将能够处理任意数量的布尔值,而byte
只能容纳8个,int
只能容纳32个,等等。这将是两者之间最大的区别。
此外,BitArray
实现了IEnumerable
,而积分类型显然没有。所以这一切都取决于你的项目的要求;如果您需要IEnumerable
或类似阵列的接口,请使用BitArray
。
实际上,我会在任何一种解决方案上使用bool[]
,因为它在中更明确地说明了您要跟踪的类型的数据。T
BitArray
或bitfield
将使用大约bool[]
的1/8空间,因为它们将8个布尔值"打包"到一个字节中,而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;
}
}
对于以列表形式表示时适合缓存的数据,使用BitArray在性能上没有意义。
所展示的基准指出了显而易见的一点:由于缺乏计算需求,Bools列表的执行速度将比BitArray快。
然而,这些测试的最大问题是,它们是在32的数组上运行的。这意味着整个阵列都适合缓存。当您开始进行大量内存提取时,处理大型布尔值集合的成本将显现出来。
与5000项的列表相比,5000项的BitArray的性能将大不相同。列表将需要比BitArray多8倍的内存读取。
根据您的其他逻辑(您正在进行的分支和其他操作的数量(,差异可能很小,也可能很大。内存预取允许CPU将下一个预测的内存块拉入高速缓存,同时仍然处理第一个块。如果您正在对数据结构进行干净的直接迭代,您可能看不到显著的性能差异。另一方面,如果您正在进行一些分支或操作,使CPU很难预测内存获取,那么您更有可能看到性能差异。
此外,如果你开始谈论多重数据结构,事情会变得更加模糊。如果您的代码依赖于对100个不同BitArrays的引用,该怎么办?好吧,现在我们讨论的是更多的数据,即使BitArrays本身很小,你也会跳来跳去访问不同的BitArrays,所以访问模式会影响事情。
如果不在特定的算法/场景中进行基准测试,就不可能知道真实的行为。
如果有人仍在寻找足够快的不同解决方案:我建议在GetBit和SetBit方法上使用激进的内联[MethodImpl(256(]。还具有位位置的OR和XOR值的查找表。从System.IndexOutOfRangeException中删除位位置检查应足以指示位位置中的错误,并且我们不需要为额外的检查消耗CPU。此外,如果在大量元素上执行此操作并进行调试,强烈建议使用[DeggerHidden]属性。DebuggerHidden属性可帮助调试器跳过标记有该属性的方法的调试,并加快调试过程。
使用Jonathon-Reinhart答案中的代码,并为TestBitFieldOpt和TestBitFieldOpt2添加此方法和测试。
static readonly uint[] BITMASK = new uint[]
{
0x00000001, 0x00000002, 0x00000004, 0x00000008, 0x00000010, 0x00000020, 0x00000040, 0x00000080,
0x00000100, 0x00000200, 0x00000400, 0x00000800, 0x00001000, 0x00002000, 0x00004000, 0x00008000,
0x00010000, 0x00020000, 0x00040000, 0x00080000, 0x00100000, 0x00200000, 0x00400000, 0x00800000,
0x01000000, 0x02000000, 0x04000000, 0x08000000, 0x10000000, 0x20000000, 0x40000000, 0x80000000
};
static readonly uint[] BITMASK_XOR = new uint[]
{
0xFFFFFFFE, 0xFFFFFFFD, 0xFFFFFFFB, 0xFFFFFFF7, 0xFFFFFFEF, 0xFFFFFFDF, 0xFFFFFFBF, 0xFFFFFF7F,
0xFFFFFEFF, 0xFFFFFDFF, 0xFFFFFBFF, 0xFFFFF7FF, 0xFFFFEFFF, 0xFFFFDFFF, 0xFFFFBFFF, 0xFFFF7FFF,
0xFFFEFFFF, 0xFFFDFFFF, 0xFFFBFFFF, 0xFFF7FFFF, 0xFFEFFFFF, 0xFFDFFFFF, 0xFFBFFFFF, 0xFF7FFFFF,
0xFEFFFFFF, 0xFDFFFFFF, 0xFBFFFFFF, 0xF7FFFFFF, 0xEFFFFFFF, 0xDFFFFFFF, 0xBFFFFFFF, 0x7FFFFFFF
};
static long TestBitFieldOpt(Random r, int n)
{
bool value;
UInt32 bitfield = 0;
var sw = Stopwatch.StartNew();
for (int i = 0; i < n; i++)
{
SetBitOpt(ref bitfield, r.Next(32), true);
value = GetBitOpt(bitfield, r.Next(32));
SetBitOpt(ref bitfield, r.Next(32), value);
}
sw.Stop();
return sw.ElapsedMilliseconds;
}
static long TestBitFieldOpt2(Random r, int n)
{
bool value;
UInt32 bitfield = 0;
var sw = Stopwatch.StartNew();
for (int i = 0; i < n; i++)
{
bitfield = SetBitOpt2(bitfield, r.Next(32), true);
value = GetBitOpt(bitfield, r.Next(32));
bitfield = SetBitOpt2(bitfield, r.Next(32), value);
}
sw.Stop();
return sw.ElapsedMilliseconds;
}
[MethodImpl(256)]
static bool GetBitOpt(UInt32 bitfield, int bitindex)
{
return (bitfield & BITMASK[bitindex]) != 0;
}
[MethodImpl(256)]
static void SetBitOpt(ref UInt32 bitfield, int bitindex, bool value)
{
if (value)
bitfield |= BITMASK[bitindex];
else
bitfield &= BITMASK_XOR[bitindex];
}
[MethodImpl(256)]
static UInt32 SetBitOpt2(UInt32 bitfield, int bitindex, bool value)
{
if (value)
return (bitfield | BITMASK[bitindex]);
return (bitfield & BITMASK_XOR[bitindex]);
}
我将测试次数增加了10次方(以获得更真实的结果(,优化代码的结果非常接近最快的方法:
Testing with 100000000 operations:
A BitArray (32) took : 4947 ms.
A UInt32 bitfield took : 4399 ms.
A UInt32 bitfieldopt : 3583 ms.
A UInt32 bitfieldopt2 : 3583 ms.
A List<bool>(32) took : 3491 ms.
通常情况下,局部堆栈上较少的变量、较少的分支和预先计算的值在大多数情况下获胜。所以拿着书和铅笔,把数学题缩短,这样就少了。。。函数内部的真正内联有很大帮助,但在方法上更好地使用[MethodImpl(256(]属性可以提高源代码的可读性/保持源代码,如上所述。
希望这能帮助某人找到解决问题的方法。