Go
by smallnest

Go中秘而不宣的数据结构 BitVec, 资源优化方法之位向量

位图(bitmap)是一种优雅而高效的数据结构,它巧妙地利用了计算机最底层的位运算能力。你可以把它想象成一个巨大的开关阵列,每个开关只有打开和关闭两种状态 —— 这就是位图的本质。每一位都可以独立控制,却又可以通过位运算实现群体操作。

在实际应用中,位图的威力令人惊叹。设想你需要在海量数据中查找重复的数字,传统的哈希表或数组都会占用大量内存。而位图却能巧妙地用一个比特位标记一个数字的出现情况,极大地压缩了存储空间。在处理10亿个不重复的整数时,位图仅需要125MB内存,相比其他数据结构动辄需要几个GB,效率提升显著。

位图的运用也体现在我们日常使用的数据库系统中。数据库会用位图索引来加速查询,尤其是对于性别、状态这样的枚举字段,一个位图就能快速定位满足条件的记录。比如在电商系统中,快速筛选出"在售且有库存"的商品,位图索引可以通过简单的位与运算瞬间得出结果。

在大规模系统的权限控制中,位图也显示出其独特魅力。用户的各项权限可以编码到不同的位上,判断权限时只需一条位运算指令,既高效又直观。比如一个CMS系统,可以用一个32位的整数表示用户的全部权限状态,包括读、写、管理等多个维度。

布隆过滤器更是位图思想的精妙应用。它用多个哈希函数在位图上标记数据,能够以极小的内存代价判断一个元素是否可能存在。这在网页爬虫、垃圾邮件过滤等场景下广泛应用。虽然可能有小概率的误判,但在实际应用中往往是可以接受的权衡。

正是由于以上特点,位图在处理海量数据、状态标记、数据压缩、快速统计等场景中表现出色。它用最简单的方式解决了最复杂的问题,这正是计算机科学之美的体现。

BitVec 和 BitMap 类似，只是关注点有些不同。BitVec更像是位操作的抽象数据类型,它强调的是向量化的位运算操作。比如在Rust语言中, bitvec 提供了一系列方便的接口来进行位操作。而Bitmap则更强调其作为"图"的特性,通常用固定大小的位数组来表示集合中元素的存在性。

BitVec 具有以下的优势：

  • 空间效率高 - 每个比特位只占用1位(bit)空间,可以表示0或1两种状态
  • 快速的位运算 - 支持AND、OR、XOR等位运算操作,性能很高，甚至可以利用 SIMD 加速
  • 随机访问快 - 可以O(1)时间定位到任意位置的比特位
  • 紧凑存储 - 一个字节(byte)可以存储8个比特位的信息
  • 内存占用小 - 对于数据量大但状态简单的场景很节省内存

Go 内部实现的 BitVec

在 Go 运行时的内部， cmd/compile/internal/bitvec 实现了一个位向量数据结构 BitVec，在 ssa 活跃性分析中使用(bvecSet 封装了 BitVec)。在 runtime/stack.go 中实现了 bitvector 并在内存管理中使用。

我们重点看 BitVec, 它的方法比较全。

BitVec 的结构体定义如下：

1
2
3
4
5
6
7
8
9
type BitVec struct {
	N int32    // 这个向量中包含的bit数
	B []uint32 // 保存这些bit所需的数组
}
func New(n int32) BitVec {
	nword := (n + wordBits - 1) / wordBits // 计算保存这些bit所需的最少的数组
	return BitVec{n, make([]uint32, nword)}
}

然后定义了一批位操作的方法：

这里可以看到 Go 内部实现也有一些"不规范"的方法，这些 Receiver 的名字不一致，叫做了 dst、bv、bv 1 三种名称，看起来是有深意的。dst 代表操作最后存储的位向量。不过 bv 1 就有点说不过去了，虽然也能理解，为了和参数中的 bv 2 保持一致。

我们可以挑几个方法看它的实现。

比如 And 方法:

1
2
3
4
5
6
7
8
9
10
func (dst BitVec) And(src1, src2 BitVec) {
	if len(src1.B) == 0 {
		return
	}
	_, _ = dst.B[len(src1.B)-1], src2.B[len(src1.B)-1] // hoist bounds checks out of the loop
	for i, x := range src1.B {
		dst.B[i] = x & src2.B[i]
	}
}

就是求两个位向量的交集，这里用到了位运算 &。逐个元素进行位与操作，然后存储到 dst 中。

可以看到如果使用SIMD指令，这里的性能会有很大的提升。

再比如Not方法:

1
2
3
4
5
6
7
8
func (bv BitVec) Not() {
	for i, x := range bv.B {
		bv.B[i] = ^x
	}
	if bv.N%wordBits != 0 {
		bv.B[len(bv.B)-1] &= 1<<uint(bv.N%wordBits) - 1 // clear bits past N in the last word
	}
}

这里是对位向量取反，用到了位运算 ^。然后对最后一个元素进行了特殊处理，清除了多余的位。
这里这一句bv.B[len(bv.B)-1] &= 1<<uint(bv.N%wordBits) - 1可能难以理解，其实是为了清除最后一个元素中多余的位，这里的 1<<uint(bv.N%wordBits) - 1 就是一个掩码，用来清除多余的位。

再比如Count方法:

1
2
3
4
5
6
7
func (bv BitVec) Count() int {
	n := 0
	for _, x := range bv.B {
		n += bits.OnesCount32(x)
	}
	return n
}

这里是统计位向量中 1 的个数，用到了 bits.OnesCount32 方法，这个方法是一个快速计算Uint32中bit为1的个数的方法。

这里的实现都是比较简单的，但是在实际应用中，位向量的操作是非常高效的，可以用来解决很多问题。

如果你的项目中有这种需求，比如你要实现一个布隆过滤器/布谷鸟过滤器，或者你要实现一个高效的权限控制系统，那么位向量是一个非常好的选择。