标签 Cpp 下的文章

11个现代Go特性:用gopls/modernize让你的代码焕然一新

本文永久链接 – https://tonybai.com/2025/04/15/embrace-modern-go-style-with-gopls-modernize

大家好,我是Tony Bai。

最近在思考Go语言的发展时,不禁让我想起了当年学习C++的经历。Bjarne Stroustrup在《C++程序设计语言(特别版)》中就专门强调了“现代 C++”(Modern C++)的编程风格,鼓励使用模板、STL等新特性来编写更优雅、更高效的C++代码。

那么,我们热爱的Go语言,随着版本的不断迭代,是否也逐渐形成了一种“现代Go”(Modern Go)的风格呢?答案是肯定的。Go团队不仅在语言层面引入新特性(如泛型range over int),也在标准库中添加了更强大、更便捷的包(如slices、maps)。

更棒的是,Go官方工具链gopls(Go Language Server Protocol的实现)中,就内置了一个名为modernize的分析器(Analyzer),专门用于帮助我们识别代码中可以用现代Go风格替代的“旧习”,并给出建议。

今天,我们就来深入了解一下gopls/modernize这个利器,看看它如何帮助我们的Go代码焕然一新,并学习一下它所倡导的11个“现代Go”风格语法要素具体包含哪些内容。

1. gopls/modernize分析器以及现代Go风格简介

gopls/modernize是golang.org/x/tools/gopls/internal/analysis/modernize 包提供的一个分析器。它的核心目标就是扫描你的Go代码,找出那些可以通过使用Go 1.18及之后版本引入的新特性或标准库函数来简化的代码片段。

modernize工具目前可以识别并建议修改多种“旧”代码模式。让我们逐一看看这些建议,并附上代码示例:

(注:以下示例中的版本号指明了该现代写法是何时被推荐或可用的)

1). 使用min/max内建函数 (Go 1.21+)

  • 旧风格: 使用 if/else 进行条件赋值来找最大/最小值。
func findMax(a, b int) int {
    var maxVal int
    if a > b {
        maxVal = a
    } else {
        maxVal = b
    }
    return maxVal
}
  • 现代风格: 直接调用 max 内建函数。
import "cmp" // Go 1.21 implicitly uses built-ins, Go 1.22+ might suggest cmp.Or for clarity if needed

func findMaxModern(a, b int) int {
    // Go 1.21 onwards have built-in min/max
    return max(a, b)
    // Note: for floats or custom types, use cmp.Compare from "cmp" package
}
  • 理由: 更简洁,意图更明确。

2). 使用slices.Sort (Go 1.21+)

  • 旧风格: 使用 sort.Slice 配合自定义比较函数对 slice 排序。
import "sort"

func sortInts(s []int) {
    sort.Slice(s, func(i, j int) bool {
        return s[i] < s[j] // Common case for ascending order
    })
}
  • 现代风格: 使用 slices.Sort 或 slices.SortFunc / slices.SortStableFunc。
import "slices"

func sortIntsModern(s []int) {
    slices.Sort(s) // For basic ordered types
}

// For custom comparison logic:
// func sortStructsModern(items []MyStruct) {
//     slices.SortFunc(items, func(a, b MyStruct) int {
//         return cmp.Compare(a.Field, b.Field) // Using cmp.Compare (Go 1.21+)
//     })
// }
  • 理由: slices包提供了更丰富、类型更安全的排序功能,且通常性能更好。

3). 使用 any 替代 interface{} (Go 1.18+)

  • 旧风格: 使用 interface{} 表示任意类型。
func processAnything(v interface{}) {
    // ... process v ...
}
  • 现代风格: 使用 any 类型别名。
func processAnythingModern(v any) {
    // ... process v ...
}
  • 理由: any 是 interface{} 的官方别名,更简洁,更能体现其“任意类型”的语义。

4). 使用 slices.Clone 或 slices.Concat (Go 1.21+)

  • 旧风格: 使用 append([]T(nil), s…) 来克隆 slice。
func cloneSlice(s []byte) []byte {
    return append([]byte(nil), s...)
}
  • 现代风格: 使用 slices.Clone。
import "slices"

func cloneSliceModern(s []byte) []byte {
    return slices.Clone(s)
}
  • 理由: slices.Clone 意图更明确,由标准库实现可能更优化。slices.Concat 则用于拼接多个 slice。

5). 使用 maps 包函数 (Go 1.21+)

  • 旧风格: 手动写循环来拷贝或操作 map。
func copyMap(src map[string]int) map[string]int {
    dst := make(map[string]int, len(src))
    for k, v := range src {
        dst[k] = v
    }
    return dst
}
  • 现代风格: 使用 maps.Clone 或 maps.Copy。
import "maps"

func copyMapModern(src map[string]int) map[string]int {
    return maps.Clone(src) // Clone creates a new map
}

