go internals zh深入解析go语言

2020-03-01 333浏览

1.目錄 Introduction 1.1 如何研究Go内部实现 1.2 从源代码安装Go 1.2.1 本书的组织结构 1.2.2 基本技巧 1.2.3 基本数据结构 1.3 基本类型 1.3.1 slice 1.3.2 map的实现 1.3.3 nil 1.3.4 函数调用协议 1.4 Go调用汇编和C 1.4.1 多值返回 1.4.2 go关键字 1.4.3 defer关键字 1.4.4 连续栈 1.4.5 闭包的实现 1.4.6 Go语言程序初始化过程 1.5 系统初始化 1.5.1 main.main之前的准备 1.5.2 goroutine调度 1.6 调度器相关数据结构 1.6.1 goroutine的生老病死 1.6.2 设计与演化 1.6.3 [死锁检测和竞态检测] 1.6.4 抢占式调度 1.6.5 内存管理 1.7 内存池 1.7.1 垃圾回收上篇 1.7.2 垃圾回收下篇 1.7.3 高级数据结构的实现 1.8 channel 1.8.1 interface 1.8.2 方法调用 1.8.3 网络 1.9 非阻塞io 1.9.1 [net包] 1.9.2 cgo 1.10 预备知识 1.10.1 1
2.cgo关键技术 1.10.2 Go调用C 1.10.3 C调用Go 1.10.4 [杂项] 1.11 内存模型 1.11.1 [pprof] 1.11.2 [底层同步机制] 1.11.3 [系统调用] 1.11.4 [timer] 1.11.5 [运行时符号信息] 1.11.6 [signal处理] 1.11.7 2
3.Introduction 《深入解析Go》因为自己对Go底层的东西比较感兴趣，所以抽空在写一本开源的书籍《深入解析Go》。写这本书不表示我能力很强，而是我愿意分享，和大家一起分享对Go语言的内部实现的一些研究。我一直认为知识是用来分享的，让更多的人分享自己拥有的一切知识这个才是人生最大的快乐。这本书目前我放在Github上，时间有限、能力有限，所以希望更多的朋友参与到这个开源项目中来。 3
4.如何研究Go内部实现 1 如何阅读欢迎来到Go的世界，让我们开始探索吧！ Go是一种新的语言，一种并发的、带垃圾回收的、快速编译的语言。它具有以下特点：它可以在一台计算机上用几秒钟的时间编译一个大型的Go程序。 Go为软件构造提供了一种模型，它使依赖分析更加容易，且避免了大部分C风格include文件与库的开头。 Go是静态类型的语言，它的类型系统没有层级。因此用户不需要在定义类型之间的关系上花费时间，这样感觉起来比典型的面向对象语言更轻量级。 Go完全是垃圾回收型的语言，并为并发执行与通信提供了基本的支持。按照其设计，Go打算为多核机器上系统软件的构造提供一种方法。 Go是一种编译型语言，它结合了解释型语言的游刃有余，动态类型语言的开发效率，以及静态类型的安全性。它也打算成为现代的，支持网络与多核计算的语言。要满足这些目标，需要解决一些语言上的问题：一个富有表达能力但轻量级的类型系统，并发与垃圾回收机制，严格的依赖规范等等。这些无法通过库或工具解决好，因此Go也就应运而生了。在本章中，我们将讲述Go的安装方法，以及如何阅读本书。 links 目录下一节: 从源码安装Go 4
5.从源代码安装Go 1.1 从源代码安装Go 本书面向的是已经对Go语言有一定的经验，希望能了解它的底层机制的用户。因此，只推荐从源代码安装Go。 Go源码安装在Go的源代码中，有些部分是用Plan 9 C和AT&T汇编写的，因此假如你要想从源码安装，就必须安装C的编译工具。在Mac系统中，只要你安装了Xcode，就已经包含了相应的编译工具。在类Unix系统中，需要安装gcc等工具。例如Ubuntu系统可通过在终端中执行 sudo apt-get install gcc libc6-dev 来安装编译工具。在Windows系统中，你需要安装MinGW，然后通过MinGW安装gcc，并设置相应的环境变量。 Go使用Mercurial进行版本管理，首先你必须安装了Mercurial，然后才能下载。假设你已经安装好Mercurial，执行如下代码：假设已经位于Go的安装目录 $GO_INSTALL_DIR 下 hg clone -u releasehttps://code.google.com/p/gocd go/src ./all.bash 运行all.bash后出现"ALL TESTS PASSED"字样时才算安装成功。上面是Unix风格的命令，Windows下的安装方式类似，只不过是运行all.bat，调用的编译器是MinGW的gcc。然后设置几个环境变量， export GOROOT=$HOME/go export GOBIN=$GOROOT/bin export PATH=$PATH:$GOBIN看到如下图片即说明你已经安装成功图1.1 源码安装之后执行Go命令的图如果出现Go的Usage信息，那么说明Go已经安装成功了；如果出现该命令不存在，那么可以检查一下自己的PATH环境变中是否包含了Go的安装目录。 links 目录上一节: 如何阅读下一节: 本书的组织结构 5
6.本书的组织结构 1.2 本书的组织结构本书结构第二章首先会介绍一些Go的基本数据结构的实现，如slice和map。第三章会介绍Go语言中的函数调用协议。第四章分析runtime初始化过程。第五章是goroutine的调度。第六章分析Go语言中的内存管理。第七章分析Go语言中一些高级数据结构的实现。第八章是网络封装的实现第九章讲cgo使用的一些技术第十章是其它一些杂项推荐的阅读方式本书的写作基本上是按一个循序浅近的过程。大多数章节可以独立阅读，如内存管理，goroutine调度等。而某些知识则需要前面章节的一些基础知识，比如cgo必须了解前面函数调用协议方面的一些知识，第七章高级数据结构最好对前面内存管理和goroutine调度有一定的了解。推荐的阅读方式还是按本文章节顺序，如果读者已经有一定基础，也可以只挑自己感兴趣的章节阅读。如果想更深入的了解Go语言的内部实现，希望读者能拿着Go的源代码亲自分析。通过自己学习研究得到的东西才是理解最深的。 links 目录上一节: 从源码安装Go 下一节: 基本技巧 6
7.基本技巧 1.3 基本技巧研究Go的内部实现，这里介绍一些基本的技巧。阅读源代码 Go语言的源代码布局是有一些规律的。假定读者在$GOROOT下: - ./misc 一些工具 - ./src 源代码 - ./src/cmd 命令工具，包括6c, 6l, 6g等等。最后打包成go命令。 - ./src/pkg 各个package的源代码 - ./src/pkg/runtime Go的runtime包，本书分析的最主要的部分 - AUTHORS — 文件，官方 Go语言作者列表 – CONTRIBUTORS — 文件，第三方贡献者列表 – LICENSE — 文件，Go语言发布授权协议 – PATENTS — 文件，专利 – README — 文件，README文件，大家懂的。提一下，经常有人说：Go官网打不开啊，怎么办？其实，在README中说到了这个。该文件还提到，如果通过二进制安装，需要设置GOROOT环境变量；如果你将Go放在了/usr/local/go中，则可以不设置该环境变量（Windows下是C:\go）。当然，建议不管什么时候都设置GOROOT。另外，确保$GOROOT/bin在PATH目录中。 – VERSION — 文件，当前Go版本 – api — 目录，包含所有API列表，方便IDE使用 – doc — 目录，Go语言的各种文档，官网上有的，这里基本会有，这也就是为什么说可以本地搭建”官网”。这里面有不少其他资源，比如gopher图标之类的。 – favicon.ico — 文件，官网logo – include — 目录，Go 基本工具依赖的库的头文件 – lib — 目录，文档模板 – misc — 目录，其他的一些工具，相当于大杂烩，大部分是各种编辑器的Go语言支持，还有cgo的例子等 – robots.txt — 文件，搜索引擎robots文件 – src — 目录，Go语言源码：基本工具（编译器等）、标准库 `– test — 目录，包含很多测试程序（并非_test.go方式的单元测试，而是包含main包的测试），包括一些fixbug测试。可以通过这个学到一些特性的使用。学习Go语言的内部实现，主要依靠对源代码的分析，所以阅读源代码是很好的方式。linus谈到如何学习Linux内核时也说过"Read the F**ing Source code"。使用调试器通过gdb下断点，跟踪程序的行为。调试跟代码的方式是源代码阅读的一种辅助手段。用户代码入口是在main.main，runtime库中的函数可以通过runtime.XXX断点捕获。比如写一个test.go： package main import ( "fmt" ) func main() { fmt.Println("hello world!") } 编译，调试 go build test.go gdb test 7
8.基本技巧可以在main.main处下断点，单步执行，你会发现进入了一个runtime·convT2E的函数。这个就是由于fmt.Println接受的是一个interface，而传入的是一个string，这里会做一个转换。以这个为一个突破点去跟代码，就可以研究Go语言中具体类型如何转为interface抽象类型。分析生成的汇编代码有时候分析会需要研究生成的汇编代码，这里介绍生成汇编代码的方法。 go tool 6g -S hello.go -S参数表示打印出汇编代码，更多参数可以通过-h参数查看。 go tool 6g -h 或者可以反汇编生成的可执行文件： go build test.go go tool 6l -a test less 本机是amd64的机器，如果是i386的机器，则命令是8g 需要注意的是用6g的-S生成的汇编代码和6l -a生成的反汇编代码是不太一样的。前者是直接对源代码进行汇编，后者是对可执行文件进行反汇编。在6l进行链接过程中，可能会在原汇编文件基础上插入新的指令。所以6l反汇编出来的是最接近真实代码的。不过Go的汇编语法跟常用的有点不太一致，可能读起来会不太习惯。还有另一种方式，就是在用gdb调试的过程中查看汇编。 gdb test b main.main disas links 目录上一节: 本书的组织结构下一节: 基本数据结构 8
9.基本数据结构 2 基本数据结构这一章中我们将看一下基本的数据结构，都是Go语言内置的类型。这些知识很基础，但是理解它们非常重要。我们将从最基本的类型开始，Go语言的基本类型部分跟C语言很类似，熟习C语言的朋友们应该不会陌生。我们也将对slice 和map的实现一窥究竟。看完这章，你会知道slice不是一个指针，它在栈中是占三个机器字节的。好吧，让我们开始吧！ links 目录上一节: 基本技巧下一节: 基本类型 9
10.基本类型 2.1 基本类型向新手介绍Go语言时，解释一下Go中各种类型变量在内存中的布局通常有利于帮助他们加深理解。先看一些基础的例子: 变量i属于类型int，在内存中用一个32位字长(word)表示。(32位内存布局方式）变量j由于做了精确的转换，属于int32类型。尽管i和j有着相同的内存布局，但是它们属于不同的类型：赋值操作种类型错误，必须写成更精确的转换方式： i = int(j) i = j 是一。变量f属于float类型，Go语言当前使用32位浮点型值表示(float32)。它与int32很像，但是内部实现不同。接下来，变量bytes的类型是[5]byte，一个由5个字节组成的数组。它的内存表示就是连起来的5个字节，就像C的数组。类似地，变量primes是4个int的数组。结构体和指针与C相同而与Java不同的是，Go语言让程序员决定何时使用指针。举例来说，这种类型定义： type Point struct { X, Y int } 先来定义一个简单的struct类型，名为Point，表示内存中两个相邻的整数。 Point{10,20} 表示一个已初始化的Point类型。对它进行取地址表示一个指向刚刚分配和初始化的Point类型的指针。前者在内存中是两个词，而后者是一个指向两个词的指针。结构体的域在内存中是紧挨着排列的。 10
11.基本类型 type Rect1 struct { Min, Max Point } type Rect2 struct { Min, Max *Point } Rect1是一个具有两个Point类型属性的结构体，由在一行的两个Point--四个int代表。Rect2是一个具有两个 *Point 类型属性的结构体，由两个*Point表示。使用过C的程序员可能对 Point 和 *Point 的不同毫不见怪，但用惯Java或Python的程序员们可能就不那么轻松了。Go语言给了程序员基本内存层面的控制，由此提供了诸多能力，如控制给定数据结构集合的总大小、内存分配的次数、内存访问模式以及建立优秀系统的所有要点。字符串有了前面的准备，我们就可以开始研究更有趣的数据类型了。（灰色的箭头表示已经实现的但不能直接可见的指针）字符串在Go语言内存模型中用一个2字长的数据结构表示。它包含一个指向字符串存储数据的指针和一个长度数据。因为 string类型是不可变的，对于多字符串共享同一个存储数据是安全的。切分操作 str[i:j]会得到一个新的2字长结构，一个可能不同的但仍指向同一个字节序列(即上文说的存储数据)的指针和长度数据。这意味着字符串切分可以在不涉及内存分配或复制操作。这使得字符串切分的效率等同于传递下标。（说句题外话，在Java和其他语言里有一个有名的“疑难杂症”：在你分割字符串并保存时，对于源字符串的引用在内存中仍然保存着完整的原始字符串--即使只有一小部分仍被需要，Go也有这个“毛病”。另一方面，我们努力但又失败了的是，让字符串分割操作变得昂贵--包含一次分配和一次复制。在大多数程序中都避免了这么做。） links 目录上一节: 基本数据结构下一节: slice 11
12.slice 2.2 slice 一个slice是一个数组某个部分的引用。在内存中，它是一个包含3个域的结构体：指向slice中第一个元素的指针，slice的长度，以及slice的容量。长度是下标操作的上界，如x[i]中i必须小于长度。容量是分割操作的上界，如x[i:j]中j不能大于容量。数组的slice并不会实际复制一份数据，它只是创建一个新的数据结构，包含了另外的一个指针，一个长度和一个容量数据。如同分割一个字符串，分割数组也不涉及复制操作：它只是新建了一个结构来放置一个不同的指针，长度和容量。在例子中，对 []int{2,3,5,7,11} 求值操作会创建一个包含五个值的数组，并设置x的属性来描述这个数组。分割表达式 x[1:3] 并不分配更多的数据：它只是写了一个新的slice结构的属性来引用相同的存储数据。在例子中，长度为2--只有y[0]和y[1]是有效的索引，但是容量为4--y[0:4]是一个有效的分割表达式。由于slice是不同于指针的多字长结构，分割操作并不需要分配内存，甚至没有通常被保存在堆中的slice头部。这种表示方法使slice操作和在C中传递指针、长度对一样廉价。Go语言最初使用一个指向以上结构的指针来表示slice，但是这样做意味着每个slice操作都会分配一块新的内存对象。即使使用了快速的分配器，还是给垃圾收集器制造了很多没有必要的工作。移除间接引用及分配操作可以让slice足够廉价，以避免传递显式索引。 slice的扩容其实slice在Go的运行时库中就是一个C语言动态数组的实现，在$GOROOT/src/pkg/runtime/runtime.h中可以看到它的定义： struct { Slice // must not move anything byte* array; uintgo len; // number of elements // actual data uintgo cap; // allocated number of elements }; 在对slice进行append等操作时，可能会造成slice的自动扩容。其扩容时的大小增长规则是：如果新的大小是当前大小2倍以上，则大小增长为新大小否则循环以下操作：如果当前大小小于1024，按每次2倍增长，否则每次按当前大小1/4增长。直到增长的大小超过或等于新大小。 make和new Go有两个数据结构创建函数：new和make。两者的区别在学习Go语言的初期是一个常见的混淆点。基本的区别是回一个 *T ，返回的这个指针可以被隐式地消除引用（图中的黑色箭头）。而 make(T, args) new(T) 返返回一个普通的T。通常情况下，T内部有一些隐式的指针（图中的灰色箭头）。一句话，new返回一个指向已清零内存的指针，而make返回一个复杂的结构。 12
13.slice 有一种方法可以统一这两种创建方式，但是可能会与C/C++的传统有显著不同：定义 make(*T) 来返回一个指向新分配的T的指针，这样一来，new(Point)得写成make(*Point)。但这样做实在是和人们期望的分配函数太不一样了，所以Go没有采用这种设计。 slice与unsafe.Pointer相互转换有时候可能需要使用一些比较tricky的技巧，比如利用make弄一块内存自己管理，或者用cgo之类的方式得到的内存，转换为 Go类型使用。从slice中得到一块内存地址是很容易的： s := make([]byte, 200) ptr := unsafe.Pointer(&s[0]) 从一个内存指针构造出Go语言的slice结构相对麻烦一些，比如其中一种方式： var ptr unsafe.Pointer s := ((*[1<<10]byte)(ptr))[:200] 13
14.slice 先将 ptr 强制类型转换为另一种指针，一个指向这个数组的前200个，于是 s [1<<10]byte 数组的指针，这里数组大小其实是假的。然后用slice操作取出就是一个200个元素的slice。或者这种方式： var ptr unsafe.Pointer var s1 = struct { addr uintptr len int cap int }{ptr, length, length} s := *(*[]byte)(unsafe.Pointer(&s1)) 把slice的底层结构写出来，将addr，len，cap等字段写进去，将这个结构体赋给s。相比上一种写法，这种更好的地方在于 cap更加自然，虽然上面写法中实际上1<<10就是cap。或者使用reflect.SliceHeader的方式来构造slice，比较推荐这种做法： var o []byte sliceHeader := (*reflect.SliceHeader)((unsafe.Pointer(&o))) sliceHeader.Cap = length sliceHeader.Len = length sliceHeader.Data = uintptr(ptr) links 目录上一节: 基本类型下一节: map的实现 14
15.map的实现 2.3 map的实现 Go中的map在底层是用哈希表实现的，你可以在 $GOROOT/src/pkg/runtime/hashmap.goc 找到它的实现。数据结构哈希表的数据结构中一些关键的域如下所示： struct Hmap { // 可以容纳2^B个项 uint8 B; uint16 bucketsize; // 每个桶的大小 byte *buckets; // 2^B个Buckets的数组 byte *oldbuckets; // 前一个buckets，只有当正在扩容时才不为空 }; 上面给出的结构体只是Hmap的部分的域。需要注意到的是，这里直接使用的是Bucket的数组，而不是Bucket*指针的数组。这意味着，第一个Bucket和后面溢出链的Bucket分配有些不同。第一个Bucket是用的一段连续的内存空间，而后面溢出链的 Bucket的空间是使用mallocgc分配的。这个hash结构使用的是一个可扩展哈希的算法，由hash值mod当前hash表大小决定某一个值属于哪个桶，而hash表大小是2 的指数，即上面结构体中的2^B。每次扩容，会增大到上次大小的两倍。结构体中有一个buckets和一个oldbuckets是用来实现增量扩容的。正常情况下直接使用buckets，而oldbuckets为空。如果当前哈希表正在扩容中，则oldbuckets不为空，并且 buckets大小是oldbuckets大小的两倍。具体的Bucket结构如下所示： struct Bucket { uint8 tophash[BUCKETSIZE]; // hash值的高8位....低位从bucket的array定位到bucket Bucket *overflow; // 溢出桶链表，如果有 byte // BUCKETSIZE keys followed by BUCKETSIZE values data[1]; }; 其中BUCKETSIZE是用宏定义的8，每个bucket中存放最多8个key/value对, 如果多于8个，那么会申请一个新的bucket，并将它与之前的bucket链起来。按key的类型采用相应的hash算法得到key的hash值。将hash值的低位当作Hmap结构体中buckets数组的index，找到key所在的bucket。将hash的高8位存储在了bucket的tophash中。注意，这里高8位不是用来当作key/value在bucket内部的offset 的，而是作为一个主键，在查找时对tophash数组的每一项进行顺序匹配的。先比较hash值高位与bucket的tophash[i]是否相等，如果相等则再比较bucket的第i个的key与所给的key是否相等。如果相等，则返回其对应的value，反之，在overflow buckets中按照上述方法继续寻找。整个hash的存储如下图所示(临时先采用了XX同学画的图，这个图有点问题)：图2.2 HMap的存储结构注意一个细节是Bucket中key/value的放置顺序，是将keys放在一起，values放在一起，为什么不将key和对应的value放在一起呢？如果那么做，存储结构将变成key1/value1/key2/value2… 设想如果是这样的一个map[int64]int8，考虑到字节对齐，会浪费很多存储空间。不得不说通过上述的一个小细节，可以看出Go在设计上的深思熟虑。增量扩容 15
16.map的实现大家都知道哈希表表就是以空间换时间，访问速度是直接跟填充因子相关的，所以当哈希表太满之后就需要进行扩容。如果扩容前的哈希表大小为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的比较的。 16
17.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的设计就是为插入优化的。考虑到一般的应用场景，这个应该算是很合理的。 17
18.map的实现作者还列了另个2个TODO：将多个几乎要empty的bucket合并；如果table中元素很少，考虑shrink table。(毕竟现在的实现只是单纯的grow)。 links 目录上一节: slice 下一节: nil的语义 18
19.nil 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。请读者思考一下为什么？ 19
20.nil 总之，interface跟C语言的指针一样非常灵活，关于空的语义，也跟空指针一样容易困扰新手的，需要注意。 string和slice string的空值是""，它是不能跟nil比较的。即使是空的string，它的大小也是两个机器字长的。slice也类似，它的空值并不是一个空指针，而是结构体中的指针域为空，空的slice的大小也是三个机器字长的。 channel和map channel跟string或slice有些不同，它在栈上只是一个指针，实际的数据都是由指针所指向的堆上面。跟channel相关的操作有：初始化/读/写/关闭。channel未初始化值就是nil，未初始化的channel是不能使用的。下面是一些操作规则：读或者写一个nil的channel的操作会永远阻塞。读一个关闭的channel会立刻返回一个channel元素类型的零值。写一个关闭的channel会导致panic。 map也是指针，实际数据在堆中，未初始化的值是nil。 links 目录上一节: map的实现下一节: 函数调用协议 20
21.函数调用协议 3 函数调用协议理解Go的函数调用协议对于研究其内部实现非常重要。这里将会介绍Go进行函数调用时的内存布局，参数传递和返回值的约定。正如C和汇编都是同一套约定所以能相互调用一样，Go和C以及汇编也是要满足某些约定才能够相互调用。本章先从Go调用C和汇编的例子开始(非cgo方式)，通过分析其实现学习Go的函数调用协议。然后将会研究go和defer关键字等神奇的魔法。接着会研究连续栈的实现，最后看一下闭包。这一章的内容将是后面研究cgo，goroutine实现的基础。连续栈技术是Go能够开千千万万条“线程”而不耗尽内存的基本保证，也为cgo带来了很大的限制，这些将会在后面章节中再讨论。好，让我们进入正题吧！ links 目录上一节: nil的语义下一节: Go调用汇编和C 21
22.Go调用汇编和C 3.1 Go调用汇编和C 只要不使用C的标准库函数，Go中是可以直接调用C和汇编语言的。其实道理很简单，Go的运行时库就是用C和汇编实现的，Go必须是能够调用到它们的。当然，会有一些额外的约束，这就是函数调用协议。 Go中调用汇编假设我们做一个汇编版本的加法函数。首先GOPATH的src下新建一个add目录，然后在该目录加入add.go的文件，内容如下： package add func Add(a, b uint64) uint64 { return a+b } 这个函数将两个uint64的数字相加，并返回结果。我们写一个简单的函数调用它，内容如下： package main import ( "fmt" "add" ) func main() { fmt.Println(add.Add(2, 15)) } 可以看到输出了结果为17。好的，接下来让我们删除Add函数的实现，只留下定义部分： package add func Add(a, b uint64) uint64 然后在add.go同一目录中建立一个add_amd64.s的文件(假设你使用的是64位系统)，内容如下： TEXT ·Add+0(SB),$0-24 MOVQ a+0(FP),BX MOVQ b+8(FP),BP ADDQ BP,BX MOVQ BX,res+16(FP) RET , 虽然汇编是相当难理解的，但我相信读懂上面这段不会有困难。前两条MOVQ指令分别将第一个参数放到寄存器BX，第二个参数放到寄存器BP，然后ADDQ指令将两者相加后，最后的MOVQ和RET指令返回结果。现在，再次运行前面的main函数，它将使用自定义的汇编版本函数，可以看到成功的输出了结果17。从这个例子中可以看出 Go是可以直接调用汇编实现的函数的。大多时候不必要你去写汇编，即使是研究Go的内部实现，能读懂汇编已经很足够了。也许你真的觉得在Go中写汇编很酷，但是不要忽视了这些忠告：汇编很难编写，特别是很难写好。通常编译器会比你写出更快的代码。汇编仅能运行在一个平台上。在这个例子中，代码仅能运行在 amd64 上。这个问题有一个解决方案是给 Go 对于 x86 和不同版本的代码分别写一套代码，文件名相应的以_386.s和_arm.s结尾。汇编让你和底层绑定在一起，而标准的 Go 不会。例如，slice 的长度当前是 32 位整数。但是也不是不可能为长整型。 22
23.Go调用汇编和C 当发生这些变化时，这些代码就被破坏了。当前Go编译器不能将汇编编译为函数的内联，但是对于小的Go函数是可以的。因此使用汇编可能意味着让你的程序更慢。有时需要汇编给你带来一些力量（不论是性能方面的原因，还是一些相当特殊的关于CPU的操作）。对于什么时候应该使用它，Go源码包括了若干相当好的例子（可以看看 crypto 和 math）。由于它非常容易实践，所以这绝对是个学习汇编的好途径。 Go中调用C 接下来，我们继续尝试在Go中调用C，跟调用汇编的过程很类似。首先删掉前面的add_amd64.s文件，并确保add.go文件中只是给出了Add函数的声明部分： package add func Add(a, b uint64) uint64 然后在add.go同目录中，新建一个add.c文件，内容如下： #include "runtime.h" void ·Add(uint64 a, uint64 b, uint64 ret) { ret = a + b; FLUSH(&ret); } 编译该包，运行前面的测试函数： go install add 会发现输出结果为17，说明Go中成功地调用到了C写的函数。要注意的是不管是C或是汇编实现的函数，其函数名都是以·开头的。还有，C文件中需要包含runtime.h头文件。这个原因在该文件中有说明： Go用了特殊寄存器来存放像全局的struct G和struct M。包含这个头文件可以让所有链接到Go的C文件都知道这一点，这样编译器可以避免使用这些特定的寄存器作其它用途。让我们仔细看一下这个C实现的函数。可以看到函数的返回值为空，而参数多了一个，第三个参数实际上被作为了返回值使用。其中FLUSH是在pkg/runtime/runtime.h中定义为USED(x)，这个定义是Go的C编译器自带的primitive，作用是抑制编译器优化掉对*x的赋值的。如果你很好奇USED是怎样定义的，可以去$GOROOT/include/libc.h文件里去找找。被调函数中对参数ret的修改居然返回到了调用函数，这个看起来似乎不可理解，不过早期的C编译器确实是可以这么做的。函数调用时的内存布局 Go中使用的C编译器其实是plan9的C编译器，和我们平时理解的gcc等会有一些区别。我们将上面的add.c汇编一下： go tool 6c -I $GOROOT/src/pkg/runtime -S add.c 生成的汇编代码大概是这个样子的： 23
24.Go调用汇编和C "".Add t=1 size=16 value=0 args=0x18 locals=0 000000 00000 (add.c:3)'>add.c:3)