ℹ️ 这篇文章是 “Go: 通过例子学习 Map 的设计” 的下一篇，它从高层次上介绍了 map 的设计。为了理解下文讨论的概念，我强烈建议你从上一篇文章开始阅读。



map的内部设计向我们展示了如何针对性能以及内存管理对其进行优化。 让我们从map的内存分配开始。



Map初始化

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



• 用户明确定义长度：

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



• map更新时按需分配：

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



在第二个示例中，在创建map m时，由于尚未定义长度，因此不会创建桶，Go会一直等待直到第一次更新才初始化map。因此，第二行将运行桶创建。



在这两种情况下，map都可以根据我们的需要增长。如果我们需要10个以上的键，第一个例子中定义的长度不会阻止map的增长，它只是帮助我们优化map的使用，因为按需增长对我们的代码是有成本的。



按需增长的影响

Go足够聪明，可以根据需要扩展我们的map。然而，这种天生的行为是有代价的。让我们运行一些简单的基准测试，其中我们将初始化两个map并创建100/1000个键/值对。前两个基准测试将使用一个定义为100/1000的map来运行，而另一个将使用一个按需增长的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%



在这里，我们很清晰的看到扩容和迁移桶的代价，耗时增长了 80% 到 140% 。内存消耗也受到了相同比例的影响。关于内存，Go提供了一种智能的map设计来节省其消耗。

桶填充

正如之前所见，每个桶只存储8个键/值对。有趣的是Go先存储键，后存储值：





这避免了因为填充导致的内存浪费。事实上，由于键和值的长度可能不同，最终可能导致大量的内存填充。下面是两个string/bool 对的例子，展示了键和值混在一起的情况：





现在，如果键和值分开分组存放：





我们可以清楚的看到，填充被消除了。下面看一下如何访问这些值。



数据访问

Go提供了两种访问map数据的方式：

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



我们可以单独访问值，也可以携带一个布尔变量，用来表示是否在 map 中找到该值。我们可能会好奇，既然所有的返回值都应该明确的映射到一个变量，至少是 _，怎么会有两种访问方式。实际上，Go 生成的汇编代码 会给我们提示：

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



我们可以看到，根据你访问数据的方式，编译器将会使用具有正确签名的两个不同的内部方法：

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



编译器的这个小技巧非常有用，并为我们提供了数据访问的灵活性。其实编译器甚至做的比这更好，它可以根据 map 的数据类型来选择数据访问方法。在这个例子中，我们的 map 使用 字符串 作为 键，编译器会选择 mapaccess1_faststr 作为数据访问方法。后缀 str 表明了它对于 字符串 作为键 的 map 进行了优化。让我们尝试使用整数：

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（或64位系统上的int）作为键的专用方法。如果开发人员在map分配期间没有定义长度，那么每个方法都会针对其类型的哈希比较以及延迟初始化进行优化。



⏭ 本系列的下一篇也是最后一篇文章将解释map在并发上下文中的行为。



编译自https://medium.com/a-journey-with-go/go-map-design-by-code-part-ii-50d111557c08

博客地址

https://www.chenjie.info/2529

本文首发于我的公众号：