func copyMapToExisting(dst, src map[string]int) {
     maps.Copy(dst, src) // Copy copies key-values, potentially overwriting
}
  • 理由: maps 包提供了标准化的 map 操作,代码更简洁,不易出错。还有 maps.DeleteFunc, maps.Equal 等实用函数。

6). 使用 fmt.Appendf (Go 1.19+)

  • 旧风格: 使用 []byte(fmt.Sprintf(…)) 来获取格式化后的字节 slice。
import "fmt"

func formatToBytes(id int, name string) []byte {
    s := fmt.Sprintf("ID=%d, Name=%s", id, name)
    return []byte(s)
}
  • 现代风格: 使用 fmt.Appendf,通常配合 nil 作为初始 slice。
import "fmt"

func formatToBytesModern(id int, name string) []byte {
    // Appends formatted string directly to a byte slice
    return fmt.Appendf(nil, "ID=%d, Name=%s", id, name)
}
  • 理由: fmt.Appendf 更高效,它避免了先生成 string 再转换成 []byte 的中间步骤和内存分配。

7). 在测试中使用 t.Context (Go 1.24+)

  • 旧风格: 在测试函数中需要 cancellable context 时,使用 context.WithCancel。
import (
    "context"
    "testing"
    "time"
)

func TestSomethingWithContext(t *testing.T) {
    ctx, cancel := context.WithCancel(context.Background())
    defer cancel()

    // Use ctx in goroutines or functions that need cancellation
    go func(ctx context.Context) {
        select {
        case <-time.After(1 * time.Second):
            t.Log("Worker finished")
        case <-ctx.Done():
            t.Log("Worker cancelled")
        }
    }(ctx)

    // Simulate test work
    time.Sleep(100 * time.Millisecond)
    // Maybe cancel based on some condition, or rely on defer cancel() at end
}
  • 现代风格: 直接使用 testing.T 提供的 Context() 方法。
import (
    "context"
    "testing"
    "time"
)

func TestSomethingWithContextModern(t *testing.T) {
    // t.Context() is automatically cancelled when the test (or subtest) finishes.
    // It may also be cancelled sooner if the test times out (e.g., using t.Deadline()).
    ctx := t.Context()

    go func(ctx context.Context) {
        select {
        case <-time.After(1 * time.Second):
            t.Log("Worker finished")
        case <-ctx.Done():
            t.Logf("Worker cancelled: %v", ctx.Err()) // Good practice to log the error
        }
    }(ctx)

    time.Sleep(100 * time.Millisecond)
}
  • 理由: t.Context() 更方便,自动管理 context 的生命周期与测试的生命周期绑定,减少了样板代码,并能正确处理测试超时。

8). 使用 omitzero 代替 omitempty (Go 1.24+)

  • 旧风格: 在 json 或类似 tag 中使用 omitempty,它会在字段值为其类型的零值(如 0, “”, nil, 空 slice/map)时省略该字段。但对于空结构体字段则表现不如预期:
type ConfigOld struct {
    EmptyStruct struct{} `json:",omitempty"`
}

// JSON 输出为 {"EmptyStruct":{}}
  • 现代风格: 如果意图是“当字段值为零值时省略”,则使用 omitzero。
type ConfigModern struct {
    EmptyStruct struct{} `json:",omitzero"`
}
// JSON 输出为 {}

9). 使用 slices.Delete (Go 1.21+)

  • 旧风格: 使用 append(s[:i], s[i+1]…) 来删除 slice 中的单个元素。
func deleteElement(s []int, i int) []int {
    if i < 0 || i >= len(s) {
        return s // Index out of bounds
    }
    return append(s[:i], s[i+1:]...)
}
  • 现代风格: 使用 slices.Delete 删除一个或一段元素。
import "slices"

func deleteElementModern(s []int, i int) []int {
    if i < 0 || i >= len(s) {
        return s
    }
    // Delete element at index i
    return slices.Delete(s, i, i+1)
}

func deleteElementsModern(s []int, start, end int) []int {
     // Delete elements from index start (inclusive) to end (exclusive)
     return slices.Delete(s, start, end)
}
  • 理由: slices.Delete 意图更明确,更通用(可以删除区间),由标准库实现可能更健壮(处理边界情况)。

10). 使用for range n (Go 1.22+)

  • 旧风格: 使用经典的三段式 for 循环遍历 0 到 n-1。
func iterateN(n int) {
    for i := 0; i < n; i++ {
        // Use i
        _ = i
    }
}
  • 现代风格: 使用 for range 遍历整数。
func iterateNModern(n int) {
    for i := range n { // Requires Go 1.22+
        // Use i
         _ = i
    }
}
  • 理由: 语法更简洁。在某些情况下(虽然不常见),如果循环体没有使用 i,for range n 可能比 for i:=0; i<n; i++ 有微弱的性能优势(避免迭代变量的开销)。

