Go
by smallnest

替换标准库的map实现，SwissTable更快？

在最新的一期Go开发团队的每周会议中，他们讨论了Google3再评估SwissTable的性能，或许值得跟进，替换标准库的map。

  • SwissTable
    • [MichaelP]: Google3 may want to do some benchmarking on this. Maps are used heavily in google3. This may be of value to us.
    • So this may be worth investing in.

可能有的同学不了解SwissTable (或者叫Swiss Tables)是啥?Google3又是啥？

Google3或许谷歌内部的同学比较熟悉，但是外部很少介绍这个概念的。Google3指的就是谷歌的那个大单体代码仓库(monorepo),谷歌95%的代码都在这个大仓库下，除了Chrome 和 Android等特殊的一些项目。

SwissTable是谷歌开源的一个哈希表(hash table、map)的实现，在cppcon 2017大会上公布出来，Google内部大量采用它替换std:unordered_map,精巧的设计使的它非常的高效，它也被port到其他语言，比如Rust语言中有一个库hashbrown就是根据SwissTable实现的，并且在Rust 1.36中开始替换标准库的HashMap。

官方文档和一些开发者的介绍SwissTable的优点，比如

所以Go开发团队也开始关注SwissTable,或许在将来的某个版本实现它并替换标准库的map,毕竟这些基础的数据类型和算法的提升会帮助千千万万使用Go做开发的项目，比如排序算法吧，去年字节的同学提交了一个pdqsort算法，替换了标准库中的排序算法，现在又有人提出了dual-pivot quicksort,据测试性能更好更简洁，大家对几十年来一直使用的这些人基础算法和数据结构还是孜孜不倦的进行优化。

虽然Go开发团队目前也只是关注和讨论SwissTable,将来也未必实现，但是社区最近也有人自己实现了SwissTable: swiss。

我在去年的一篇文章中机智！生抠 map的哈希函数,就介绍这位作者的maphash,看样子作者一直在为他的SwissTable做准备，今年他就提交了SwissTable的Go语言实现，其中计算哈希的方法就是使用他的maphash。

作者专门写了一篇文章介绍他的swiss设计，我们至少可以从这个库中了解Go语言如何设计SwissTable,也有在一些优化场景下你可以私用这个库替换内建的map,正如作者那样。

内建的map采用开放寻址法(open-hashing，也叫拉链法),哈希值冲突(哈希值一样)的键值对会被放在一个桶中，查找的时候，先根据哈希值找到对应的桶，然后再遍历桶中的元素，找到对应的值，当然这里面还是有一些优化的，通过额外的bit做更快的检查，内建的map细节可以参看2016 GopherCon大会的分享：Inside the Map Implementation。

SwissTable 使用一种称为“封闭哈希”（Closed Hashing,也叫开地址法）的不同哈希方案。每一个哈希值都会有一个自己的槽(slot),槽的选择是由哈希值决定，最简单的方式就是从hash(key) mod size的槽开始查找，一直往后查找，直到直到对应的键或者空的槽(不存在的 key),这也是开地址法常见的套路。SwissTable也是和内建的map一样采用短哈希(short hash),以便支持快速检查，但是它的元数据却是独立存储的，和哈希值存储分开。

使用这种方式，对CPU的cache更友好，更重要的是，可以通过SSE 指令并行比较 16 个短哈希。

因为find方法是其他方法Get()、 Has()、 Put()、Delete()的基础，它要查找对应的槽位，所以我们看看swiss这个库它是如何实现上面的逻辑的(伪代码):

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
func (m Map) find(key) (slot int, ok bool) {
    h1, h2 := hashOf(key)            // 高低 hash bit，类似内建的map的处理，实现短地址
    s := modulus(h1, len(m.keys)/16) // 计算探测开始的位置
    for {
        // 使用SSE指令实现的探针， 使用h2进行短地址匹配
        matches := matchH2(m.metadata[s:s+16], h2)
        for _, idx := range matches {
            if m.keys[idx] == key { 
                return idx, true // 找到，返回对应的槽位
            }
        }
        // 利用SSE指令，寻找空槽位
        matches = matchEmpty(m.metadata[s:s+16])
        for _, idx := range matches {
            return idx, false // 发现空槽位，返回
        }
        s += 16
    }
}

