map[int]interface{} vs map[int]struct{} 的内存分配

Question

我们和一位同事讨论了使用 map 作为列表的性能，并比较了 interface 作为 value( map[int]interface{}) 与空结构（）的使用map[int]struct{})，我们在基准测试中得到了一些奇怪的值。

代码

package main

func main() {}

func MapWithInterface() {
    m := map[int]interface{}{}
    for i := 1; i <= 100; i++ {
        m[i] = nil
    }
}

func MapWithEmptyStruct() {
    m := map[int]struct{}{}
    for i := 1; i <= 100; i++ {
        m[i] = struct{}{}
    }
}

测试

package main

import "testing"

func Benchmark_Interface(b *testing.B) {
    for i := 0; i < b.N; i++ {
        MapWithInterface()
    }
}

func Benchmark_EmptyStruct(b *testing.B) {
    for i := 0; i < b.N; i++ {
        MapWithEmptyStruct()
    }
}

结果

go version go1.15.5 darwin/amd64

go test -bench=. -benchmem

goos: darwin
goarch: amd64
pkg: awesomeProject1
Benchmark_Interface-8         130419          8949 ns/op        7824 B/op          7 allocs/op
Benchmark_EmptyStruct-8       165147          6964 ns/op        3070 B/op         17 allocs/op
PASS
ok      awesomeProject1 3.122s

题

因此，似乎空结构版本运行速度更快，使用的内存更少，但分配更多，无法弄清楚原因。有谁知道为什么会这样？

Answer 1

我创建了一个存储库，其中包含一些测试来帮助理解这个答案。

长话短说

Golang 中映射的内部设计针对性能和内存管理进行了高度优化。映射会跟踪可以保存指针的键和值。如果存储桶中的条目无法容纳指针，则映射只会创建溢出存储桶以避免 GC 带来不必要的开销，从而导致更多分配（情况map[int]struct{}）。

长答案

我们需要了解地图初始化和地图结构。然后，我们将分析基准。

地图初始化

地图初始化有两种方法：

• make(map[int]string)当我们不知道将添加多少条目时。
• make(map[int]string, hint)当我们知道要添加多少条目时。hint是初始容量的估计。

映射是可变的，无论我们选择哪种初始化方法，它们都会按需增长。然而，第二种方法至少为hint条目预先分配内存，这会提高性能。

地图结构

Go 中的映射是一个哈希表，将其键/值对存储到存储桶中。每个存储桶都是一个最多可容纳 8 个条目的数组。默认的存储桶数量为 1。一旦每个存储桶中的条目数量达到存储桶的平均负载（也称为负载因子），映射就会通过将存储桶数量加倍而变得更大。每次映射增长时，它都会为新出现的条目分配内存。实际上，每当桶的负载达到 6.5 或更多时，地图就会增长。

在幕后，映射是指向hmap结构的指针。还有一个maptype结构体，它保存有关 的类型的一些信息map。地图的源代码可以在这里找到：

https://github.com/golang/go/blob/master/src/runtime/map.go

您可以在下面找到有关如何破解类型map以及如何查看地图增长的一些见解：

• https://hackernoon.com/some-insights-on-maps-in-golang-rm5v3ywh
• https://play.golang.org/p/NaoC8fkmy9x

需要注意的一件重要事情是，映射会跟踪可以保存指针的键和值。如果存储桶中的条目不能容纳任何指针，则该存储桶将被标记为不包含指针，并且映射只会创建溢出存储桶（这意味着更多的内存分配）。这避免了 GC 带来的不必要的开销。请参阅结构中的评论mapextra（第 132 行）和这篇文章以供参考。

基准测试

空结构struct{}没有字段，也不能保存任何指针。因此，空结构中的存储桶将被标记为不包含指针，并且随着类型映射的map[int]struct{}增长，我们可以预期会分配更多的内存。另一方面，interface{}可以保存任何值，包括指针。Map Bucket 跟踪保存指针的内存前缀的大小（ptrdatafield，第 33 行），以决定是否创建更多溢出 Bucket（map.go，第 265 行）。请参阅此链接map[int]struct{}以查看保存和的所有指针的内存前缀的大小map[int]interface{}。

当我们看到 CPU 配置文件时，两个基准测试（Benchmark_EmptyStruct和）之间的差异就很明显了。没有导致额外内存分配流程的方法：Benchmark_InterfaceBenchmark_Interface(*hmap) createOverflow

Benchmark_EmptyStruct CPU 配置文件

Benchmark_EmptyStruct CPU 配置文件 [ png , svg ]

Benchmark_Interface CPU 配置文件

Benchmark_Interface CPU 配置文件 [ png , svg ]

我定制了测试以通过条目数量和地图的初始容量（提示）。以下是执行的结果。当条目数较少或初始容量大于条目数时，结果基本相同。如果您有很多条目且初始容量为 0，您将获得完全不同的分配数量。

基准	参赛作品	初始容量	速度	字节/操作数	分配/操作
空结构体	7	0	115 纳秒/操作	0 B/操作	0 分配/操作
界面	7	0	94.8 纳秒/操作	0 B/操作	0 分配/操作
空结构体	8	0	114 纳秒/操作	0 B/操作	0 分配/操作
界面	8	0	110 纳秒/操作	0 B/操作	0 分配/操作
空结构体	9	0	339 纳秒/操作	160 B/操作	1 个分配/操作
界面	9	0	439 纳秒/操作	416 B/操作	1 个分配/操作
空结构体	16	16	444 纳秒/操作	324 B/操作	1 个分配/操作
界面	16	16	586 纳秒/操作	902 B/操作	1 个分配/操作
空结构体	16	32	448 纳秒/操作	640 B/操作	1 个分配/操作
界面	16	32	724 纳秒/操作	1792 B/OP	1 个分配/操作
空结构体	16	100	634 纳秒/操作	1440 B/操作	2 个分配/操作
界面	16	100	1241 纳秒/操作	4128 B/操作	2 个分配/操作
空结构体	100	0	5339 纳秒/操作	3071 B/操作	17 个分配/操作
界面	100	0	6524 纳秒/操作	7824 B/op	7 个分配/操作
空结构体	100	128	2665 纳秒/操作	3109 B/操作	2 个分配/操作
界面	100	128	3938 纳秒/操作	8224 B/操作	2 个分配/操作

结论

基准测试方法没有任何问题。这一切都与性能和内存管理的映射优化有关。基准测试显示每次迭代的平均值。类型的映射速度map[int]interface{}较慢，因为当 GC 扫描可以保存指针的存储桶时，它们的性能会下降。类型的映射map[int]struct{}使用较少的内存，因为它们实际上使用较少的内存（Test_EmptyStructValueSize显示struct{}{}大小为零）。尽管nil的值为零interface{}，但此类型需要一些空间来存储任何值（测试显示持有值Test_NilInterfaceValueSize的大小不为零）。最后，空结构基准分配更高，因为该类型需要更多溢出桶（用于性能优化），因为它的桶不保存任何指针。interface{}nilmap[int]struct{}