11). 使用 strings.SplitSeq (Go 1.24+)

  • 旧风格: 在循环中迭代 strings.Split 的结果。
import "strings"

func processSplits(s, sep string) {
    parts := strings.Split(s, sep)
    for _, part := range parts {
        // Process part
        _ = part
    }
}
  • 现代风格: 如果只是为了迭代,推荐使用 strings.SplitSeq(如果 Go 版本支持)。
import "strings"

func processSplitsModern(s, sep string) {
    // SplitSeq returns an iterator, potentially more efficient
    // as it doesn't necessarily allocate the slice for all parts at once.
    for part := range strings.SplitSeq(s, sep) { // Requires Go 1.24+
        // Process part
         _ = part
    }
}
  • 理由: strings.SplitSeq 返回一个迭代器 (iter.Seq[string]),它在迭代时才切分字符串,避免了一次性分配存储所有子串的 slice 的开销,对于大字符串和/或大量子串的情况,内存效率更高。

2. 为什么要拥抱“现代Go”风格?

通过前面modernize工具支持的现代风格的示例,我们大致可以得到三点采用现代Go风格的好处:

  • 代码更简洁、可读性更高: 新的语言特性或标准库函数往往能用更少的代码、更清晰地表达意图。
  • 利用标准库优化: slices、maps等新包通常经过精心设计和优化,性能和健壮性可能优于手写的等效逻辑。
  • 与时俱进,降低维护成本: 使用社区和官方推荐的新方式,有助于保持代码库的技术先进性,也便于团队成员(尤其是新人)理解和维护。

认识到拥抱“现代 Go”风格的诸多好处,自然会问:如何使用modern工具才能帮助我们识别并实践这些风格呢?接下来我们就来看看modernize工具的用法。

3. 如何在你的项目中使用 modernize

modernize工具本身是一个命令行程序。你可以通过以下方式在你的项目根目录下运行它:

$go run golang.org/x/tools/gopls/internal/analysis/modernize/cmd/modernize@latest [flags] [package pattern]
  • [package pattern]:指定要扫描的包,通常我们会使用 ./… 来扫描当前目录及其所有子目录下的包。
  • [flags]:一些常用的标志:
    • -test (boolean, default true):是否分析测试文件 (_test.go)。默认是分析的。
    • -fix (boolean, default false):自动应用所有建议的修复。请谨慎使用,建议先人工检查或在版本控制下使用。
    • -diff (boolean, default false):如果同时使用了 -fix,此标志会让工具不直接修改文件,而是打印出 unified diff 格式的变更内容,方便预览。

执行示例:

正如我在我的两个开源项目go-cache-proglocal-gitingest中尝试的那样:

➜  /Users/tonybai/go/src/github.com/bigwhite/go-cache-prog git:(main) $ go run golang.org/x/tools/gopls/internal/analysis/modernize/cmd/modernize@latest -test ./...
/Users/tonybai/go/src/github.com/bigwhite/go-cache-prog/cmd/go-cache-prog/main.go:19:2: Loop can be simplified using slices.Contains
exit status 3

➜  /Users/tonybai/go/src/github.com/bigwhite/local-gitingest git:(main) ✗ $ go run golang.org/x/tools/gopls/internal/analysis/modernize/cmd/modernize@latest -test ./...
/Users/tonybai/go/src/github.com/bigwhite/local-gitingest/main_test.go:191:5: Loop can be simplified using slices.Contains
exit status 3

我们看到modernize的输出格式为:

文件路径:行号:列号: 建议信息。

这里的 exit status 3 通常表示 Linter 发现了问题。它提示我在这两个项目的指定位置,存在一个循环可以用 slices.Contains 来简化(这也是 modernize 支持的一个检查,虽然未在上述重点说明的现代风格列表中,但也属于简化代码的范畴)。

注意: 工具的文档提到,如果修复之间存在冲突(比如一个修复改变了代码结构,使得另一个修复不再适用或需要调整),你可能需要运行 -fix 多次,直到没有新的修复被应用。

IDE 集成:

好消息是,如果你在使用 VS Code、GoLand 等配置了 gopls 的现代 Go IDE,很多 modernize 提出的建议通常会直接以代码高亮或建议(Quick Fix / Intention Action)的形式出现在你的编辑器中,让你可以在编码时就实时地进行现代化改造。

掌握了如何在项目中使用 modernize 工具后,让我们回到最初的话题,对这个工具及其倡导的“现代 Go”风格做一些思考和总结。

4. 小结

gopls/modernize不仅仅是一个代码检查工具,它更像是Go语言演进过程中的一个向导,温和地提醒我们:“嘿,这里有更现代、可能更好的写法了!”

拥抱“现代 Go”风格,利用好 modernize 这样的工具,不仅能让我们的代码库保持活力,也能促使我们不断学习和掌握 Go 的新知识。这与当年拥抱“现代 C++”的精神是一脉相承的。

