深入剖析Go语言内部实现：并发、垃圾回收与底层机制详解

源码

需积分: 9 170 浏览量更新于2024-07-19 1 收藏 1015KB PDF 举报

身份认证购VIP最低享 7 折!

领优惠券(最高得80元）

资源详情

资源推荐

大家都知道哈希表表就是以空间换时间，访问速度是直接跟填充因子相关的，所以当哈希表太满之后就需要进行扩容。

如果扩容前的哈希表大小为2^B，扩容之后的大小为2^(B+1)，每次扩容都变为原来大小的两倍，哈希表大小始终为2的指数

倍，则有(hashmod2^B)等价于(hash&(2^B-1))。这样可以简化运算，避免了取余操作。

假设扩容之前容量为X，扩容之后容量为Y，对于某个哈希值hash，一般情况下(hashmodX)不等于(hashmodY)，所以扩容

之后要重新计算每一项在哈希表中的新位置。当hash表扩容之后，需要将那些旧的pair重新哈希到新的table上(源代码中称之

为evacuate)，这个工作并没有在扩容之后一次性完成，而是逐步的完成（在insert和remove时每次搬移1-2个pair），Go语

言使用的是增量扩容。

为什么会增量扩容呢？主要是缩短map容器的响应时间。假如我们直接将map用作某个响应实时性要求非常高的web应用存

储，如果不采用增量扩容，当map里面存储的元素很多之后，扩容时系统就会卡往，导致较长一段时间内无法响应请求。不

过增量扩容本质上还是将总的扩容时间分摊到了每一次哈希操作上面。

扩容会建立一个大小是原来2倍的新的表，将旧的bucket搬到新的表中之后，并不会将旧的bucket从oldbucket中删除，而是

加上一个已删除的标记。

正是由于这个工作是逐渐完成的，这样就会导致一部分数据在oldtable中，一部分在newtable中，所以对于hashtable的

insert,remove,lookup操作的处理逻辑产生影响。只有当所有的bucket都从旧表移到新表之后，才会将oldbucket释放掉。

扩容的填充因子是多少呢？如果grow的太频繁，会造成空间的利用率很低，如果很久才grow，会形成很多的overflow

buckets，查找的效率也会下降。这个平衡点如何选取呢(在go中，这个平衡点是有一个宏控制的(#defineLOAD6.5),它的意

思是这样的，如果table中元素的个数大于table中能容纳的元素的个数，那么就触发一次grow动作。那么这个6.5是怎么得到

的呢？原来这个值来源于作者的一个测试程序，遗憾的是没能找到相关的源码，不过作者给出了测试的结果：

LOAD%overflowbytes/entryhitprobemissprobe

4.002.1320.773.004.00

4.504.0517.303.254.50

5.006.8514.773.505.00

5.5010.5512.943.755.50

6.0015.2711.674.006.00

6.5020.9010.794.256.50

7.0027.1410.154.507.00

7.5034.039.734.757.50

8.0041.109.405.008.00

%overflow=percentageofbucketswhichhaveanoverflowbucket

bytes/entry=overheadbytesusedperkey/valuepair

hitprobe=#ofentriestocheckwhenlookingupapresentkey

missprobe=#ofentriestocheckwhenlookingupanabsentkey

可以看出作者取了一个相对适中的值。

查找过程

1. 根据key计算出hash值。

2. 如果存在oldtable,首先在oldtable中查找，如果找到的bucket已经evacuated，转到步骤3。反之，返回其对应的

value。

3. 在newtable中查找对应的value。

这里一个细节需要注意一下。不认真看可能会以为低位用于定位bucket在数组的index，那么高位就是用于key/valule在

bucket内部的offset。事实上高8位不是用作offset的，而是用于加快key的比较的。

map的实现

do{//对每个桶b

//依次比较桶内的每一项存放的tophash与所求的hash值高位是否相等

for(i=0,k=b->data,v=k+h->keysize*BUCKETSIZE;i<BUCKETSIZE;i++,k+=h->keysize,v+=h->valuesize)

{

if(b->tophash[i]==top){

k2=IK(h,k);

t->key->alg->equal(&eq,t->key->size,key,k2);

if(eq){//相等的情况下再去做key比较...

*keyp=k2;

returnIV(h,v);

}

}

}

b=b->overflow;//b设置为它的下一下溢出链

}while(b!=nil);

插入过程分析

1. 根据key算出hash值，进而得出对应的bucket。

2. 如果bucket在oldtable中，将其重新散列到newtable中。

3. 在bucket中，查找空闲的位置，如果已经存在需要插入的key，更新其对应的value。

4. 根据table中元素的个数，判断是否growtable。

5. 如果对应的bucket已经full，重新申请新的bucket作为overbucket。

6. 将key/valuepair插入到bucket中。

这里也有几个细节需要注意一下。

在扩容过程中，oldbucket是被冻结的，查找时会在oldbucket中查找，但不会在oldbucket中插入数据。如果在oldbucket是找

到了相应的key，做法是将它迁移到新bucket后加入evalucated标记。并且还会额外的迁移另一个pair。

然后就是只要在某个bucket中找到第一个空位，就会将key/value插入到这个位置。也就是位置位于bucket前面的会覆盖后面

的(类似于存储系统设计中做删除时的常用的技巧之一，直接用新数据追加方式写，新版本数据覆盖老版本数据)。找到了相

同的key或者找到第一个空位就可以结束遍历了。不过这也意味着做删除时必须完全的遍历bucket所有溢出链，将所有的相同

key数据都删除。所以目前map的设计是为插入而优化的，删除效率会比插入低一些。

map设计中的性能优化

读完map源代码发现作者还是做了很多设计上的选择的。本人水平有限，谈不上优劣的点评，这里只是拿出来与读者分享。

HMap中是Bucket的数组，而不是Bucket指针的数组。好的方面是可以一次分配较大内存，减少了分配次数，避免多次调用

mallocgc。但相应的缺点，其一是可扩展哈希的算法并没有发生作用，扩容时会造成对整个数组的值拷贝(如果实现上用

Bucket指针的数组就是指针拷贝了，代价小很多)。其二是首个bucket与后面产生了不一致性。这个会使删除逻辑变得复杂一

点。比如删除后面的溢出链可以直接删除，而对于首个bucket，要等到evalucated完毕后，整个oldbucket删除时进行。

没有重用设freelist重用删除的结点。作者把这个加了一个TODO的注释，不过想了一下觉得这个做的意义不大。因为一方

面，bucket大小并不一致，重用比较麻烦。另一方面，下层存储已经做过内存池的实现了，所以这里不做重用也会在内存分

配那一层被重用的，

bucket直接key/value和间接key/value优化。这个优化做得蛮好的。注意看代码会发现，如果key或value小于128字节，则它

们的值是直接使用的bucket作为存储的。否则bucket中存储的是指向实际key/value数据的指针，

bucket存8个key/value对。查找时进行顺序比较。第一次发现高位居然不是用作offset，而是用于加快比较的。定位到bucket

之后，居然是一个顺序比较的查找过程。后面仔细想了想，觉得还行。由于bucket只有8个，顺序比较下来也不算过分。仍然

是O(1)只不过前面系数大一点点罢了。相当于hash到一个小范围之后，在这个小范围内顺序查找。

插入删除的优化。前面已经提过了，插入只要找到相同的key或者第一个空位，bucket中如果存在一个以上的相同key，前面

覆盖后面的(只是如果，实际上不会发生)。而删除就需要遍历完所有bucket溢出链了。这样map的设计就是为插入优化的。考

虑到一般的应用场景，这个应该算是很合理的。

map的实现

2.4nil的语义

什么？nil是一种数据结构么？为什么会讲到它，没搞错吧？没搞错。不仅仅是Go语言中，每门语言中nil都是非常重要的，它

代表的是空值的语义。

在不同语言中，表示空这个概念都有细微不同。比如在scheme语言(一种lisp方言)中，nil是true的！而在ruby语言中，一切都

是对象，连nil也是一个对象！在C中NULL跟0是等价的。

按照Go语言规范，任何类型在未初始化时都对应一个零值：布尔类型是false，整型是0，字符串是""，而指针，函数，

interface，slice，channel和map的零值都是nil。

interface

一个interface在没有进行初始化时，对应的值是nil。也就是说varvinterface{}，

此时v就是一个nil。在底层存储上，它是一个空指针。与之不同的情况是，interface值为空。比如：

varv*T

variinterface{}

i=v

此时i是一个interface，它的值是nil，但它自身不为nil。

Go中的error其实就是一个实现了Error方法的接口：

typeerrorinterface{

Error()string

}

因此，我们可以自定义一个error：

typeErrorstruct{

errCodeuint8

}

func(e*Error)Error()string{

switche.errCode{

case1:

return"filenotfound"

case2:

return"timeout"

case3:

return"permissiondenied"

default:

return"unknownerror"

}

}

如果我们这样使用它：

funccheckError(errerror){

iferr!=nil{

panic(err)

}

}

vare*Error

checkError(e)

e是nil的，但是当我们checkError时就会panic。请读者思考一下为什么？

nil

剩余93页未读，继续阅读

AhhSong

粉丝: 25
资源: 3

深入剖析Go语言内部实现：并发、垃圾回收与底层机制详解

go语言实战源码

Go：Go语言标准库深度解析

赵老师深度解析Go语言汇编高级课程+6.8GB视频教程下载

Go语言编程深度解析

Go语言深度解析：源码篇

Go语言源码深度解析

Go语言复合类型深度解析

深度解析Go语言的特性与用途

Go语言进阶：标识符与关键字深度解析

Go语言中的建造者模式深度解析

OSPF路由算法深度解析

分布式事务处理深度解析

tensorrt深度解析是什么

spring源码深度解析

springboot源码深度解析

mybatis 3源码深度解析pdf下载

linux内核深度解析 余华兵 pdf

5g物理层深度解析(1).pdf

mybatis源码深度解析

springmvc源码深度解析

最新资源

linux内核深度解析余华兵 pdf