golang 性能優化之 bitset 代替 hashset

hashset 是一種非常高效的資料結構，插入和查詢的複雜度都是 O(1)，基本上能滿足大部分場景的性能需求，但在一些特殊的場景下，頻次非常高的調用依然會成為性能瓶頸（用 pprof 分析），比如廣告裡面的定向邏輯，在一次請求中過濾邏輯可能會執行上千次，而其中有些過濾剛好都是一些枚舉值，比如性别定向，年齡定向等等，對于這種可以用枚舉表示的值可以用 bitset 優化，能有20多倍的性能提升

bitset 的本質也是一種 hashset，隻不過哈希桶用一個 uint64 來表示了，uint64 中的每一位用來代表一個元素是否存在，如果為1表示存在，為0表示不存在，而插入和查詢操作就變成了位運算

bitset 實作

bitset 的實作比較容易，下面這個是一個隻支援枚舉值不超過64的版本，當然也可以拓展到任意長度，使用一個 uint64 數組作為 hash 桶即可

type BitSet struct {
    bit uint64
}

func (bs *BitSet) Add(i uint64) {
    bs.bit |= << i
}

func (bs *BitSet) Del(i uint64) {
    bs.bit &= ^ << i)
}

func (bs BitSet) Has(i uint64) bool {
    return bs.bit&<<i) !=
}
           

性能測試

func BenchmarkSetContains(b *testing.B) {
    bitset := NewBitSet()
    hashset := map[uint64]struct{}{}
    for _, i := range []uint64,,,} {
        bitset.Add(i)
        hashset[i] = struct{}{}
    }

    b.Run("bitset", func(b *testing.B) {
        for i :=; i < b.N; i++ {
            for i := uint64); i < uint64); i++ {
                _ = bitset.Has(i)
            }
        }
    })

    b.Run("hashset", func(b *testing.B) {
        for i :=; i < b.N; i++ {
            for i := uint64); i < uint64); i++ {
                _, _ = hashset[i]
            }
        }
    })
}
           

BenchmarkSetContains/bitset-                        ns/op         B/op           allocs/op
BenchmarkSetContains/hashset-                       ns/op          B/op           allocs/op
           

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

參考連結

• 代碼位址：https://github.com/hatlonely/easygolang/blob/master/datastruct/bitset.go

轉載請注明出處

本文連結：http://www.hatlonely.com/2018/04/12/golang-性能優化之-bitset-代替-set/