建议大家不妨在自己的项目上运行一下 modernize 工具,看看它能给你带来哪些惊喜和改进建议。也欢迎在评论区分享你使用 modernize 的经验或对“现代 Go”风格的看法!觉得这篇文章有用?点个‘在看’,分享给更多Gopher吧!

免责声明: modernize 工具及其命令行接口 golang.org/x/tools/gopls/internal/analysis/modernize/cmd/modernize 目前并非官方稳定支持的接口,未来可能会有变动。使用 -fix 功能前请务必备份或确保代码已提交到版本控制系统。


原「Gopher部落」已重装升级为「Go & AI 精进营」知识星球,快来加入星球,开启你的技术跃迁之旅吧!

我们致力于打造一个高品质的 Go 语言深度学习AI 应用探索 平台。在这里,你将获得:

  • 体系化 Go 核心进阶内容: 深入「Go原理课」、「Go进阶课」、「Go避坑课」等独家深度专栏,夯实你的 Go 内功。
  • 前沿 Go+AI 实战赋能: 紧跟时代步伐,学习「Go+AI应用实战」、「Agent开发实战课」,掌握 AI 时代新技能。
  • 星主 Tony Bai 亲自答疑: 遇到难题?星主第一时间为你深度解析,扫清学习障碍。
  • 高活跃 Gopher 交流圈: 与众多优秀 Gopher 分享心得、讨论技术,碰撞思想火花。
  • 独家资源与内容首发: 技术文章、课程更新、精选资源,第一时间触达。

衷心希望「Go & AI 精进营」能成为你学习、进步、交流的港湾。让我们在此相聚,享受技术精进的快乐!欢迎你的加入!

img{512x368}
img{512x368}
img{512x368}

著名云主机服务厂商DigitalOcean发布最新的主机计划,入门级Droplet配置升级为:1 core CPU、1G内存、25G高速SSD,价格6$/月。有使用DigitalOcean需求的朋友,可以打开这个链接地址:https://m.do.co/c/bff6eed92687 开启你的DO主机之路。

Gopher Daily(Gopher每日新闻) – https://gopherdaily.tonybai.com

我的联系方式:

  • 微博(暂不可用):https://weibo.com/bigwhite20xx
  • 微博2:https://weibo.com/u/6484441286
  • 博客:tonybai.com
  • github: https://github.com/bigwhite
  • Gopher Daily归档 – https://github.com/bigwhite/gopherdaily
  • Gopher Daily Feed订阅 – https://gopherdaily.tonybai.com/feed

商务合作方式:撰稿、出书、培训、在线课程、合伙创业、咨询、广告合作。

Go map使用Swiss Table重新实现,性能最高提升近50%

本文永久链接 – https://tonybai.com/2024/11/14/go-map-use-swiss-table

2024月11月5日的Go compiler and runtime meeting notes中,我们注意到了一段重要内容,如下图红框所示:

这表明,来自字节的一位工程师在两年多前提出的“使用Swiss table重新实现Go map”的建议即将落地,目前该issue已经被纳入Go 1.24里程碑

Swiss Table是由Google工程师于2017年开发的一种高效哈希表实现,旨在优化内存使用和提升性能,解决Google内部代码库中广泛使用的std::unordered_map所面临的性能问题。Google工程师Matt Kulukundis在2017年CppCon大会上详细介绍了他们在Swiss Table上的工作

目前,Swiss Table已被应用于多种编程语言,包括C++ Abseil库的flat_hash_map(可替换std::unordered_map)Rust标准库Hashmap的默认实现等。

Swiss Table的出色表现是字节工程师提出这一问题的直接原因。字节跳动作为国内使用Go语言较为广泛的大厂。据issue描述,Go map的CPU消耗约占服务总体开销的4%。其中,map的插入(mapassign)和访问(mapaccess)操作的CPU消耗几乎是1:1。大家可千万不能小看4%这个数字,以字节、Google这样大厂的体量,减少1%也意味着真金白银的大幅节省。

Swiss Table被视为解决这一问题的潜在方案。字节工程师初版实现的基准测试结果显示,与原实现相比,Swiss Table在查询、插入和删除操作上均提升了20%至50%的性能,尤其是在处理大hashmap时表现尤为突出;迭代性能提升了10%;内存使用减少了0%至25%,并且不再消耗额外内存。

这些显著的性能提升引起了Go编译器和运行时团队的关注,特别是当时负责该子团队的Austin Clements。在经过两年多的实验和评估后,Go团队成员Michael Pratt基于Swiss Table实现的internal/runtime/maps最终成为Go map的底层默认实现。

在本文中,我们将简单介绍Swiss Table这一高效的哈希表实现算法,并提前看一下Go map的Swiss Table实现。

在进入swiss table工作原理介绍之前,我们先来回顾一下当前Go map的实现(Go 1.23.x)。

