Go: 通过代码学习 Map 的设计 — Part II

用户头像
陈思敏捷
关注
发布于: 2020 年 07 月 24 日
Go: 通过代码学习 Map 的设计 — Part II

ℹ️ 这篇文章是 “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

本文首发于我的公众号:



发布于: 2020 年 07 月 24 日 阅读数: 50
用户头像

陈思敏捷

关注

多动脑不痴呆 2017.12.21 加入

gopher

评论

发布
暂无评论
Go: 通过代码学习 Map 的设计 — Part II