Press "Enter" to skip to content

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

发表回复

您的电子邮箱地址不会被公开。 必填项已用 * 标注

此站点使用Akismet来减少垃圾评论。了解我们如何处理您的评论数据