1. Go map的当前实现

map,也称为映射,或字典,或哈希表,是和数组等一样的最常见的数据结构。实现map有两个关键的考量,一个是哈希函数(hash function),另一个就是碰撞处理(collision handling)。hash函数是数学家的事情,这里不表。对于碰撞处理,在大学数据结构课程中,老师通常会介绍两种常见的处理方案:

  • 开放寻址法(Open Addressing)

在发生哈希碰撞时,尝试在哈希表中寻找下一个可用的位置,如下图所示k3与k1的哈希值发生碰撞后,算法会尝试从k1的位置开始向后找到一个空闲的位置:

  • 链式哈希法(拉链法, Chaining)

每个哈希桶(bucket)存储一个链表(或其他数据结构),所有哈希值相同的元素(比如k1和k3)都被存储在该链表中。

Go当前的map实现采用的就是链式哈希,当然是经过优化过的了。要了解Go map的实现,关键把握住下面几点:

  • 编译器重写

我们在用户层代码中使用的map操作都会被Go编译器重写为对应的runtime的map操作,就如下面Go团队成员Keith Randall在GopherCon大会上讲解map实现原理的一个截图所示:

  • 链式哈希

前面提过,Go map当前采用的是链式哈希的实现,一个map在内存中的结构大致如下:


来自Keith Randall的ppt截图

我们看到,一个map Header代表了一个map类型的实例,map header中存储了有关map的元数据(图中字段与当前实现可能有少许差异,毕竟那是几年前的一个片子了),如:

- len: 当前map中键值对的数量。
- bucket array: 存储数据的bucket数组,可以对比前面的链式哈希的原理图进行理解,不过不同的是,Go map中每个bucket本身就可以存储多个键值对,而不是指向一个键值对的链表。
- hash seed: 用于哈希计算的种子,用于分散数据并提高安全性。

通常一个bucket可以存储8个键值对,这些键值对是根据键的哈希值分配到对应的bucket中。

注:在《Go语言第一课》专栏中,有关于Go map工作原理的系统说明,感兴趣的童鞋可以看看。

  • 溢出桶(overflow bucket)

每个bucket后面还会有Overflow Bucket。当一个bucket中的数据超出容量时,会创建overflow bucket来存储多余的数据。这样可以避免直接扩展bucket数组,节省内存空间。但如果出现过多的overflow bucket,性能就会下降。

  • “蚂蚁搬家”式的扩容

当map中出现过多overflow bucket而导致性能下降时,我们就要考虑map bucket扩容的事儿了,以始终保证map的操作性能在一个合理的范围。是否扩容由一个名为load factor的参数所控制。load factor是元素数量与bucket数量的比值,比值越高,map的读写性能越差。目前Go map采用了一个经验值来确定是否要扩容,即load factor = 6.5。当load factor超过这个值时,就会触发扩容。所谓扩容就是增大bucket数量(当前实现为增大一倍数量),减少碰撞,让每个bucket中存放的element数量降下来。

扩容需要对存量element做rehash,在元素数量较多的情况下,“一次性”的完成桶的扩容会造成map操作延迟“突增”,无法满足一些业务场景的要求,因此Go map采用“增量”扩容的方式,即在访问和插入数据时,“蚂蚁搬家”式的做点搬移元素的操作,直到所有元素完成搬移。

Go map的当前实现应该可以适合大多数的场合,但依然有一些性能和延迟敏感的业务场景觉得Go map不够快,另外一个常被诟病的就是当前实现的桶扩容后就不再缩容(shrink)了,这会给内存带来压力。


来自issue 20135的截图

下面我们再来看看swiss table的结构和工作原理。

2. Swiss table的工作原理

就像前面提到的,Swiss table并非来自某个大学或研究机构的论文,而是来自Google工程师在工程领域的”最佳实践”,因此关于Swiss table的主要资料都来自Google的开源C++ library Abseil以及开发者的演讲视频。在Abseil库中,它是flat_hash_map、flat_hash_set、node_hash_map以及node_hash_set等数据结构的底层实现,并且Swiss table的实现在2018年9月正式开源

和Go map当前实现不同,Swiss table使用的不是拉链法,而是开放寻址,但并非传统的方案。下面是根据公开资源画出的一个Swiss table的逻辑结构图(注意:并非真实内存布局):

如果用一个式子来表示Swiss table,我们可以用:

A swiss table = N * (metdata array + slots array)

我们看到:swiss table将所谓的桶(这里叫slot)分为多个group,每个group中有16个slot,这也是swiss table的创新,即将开放寻址方法中的probing(探测key碰撞后下一个可用的位置(slot))放到一个16个slot的group中进行,这样的好处是可以通过一个SIMD指令并行探测16个slot,这种方法也被称为Group Probing

