Golang中map的桶为何将8个键值对存储在同一个字节数组？

Golang中map的桶为何将8个键值对存储在同一个字节数组？ 我在代码中看到，桶（bucket）将键和值存储在同一个字节数组中。它采用了类似这样的方式，例如，如果只存在两个键值对：键1、键2、空、…… 空、值1、值2、空、…… 空。

之所以采用这种存储在同一个字节数组的方式，是由于地址对齐保证。我理解，如果采用存储键1、值1、键2、值2…… 的方式，那么由于地址对齐保证，每个键和值之间可能会存在一些填充（padding）。

然而，为什么不直接使用一个字节数组来存储8个键，再用另一个字节数组来存储8个值呢？这样在键区域和值区域之间就不会再有潜在的填充了。

为什么选择了这种单一数组的版本？有谁知道原因吗？


更多关于Golang中map的桶为何将8个键值对存储在同一个字节数组？的实战教程也可以访问 https://www.itying.com/category-94-b0.html

4 回复

如果你想从作者那里获得反馈，你应该在 go-nuts 谷歌群组中提问。

更多关于Golang中map的桶为何将8个键值对存储在同一个字节数组？的实战系列教程也可以访问 https://www.itying.com/category-94-b0.html


你好 @Christophe_Meessen，

不过，我们真的确定吗？有没有什么方法可以让我询问或再次确认他们为何选择这个解决方案？

我读过代码，它有不错的文档，但几乎没有解释原因或架构决策。

这可能是出于性能考虑。通过将键和值在内存中保持连续，它们可能适合单个缓存条目。在一次加载中，您将同时获取键和值。如果将它们分开存储，就无法从中受益。

我猜这个决定是基于基准测试做出的。

在Go语言的map实现中，桶（bucket）采用单一字节数组存储8个键值对的设计，主要基于以下技术考量：

  1. 内存局部性优化：将键和值存储在连续内存中，能显著提升CPU缓存命中率。当通过键查找值时，键和值在内存中位置相邻，减少了缓存行（cache line）的加载次数。

  2. 内存分配效率：单一数组只需一次内存分配操作，而分开存储需要两次独立分配。这不仅减少了分配开销，还避免了内存碎片化问题。

  3. 对齐处理的一致性：Go运行时在创建数组时会统一处理对齐问题。虽然键值区域之间可能存在填充，但这是在单一连续内存块内进行的，比多个独立数组更容易管理。

以下是简化示例，展示这种布局的内存结构：

// 桶的典型内存布局示意（以两个键值对为例）
type bucket struct {
    // 顶部8个哈希值（tophash）
    tophash [bucketCnt]uint8
    
    // 键值存储区：键区域 + 值区域
    // 实际实现中是连续字节数组
    data []byte
    // 布局：[key1][key2][padding...][value1][value2][padding...]
}

// 实际访问时的指针计算
func (b *bucket) keyAt(i int) unsafe.Pointer {
    // 计算键的偏移量
    keysOffset := unsafe.Sizeof(b.tophash)
    keySize := // 键类型大小
    return unsafe.Pointer(uintptr(unsafe.Pointer(&b.data)) + uintptr(keysOffset) + uintptr(i*keySize))
}

func (b *bucket) valueAt(i int) unsafe.Pointer {
    // 计算值的偏移量（跳过所有键区域）
    keysOffset := unsafe.Sizeof(b.tophash)
    keySize := // 键类型大小
    valuesOffset := keysOffset + bucketCnt*uintptr(keySize)
    valueSize := // 值类型大小
    return unsafe.Pointer(uintptr(unsafe.Pointer(&b.data)) + uintptr(valuesOffset) + uintptr(i*valueSize))
}

  1. GC扫描优化：垃圾回收器扫描时，单一连续内存块比多个分散块更容易处理。GC只需识别整个桶对象的起始和结束地址，而不需要追踪多个独立数组的引用。

  2. 内存紧凑性：对于小尺寸的键值类型，单一数组的填充开销通常小于独立数组的元数据开销。每个独立数组都有长度、容量等元数据，而单一数组只需一份元数据。

这种设计在Go 1.0的map实现中就已采用，经过多年实践验证，在性能和内存效率之间取得了良好平衡。虽然理论上键值区域间可能存在填充，但实际测试表明，这种布局的综合性能优于分离数组的方案。

回到顶部