go map 的内存高效实现？

Question

我的用例是通过网络传输一组成员（整数），所以我们采用增量编码，在接收端我们解码并将整个列表作为映射，map[string]struct{} 复杂度为 O(1)用于会员检查。我面临的问题是，对于 200 万个整数，成员的实际大小仅为 15MB，但堆中映射的大小为 100+MB。似乎 Go 的实际地图实现不适合大型地图。由于它是一个客户端 SDK，我不想对可用内存产生太大影响，并且可能有多个这样的组需要在内存中保存很长时间——大约 1 周。为此，Go 中是否有更好的替代 DS？type void struct{}func ToMap(v []int64) map[string]void { out := map[string]void{} for _, i := range v {   out[strconv.Itoa(int(i))] = void{} } return out}

Answer 1

这是一种更节省内存的地图形式：

type void struct{}

func ToMap(v []int64) map[int64]void {

    m := make(map[int64]void, len(v))

    for _, i := range v {

        m[i] = void{}

    }

    return m

}

Go 映射针对整数键进行了优化。通过给出确切的地图大小作为提示来优化地图分配。

Astring有一个隐式指针，它会使垃圾收集器 (gc) 每次扫描时都遵循该指针。

这是 200 万个伪随机整数的 Go 基准测试：

package main

import (

    "math/rand"

    "strconv"

    "testing"

)

type void struct{}

func ToMap1(v []int64) map[string]void {

    out := map[string]void{}

    for _, i := range v {

        out[strconv.Itoa(int(i))] = void{}

    }

    return out

}

func ToMap2(v []int64) map[int64]void {

    m := make(map[int64]void, len(v))

    for _, i := range v {

        m[i] = void{}

    }

    return m

}

var benchmarkV = func() []int64 {

    v := make([]int64, 2000000)

    for i := range v {

        v[i] = rand.Int63()

    }

    return v

}()

func BenchmarkToMap1(b *testing.B) {

    b.ReportAllocs()

    b.ResetTimer()

    for N := 0; N < b.N; N++ {

        ToMap1(benchmarkV)

    }

}

func BenchmarkToMap2(b *testing.B) {

    b.ReportAllocs()

    b.ResetTimer()

    for N := 0; N < b.N; N++ {

        ToMap2(benchmarkV)

    }

}

输出：

$ go test tomap_test.go -bench=.

BenchmarkToMap1-4     2  973358894 ns/op    235475280 B/op    2076779 allocs/op

BenchmarkToMap2-4    10  188489170 ns/op     44852584 B/op         23 allocs/op

$