Go: Map设计(2)

【译文】原文地址
本文用代码为例从更高的层次来分析Map的设计，紧随Go: Map设计(1)。强烈建议从设计(1)开始阅读便于理解本文当中提到的概念。

map的内部设计向我们展示了它是如何为性能和内存管理进行优化的。下面从map的定义开始。

Map初始化

Go提供了两种方式来初始化map和内部的桶：

• 用户显示定义map长度

m := make(map[string]int, 10)

• 按需更新map

m := make(map[string]int)
m[`foo`] = 1

在第二个例子当中，创建map没有指定长度，因此不会创建桶，Go将等待第一次更新来初始化map，第二行代码会创建桶。

两个例子当中，map都会根据需要扩容。第一个例子当中桶长度为10不会阻止map的扩容如果超过10个键值对，设定长度优化了map的使用，因为扩容是有成本的。

map按需扩容的影响

Go灵活的按需扩容是有代价的，我们可以通过初始化两个map并创建100和1000个键值对，运行这些简单的基准测试来对比看看扩容的影响。前两个基准测试map的长度是会定义为100和1000，另个一例子map的长度是没有定义的，按需扩容。

// 100 allocations
name                   time/op
LazyInitMap100Keys-8   6.67µs ± 0%
InitMap100Keys-8       3.57µs ± 0%
name                   alloc/op
LazyInitMap100Keys-8   5.59kB ± 0%
InitMap100Keys-8       2.97kB ± 0%
name                   allocs/op
LazyInitMap100Keys-8     18.0 ± 0%
InitMap100Keys-8         7.00 ± 0%
// 1000 allocations
name                   time/op
LazyInitMap1000Keys-8  77.8µs ± 0%
InitMap1000Keys-8      32.2µs ± 0%
name                   alloc/op
LazyInitMap1000Keys-8  86.8kB ± 0%
InitMap1000Keys-8      41.2kB ± 0%
name                   allocs/op
LazyInitMap1000Keys-8    66.0 ± 0%
InitMap1000Keys-8        7.00 ± 0%

可以看到map扩容和桶的扩展产生的代价，执行时间增加80-140%。内存分配也相应的受到影响。关于内存，Go提供了灵活设计来节省内存的消耗。

桶和边界对齐

如前所述每个桶只包含8个键值对，有趣的是为了节省内存Go会先保存key值然后在保存value：

image.png

这个可以防止因内存的边界对齐而浪费内存。事实上，因为keys和values不一定大小相同的，将导致内存大量的边界对齐出现。下面是一个两对sting/bool的键值对例子，如果keys和values混合存储将导致很多边界对齐出现：

混合存储边界对齐

如果key和value单独分组的话：

image.png

可以清楚的看到内存对齐消除了，下面看看如何访问这些值。

value值的读取

m := make(map[string]int)
v := m[`my_key`]
v, ok := m[`my_key`]

我们可以单独读取value值，也可以使用一个布尔值来表示键值对是否在map中存在。我们可能会想，这怎么可能。因为所有的返回结果要么显示映射到对应的变量或者用_忽略。实际上，通过汇编代码我们可以发现一些线索：

(main.go:3) CALL    runtime.mapaccess1_faststr(SB)
(main.go:4) CALL    runtime.mapaccess2_faststr(SB)

正如我们看到的，根据读取key/value的方式，编译器会使用两个参数不同的内部函数：

func mapaccess1_faststr(t *maptype, h *hmap, ky string) unsafe.Pointer

func mapaccess2_faststr(t *maptype, h *hmap, ky string) (unsafe.Pointer, bool)

编译器的这个技巧非常有用，为我们提供了读取数据的灵活性。编译器甚至可以根据map的key值类型来使用对应的函数。在以上例子当中，我们使用一个以string作为key的map，所选择的方法是mapaccess1_faststr。后缀str表示字符串作为key进行了优化。下面看下整数key：

m := make(map[int]int)

v := m[1]
v, ok := m[1]

汇编代码显示了所选择的方法：

(main.go:3) CALL    runtime.mapaccess1_fast64(SB)
(main.go:4) CALL    runtime.mapaccess2_fast64(SB)

现在，编译器将使用一种专用的方法来映射，将int64作为key。如果开发人员没有定义map的容量，那么每个方法都是针对相关类型的hash比较进行了优化。