这个库还提供了benchmark的代码，我们在Apple M2和虚机上分别测试它和内建map的性能。

Apple M1
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
goos: darwin
goarch: arm64
pkg: github.com/dolthub/swiss
BenchmarkStringMaps/n=16/runtime_map-8         	190298112	         6.716 ns/op	       0 B/op	       0 allocs/op
BenchmarkStringMaps/n=16/swiss.Map-8           	114514650	         9.000 ns/op	       0 B/op	       0 allocs/op
BenchmarkStringMaps/n=128/runtime_map-8        	181336688	         6.934 ns/op	       0 B/op	       0 allocs/op
BenchmarkStringMaps/n=128/swiss.Map-8          	124560243	        13.63 ns/op	       0 B/op	       0 allocs/op
BenchmarkStringMaps/n=1024/runtime_map-8       	100000000	        10.09 ns/op	       0 B/op	       0 allocs/op
BenchmarkStringMaps/n=1024/swiss.Map-8         	100000000	        11.27 ns/op	       0 B/op	       0 allocs/op
BenchmarkStringMaps/n=8192/runtime_map-8       	60224208	        19.38 ns/op	       0 B/op	       0 allocs/op
BenchmarkStringMaps/n=8192/swiss.Map-8         	88910022	        13.28 ns/op	       0 B/op	       0 allocs/op
BenchmarkStringMaps/n=131072/runtime_map-8     	53933996	        22.12 ns/op	       0 B/op	       0 allocs/op
BenchmarkStringMaps/n=131072/swiss.Map-8       	76083596	        16.36 ns/op	       0 B/op	       0 allocs/op
BenchmarkInt64Maps/n=16/runtime_map-8          	262228116	         4.678 ns/op	       0 B/op	       0 allocs/op
BenchmarkInt64Maps/n=16/swiss.Map-8            	227993193	         5.439 ns/op	       0 B/op	       0 allocs/op
BenchmarkInt64Maps/n=128/runtime_map-8         	242425221	         4.708 ns/op	       0 B/op	       0 allocs/op
BenchmarkInt64Maps/n=128/swiss.Map-8           	185926908	         5.876 ns/op	       0 B/op	       0 allocs/op
BenchmarkInt64Maps/n=1024/runtime_map-8        	173284822	         6.709 ns/op	       0 B/op	       0 allocs/op
BenchmarkInt64Maps/n=1024/swiss.Map-8          	186861410	         6.550 ns/op	       0 B/op	       0 allocs/op
BenchmarkInt64Maps/n=8192/runtime_map-8        	71231763	        16.57 ns/op	       0 B/op	       0 allocs/op
BenchmarkInt64Maps/n=8192/swiss.Map-8          	139595205	         8.635 ns/op	       0 B/op	       0 allocs/op
BenchmarkInt64Maps/n=131072/runtime_map-8      	64039132	        19.05 ns/op	       0 B/op	       0 allocs/op
BenchmarkInt64Maps/n=131072/swiss.Map-8        	100000000	        11.56 ns/op	       0 B/op	       0 allocs/op
PASS
ok  	github.com/dolthub/swiss	33.538s
Linux
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
goos: linux
goarch: amd64
pkg: github.com/dolthub/swiss
cpu: Intel(R) Xeon(R) Platinum 8255C CPU @ 2.50GHz
BenchmarkStringMaps/n=16/runtime_map-2         	97587910	        12.65 ns/op	       0 B/op	       0 allocs/op
BenchmarkStringMaps/n=16/swiss.Map-2           	61206505	        19.38 ns/op	       0 B/op	       0 allocs/op
BenchmarkStringMaps/n=128/runtime_map-2        	92861481	        13.35 ns/op	       0 B/op	       0 allocs/op
BenchmarkStringMaps/n=128/swiss.Map-2          	58353951	        20.83 ns/op	       0 B/op	       0 allocs/op
BenchmarkStringMaps/n=1024/runtime_map-2       	51516268	        22.70 ns/op	       0 B/op	       0 allocs/op
BenchmarkStringMaps/n=1024/swiss.Map-2         	51832698	        23.09 ns/op	       0 B/op	       0 allocs/op
BenchmarkStringMaps/n=8192/runtime_map-2       	40324459	        29.54 ns/op	       0 B/op	       0 allocs/op
BenchmarkStringMaps/n=8192/swiss.Map-2         	45826951	        26.19 ns/op	       0 B/op	       0 allocs/op
BenchmarkStringMaps/n=131072/runtime_map-2     	26659296	        43.71 ns/op	       0 B/op	       0 allocs/op
BenchmarkStringMaps/n=131072/swiss.Map-2       	30621675	        39.84 ns/op	       0 B/op	       0 allocs/op
BenchmarkInt64Maps/n=16/runtime_map-2          	128090280	         9.332 ns/op	       0 B/op	       0 allocs/op
BenchmarkInt64Maps/n=16/swiss.Map-2            	87047056	        15.01 ns/op	       0 B/op	       0 allocs/op
BenchmarkInt64Maps/n=128/runtime_map-2         	125906628	         9.837 ns/op	       0 B/op	       0 allocs/op
BenchmarkInt64Maps/n=128/swiss.Map-2           	79239448	        15.52 ns/op	       0 B/op	       0 allocs/op
BenchmarkInt64Maps/n=1024/runtime_map-2        	65208208	        17.22 ns/op	       0 B/op	       0 allocs/op
BenchmarkInt64Maps/n=1024/swiss.Map-2          	77075527	        15.81 ns/op	       0 B/op	       0 allocs/op
BenchmarkInt64Maps/n=8192/runtime_map-2        	48505800	        25.28 ns/op	       0 B/op	       0 allocs/op
BenchmarkInt64Maps/n=8192/swiss.Map-2          	64617066	        18.19 ns/op	       0 B/op	       0 allocs/op
BenchmarkInt64Maps/n=131072/runtime_map-2      	36938596	        32.38 ns/op	       0 B/op	       0 allocs/op
BenchmarkInt64Maps/n=131072/swiss.Map-2        	41026358	        28.41 ns/op	       0 B/op	       0 allocs/op

可以看到，在key的数量比较少时,swiss并不能发挥它的SSE指令的优势，但是在key值非常多的情况下， swiss优势明显。
前面也介绍了作者的maphash库，在一些支持AES指令平台上，可以利用硬件的能力，更快的计算哈希值。

不止如此，swiss在内存占用上也有它的优点。根据作者的测试,swiss可以更节省内存：

内建的map在键的数量增大时，内存会呈现阶梯状的上升，原因在于大家普遍采用的bit-hacking优化模式，为了提高求余数的方法，一般除数都会采用2的指数，因此key数量增大时需要扩展内存时，分配的内存会翻倍。所以你看到Go内建的map的内存会呈现阶梯状的增大，有时候非常的浪费。

swiss库采用了Daniel Lemire提出的一个快速求余(更准确的说，是modulo reduction)的算法，这个想法看似简单，但实际上非常巧妙 (x * N) / 232 ：

1
2
3
func fastModN(x, n uint32) uint32 {
    return uint32((uint64(x) * uint64(n)) >> 32)
}

这个方法限制n的类型是uint32,最大支持 2 ^ 32，又因为每个桶16个元素，所以swiss库最大支持2 ^ 36个元素，对于绝大部分场景，它足够了。