在上图中,我们看到一个Group由metadata和16个slot组成。metadata中存储的是元数据,而slot中存储的是元素(key和value)。Group probling主要是基于metadata实现的,Google工程师的演讲有对group probing实现的细节描述。

当我们向swiss table插入一个元素或是查找一个元素时,swiss table会通过hash函数对key进行求值,结果是一个8字节(64bit)的数。和Go map的当前实现一样,这个哈希值的不同bit功用不同,下图是一个来自abseil官网的示例:

哈希值的高57bit被称为H1,低7bit被称为H2。前者用于标识该元素在Group内的索引,查找和插入时都需要它。后者将被用于该元素的元数据,放在metadata中存储,用于快速的group probing之用,也被称为哈希指纹

每个Group的metadata也是一个16字节数组,每个字节对应一个slot,是该slot的控制字节。这个字节的8个bit位的组成如下:


图来自abseil库官网

metadata中的控制字节有三个状态:

  • 最高位为1,其余全零为空闲状态(Empty),即对应的slot尚未曾被任何element占据过;
  • 最高位为0,后7位为哈希指纹(H2),为对应的slot当前已经有element占据的已使用状态
  • 最高位为1,其他位为1111110的,为对应的slot为已删除状态,后续可以被继续使用。

下面是Abseil开发者演进slide中的一个针对swiss table的迭代逻辑:

通过这幅图可以看出H1的作用。不过这里通过pos = pos + 1进行probing(探测)显然是不高效的!metadata之所以设计为如此,并保存了插入元素的哈希指纹就是为了实现高效的probing,下图演示了基于key的hash值的H2指纹通过SIMD指令从16个位置中快速得到匹配的pos的过程:

虽然有两个匹配项,但这个过程就像“布隆过滤器”一样,快速排除了不可能的匹配项,减少了不必要的内存访问。

由此也可以看到:swiss table的16个条目的分组大小不是随意选择的,而是基于SSE2寄存器长度(128bit, 16bytes)和现代CPU的缓存行大小(64字节)优化的,保证了一个Group的控制字节能被单次SIMD指令处理。

此外swiss table也是通过load factor来判定是否需要对哈希表进行扩容,一旦扩容,swiss table通常是会将group数量增加一倍,然后重新计算当前所有元素在新groups中的新位置(rehash),这个过程是有一定开销的。如果不做优化,当表中元素数量较多时,这个过程会导致操作延迟增加。

最后,虽然多数情况是在group内做probing,但当元素插入时,如果当前Group已满,就必须探测到下一个Group,并将元素插入到下一个Group。这样,在该元素的查找操作中,probing也会跨group进行。

到这里,我们已经粗略了解了swiss table的工作原理,那么Go tip对swiss table当前的实现又是怎样的呢?我们下面就来看看。

3. Go tip版本当前的实现

Go tip版本基于swiss table的实现在https://github.com/golang/go/blob/master/src/internal/runtime/maps下。

由于Go map是原生类型,且有了第一版实现,考虑到Go1兼容性,新版基于swiss table的实现也要继承已有的语义约束。同时,也要尽量避免swiss table自身的短板,Go团队在swiss table之上做了局部改进。比如为了将扩容带来的开销降到最低,Go引入了多table的设计,以支持渐进式扩容。也就是说一个map实际上是多个swiss table,而不是像上面说的一个map就是一个swiss table。每个table拥有自己的load factor,可以独立扩容(table的扩容是一次性扩容),这样就可以将扩容的开销从全部数据变为局部少量数据,减少扩容带来的影响

Go swiss-table based map的逻辑结构大致如下:

我们可以看出与C++ swisstable的最直观不同之处除了有多个table外,每个group包含8个slot和一个control word,而不是16个slot。此外,Go使用了二次探测(quadratic probing), 探测序列必须以空slot结束。

为了实现渐进式扩容,数据分散在多个table中;单个table容量有上限(maxTableCapacity),超过上限时分裂成两个table;使用可扩展哈希(extendible hashing)根据hash高位选择table,且每个table可以独立增长。

Go使用Directory管理多个table,Directory是Table的数组,大小为2^globalDepth。如果globalDepth=2,那Directory最多有4个表,分为0×00、0×01、0×10、0×11。Go通过key的hash值的前globalDepth个bit来选择table。这是一种“extendible hashing”,这是一种动态哈希技术,其核心特点是通过动态调整使用的哈希位数(比如上面提到的globalDepth)来实现渐进式扩容。比如:初始可能只用1位哈希值来区分,需要时可以扩展到用2位,再需要时可以扩展到用3位,以此类推。

举个例子,假设我们用二进制表示哈希值的高位,来看一个渐进式扩容的过程:

  • 初始状态 (Global Depth = 1):
directory
hash前缀  指向的table
0*** --> table1 (Local Depth = 1)
1*** --> table2 (Local Depth = 1)
  • 当table1满了需要分裂时,增加一位哈希值 (Global Depth = 2):
