map[int]interface{} 与 map[int]struct{} 的内存分配
Memory allocation of map[int]interface{} vs map[int]struct{}
我们与一位同事讨论了将映射用作列表的性能，并将接口用作值 (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
问题
因此，似乎空结构版本 运行 速度更快，使用的内存更少，但分配更多，无法弄清楚原因。有谁知道为什么会这样？
你的测试方法有误。您对向地图添加 100 个项目的 N 个样本进行基准测试。由于将值分配到映射中而完成的分配处理映射索引，这会混淆分配。两个值都不分配任何内容。
为了获得可靠的结果，它应该看起来像这样：
package main
import "testing"
func Benchmark_Interface(b *testing.B) {
m := map[int]interface{}{}
for i := 0; i < b.N; i++ {
m[i] = nil
}
}
func Benchmark_EmptyStruct(b *testing.B) {
m := map[int]struct{}{}
for i := 0; i < b.N; i++ {
m[i] = struct{}{}
}
}
这说明总体上没有区别
我创建了一个 repository，其中包含一些测试以帮助理解这个答案。
TL;DR
Golang 中映射的内部设计针对性能和内存管理进行了高度优化。地图跟踪可以保存指针的键和值。如果存储桶中的条目不能容纳指针，映射将创建溢出存储桶以避免不必要的 GC 开销，这会导致更多分配（map[int]struct{} 的情况）。
长答案
我们需要了解地图初始化和地图结构。然后，我们将分析基准。
地图初始化
地图初始化有两种方法：
make(map[int]string) 当我们不知道要添加多少条目时。make(map[int]string, hint) 当我们知道将添加多少条目时。 hint 是对初始容量的估计。
地图是 mutable，无论我们选择哪种初始化方法，它们都会增长 on-demand。但是，第二种方法 pre-allocates 内存至少 hint 个条目，这会提高性能。
地图结构
Go 中的映射是一个散列 table，它将其 key/value 对存储到桶中。每个桶是一个最多包含 8 个条目的数组。桶的默认数量是 1。一旦每个桶中的条目数量达到桶的平均负载（也称为负载因子），地图就会通过加倍桶的数量而变大。每次地图增长时，它都会为 new-coming 条目分配内存。实际上，每当桶的负载达到 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 开销。请参阅此 comment in the mapextra struct (line 132) and this post 以供参考。
基准
空结构 struct{} 没有字段，不能包含任何指针。因此，空结构案例中的桶将被标记为 不包含指针 并且我们可以预期随着类型 map[int]struct{} 的映射的增长会有更多的内存分配。另一方面，interface{} 可以保存任何值，包括指针。映射桶跟踪保存指针的内存前缀的大小（ptrdata field, line 33) to decide if more overflow buckets will be created (map.go, line 265). Refer to this link 以查看保存 map[int]struct{} 和 map[int]interface{}.
的所有指针的内存前缀的大小
当我们看到 CPU 配置文件时，两个基准（Benchmark_EmptyStruct 和 Benchmark_Interface）之间的区别就很明显了。 Benchmark_Interface 没有导致额外内存分配流程的 (*hmap) createOverflow 方法：
Benchmark_EmptyStruct CPU 简介
Benchmark_EmptyStruct CPU 简介 [png, svg]
Benchmark_Interface CPU 简介
Benchmark_Interface CPU 简介 [png, svg]
我自定义测试以通过条目数和地图的初始容量（提示）。这是处决的结果。当条目数很少或初始容量大于条目数时，结果基本相同。如果您有很多条目且初始容量为 0，您将获得完全不同的分配数。
Benchmark
Entries
InitialCapacity
Speed
Bytes/op
Allocations/op
EmptyStruct
7
0
115 ns/op
0 B/op
0 allocs/op
Interface
7
0
94.8 ns/op
0 B/op
0 allocs/op
EmptyStruct
8
0
114 ns/op
0 B/op
0 allocs/op
Interface
8
0
110 ns/op
0 B/op
0 allocs/op
EmptyStruct
9
0
339 ns/op
160 B/op
1 allocs/op
Interface
9
0
439 ns/op
416 B/op
1 allocs/op
EmptyStruct
16
16
444 ns/op
324 B/op
1 allocs/op
Interface
16
16
586 ns/op
902 B/op
1 allocs/op
EmptyStruct
16
32
448 ns/op
640 B/op
1 allocs/op
Interface
16
32
724 ns/op
1792 B/op
1 allocs/op
EmptyStruct
16
100
634 ns/op
1440 B/op
2 allocs/op
Interface
16
100
1241 ns/op
4128 B/op
2 allocs/op
EmptyStruct
100
0
5339 ns/op
3071 B/op
17 allocs/op
Interface
100
0
6524 ns/op
7824 B/op
7 allocs/op
EmptyStruct
100
128
2665 ns/op
3109 B/op
2 allocs/op
Interface
100
128
3938 ns/op
8224 B/op
2 allocs/op
结论
基准测试方法没有任何问题。这都与性能和内存管理的地图优化有关。基准显示每次迭代的平均值。 map[int]interface{} 类型的映射速度较慢，因为当 GC 扫描可以容纳指针的桶时，它们的性能会下降。 map[int]struct{} 类型的映射使用较少的内存，因为它们实际上使用较少的内存（Test_EmptyStructValueSize 表明 struct{}{} 的大小为零）。尽管 nil 是 interface{} 的零值，但这种类型需要一些 space 来存储任何值（Test_NilInterfaceValueSize 测试显示 interface{} 的大小持有 nil 值不为零）。最后，空结构基准分配更高，因为类型 map[int]struct{} 需要更多溢出桶（用于性能优化），因为它的桶不包含任何指针。
我们与一位同事讨论了将映射用作列表的性能，并将接口用作值 (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
问题
因此，似乎空结构版本 运行 速度更快，使用的内存更少，但分配更多，无法弄清楚原因。有谁知道为什么会这样？
你的测试方法有误。您对向地图添加 100 个项目的 N 个样本进行基准测试。由于将值分配到映射中而完成的分配处理映射索引，这会混淆分配。两个值都不分配任何内容。
为了获得可靠的结果，它应该看起来像这样：
package main
import "testing"
func Benchmark_Interface(b *testing.B) {
m := map[int]interface{}{}
for i := 0; i < b.N; i++ {
m[i] = nil
}
}
func Benchmark_EmptyStruct(b *testing.B) {
m := map[int]struct{}{}
for i := 0; i < b.N; i++ {
m[i] = struct{}{}
}
}
这说明总体上没有区别
我创建了一个 repository，其中包含一些测试以帮助理解这个答案。
TL;DR
Golang 中映射的内部设计针对性能和内存管理进行了高度优化。地图跟踪可以保存指针的键和值。如果存储桶中的条目不能容纳指针，映射将创建溢出存储桶以避免不必要的 GC 开销，这会导致更多分配（map[int]struct{} 的情况）。
长答案
我们需要了解地图初始化和地图结构。然后，我们将分析基准。
地图初始化
地图初始化有两种方法：
make(map[int]string)当我们不知道要添加多少条目时。make(map[int]string, hint)当我们知道将添加多少条目时。hint是对初始容量的估计。
地图是 mutable，无论我们选择哪种初始化方法，它们都会增长 on-demand。但是，第二种方法 pre-allocates 内存至少 hint 个条目，这会提高性能。
地图结构
Go 中的映射是一个散列 table，它将其 key/value 对存储到桶中。每个桶是一个最多包含 8 个条目的数组。桶的默认数量是 1。一旦每个桶中的条目数量达到桶的平均负载（也称为负载因子），地图就会通过加倍桶的数量而变大。每次地图增长时，它都会为 new-coming 条目分配内存。实际上，每当桶的负载达到 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 开销。请参阅此 comment in the mapextra struct (line 132) and this post 以供参考。
基准
空结构 struct{} 没有字段，不能包含任何指针。因此，空结构案例中的桶将被标记为 不包含指针 并且我们可以预期随着类型 map[int]struct{} 的映射的增长会有更多的内存分配。另一方面，interface{} 可以保存任何值，包括指针。映射桶跟踪保存指针的内存前缀的大小（ptrdata field, line 33) to decide if more overflow buckets will be created (map.go, line 265). Refer to this link 以查看保存 map[int]struct{} 和 map[int]interface{}.
当我们看到 CPU 配置文件时，两个基准（Benchmark_EmptyStruct 和 Benchmark_Interface）之间的区别就很明显了。 Benchmark_Interface 没有导致额外内存分配流程的 (*hmap) createOverflow 方法：
Benchmark_EmptyStruct CPU 简介
Benchmark_Interface CPU 简介
我自定义测试以通过条目数和地图的初始容量（提示）。这是处决的结果。当条目数很少或初始容量大于条目数时，结果基本相同。如果您有很多条目且初始容量为 0，您将获得完全不同的分配数。
| Benchmark | Entries | InitialCapacity | Speed | Bytes/op | Allocations/op |
|---|---|---|---|---|---|
| EmptyStruct | 7 | 0 | 115 ns/op | 0 B/op | 0 allocs/op |
| Interface | 7 | 0 | 94.8 ns/op | 0 B/op | 0 allocs/op |
| EmptyStruct | 8 | 0 | 114 ns/op | 0 B/op | 0 allocs/op |
| Interface | 8 | 0 | 110 ns/op | 0 B/op | 0 allocs/op |
| EmptyStruct | 9 | 0 | 339 ns/op | 160 B/op | 1 allocs/op |
| Interface | 9 | 0 | 439 ns/op | 416 B/op | 1 allocs/op |
| EmptyStruct | 16 | 16 | 444 ns/op | 324 B/op | 1 allocs/op |
| Interface | 16 | 16 | 586 ns/op | 902 B/op | 1 allocs/op |
| EmptyStruct | 16 | 32 | 448 ns/op | 640 B/op | 1 allocs/op |
| Interface | 16 | 32 | 724 ns/op | 1792 B/op | 1 allocs/op |
| EmptyStruct | 16 | 100 | 634 ns/op | 1440 B/op | 2 allocs/op |
| Interface | 16 | 100 | 1241 ns/op | 4128 B/op | 2 allocs/op |
| EmptyStruct | 100 | 0 | 5339 ns/op | 3071 B/op | 17 allocs/op |
| Interface | 100 | 0 | 6524 ns/op | 7824 B/op | 7 allocs/op |
| EmptyStruct | 100 | 128 | 2665 ns/op | 3109 B/op | 2 allocs/op |
| Interface | 100 | 128 | 3938 ns/op | 8224 B/op | 2 allocs/op |
结论
基准测试方法没有任何问题。这都与性能和内存管理的地图优化有关。基准显示每次迭代的平均值。 map[int]interface{} 类型的映射速度较慢，因为当 GC 扫描可以容纳指针的桶时，它们的性能会下降。 map[int]struct{} 类型的映射使用较少的内存，因为它们实际上使用较少的内存（Test_EmptyStructValueSize 表明 struct{}{} 的大小为零）。尽管 nil 是 interface{} 的零值，但这种类型需要一些 space 来存储任何值（Test_NilInterfaceValueSize 测试显示 interface{} 的大小持有 nil 值不为零）。最后，空结构基准分配更高，因为类型 map[int]struct{} 需要更多溢出桶（用于性能优化），因为它的桶不包含任何指针。