最小化内存使用
自然而然的,一个非常普遍的原因是将大量数据压缩到少量的内存中。如果你考虑这样一个布尔数组:
bool data[64] = {...};
那需要占用64字节(512位)的内存。而同一概念可以使用8字节(64位)的内存表示:
uint64_t data = ...;
当然,现在我们有大量的DRAM,所以似乎将所有这些数据压缩到最小尺寸可能并没有什么区别,但我们仍然处理64位通用寄存器。 我们仍在处理64字节的高速缓存行,例如每个物理映射页面的千字节,并且将数据向下移动内存层次结构是昂贵的。 因此,如果您正在顺序处理大量数据,并且可以将其减少到1/8的大小,那么通常您将能够在更短的时间内处理更多的数据。
因此,上面的类比的常见用途是在涉及位标志的情况下将一堆布尔值存储在较小的空间中,例如:
enum Flags
{
flag_selected = 1 << 0,
flag_hidden = 1 << 1,
flag_removed = 1 << 2,
flag_hovering = 1 << 3,
flag_minimized = 1 << 4,
...
};
uint8_t flags = flag_selected | flag_hovering;
同时操作多个位
除了将所有数据压缩到更小的空间中,您还可以同时测试多个位:
// Check if the element is hidden or removed.
if (flags & (flag_hidden | flag_removed))
{
...
}
一个聪明的优化器通常会将其缩减为单个按位与
,如果flag_hidden
和flag_removed
是在编译时已知的字面常量。
作为另一个例子,让我们回到上面的例子:
bool data[64];
假设你想要测试是否所有的64个布尔值都被设置了,如果是的话,你需要执行不同的操作。根据这种表示方式,我们可能需要这样做:
bool all_set = true;
for (int j=0; j < 64; ++j)
{
if (!data[j])
{
all_set = false;
break;
}
}
if (all_set)
{
...
}
当位运算表示法允许我们这样做时,那就相当昂贵了:
uint64_t data = ...;
if (data == 0xffffffffffffffff)
{
// Do something different when all bits are set.
...
}
在64位机器上,此版本可以使用单个指令执行对所有64位设置的检查。使用SIMD寄存器,您甚至可以使用单个SIMD指令一次测试超过64位。
另一个例子是,假设您想计算设置了多少个布尔值。在这种情况下,您可能需要使用布尔表示进行操作:
int count = 0;
for (int j=0; j < 64; ++j)
count += data[j];
// do something with count
如果您使用位运算,可以这样做:
uint64_t data = ...;
const int count = __popcnt64(data);
// do something with count
有些硬件可以作为本地指令非常高效地执行这个任务,而另一些则仍然可以比循环遍历 64 个布尔值并计算被设置为 true 的布尔值的数量更快。
高效的算术运算
另一个常见的问题是高效的算术运算。如果你面对以下类似的情况:
x = pow(2, n);
如果 n
是一个运行时变量,那么你通常可以通过以下方式获得更高效的结果:
x = 1 << n;
当然,使用内置函数的优化编译器可能能够将前者转换为后者,但至少我最近检查过的C和C++编译器在编译时无法执行此优化,至少当n不是在编译时已知的情况下。
每当你处理2的幂时,通常可以使用位移和其他位运算来高效地完成许多操作。例如,考虑以下内容:
x = n % power_of_two;
...其中power_of_two
是一个始终为2的幂次方的运行时变量。在这种情况下,您可以执行以下操作:
x = n & (power_of_two - 1);
这与模数运算具有相同的效果(仅适用于2的幂次方)。这是因为2的幂次方值始终是一个设置位后跟着零。例如,16将是0b10000
。如果从中减去1,则变为:0b1111
,并使用按位与操作将有效地清除所有上位位,以一种类比于n%16
的方式。
类似的事情可以用左移来乘以2的幂次方,用右移来除以2的幂次方等等。许多硬件喜欢使用2的幂次方图像大小,如16x16、32x32、64x64、256x256等,其中一个主要原因是它使用位操作指令实现了高效的算术运算。
结论
总之,这是对位运算和指令可以做什么的简要介绍,包括快速算术、减少内存使用以及能够在不循环遍历它们并逐位操作它们的情况下同时对可能的许多位执行操作。
它们在性能关键领域仍然非常相关。例如,如果你看一下Atomontage体素渲染引擎,它声称可以仅用一个比特表示一个体素,这不仅重要是为了将巨大的体素数据适应DRAM,而且还要从较小、快速的存储器(如寄存器)中快速地呈现它。如果它要使用8位来存储需要单独检查的类似true/false
值,那么自然无法做到这一点。