directory
hash前缀  指向的table
00** --> table3 (Local Depth = 2)  // 由table1扩容而成
01** --> table4 (Local Depth = 2)  // 由table1扩容而成
10** --> table2 (Local Depth = 1)
11** --> table2 (Local Depth = 1)  // 复用table2因为它的Local Depth还是1
  • 如果table2也满了,需要分裂:
directory
hash前缀  指向的table
00** --> table3 (Local Depth = 2)
01** --> table4 (Local Depth = 2)
10** --> table5 (Local Depth = 2) // 由table2扩容而成
11** --> table6 (Local Depth = 2) // 由table2扩容而成

通过extendible hashing实现的渐进式扩容,每次只处理一部分数据,扩容过程对其他操作影响小,空间利用更灵活。

对于新版go map实现而言,单个Table达到负载因子阈值时触发Table扩容。当需要分裂的Table的localDepth等于map的globalDepth时触发Directory扩容,这就好理解了。

除此之外,Go版本对small map也有特定优化,比如少量元素(<=8)时直接使用单个group,避免或尽量降低swiss table天生在少量元素情况下的性能回退问题。

更多实现细节,大家可以自行阅读https://github.com/golang/go/blob/master/src/internal/runtime/maps/下的Go源码进行理解。

注:目前swiss table版的go map依然还未最终定型,并且后续还会有各种优化加入,这里只是对当前的实现(2024.11.10)做概略介绍,不代表以后的map实现与上述思路完全一致。

4. Benchmark

目前gotip版本中GOEXPERIMENT=swissmap默认已经打开,我们直接用gotip版本即可体验基于swiss table实现的map。

字节工程师zhangyunhao的gomapbench repo提供了对map的性能基准测试代码,不过这个基准测试太多,我大幅简化了一下,只使用Int64,并只测试了元素个数分别为12、256和8192时的情况。

注:我基于Centos 7.9,使用Go 1.23.0和gotip(devel go1.24-84e58c8 linux/amd64)跑的benchmark。

// 在experiments/swiss-table-map/mapbenchmark目录下
$go test -run='^$' -timeout=10h -bench=. -count=10 > origin-map.txt
$GOEXPERIMENT=swissmap gotip test -run='^$' -timeout=10h -bench=. -count=10 > swiss-table-map.txt
$benchstat origin-map.txt swiss-table-map.txt > result.txt

注:gotip版本的安装请参考《Go语言第一课》专栏的第3讲。benchstat安装命令为go install golang.org/x/perf/cmd/benchstat@latest

下面是result.txt中的结果:

goos: linux
goarch: amd64
pkg: demo
cpu: Intel(R) Xeon(R) Platinum
                                  │ origin-map.txt │         swiss-table-map.txt          │
                                  │     sec/op     │    sec/op     vs base                │
MapIter/Int/12-8                      179.7n ± 10%   190.6n ±  4%        ~ (p=0.436 n=10)
MapIter/Int/256-8                     4.328µ ±  5%   3.748µ ±  1%  -13.40% (p=0.000 n=10)
MapIter/Int/8192-8                    137.3µ ±  1%   123.6µ ±  1%   -9.95% (p=0.000 n=10)
MapAccessHit/Int64/12-8               10.12n ±  2%   10.68n ± 14%   +5.64% (p=0.000 n=10)
MapAccessHit/Int64/256-8              10.29n ±  3%   11.29n ±  1%   +9.77% (p=0.000 n=10)
MapAccessHit/Int64/8192-8             25.99n ±  1%   14.93n ±  1%  -42.57% (p=0.000 n=10)
MapAccessMiss/Int64/12-8              12.39n ± 88%   20.99n ± 50%        ~ (p=0.669 n=10)
MapAccessMiss/Int64/256-8             13.12n ±  6%   11.34n ±  7%  -13.56% (p=0.000 n=10)
MapAccessMiss/Int64/8192-8            15.71n ±  1%   14.03n ±  1%  -10.66% (p=0.000 n=10)
MapAssignGrow/Int64/12-8              607.1n ±  2%   622.6n ±  2%   +2.54% (p=0.000 n=10)
MapAssignGrow/Int64/256-8             25.98µ ±  3%   23.22µ ±  1%  -10.64% (p=0.000 n=10)
MapAssignGrow/Int64/8192-8            792.3µ ±  1%   844.1µ ±  1%   +6.54% (p=0.000 n=10)
MapAssignPreAllocate/Int64/12-8       450.2n ±  2%   409.2n ±  1%   -9.11% (p=0.000 n=10)
MapAssignPreAllocate/Int64/256-8     10.412µ ±  1%   6.055µ ±  2%  -41.84% (p=0.000 n=10)
MapAssignPreAllocate/Int64/8192-8     342.4µ ±  1%   232.6µ ±  2%  -32.05% (p=0.000 n=10)
MapAssignReuse/Int64/12-8             374.2n ±  1%   235.4n ±  2%  -37.07% (p=0.000 n=10)
MapAssignReuse/Int64/256-8            8.737µ ±  1%   4.716µ ±  4%  -46.03% (p=0.000 n=10)
MapAssignReuse/Int64/8192-8           296.4µ ±  1%   181.0µ ±  1%  -38.93% (p=0.000 n=10)
geomean                               1.159µ         984.2n        -15.11%

