去映射大量键的性能不佳

Question

我最近发现 go maps 有非常奇怪的行为。用例是创建一组整数并让 O(1) 检查 IsMember(id int)。

当前的实现是：

func convertToMap(v []int64) map[int64]void {
    out := make(map[int64]void, len(v))
    for _, i := range v {
        out[i] = void{}
    }
   return out
}

type Group struct {
    members map[int64]void
}

type void struct{}

func (g *Group) IsMember(input string) (ok bool) {
    memberID, _ := strconv.ParseInt(input, 10, 64)      
    _, ok = g.members[memberID]
    return
}

当我对 IsMember 方法进行基准测试时，直到 600 万成员，一切看起来都很好。但除此之外，地图查找每次查找需要 1 秒！！

基准测试：

func BenchmarkIsMember(b *testing.B) {
    b.ReportAllocs()
    b.ResetTimer()
    g := &Group{}
    g.members = convertToMap(benchmarkV)

    for N := 0; N < b.N && N < sizeOfGroup; N++ {
        g.IsMember(benchmarkKVString[N])
    }
}

var benchmarkV, benchmarkKVString = func(size int) ([]int64, []string{
    v := make([]int64, size)
    s := make([]string, size)
    for i := range v {
        val := rand.Int63()
        v[i] = val
        s[i] = strconv.FormatInt(val, 10)
    }
return v, s
}(sizeOfGroup)

基准数字：

const sizeOfGroup  = 6000000
BenchmarkIsMember-8      2000000           568 ns/op          50 B/op          0 allocs/op

const sizeOfGroup  = 6830000
BenchmarkIsMember-8            1    1051725455 ns/op    178767208 B/op        25 allocs/op

任何超过 680 万的组大小都会给出相同的结果。

有人可以帮我解释为什么会这样吗？可以做些什么来在仍然使用地图的同时提高性能吗？

另外，我不明白为什么要分配这么多内存？就算是碰撞再遍历链表耗时，也不应该有mem分配，我的思路是不是错了？

Answer 1

无需测量将切片转换为映射的额外分配，因为我们只想测量查找操作。

我稍微修改了基准：

func BenchmarkIsMember(b *testing.B) {
    fn := func(size int) ([]int64, []string) {
        v := make([]int64, size)
        s := make([]string, size)

        for i := range v {
            val := rand.Int63()
            v[i] = val
            s[i] = strconv.FormatInt(val, 10)
        }

        return v, s
    }

    for _, size := range []int{
        6000000,
        6800000,
        6830000,
        60000000,
    } {
        b.Run(fmt.Sprintf("size=%d", size), func(b *testing.B) {
            var benchmarkV, benchmarkKVString = fn(size)

            g := &deltaGroup{}
            g.members = convertToMap(benchmarkV)

            b.ReportAllocs()
            b.ResetTimer()

            for N := 0; N < b.N && N < size; N++ {
                g.IsMember(benchmarkKVString[N])
            }
        })
    }
}

得到如下结果：

go test ./... -bench=. -benchtime=10s -cpu=1
goos: linux
goarch: amd64
pkg: trash
BenchmarkIsMember/size=6000000          2000000000               0.55 ns/op            0 B/op          0 allocs/op
BenchmarkIsMember/size=6800000          1000000000               1.27 ns/op            0 B/op          0 allocs/op
BenchmarkIsMember/size=6830000          1000000000               1.23 ns/op            0 B/op          0 allocs/op
BenchmarkIsMember/size=60000000         100000000                136 ns/op               0 B/op          0 allocs/op
PASS
ok      trash   167.578s

降级并不像您的示例中那么明显。

去映射大量键的性能不佳

go maps non-performant for large number of keys

go

hashmap

maps

hash-collision