неиспользуемые карты для большого количества ключей

Question

Недавно я обнаружил очень странное поведение с go-картами.Вариант использования - создание группы целых чисел и проверка 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, до 6 миллионов членов, все выглядит хорошо.Но, кроме того, поиск карты занимает 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

Все, что выше группыразмер 6,8 млн. дает тот же результат.

Может ли кто-нибудь помочь мне объяснить, почему это происходит, и можно ли что-нибудь сделать, чтобы сделать это быстродействующим, все еще используя карты?

Кроме того, я не понимаю, почему выделяется столько памяти?Даже если время затрачивается на столкновение, а затем на обход связанного списка, не должно быть никакого распределения памяти, мой мыслительный процесс неверен?

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

Деградация не так значительна, как в вашем примере.