map 的扩容:Swiss Table 里的翻倍与分裂,以及插入耗时的分布

源码里的设计

  internal/runtime/maps/table.go:20:const maxTableCapacity = 1024
  internal/runtime/maps/group.go:20:	maxAvgGroupLoad = 7
  internal/abi/map.go:18:	MapGroupSlots = 1 << MapGroupSlotsBits // 8
  internal/goexperiment 里是否还有 noswissmap 开关:没有(只剩 Swiss Table 实现,旧的 hmap 增量搬迁实现已经移除)

internal/runtime/maps/map.go 开头的注释把设计讲得很清楚(以下是我读到的):键值放在“组”里,每组 8 个槽外加一个 8 字节的控制字,每个字节记录一个槽是空、已删除还是在用,在用时还带着哈希的低 7 位,所以一次位运算就能并行比较 8 个槽;一张表由若干组构成,探测用二次探测;删除时若整组已满就放“墓碑”,墓碑只在扩容时清理。增长是整张表一次完成的(探测序列依赖组数,必须重排),为了让一次增长不至于太大,map 把内容分到多张表里,每张表最大 maxTableCapacity = 1024 个槽:不到上限时增长就是换成两倍容量的新表,到上限后把表拆分成两张,由一个“目录”按哈希高位选表。注释里写的目的是 “to support incremental growth”,所以“渐进”这个词现在指的是“每次增长只涉及一张最多 1024 个槽的表”,而不是旧实现里“分摊到后续读写里逐步搬迁”。

扩容发生的时刻

  逐个插入 map[int]int 的前 3000 个键(不给容量提示),Mallocs 增加的时刻(len(+新增分配次数)),共 10 次:
    [9(+3) 15(+2) 29(+2) 57(+2) 113(+2) 225(+2) 449(+2) 897(+5) 1793(+5) 1794(+4)]

从 Mallocs 的变化能看出每次扩容:第 9 个元素时从小 map(一个组)变成真正的表,之后每次容量翻倍(15、29、57……449 对应容量 16 到 512 个槽的 7/8 再加一),到容量 1024 的表满了以后(897)就不再翻倍,而是拆分。这些“+2 次、+5 次”的分配数是 Mallocs 计数的直接结果,每个分配分别是什么(组数组、表结构、目录)我没有逐个确认。

单次插入的耗时

  不给容量提示:p50 42 ns,p99 208 ns,p99.9 16125 ns,最大 80042 ns;最慢的 8 次插入发生在 len = 935678(80 µs) 965281(50 µs) 57351(48 µs) 114729(46 µs) 864034(44 µs) 912718(44 µs) 901480(43 µs) 909898(41 µs)
  make(map[int]int, 1000000):p50 42 ns,p99 167 ns,p99.9 1500 ns,最大 26542 ns;最慢的 8 次插入发生在 len = 12925(26 µs) 65269(23 µs) 245121(16 µs) 1922(15 µs) 940403(14 µs) 220465(14 µs) 575625(14 µs) 68176(13 µs)

绝大多数插入只要几十纳秒(含计时开销),但每次扩容或拆分都会让当次插入变慢。关掉 GC 以后(排除 GC 干扰),不给容量提示的 p99.9 是 16125 ns、最大 80 µs;给容量提示后 p99.9 只有 1500 ns,最大 26.5 µs。注意:最慢的几次发生在哪个 len,每次运行都不完全相同,我没有把它们逐一对应到具体的表拆分或目录扩容上,所以只能说“与扩容有关,不能保证每一次都是”。

map 不缩小

  基线 0.20 MiB;插入 100 万个键后 36.27 MiB;delete 掉全部键后(len = 0)36.27 MiB
  clear(m) 之后 0.20 MiB
  m = nil 之后 0.20 MiB(整个 map 才被回收)

delete 只是把槽标成空,不释放表。插入 100 万个键后堆是 36.27 MiB,删光之后还是 36.27 MiB;clear(m) 之后堆回到基线,说明 Go 1.27.1 的 clear 会放弃大的表(这一点是实测结果,我没有读 clear 的实现)。需要真正释放内存时,把 map 置为 nil 或重建一个新 map 同样有效。

分步演示