go map源码阅读及与php map实现对比

Posted by 行如风 Blog on February 23, 2021

本文作者:刘代明(常用网名:行如风,常用游戏名:学长的棉被),一个文艺青年(纳尼?青年?是的,你没看错:世界卫生组织(2020年)对青年的定义:18-65周岁[来自百度百科])。现在奇虎360搜索技术部任web服务端技术专家职位。 本文为作者原创,祝大家阅读愉快。

前言

之前在openresty协程调度对比go协程调度文章中分析了go程序启动过程(从go程序开始执行到用户的main程序执行前发生了些什么),今天结合一个简短例子说下go map的底层实现(顺便看下在编译阶段发生了什么),同时对比下php的map实现

go map实现

说明:go版本:1.15.6,平台:linux

一段简单的代码如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
package main
import (
    "fmt"
)

func main() {
    m := make(map[string]int64, 53)
	m["a"] = 111111111
	m["b"] = 111111111
	delete(m, "a")
	fmt.Println(m["a"], m["b"])
}

为了定位到其底层实现,我们先看下go语言的编译过程。

编译

其实,go作为一个编译型语言,go程序会在编译阶段经过一系列处理后最终生成机器码:

解析阶段

源码地址:cmd/compile/internal/syntax

1.词法分析

解析成token,我们可以通过go提供的这两个package:”go/scanner”和”go/token”模拟

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
func TestToken(t *testing.T) {
	src := []byte(`package main
    import "fmt"

    func main() {
        m := make(map[string]int64, 53)
        m["a"] = 111111111
        fmt.Println(m["a"])
    }
    `)
	var s scanner.Scanner
	fset := token.NewFileSet()
	file := fset.AddFile("", fset.Base(), len(src))
	s.Init(file, src, nil, 0)
	for {
		pos, tok, lit := s.Scan()
		if tok == token.EOF {
			break
		}
		fmt.Printf("%s\t%s\t%q\n", fset.Position(pos), tok, lit)
	}
}

最终结果截取:

1
2
3
4
5
6
7
8
9
1:1 package "package"
1:9 IDENT   "main"
      ......