我们看到了除了少数测试项有不足外(比如MapAssignGrow以及一些元素数量少的情况下),大多数测试项中,新版基于swiss table的map的性能都有大幅提升,有些甚至接近50%!

5. 小结

本文探讨了Go语言中的map实现的重塑,即引入Swiss Table这一高效哈希表结构的背景与优势。Swiss Table由Google工程师开发,旨在优化内存使用和提升性能,解决了传统哈希表在高负载情况下的性能瓶颈。通过对比现有的链式哈希实现,Swiss Table展示了在查询、插入和删除操作上显著提高的性能,尤其是在处理大规模数据时。

经过两年多的实验与评估,Go团队决定将Swiss Table作为Go map的底层实现,预计将在Go 1.24中正式落地。新的实现不仅承继了原有的语义约束,还通过引入多表和渐进式扩容的设计,进一步优化了扩容过程的性能。尽管当前实现仍在完善中,但Swiss Table的引入无疑为Go语言的性能提升提供了新的可能性,并为未来进一步优化奠定了基础。

对于那些因Go引入自定义iterator而批评Go团队的Gopher来说,这个Go map的重塑无疑会很对他们的胃口。

本文涉及的源码可以在这里下载。

6. 参考资料


Gopher部落知识星球在2024年将继续致力于打造一个高品质的Go语言学习和交流平台。我们将继续提供优质的Go技术文章首发和阅读体验。同时,我们也会加强代码质量和最佳实践的分享,包括如何编写简洁、可读、可测试的Go代码。此外,我们还会加强星友之间的交流和互动。欢迎大家踊跃提问,分享心得,讨论技术。我会在第一时间进行解答和交流。我衷心希望Gopher部落可以成为大家学习、进步、交流的港湾。让我相聚在Gopher部落,享受coding的快乐! 欢迎大家踊跃加入!

img{512x368}
img{512x368}

img{512x368}
img{512x368}

著名云主机服务厂商DigitalOcean发布最新的主机计划,入门级Droplet配置升级为:1 core CPU、1G内存、25G高速SSD,价格5$/月。有使用DigitalOcean需求的朋友,可以打开这个链接地址:https://m.do.co/c/bff6eed92687 开启你的DO主机之路。

Gopher Daily(Gopher每日新闻) – https://gopherdaily.tonybai.com

我的联系方式:

  • 微博(暂不可用):https://weibo.com/bigwhite20xx
  • 微博2:https://weibo.com/u/6484441286
  • 博客:tonybai.com
  • github: https://github.com/bigwhite
  • Gopher Daily归档 – https://github.com/bigwhite/gopherdaily
  • Gopher Daily Feed订阅 – https://gopherdaily.tonybai.com/feed

商务合作方式:撰稿、出书、培训、在线课程、合伙创业、咨询、广告合作。

如发现本站页面被黑,比如:挂载广告、挖矿等恶意代码,请朋友们及时联系我。十分感谢! Go语言第一课 Go语言精进之路1 Go语言精进之路2 Go语言编程指南
商务合作请联系bigwhite.cn AT aliyun.com

欢迎使用邮件订阅我的博客

输入邮箱订阅本站,只要有新文章发布,就会第一时间发送邮件通知你哦!

这里是 Tony Bai的个人Blog,欢迎访问、订阅和留言! 订阅Feed请点击上面图片

如果您觉得这里的文章对您有帮助,请扫描上方二维码进行捐赠 ,加油后的Tony Bai将会为您呈现更多精彩的文章,谢谢!

如果您希望通过微信捐赠,请用微信客户端扫描下方赞赏码:

如果您希望通过比特币或以太币捐赠,可以扫描下方二维码:

比特币:

以太币:

如果您喜欢通过微信浏览本站内容,可以扫描下方二维码,订阅本站官方微信订阅号“iamtonybai”;点击二维码,可直达本人官方微博主页^_^:
本站Powered by Digital Ocean VPS。
选择Digital Ocean VPS主机,即可获得10美元现金充值,可 免费使用两个月哟! 著名主机提供商Linode 10$优惠码:linode10,在 这里注册即可免费获 得。阿里云推荐码: 1WFZ0V立享9折!


View Tony Bai's profile on LinkedIn
DigitalOcean Referral Badge

文章

评论

  • 正在加载...

分类

标签

归档



Statcounter View My Stats