BitArray 在 C# 中获取位值是否比简单的按位移位组合更快？
声明：本页面是StackOverFlow热门问题的中英对照翻译，遵循CC BY-SA 4.0协议，如果您需要使用它，必须同样遵循CC BY-SA许可，注明原文地址和作者信息，同时你必须将它归于原作者（不是我）：StackOverFlow
原文地址: http://stackoverflow.com/questions/16471759/
Warning: these are provided under cc-by-sa 4.0 license. You are free to use/share it, But you must attribute it to the original authors (not me):
StackOverFlow
Is BitArray faster in C# for getting a bit value than a simple conjuction with bitwise shift?
提问by Secret
1). var bitValue = (byteValue & (1 << bitNumber)) != 0;
1）。 var bitValue = (byteValue & (1 << bitNumber)) != 0;
2). using System.Collections.BitArraywith a Get(int index)method
2）。使用System.Collections.BitArray与Get(int index)方法
- What is faster?
- In what situations for the .NET projects BitArraycould be more useful than a simple conjunction with the bitwise shift?
- 什么更快？
- 在 .NET 项目的哪些情况下，BitArray比与按位移位的简单结合更有用？
回答by Jonathon Reinhart
BitArrayis going to be able to handle an arbitrary number of boolean values, whereas a bytewill hold only 8, intonly 32, etc. This is going to be the biggest difference between the two.
BitArray将能够处理任意数量的布尔值，而 abyte只能容纳 8 个，int只有 32 个等等。这将是两者之间最大的区别。
Also, BitArrayimplements IEnumerable, where a integral type obviously does not. So it all depends on the requirements of your project; if you need an IEnumerableor array-like interface, then go with the BitArray.
此外，BitArrayimplements IEnumerable，其中整数类型显然没有。所以这一切都取决于你的项目的要求；如果您需要IEnumerable类似或数组的接口，请使用BitArray.
I would actually use a bool[]over either solution, simply because it is more explicit in whatkind of data you're keeping track of. T
我真的使用bool[]过任何一个解决方案，只是因为它是在更加明确什么样的数据你保持跟踪。吨
BitArrayor bitfieldwill use approximately 1/8th the space of a bool[]because they "pack" 8 boolean values into a single byte, whereas a boolby itself will take up the whole 8-bit byte. The space advantage of using a bitfield or BitArrayisn't going to matter though until you being storing lotsof bools. (The math is left up to the reader :-))
BitArrayorbitfield将使用 a 的大约 1/8 的空间，bool[]因为它们将 8 个布尔值“打包”到一个字节中，而 abool本身将占用整个 8 位字节。使用位域或空间的优势BitArray是不会不要紧，虽然直到你是存储大量的bools。（数学留给读者:-)）
Benchmark
基准
Results: For my primitive test environment, it appears that BitArrayis a bitfaster, but is on the same order of magnitude as doing it yourself with an integral type. Also tested was a bool[], which was unsurprisingly the fastest. Accessing single bytes in memory is going to be less complex than accessing individual bits in different bytes.
结果：我的原始测试环境，似乎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.
Code:
代码：
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;
}
}
回答by Jonathon Reinhart
@Jonathon Reinhart,
@乔纳森莱因哈特，
your benchmark is unfortunately inconclusive. It does not take into account the effects of possible lazy-loading, caching and/or prefetching (by the CPU, the host OS and/or the .NET runtime).
不幸的是，您的基准是不确定的。它没有考虑可能的延迟加载、缓存和/或预取（由 CPU、主机操作系统和/或 .NET 运行时）的影响。
Shuffle the order of the tests (or call the test methods multiple times) and you might notice different time measurments.
改变测试的顺序（或多次调用测试方法），您可能会注意到不同的时间度量。
I did your original benchmark built with "Any CPU" platform target and .NET 4.0 client profile, running on my machine with a i7-3770 CPU and 64-bit Windows 7.
我使用“Any CPU”平台目标和 .NET 4.0 客户端配置文件构建了您的原始基准测试，在我的机器上运行，配备 i7-3770 CPU 和 64 位 Windows 7。
What i got was this:
我得到的是这个：
Testing with 10000000 operations:
A UInt32 bitfield took 484 ms.
A BitArray (32) took 459 ms.
A List<bool>(32) took 393 ms.
which is pretty much in line with your observations.
这与您的观察非常一致。
However, executing the BitArray test before the UInt32 test yielded this:
然而，在 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.
By looking at the times for the UInt32 and BitArray tests you will notice that the measured time does not seem to be connected to the tests themselves, but rather to the order in which the tests are run.
通过查看 UInt32 和 BitArray 测试的时间，您会注意到测量的时间似乎与测试本身无关，而是与测试运行的顺序有关。
To alleviate these side effects at least a little bit, i executed the test methods twice in each program run with the following results.
为了至少稍微减轻这些副作用，我在每个程序运行中执行了两次测试方法，结果如下。
Test order UInt32, BitArray, BoolArray, UInt32, BitArray, BoolArray:
测试顺序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.
Test order BitArray, UInt32, BoolArray, BitArray, UInt32, BoolArray:
测试顺序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.
Looking at the second invocations of the test methods, it appears that at least on i7 CPUs with up-to-date .NET runtime, the UInt32 test is faster than the BitArray test, while the BoolArray test is still being the fastest.
查看测试方法的第二次调用，似乎至少在具有最新 .NET 运行时的 i7 CPU 上，UInt32 测试比 BitArray 测试快，而 BoolArray 测试仍然是最快的。
(I apologize that i had to write my response to Jonathon's benchmark as an answer, but as a new SO user i am not allowed to comment...)
（我很抱歉我不得不写下我对 Jonathon 基准测试的回应作为答案，但作为一个新的 SO 用户，我不允许发表评论......）
EDIT:
编辑：
Instead of shuffling the order of test methods, you might try putting a Thread.Sleep(5000) or similar right before calling the first test...
您可以尝试在调用第一个测试之前放置一个 Thread.Sleep(5000) 或类似的东西，而不是改变测试方法的顺序......
Also the original test seems to put the UInt32 test at disadvantage, because it includes a boundary check "if (bitnum < 0 || bitnum > 31)", which is executed 30 million times. None of the other two tests include such a boundary check. However, this is actually not the whole truth, since both the BitArray and the bool array do boundary checks internally.
此外，原始测试似乎将 UInt32 测试置于不利地位，因为它包括边界检查“ if (bitnum < 0 || bitnum > 31)”，执行 3000 万次。其他两个测试都不包括这样的边界检查。然而，这实际上并不是全部事实，因为 BitArray 和 bool 数组都在内部进行边界检查。
Although i didn't test, i expect that eliminating the boundary checks will make the UInt32 and BoolArray tests perform similarly, but that would not be a good proposition for a public API.
虽然我没有测试，但我希望消除边界检查将使 UInt32 和 BoolArray 测试的性能相似，但这对于公共 API 来说不是一个好建议。