7:13    IDENT   "Println"
7:20    (   ""
7:21    IDENT   "m"
     ......

2.语法分析 将扫描后生成的token转化为抽象语法树,每个go源码文件被构造为独立的语法树。同样,我们可以通过go提供的包:go/parser和go/ast来看下AST

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
func TestParser(t *testing.T) {
	src := []byte(`package main
    import "fmt"

    func main() {
        m := make(map[string]int64, 53)
        m["a"] = 111111111
        fmt.Println(m["a"])
    }
    `)
	fset := token.NewFileSet()
	file, err := parser.ParseFile(fset, "", src, 0)
	if err != nil {
		log.Fatal(err)
	}
	ast.Print(fset, file)
}

输出结果截取:

1
2
3
4
5
6
7
8
9
10
11
12
13
 0  *ast.File {
 1  .  Package: 1:1
 2  .  Name: *ast.Ident {
 3  .  .  NamePos: 1:9
 4  .  .  Name: "main"
 5  .  }
 6  .  Decls: []ast.Decl (len = 2) {
         ......
151  .  }
        ......
166  }

类型检查

源码地址:cmd/compile/internal/gc

在这个阶段,会对上面生成的每个文件对应的AST进行节点遍历,对每个节点类型进行检查,去掉声明但未使用,消除dead code等

生成中间代码

源码地址:

cmd/compile/internal/gc(AST转换成SSA)

cmd/compile/internal/ssa(SSA多轮传递及规则)

在这个阶段,AST会被转换为SSA(静态单赋值,Static Single Assignment)形式的中间代码,同时关键字,操作符会被转换成runtime函数。

如我们今天要说的map这个关键字及其操作就会在这个阶段进行转换。

我们可以通过执行下面命令产生ssa文件:

GOSSAFUNC=func go build go file

如:GOSSAFUNC=maps go build main.go

说明: 笔者当前版本为1.15.6,如果对main方法执行ssa生成会报panic

这个issue会在1.16版本进行修复

生成ssa文件内容如下,选择源码某行,可以看到对应的各阶段过程:

最终生成机器码

定位

通过编译过程,我们看到map的底层实现是在编译阶段将map关键字及其操作进行了运行时转换。

而我们想要定位到这段代码map的相关实现,可以有多种方式:

1.借助go tool工具生成反汇编代码:go build -gcflags “-S” main.go或go tool compile -S main.go

2.gdb或dlv调试看反汇编代码

3.看中间代码(SSA生成)

由此我们可以定位到,map的底层代码的实现。

数据结构:

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
27
28
29
// A header for a Go map.
type hmap struct {
	count     int // map中有效元素的个数
	flags     uint8
	B         uint8  // buckets个数为2^B,可装的元素个数为:负载因子 * 2^B,负载因子为6.5
	noverflow uint16 // 溢出的bmap数量(近似值)
	hash0     uint32 // hash seed

	buckets    unsafe.Pointer // 指向第一个bucket
	oldbuckets unsafe.Pointer // 在扩容的时候使用,为之前的buckets
	nevacuate  uintptr        // 搬迁计数器,在扩容阶段使用

	extra *mapextra // optional fields
}

// mapextra holds fields that are not present on all maps.
type mapextra struct {
	overflow    *[]*bmap // 存储溢出的bmap
	oldoverflow *[]*bmap // 扩容阶段使用,为之前的overflow

	nextOverflow *bmap // 下一个待使用的空闲bmap,溢出时使用
}

// A bucket for a Go map.
type bmap struct {
	tophash [bucketCnt]uint8 // key的hash值高8位
}

需要指出的是bmap作为真正存储map数据的地方,为什么只有tophash字段,其key和value呢?其实我们知道map的key和value有多种类型,go作为强类型语言,在定义后其类型就确定了,所以bmap的key和value字段类型就可以在编译阶段确定,避免了穷举,减少代码复杂度。

bmap中key和value类型通过func bmap(t *types.Type) *types.Type确定。

bmap结构为:

1
2
3
4
5
6
7
8
type bmap struct {
	topbits  [8]uint      // key的hash高8位
	keys     [8]keytype	  // key
	elems    [8]elemtype  // value
	overflow uintptr	  // 溢出后下一个bmap
}

go map实现

总览

先上总结,大家在学习的时候根据总结来看源码,更容易理解。

1.编译器会根据key类型,位数来映射不同的运行时函数,但他们实现大体是一致的。如访问运行时函数:mapaccess,mapaccess1_fast32,mapaccess2_fast64,mapaccess1_faststr等,所以大家看到不同的文章中有对不同函数的解析。

2.go使用bmap数据结构来存储key和value

3.查找时先定位key属于哪个bucket,再查看位于bmap的哪个位置

4.go的map使用开放地址法来解决hash冲突,并放入bmap的overflow字段指向的bmap

回到最开始的代码,来分别看下初始化,赋值,删除,扩容过程

代码比较多,我只讲一些我认为值得提一下或者大家看起来模糊的部分,函数我都会给出链接,大家可以跳进去看源码。

初始化

make(map[k]v, hint)或map[k]v{}

初始化函数家族:

func makemap_small() *hmap 在 hint <= 8 或不提供hint时编译器会使用这个函数用来初始化

func makemap64(t *maptype, hint int64, h *hmap) *hmap

func makemap(t *maptype, hint int, h *hmap) *hmap

其实除了上面外,还有可能在汇编层面看不到makemap相关函数,其实编译器还会根据逃逸分析结果,来确定map初始化,相关函数位置在这里

我们主要看makemap的实现。

1.h.hash0 = fastrand() //初始化hash0

使用随机数对hash0进行初始化。看到了吗,其使用了xorshift64进行的随机数生成,我们之前介绍的分布式唯一ID生成文章中最后的实现也是使用这种高效的随机数生成算法。

而其使用的mp.fastrand,其fastrandseed正是我们在openresty协程调度对比go协程调度文章中提到的runtime.args初始化阶段由startupRandomData字段生成的

2.使用func overLoadFactor(count int, B uint8) bool 函数初始化h.B

B从0开始,不断增加,直到找到B使得 负载因子 * 2^B >= count,其中负载因子为6.5。对于我们上面这段代码,count就是53.得到的B就是4.

3.初始化h.buckets,h.extra.nextOverflow

至此,初始化完成,如下图所示:

赋值

赋值家族函数:mapassign*。同样,我们结合本例,看下赋值过程。

在本例中,赋值函数为:func mapassign_faststr(t *maptype, h *hmap, s string) unsafe.Pointer

1.again标签内:

bucket := hash & bucketMask(h.B) // hash值的低2^h.B-1位来定位到这个key属于哪个bucket

b := (bmap)(unsafe.Pointer(uintptr(h.buckets) + bucketuintptr(t.bucketsize))) // 这个bucket内的bmap

top := tophash(hash) // hash的高8位为tophash

2.bucketloop标签内:

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
27
28
29
30
31
for {
	for i := uintptr(0); i < bucketCnt; i++ {
		if b.tophash[i] != top {
			if isEmpty(b.tophash[i]) && insertb == nil {
				insertb = b
				inserti = i
			}
			if b.tophash[i] == emptyRest {
				break bucketloop
			}
			continue
		}
		k := (*stringStruct)(add(unsafe.Pointer(b), dataOffset+i*2*sys.PtrSize))
		if k.len != key.len {
			continue
		}
		if k.str != key.str && !memequal(k.str, key.str, uintptr(key.len)) {
			continue
		}
		// already have a mapping for key. Update it.
		inserti = i
		insertb = b
		goto done
	}
	ovf := b.overflow(t)
	if ovf == nil {
		break
	}
	b = ovf
}

双重for循环寻找合适插入点

  • 遍历顺序:从当前bmap开始,从前往后遍历,如果找不到,会从overflow的bmap中继续查找
  • 我们考虑两种情况:
  • 1.刚初始化完毕:此时每个bmap的tophash均为emptyRest(即0值),所以找到了当前的插入点直接跳出bucketloop标签。
  • 2.被删除过,则tophash值为emptyOne(即1值),如当前bmap的tophash为:|1|1|1|76|0|0|0|0|,则会优先插入到第一个值为1的位置。此时还要继续遍历看是否有和计算出的top值相等的tophash值没,如果有,且key值相等,则更新插入点。
  • 可以看出插入赋值是一个紧凑的过程(有空位时优先往插入前面的)
1
2
3
4
5
6
7
if insertb == nil {
	// all current buckets are full, allocate a new one.
	insertb = h.newoverflow(t, b)
	inserti = 0 // not necessary, but avoids needlessly spilling inserti
}

如果没找到插入点,则会创建溢出的bmap(拉链法):

  • 1.会优先使用之前预分配的bucket(h.extra.nextOverflow)
  • 如果当前h.extra.nextOverflow不是预分配的最后一位,则把h.extra.nextOverflow往后移一位(之前介绍数据结构时提到,nextOverflow就是下一个待分配的bmap)
  • 如果是最后一位,则把其overflow置为nil(初始化时我们看到最后一个bucket的overflow指向了第一个bucket),同时h.extra.nextOverflow无可用bucket,置为nil
  • 2.如果无可用的nextOverflow,则新建一个

对于m[k]=v,我们看到赋值函数并没有接收v,而是返回了v的内存指针

其实,是编译器生成的汇编指令来完成值的存储的,我们用gdb来看下反汇编代码:

1
2
3
4
5
6
7
8
   0x00000000004999e0 <+160>:	callq  0x4117c0 <runtime.mapassign_faststr>
   0x00000000004999e5 <+165>:	mov    0x20(%rsp),%rax
   0x00000000004999ea <+170>:	mov    %rax,0x60(%rsp)
   0x00000000004999ef <+175>:	test   %al,(%rax)
   0x00000000004999f1 <+177>:	movq   $0x69f6bc7,(%rax) // 寄存器间接寻址,rax存储的是v的内存地址,把 111111111放入这个内存地址
   0x00000000004999f8 <+184>:	lea    0xe841(%rip),%rax        # 0x4a8240

当然在赋值过程中会出现需要扩容的情况,我们后面说

访问

访问家族函数:mapaccess*。同样,我们结合本例,看下访问过程。

本例中访问函数为:func mapaccess1_faststr(t *maptype, h *hmap, ky string) unsafe.Pointer

上面讲了赋值过程的查找,访问也是一样的过程。访问函数中区分了只有一个bucket和多bucket情况,我们看下多bucket情况。

1.同样需要先计算key的hash值

2.使用hash值的低2^B-1位定位出key所在bucket

3.使用hash值的高8位来匹配tophash

4.依次在当前bucket所在的bmap中寻找,没有的话在overflow中寻找,循环寻找,直到结束

删除

删除家族函数:mapdelete*。

本例中删除函数为:func mapdelete_faststr(t *maptype, h *hmap, ky string)

1.删除前同样需要先查找到该key的位置,查找过程同上面的访问过程。

2.b.tophash[i] = emptyOne // 删除仅需把tophash值设为1

3.每删除一个key,需要查看当前key位置的下一位tophash值是否是emptyRest(即是否是0值),如果是0值的话,需要把下一位前的emptyOne变更为emptyRest,直到遇到非emptyOne为止。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
for {
				b.tophash[i] = emptyRest
				if i == 0 {
					if b == bOrig {
						break // beginning of initial bucket, we're done.
					}
					// 从当前bucket的第一个bmap查找,直到当前bmap的前一个停止
					c := b
					for b = bOrig; b.overflow(t) != c; b = b.overflow(t) {
					}
					i = bucketCnt - 1
				} else {
					i--
				}
				if b.tophash[i] != emptyOne {
					break
				}
			}

我们通过一个示例来看下这个过程:

扩容

由编译器确定选用哪个函数进行增量式扩容: growWork*。

在赋值阶段,可能会触发扩容,触发条件为:

1.本次元素如果插入,负载将达到临界点:插入的元素数量 > 负载因子*2^B;此时容量需扩大一倍

2.bmap的overflow过多,overflow数量 >= 2^(B&15)的数量。此时容量不变,目的仅是使排除删除造成的空洞,减少overflow,使数据结构更紧凑

我们看下过程:

1.扩容开始,使用func hashGrow(t *maptype, h *hmap)进行扩容准备:判断是否需要容量翻倍,并设置h.oldbuckets为h.buckets,新建buckets和nextOverflow

2.增量搬迁:搬迁家族函数为evacuate*,在赋值和删除时,定位到key所属的bucket,则对该bucket内的bmap及其overflow的bmap进行搬迁。

对于我们这个例子中,如果不停增加元素直至扩容,则搬迁函数为 func evacuate_faststr(t *maptype, h *hmap, oldbucket uintptr)

3.直至搬迁完毕。

搬迁使用的数据结构为:

1
2
3
4
5
6
7
8
type evacDst struct {
	b *bmap          // current destination bucket
	i int            // key/elem index into b
	k unsafe.Pointer // pointer to current key storage
	e unsafe.Pointer // pointer to current elem storage
}

我们可用把上面这个看作一个箱子。

我们看下搬迁过程:

1.如果扩容是等量扩容,则使用一个箱子搬迁;如果是双倍扩容,则使用两个箱子进行搬迁。

2.从旧bucket中bmap第一个开始,顺序搬迁直至overflow也搬迁完毕停止。

3.如果是双倍扩容,则会分为高和低两部分(两部分容量相等),并使用两个exacDst:y和x分别对应高位和低位。计算落到高位还是低位。

4.搬迁过程中tophash值不变。这样在赋值和删除时,仍通过高八位定位bmap中的位置。

双倍扩容后,如何确定key所属的bucket呢,我们看到双倍扩容会使用两个exacDst进行分流,我们看到确定是使用x还是y时,计算方式为:

1
2
3
4
5
6
hash := t.hasher(k, uintptr(h.hash0))
if hash&newbit != 0 {
	useY = 1
}

而定位bucket计算方式为:

1
bucket := hash & bucketMask(h.B)

其中newbit为原来的2^B,如果得到useY=1,则说明高位为1,最终的bucket为2^h.B(原来的B)+原来的bucket。

举个例子:

扩容前:h.B为4(即100),原来的bucket为:hash&11,假设为2,即10

扩容后:8(1000),现在的bucket为:hash&111

useY=1,则说明hash值后三位为1??,现在的bucket=110,即 2^h.B(原来的B)+原来的bucket=4+2=6。

等量扩容如下图:

双倍扩容如下图:

PHP的map实现

php版本:7.4.15

其实在php中,在语言层面,准确来说叫数组,而数组底层实现了map的功能。我们知道,map的key定位是需要hash函数来实现O(1)查询的,是无序的,而php中是如何兼顾数组的有序及hash函数的映射呢?

我们看其数据结构,定义在Zend/zend_types.h文件里

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
27
28
29
30
31
typedef struct _Bucket {
	zval              val;
	zend_ulong        h;                /* hash value (or numeric index)   */
	zend_string      *key;              /* string key or NULL for numerics */
} Bucket;

typedef struct _zend_array HashTable;

struct _zend_array {
	zend_refcounted_h gc; // 引用计数,gc使用
	union { // 辅助信息
		struct {
			ZEND_ENDIAN_LOHI_4(
				zend_uchar    flags,
				zend_uchar    _unused,
				zend_uchar    nIteratorsCount,
				zend_uchar    _unused2)
		} v;
		uint32_t flags;
	} u;
	uint32_t          nTableMask; // 哈希值计算掩码,等于nTableSize的负值(nTableMask = -nTableSize)
	Bucket           *arData; // 指向数组的第一个Bucket
	uint32_t          nNumUsed; // 已使用的Buckets数量
	uint32_t          nNumOfElements; // 有效元素数量
	uint32_t          nTableSize; // 数组总容量,2^n
	uint32_t          nInternalPointer; // 内部遍历使用指针
	zend_long         nNextFreeElement; // 下一个可用数字索引
	dtor_func_t       pDestructor; //析构函数
};

在php中,分为两部分:

1.数组元素表,每个数组内都是一个Buckets。容量为2^n,插入元素时顺序插入,新插入的元素索引idx为ht->nNumUsed++,nNumUsed是递增的,表示已使用的Buckets数量。

2.索引表,其和数组元素容量等长。存储每个key在数组元素中的索引idx。

如果插入时出现了hash冲突,通过拉链法解决hash冲突,新插入的这个元素的val.u2.next为该key所在索引表内存储的索引值。

索引计算方法:nIndex = h | ht->nTableMask;

其中h为key经过times 33算法后的值,对应计算函数为:zend_inline_hash_func(const char *str, size_t len)

如:一个容量为4,有两个元素的数组结构图总览如下图:

添加

对应函数:zend_hash_index_add_or_update()

zend_hash_str_add_or_update()

数组元素表顺序插入,更新索引表对应位置数据。值得注意的是,php中并没有对hash冲突进行特殊处理,而是每个key插入数组中的Bucket时,都让其val.u2.next为当前索引表中的值,然后再更新索引表中的值。这样如果没有冲突产生,则val.u2.next值就为-1。无需特殊处理。

如下图,新增一个元素,且出现了hash冲突:

查找

先在索引表中拿到数组元素的idx,然后拿到数据,如果key不等,在其val.u2.next中进行比较,直至结束。

删除

先找到该元素,然后将该位置数据val.type置为IS_UNDEF,并不移动数据。

扩容

在添加的过程中,如果已使用的buckets数量到达元素数组总容量,则触发扩容,对应函数为zend_hash_do_resize()

1.如果ht->nNumUsed > ht->nNumOfElements + (ht->nNumOfElements » 5),则不更改容量,仅重新hash

2.如果ht->nTableSize < HT_MAX_SIZE,则会进行双倍扩容。此时会申请双倍容量内存,并把之前的数据全部拷贝到新地址,释放旧内存,然后重新hash

重新hash时,如果存在空洞(删除导致元素数组空洞),则需要从前往后,把删除的元素往前移,把空洞给填满(使数据更紧凑)。对应函数为zend_hash_rehash(HashTable *ht)

对比

可以看出,

1.php使用索引表和元素数组两部分来实现map和数组的功能;而go使用元素数组部分,每个数组内最多可装8个数据,使用负载因子控制扩容,两者的实现各有千秋。

2.两者都使用拉链法来处理hash冲突。

3.在插入时,如果出现过空洞(删除导致),go更倾向往前插入来使得结构更紧凑,而php是顺序插入,在扩容阶段来处理空洞。

4.在扩容时,go使用增量扩容,而php是全量。

参考:

go源码1.15

golang-notes/map.md

php源码7.4.15