Go中秘而不宣的数据结构 BitVec：位向量125MB存储10亿个数据

秘而不宣系列

Go中秘而不宣的数据结构 Treap：平衡树不一定就用红黑树
Go中秘而不宣的数据结构 runq, 难怪运行时调度那么好
Go中秘而不宣的数据结构 spmc, 10倍性能于 channel

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

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

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

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

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

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

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

BitVec 具有以下的优势：

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

Go 内部实现的 BitVec

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

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

BitVec 的结构体定义如下：

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)}
}

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

• func (dst BitVec) And(src1, src2 BitVec) ^[4] ：对两个位向量进行与操作，结果放入到 dst 位向量中
• func (dst BitVec) AndNot(src1, src2 BitVec) ^[5]
• func (bv BitVec) Clear() ^[6]
• func (dst BitVec) Copy(src BitVec) ^[7]
• func (bv BitVec) Count() int ^[8]
• func (bv1 BitVec) Eq(bv2 BitVec) bool ^[9]
• func (bv BitVec) Get(i int32) bool ^[10]
• func (bv BitVec) IsEmpty() bool ^[11]
• func (bv BitVec) Next(i int32) int32 ^[12]
• func (bv BitVec) Not() ^[13]
• func (dst BitVec) Or(src1, src2 BitVec) ^[14]
• func (bv BitVec) Set(i int32) ^[15]
• func (bv BitVec) String() string ^[16]
• func (bv BitVec) Unset(i int32) ^[17]

“

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

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

比如 And 方法:

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 方法:

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< 可能难以理解，其实是为了清除最后一个元素中多余的位，这里的 1< 就是一个掩码，用来清除多余的位。

再比如 Count 方法:

func (bv BitVec) Count() int {
 n := 0
 for _, x := range bv.B {
  n += bits.OnesCount32(x)
 }
 return n
}

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

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

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