golang性能优化之bitset代替hashset

Chole121 · · 1515 次点击 · · 开始浏览

这是一个创建于的文章，其中的信息可能已经有所发展或是发生改变。

hashset 是一种非常高效的数据结构，插入和查询的复杂度都是 O(1)，基本上能满足大部分场景的性能需求，但在一些特殊的场景下，频次非常高的调用依然会成为性能瓶颈（用 pprof 分析），比如广告里面的定向逻辑，在一次请求中过滤逻辑可能会执行上千次，而其中有些过滤刚好都是一些枚举值，比如性别定向，年龄定向等等，对于这种可以用枚举表示的值可以用 bitset 优化，能有20多倍的性能提升

bitset 的本质也是一种 hashset，只不过哈希桶用一个 uint64 来表示了，uint64 中的每一位用来代表一个元素是否存在，如果为1表示存在，为0表示不存在，而插入和查询操作就变成了位运算

bitset 实现

bitset 的实现比较容易，下面这个是一个只支持枚举值不超过64的版本，当然也可以拓展到任意长度，使用一个 uint64 数组作为 hash 桶即可

1.  type BitSet  struct  {
2.  bit uint64
3.  }
4.
5.  func (bs *BitSet)  Add(i uint64)  {
6.  bs.bit |=  1  << i
7.  
8.
9. func (bs *BitSet)  Del(i uint64)  {
10.  bs.bit &=  ^(1  << i)
11.  }
12.
13.  func (bs BitSet)  Has(i uint64)  bool  {
14.  return bs.bit&(1<<i)  !=  0
15.  }

性能测试

1.  func BenchmarkSetContains(b *testing.B)  {
2.  bitset :=  NewBitSet()
3.  hashset := map[uint64]struct{}{}
4.  for _, i := range []uint64{1,  2,  4,  10}  {
5.  bitset.Add(i)
6.  hashset[i]  =  struct{}{}
7.  }
8.
9.  b.Run("bitset", func(b *testing.B)  {
10.  for i :=  0; i < b.N; i++  {
11.  for i := uint64(0); i < uint64(10); i++  
12.  _ = bitset.Has(i)
13.  }
14.  }
15.  })
16.
17.  b.Run("hashset", func(b *testing.B)  {
18.  for i :=  0; i < b.N; i++  {
19.  for i := uint64(0); i < uint64(10); i++  {
20.  _, _ = hashset[i]
21.  }
22.  }
23.  })
24.  }

1.  BenchmarkSetContains/bitset-8  500000000  3.81 ns/op 0 B/op 0 allocs/op
2.  BenchmarkSetContains/hashset-8  20000000  89.4 ns/op 0 B/op 0 allocs/op

可以看到 bitset 相比 hashset 有20多倍的性能提升