【一月一本技术书】-【Go语言设计与实现】- 9月

🚀 优质资源分享 🚀

Go ： 2009.11.10
代表作：Docker、k8s、etcd
模仿C语言，目标：互联网的C语言

讲的晦涩难懂。。。。硬板。。放弃了好几次才读完。满分10分，打6分。

下个月：Python数据结构与算法分析吧。需要算法刷题了。

四大：编译原理、基础知识、运行时、进阶知识

编译原理

编译过程

抽象语法树 Abstract Syntax Tree\ AST\ 是源代码语法的结构的一种抽象表示。

用树状的方式表示编程语言的语法结构。每一个节点表示源代码的一个元素。每一颗子树表示一个语法元素。
2 * 3 + 7

抽象语法树抹去了源代码中不重要的一些字符：空格、分号、括号等

静态单赋值Static Single Assignment\SSA 是中间代码的特性。

每个变量只会被赋值一次。 优化

|  | x := 1 # 无效 |
|  | x := 2 # 有效 |
|  | y := x |
|  |  |
|  | x\_1 := 1 # 无效，编译后，没有这个玩意了 |
|  | x\_2 := 2 |
|  | y\_1 := x\_2 |


1
2
3
4
5
6
7
8
9
10
11

指令集

• 复杂指令集 CISC： 通过增加指令的类型减少需要执行的指令数
• 精简指令集 RISC： 使用更少的指令类型完成目标计算任务

编译原理

编译器代码：src/cmd/compile目录中
编译器分为 前端和后端

• 前端： 词法分析、语法分析、类型检查、中间代码生成
• 后端： 目标代码的生成、优化；将中间代码翻译成目标机器能够运行的二进制机器码
  

四个阶段：词法和语法分析、类型检查和AST转换、通用SSA生成、机器代码生成

• 词法和语法分析
  解析源代码文件开始，词法分析的作用就是解析源代码文件。将字符串序列转换成Token序列。方便后面的处理和解析。
  执行词法分析的程序称为 词法解析器 lexer

语法分析的输入是词法分析器输出的Token序列。根据编程语言定义好的文法 Grammar分析Token序列。
每一个go的源代码文件最终会被归纳成一个SourceFile结构。

|  | SourceFile = PackageClause ";" { ImportDecl ";" } { TopLevelDecl ";" } . |


1
2
3
4
5

词法分析器会返回一个不包含空格、换行等字符的Token序列。 package,json,import,(,io,)…
语法分析器会把Token序列转换成有意义的结构体—语法树,AST.

|  | "json.go": SourceFile { |
|  |  PackageName: "json", |
|  |  ImportDecl: []Import{ |
|  |  "io", |
|  |  }, |
|  |  TopLevelDecl: ... |
|  | } |


1
2
3
4
5
6
7
8
9
10
11

一个源文件对应着一个AST. 包含：包名、定义的常量、结构体和函数。
GO使用的语法解析器是LALR(1)的文法。

语法解析的过程中发生的任何语法错误都会被语法解析器发现并打印到标准输出上。

• 类型检查
  AST生成之后。编译器会对语法树中定义和使用的类型进行检查。

1. 常量、类型和函数名及类型
2. 变量的赋值和初始化
3. 函数和闭包的主体
4. 哈希键值对的类型
5. 导入函数体
6. 外部的声明
   遍历整颗抽象语法树，保证节点不存在类型错误，

• 中间代码生成
  类型检查之后就不存在语法错误了，编译器就会将AST转换成中间代码
  会使用gc.compileFunctions编译整个Go语言项目中的全部函数。并发编译
  
• 机器码生成
  不同类型的CPU分别使用不同的包生成机器码，amd64、arm、arm64、mips、mips64、ppc64、s390x、x86、wasm.

Go语言的编译器能够生成Wasm WebAssembly 格式的指令，就可以运行在常见的主流浏览器中。

编译器入口

src/cmd/complie/internal/gc/main.go。
抽象语法树会经历类型检查、SSA 中间代码生成以及机器码生成三个阶段
检查常量、类型和函数的类型；
处理变量的赋值；
对函数的主体进行类型检查；
决定如何捕获变量；
检查内联函数的类型；
进行逃逸分析；
将闭包的主体转换成引用的捕获变量；
编译顶层函数；
检查外部依赖的声明

词法分析和语法分析

源代码对于计算机来说是无法被理解的字符串。
第一步:将字符串分组。如下分为 make、 chan、 int 和 括号

|  | make(chan int) |


1
2
3
4
5

词法分析是将字符序列转换为标记（token）序列的过程。

• lex
  lex是用于生成词法分析器的工具。
  lex生成的代码能够将一个文件中的字符分解成Token序列。
  lex就是一个正则匹配的生成器。

lex文件示例：

|  | %{ |
|  | #include  |
|  | %} |
|  |  |
|  | %% |
|  | package printf("PACKAGE "); # 解析package |
|  | import printf("IMPORT "); # 解析 import |
|  | \. printf("DOT "); # 解析点 |
|  | \{ printf("LBRACE ");  |
|  | \} printf("RBRACE "); |
|  | \( printf("LPAREN "); |
|  | \) printf("RPAREN "); |
|  | \" printf("QUOTE "); |
|  | \n printf("\n"); |
|  | [0-9]+ printf("NUMBER "); |
|  | [a-zA-Z\_]+ printf("IDENT "); |
|  | %% |


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

这个lex文件就可以解析下面这段代码

|  | package main |
|  |  |
|  | import ( |
|  | "fmt" |
|  | ) |
|  |  |
|  | func main() { |
|  |  fmt.Println("Hello") |
|  | } |


1
2
3
4
5
6
7
8
9
10
11
12
13

.l结尾的lex代码并不能直接运行，通过lex命令将上面的.l展开成C语音代码。

|  | $ lex simplego.l |
|  | $ cat lex.yy.c |
|  | ... |
|  | int yylex (void) { |
|  |  ... |
|  | while ( 1 ) { |
|  |  ... |
|  | yy\_match: |
|  | do { |
|  | register YY\_CHAR yy\_c = yy\_ec[YY\_SC\_TO\_UI(*yy\_cp)]; |
|  | if ( yy\_accept[yy\_current\_state] ) { |
|  |  (yy\_last\_accepting\_state) = yy\_current\_state; |
|  |  (yy\_last\_accepting\_cpos) = yy\_cp; |
|  |  } |
|  | while ( yy\_chk[yy\_base[yy\_current\_state] + yy\_c] != yy\_current\_state ) { |
|  |  yy\_current\_state = (int) yy\_def[yy\_current\_state]; |
|  | if ( yy\_current\_state >= 30 ) |
|  |  yy\_c = yy\_meta[(unsigned int) yy\_c]; |
|  |  } |
|  |  yy\_current\_state = yy\_nxt[yy\_base[yy\_current\_state] + (unsigned int) yy\_c]; |
|  |  ++yy\_cp; |
|  |  } while ( yy\_base[yy\_current\_state] != 37 ); |
|  |  ... |
|  |  |
|  | do\_action: |
|  | switch ( yy\_act ) |
|  | case 0: |
|  |  ... |
|  |  |
|  | case 1: |
|  | YY\_RULE\_SETUP |
|  | printf("PACKAGE "); |
|  |  YY\_BREAK |
|  |  ... |
|  | } |


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
32
33
34
35
36
37
38
39

lex.yy.c的前600行基本是宏和函数的声明和定义。后面的代码大都是yylex这个函数服务的。
这个函数使用有限自动机 Deterministic Finite Automaton\DFA.的程序结构来分析输入的字符流。
lex.yy.c编译成二进制可执行文件，就是词法分析器。
把GO语言代码作为输入传递到词法分析器中。会生成如下内容。

|  | $ cc lex.yy.c -o simplego -ll |
|  | $ cat main.go | ./simplego |
|  |  |
|  | PACKAGE IDENT |
|  |  |
|  | IMPORT LPAREN |
|  |  QUOTE IDENT QUOTE |
|  | RPAREN |
|  |  |
|  | IDENT IDENT LPAREN RPAREN LBRACE |
|  |  IDENT DOT IDENT LPAREN QUOTE IDENT QUOTE RPAREN |
|  | RBRACE |


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

lex生成的词法分析器lexer通过正则匹配的方式将机器原本很难理解的字符串分解成很多的Token. 有利于后面的处理。
从.l文件到二进制如下。

GO语言的词法解析是通过scanner.go文件中的syntax.scanner结构体实现的。

|  | type scanner struct { |
|  |  source |
|  |  mode uint |
|  |  nlsemi bool |
|  |  |
|  | // current token, valid after calling next() |
|  |  line, col uint |
|  |  blank bool // line is blank up to col |
|  |  tok token |
|  |  lit string // valid if tok is \_Name, \_Literal, or \_Semi ("semicolon", "newline", or "EOF"); may be malformed if bad is true |
|  |  bad bool // valid if tok is \_Literal, true if a syntax error occurred, lit may be malformed |
|  |  kind LitKind // valid if tok is \_Literal |
|  |  op Operator // valid if tok is \_Operator, \_AssignOp, or \_IncOp |
|  |  prec int // valid if tok is \_Operator, \_AssignOp, or \_IncOp |
|  | } |


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

tokens.go定义了go语言中支持的全部Token类。
例如操作符、括号和关键字等。

|  | const ( |
|  |  \_ token = iota |
|  |  \_EOF // EOF |
|  |  |
|  | // operators and operations |
|  |  \_Operator // op |
|  |  ... |
|  |  |
|  | // delimiters |
|  |  \_Lparen // ( |
|  |  \_Lbrack // [ |
|  |  ... |
|  |  |
|  | // keywords |
|  |  \_Break // break |
|  |  ... |
|  |  \_Type // type |
|  |  \_Var // var |
|  |  |
|  |  tokenCount // |
|  | ) |


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

语言中的元素分成几个不同的类型，分别是名称和字面量、操作符、分割符、关键字。

语法分析

根据某种特定的形式文法Grammar.对Token序列构成的输入文本进行分析并确定其语法结构的过程。

• 文法
  上下文无关文法 是用来形式化、精确描述某种编程语言的工具。
  通过文法定义一种语言的语法。包含一系列用于转换字符串的生产规则 Production Rule.
  上下文无关文法中的每一个生产规则 都会将 规则左侧的非终结符 转换成 右侧的字符串。

终结符是文法中无法再被展开的符号。比如： ‘id’、 123
文法都由以下四个部分组成

1. N 有限个非终结符的集合。
   2）Σ 有限个终结符的集合
   3）P 有限个生产规则12的集合；
   4）S 非终结符集合中唯一的开始符号；
   文法被定义成一个四元组 (N,Σ,P,S)
   S→aSb
   S→ab
   S→ϵ
   上述规则构成的文法就能够表示 ab、aabb 以及 aaa…bbb 等字符串，编程语言的文法就是由这一系列的生产规则表示的

|  | SourceFile = PackageClause ";" { ImportDecl ";" } { TopLevelDecl ";" } . |
|  | PackageClause = "package" PackageName . |
|  | PackageName = identifier . |
|  |  |
|  | ImportDecl = "import" ( ImportSpec | "(" { ImportSpec ";" } ")" ) . |
|  | ImportSpec = [ "." | PackageName ] ImportPath . |
|  | ImportPath = string\_lit . |
|  |  |
|  | TopLevelDecl = Declaration | FunctionDecl | MethodDecl . |
|  | Declaration = ConstDecl | TypeDecl | VarDecl . |


1
2
3
4
5
6
7
8
9
10
11
12
13
14

每个Go语言代码文件最终都会被解析成一个独立的抽象语法树。所以语法树最顶层的结构或者开始符号都是SourceFile:

|  | SourceFile = PackageClause ";" { ImportDecl ";" } { TopLevelDecl ";" } . |


1
2
3
4
5

每一个文件都包含一个package的定义 以及可选的 import。 和 其他的顶层声明 TopLevelDecl。

每一个sourceFile在编译器中都对应一个syntax.File结构体

|  | type File struct { |
|  | Pragma Pragma |
|  | PkgName *Name |
|  | DeclList []Decl |
|  | Lines uint |
|  | node |
|  | } |


1
2
3
4
5
6
7
8
9
10
11

顶层声明有5大类型：分别是常量、类型、变量、函数和方法

• 分析方法
  1）自定向下分析：
  2）自底向上分析

类型检查

得到抽象语法树之后开始类型检查。
术语：强类型、弱类型、静态类型、动态类型、编译、解释

• 强类型定义：在编译期间会有严格的类型限制。编译器会在编译期间发生变量复制、返回值和函数调用时的类型错误。
• 弱类型定义：类型错误可能出现在运行时 进行隐式的类型转换，
  java在编译期间进行类型检查的编程语言是强类型的
  GO语言一样。
  类型的转换是显示的还是隐式的
  编译器会帮助我们推断类型变量吗。
• 静态类型 检查
  对源代码的分析来确定 运行程序 类型安全的过程。能够减少程序在运行时的类型检查。可以看作是代码优化的方式
  静态类型检查能够帮助我们在编译期间发现程序中出现的类型错误。
  一些动态类型的编程语言都会为这些编程语言加入静态类型检查。 javascript的Flow.
• 动态类型 检查
  运行时确定类型安全的过程。
  只使用动态类型检查的编程语言叫做动态类型编程于洋。 js ruby php.
  静态和动态类型检查不是完全冲突和对立的。

Java 不仅在编译期间提前检查类型发现类型错误，还为对象添加了类型信息，在运行时使用反射根据对象的类型动态地执行方法增强灵活性并减少冗余代码。

执行过程

GO编译器 不仅使用静态类型检查来保证程序运行的类型安全，还会在编程期间引入类型信息，能够使用反射来判断参数和变量的类型。
gc.Main函数

|  | for i := 0; i < len(xtop); i++ { |
|  |  n := xtop[i] |
|  | if op := n.Op; op != ODCL && op != OAS && op != OAS2 && (op != ODCLTYPE || !n.Left.Name.Param.Alias) { |
|  |  xtop[i] = typecheck(n, ctxStmt) |
|  |  } |
|  |  } |
|  |  |
|  | for i := 0; i < len(xtop); i++ { |
|  |  n := xtop[i] |
|  | if op := n.Op; op == ODCL || op == OAS || op == OAS2 || op == ODCLTYPE && n.Left.Name.Param.Alias { |
|  |  xtop[i] = typecheck(n, ctxStmt) |
|  |  } |
|  |  } |
|  |  |
|  |  ... |
|  |  |
|  |  checkMapKeys() |


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

这段代码分为俩部分。
gc.typecheck()函数检查常量、类型函数声明以及变量赋值语句的类型。
gc.checkMapKeys()检查哈希中键的类型。
cmd/compile/internal/gc.typecheck1 根据传入节点 Op 的类型进入不同的分支，其中包括加减乘数等操作符、函数调用、方法调用等 150 多种，因为节点的种类很多，所以这里只节选几个典型案例深入分析。

|  | func typecheck1(n *Node, top int) (res *Node) { |
|  | switch n.Op { |
|  | case OTARRAY: |
|  |  ... |
|  |  |
|  | case OTMAP: |
|  |  ... |
|  |  |
|  | case OTCHAN: |
|  |  ... |
|  |  } |
|  |  |
|  |  ... |
|  |  |
|  | return n |
|  | } |


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

• 切片 OTARRATY

如果当前节点的操作类型是OTARRAY.那么这个分支首先会对右节点，进行类型检查。

|  | case OTARRAY: |
|  |  r := typecheck(n.Right, Etype) |
|  | if r.Type == nil { |
|  |  n.Type = nil |
|  | return n |
|  |  } |


1
2
3
4
5
6
7
8
9
10

然后根据当前节点的左节点不容。分三种 [] int、 […] int 、[3] int

第一种直接调用 types.NewSlice,直接返回了一个 TSLICE 类型的结构体.元素的类型信息也会存储在结构体总。

|  | if n.Left == nil { |
|  |  t = types.NewSlice(r.Type) |


1
2
3
4
5
6

第二种会调用gc.typecheckcomplit处理。

|  | func typecheckcomplit(n *Node) (res *Node) { |
|  | ... |
|  | if n.Right.Op == OTARRAY && n.Right.Left != nil && n.Right.Left.Op == ODDD { |
|  |  n.Right.Right = typecheck(n.Right.Right, ctxType) |
|  | if n.Right.Right.Type == nil { |
|  |  n.Type = nil |
|  | return n |
|  |  } |
|  |  elemType := n.Right.Right.Type |
|  |  |
|  |  length := typecheckarraylit(elemType, -1, n.List.Slice(), "array literal") |
|  |  |
|  |  n.Op = OARRAYLIT |
|  |  n.Type = types.NewArray(elemType, length) |
|  |  n.Right = nil |
|  | return n |
|  |  } |
|  | ... |
|  | } |


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

第三种。调用type.NewArray初始化一个存储着数组中元素类型和数组大小的结构体。

|  | } else { |
|  |  n.Left = indexlit(typecheck(n.Left, ctxExpr)) |
|  |  l := n.Left |
|  |  v := l.Val() |
|  |  bound := v.U.(*Mpint).Int64() |
|  |  t = types.NewArray(r.Type, bound) } |
|  |  |
|  |  n.Op = OTYPE |
|  |  n.Type = t |
|  |  n.Left = nil |
|  |  n.Right = nil |


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

• 哈希 OTMAP
  如果处理的节点是哈希，那么编译器会分别检查哈希的键值类型以验证它们类型的合法性：

|  | case OTMAP: |
|  |  n.Left = typecheck(n.Left, Etype) |
|  |  n.Right = typecheck(n.Right, Etype) |
|  |  l := n.Left |
|  |  r := n.Right |
|  |  n.Op = OTYPE |
|  |  n.Type = types.NewMap(l.Type, r.Type) |
|  |  mapqueue = append(mapqueue, n) |
|  |  n.Left = nil |
|  |  n.Right = nil |


1
2
3
4
5
6
7
8
9
10
11
12
13
14

中间代码生成

经过词法与语法分析和类型检查俩个部分之后，AST已经不存在语法错误了。
编译器的后端工作–中间代码生成。

中间代码

中间代码是编译器或虚拟机使用的语言。可以来帮助我们分析计算机程序。
编译器在将源代码转换到机器码的过程中，先把源代码换成一种中间的表示形式。 即中间代码。

很多编译器需要将源代码翻译成多种机器码，直接翻译高级编程语言相对比较困难。拆成中间代码生成和机器码生成。
中间代码是更接近机器语言的表示形式。
cmd/compile/internal/gc.funccompile 编译函数

|  | func Main(archInit func(*Arch)) { |
|  |  ... |
|  |  |
|  | initssaconfig() |
|  |  |
|  |  for i := 0; i < len(xtop); i++ { |
|  |  n := xtop[i] |
|  |  if n.Op == ODCLFUNC { |
|  | funccompile(n) |
|  |  } |
|  |  } |
|  |  |
|  | compileFunctions() |
|  | } |


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

配置初始化和函数编译俩部分。

配置初始化

SSA配置的初始化过程是中间代码生成之前的准备工作，会缓存可能用到的类型指针、初始化SSA配置和一些之后会调用的运行时函数。

|  | func initssaconfig() { |
|  |  types\_ := ssa.NewTypes() |
|  |  |
|  |  \_ = types.NewPtr(types.Types[TINTER]) // *interface{} |
|  |  \_ = types.NewPtr(types.NewPtr(types.Types[TSTRING])) // **string |
|  |  \_ = types.NewPtr(types.NewPtr(types.Idealstring)) // **string |
|  |  \_ = types.NewPtr(types.NewSlice(types.Types[TINTER])) // *[]interface{} |
|  |  .. |
|  |  \_ = types.NewPtr(types.Errortype) // *error |


1
2
3
4
5
6
7
8
9
10
11
12
13

这个函数分为三部分
1）调用ssa.NewTypes()初始化ssa.Types结构体。并调用types.NewPtr函数缓存类型的信息。比如Bool Int8 String等。

types.NewPtr函数的主要作用是根据类型生成指向这些类型的指针。同时会根据编译器的配置将 生成的指针类型缓存在当前类型中。优化类型指针的获取效率。

|  | func NewPtr(elem *Type) *Type { |
|  |  if t := elem.Cache.ptr; t != nil { |
|  |  if t.Elem() != elem { |
|  |  Fatalf("NewPtr: elem mismatch") |
|  |  } |
|  |  return t |
|  |  } |
|  |  |
|  | t := New(TPTR) |
|  | t.Extra = Ptr{Elem: elem} |
|  | t.Width = int64(Widthptr) |
|  | t.Align = uint8(Widthptr) |
|  |  if NewPtrCacheEnabled { |
|  |  elem.Cache.ptr = t |
|  |  } |
|  |  return t |
|  | } |


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

2. 根据当前的CPU架构初始化SSA配置。

|  | ssaConfig = ssa.NewConfig(thearch.LinkArch.Name, *types\_, Ctxt, Debug['N'] == 0) |


1
2
3
4
5

输入参数：CPU架构、ssa.Types结构体、上下文信息、Debug配置。
生成中间代码和机器码的函数。当前编译器使用的指针、寄存器大小、可用寄存器列表、掩码等编译选项

|  | func NewConfig(arch string, types Types, ctxt *obj.Link, optimize bool) *Config { |
|  |  c := &Config{arch: arch, Types: types} |
|  |  c.useAvg = true |
|  |  c.useHmul = true |
|  | switch arch { |
|  | case "amd64": |
|  |  c.PtrSize = 8 |
|  |  c.RegSize = 8 |
|  |  c.lowerBlock = rewriteBlockAMD64 |
|  |  c.lowerValue = rewriteValueAMD64 |
|  |  c.registers = registersAMD64[:] |
|  |  ... |
|  | case "arm64": |
|  |  ... |
|  | case "wasm": |
|  | default: |
|  |  ctxt.Diag("arch %s not implemented", arch) |
|  |  } |
|  |  c.ctxt = ctxt |
|  |  c.optimize = optimize |
|  |  |
|  |  ... |
|  | return c |
|  | } |


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

配置一旦创建，整个编译期间都是只读的。并且被全部编译阶段共享。
3）最后，会初始化 一些编译器可能用到的Go语言运行时函数

|  |  assertE2I = sysfunc("assertE2I") |
|  |  assertE2I2 = sysfunc("assertE2I2") |
|  |  assertI2I = sysfunc("assertI2I") |
|  |  assertI2I2 = sysfunc("assertI2I2") |
|  |  deferproc = sysfunc("deferproc") |
|  |  Deferreturn = sysfunc("deferreturn") |
|  |  ... |


1
2
3
4
5
6
7
8
9
10
11

遍历和替换

在生成中间代码之前，编译器还需要替换AST中节点的一些元素。go.walk等函数实现。

|  | func walk(fn *Node) |
|  | func walkappend(n *Node, init *Nodes, dst *Node) *Node |
|  | ... |
|  | func walkrange(n *Node) *Node |
|  | func walkselect(sel *Node) |
|  | func walkselectcases(cases *Nodes) []*Node |
|  | func walkstmt(n *Node) *Node |
|  | func walkstmtlist(s []*Node) |
|  | func walkswitch(sw *Node) |


1
2
3
4
5
6
7
8
9
10
11
12
13

这些用于遍历抽象语法树的函数会将一些关键字和内建函数转换成函数调用
例如： 上述函数会将 panic、recover 两个内建函数转换成 runtime.gopanic 和 runtime.gorecover 两个真正运行时函数，而关键字 new 也会被转换成调用 runtime.newobject 函数。

编译器会将Go语言关键字转换成运行时包中的函数，

SSA生成

经过walk函数处理之后，AST就不会再变了。会使用gc.compileSSA将抽象语法树转换成中间代码。

|  | func compileSSA(fn *Node, worker int) { |
|  |  f := buildssa(fn, worker) # 负责生成具有SSA特色的中间代码 |
|  |  pp := newProgs(fn, worker) |
|  | genssa(f, pp) |
|  |  |
|  |  pp.Flush() |
|  | } |


1
2
3
4
5
6
7
8
9
10
11

中间代码的生成过程是从 AST 抽象语法树到 SSA 中间代码的转换过程，在这期间会对语法树中的关键字再进行改写，改写后的语法树会经过多轮处理转变成最后的 SSA 中间代码，相关代码中包括了大量 switch 语句、复杂的函数和调用栈

机器码生成

编译的最后一个阶段是根据SSA中间代码生成机器码，这里的机器码是在目标CPU架构上能够运行的二进制代码。
中间代码的降级Lower过程。在降级过程中，编译器将一些值重写成了目标CPU架构的特定值。

指令集架构

指令集架构是 计算机的抽象模型。它是计算机软件和硬件之间的接口和桥梁。

每一个指令集架构都定义了 支持 的数据结构、寄存器、管理主内存的硬件支持（内存一致、地址模型、虚拟内存）、支持的指令集合IO模型。
让同一个二进制文件能够在不同版本的硬件上运行。

机器码生成

俩部分协同工作
1）负责SSA中间代码降级和根据目标架构进行特定处理的ssa包
2）负责生成机器码的obj.

• SSA 降级
  SSA 降级是在中间代码生成的过程中完成的,其中将近 50 轮处理的过程中，lower 以及后面的阶段都属于 SSA 降级这一过程，这么多轮的处理会将 SSA 转换成机器特定的操作

和汇编代码非常相似。

汇编器 #
汇编器是将汇编语言翻译为机器语言的程序，Go 语言的汇编器是基于 Plan 9 汇编器的输入类型设计的，

数据结构

数组

数组和切片是Go语音中常见的数据结构
数组是由相同类型元素的集合组成的数据结构。会为数组分配一块连续的内存来保存其中的元素。
常见是一维的。多维的在数值和图形领域

俩个维度来描述数组，
1） 数组中存储的元素类型
2） 数组最大能存储的元素个数

|  | [10] int |
|  | [200] interface{} |


1
2
3
4
5
6

Go语言数组在初始化之后，大小就无法改变。存储元素类型相同、大小一致才是同一类型的数组

|  | func NewArray(elem *Type, bound int64) *Type { |
|  |  if bound < 0 { |
|  |  Fatalf("NewArray: invalid bound %v", bound) |
|  |  } |
|  | t := New(TARRAY) |
|  | t.Extra = &Array{Elem: elem, Bound: bound} |
|  | t.SetNotInHeap(elem.NotInHeap()) |
|  |  return t |
|  | } |


1
2
3
4
5
6
7
8
9
10
11
12
13

编译期间的数组类型是types.NewArray函数生成的。elem是元素类型，bound是数组大小。
当前数组是否应该在堆栈中初始化在编译期间就确定了

初始化

俩种不同的创建方式

|  | arr1 := [3] int{1,2,3} # 显示指定数组大小 |
|  | arr2 = [...] int{1,2,3} # 声明数组，在编译期推导数组的大小 |


1
2
3
4
5
6

编译器的推导过程

• 上限推导
  俩种不同的声明方式会做出不同的处理
  [10]T 这种。变量类型在进行到类型检查就会被提取出来。随后使用types.NewArray创建 包含数组大小的types.Array结构体
  […]T这种。会在gc.typecheckcomplit函数中对该数组的大小进行推导。

|  | func typecheckcomplit(n *Node) (res *Node) { |
|  | ... |
|  | if n.Right.Op == OTARRAY && n.Right.Left != nil && n.Right.Left.Op == ODDD { |
|  |  n.Right.Right = typecheck(n.Right.Right, ctxType) |
|  | if n.Right.Right.Type == nil { |
|  |  n.Type = nil |
|  | return n |
|  |  } |
|  |  elemType := n.Right.Right.Type |
|  |  |
|  |  length := typecheckarraylit(elemType, -1, n.List.Slice(), "array literal") |
|  |  |
|  |  n.Op = OARRAYLIT |
|  |  n.Type = types.NewArray(elemType, length) |
|  |  n.Right = nil |
|  | return n |
|  |  } |
|  | ... |
|  |  |
|  | switch t.Etype { |
|  | case TARRAY: |
|  |  typecheckarraylit(t.Elem(), t.NumElem(), n.List.Slice(), "array literal") # 遍历计算 |
|  |  n.Op = OARRAYLIT |
|  |  n.Right = nil |
|  |  } |
|  | } |


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

调用typecheckarryalit通过遍历元素的方式来计算数组中元素的数量

• 语句转换
  由一个字面量组成的数组，根据数组元素数量的不同。编译器会在负责初始化字面量的gc.anylit函数中做俩种不同的优化

1）当元素数量<= 4 ，会直接将数组中的元素放置在栈上
2）>4 ,会将数组中的元素放置到静态区，并在运行时 取出

访问和赋值

无论是在栈上，还是静态存储区。 数组在内存中都是一连串的内存空间。
指向数组开头的指针、元素的数量、元素类型占的空间大小 三个 维度来表示一个数组。
数组访问越界是非常严重的错误，Go 语言中可以在编译期间的静态类型检查判断数组越界。

数组和字符串的一些简单越界错误都会在编译期间发现。
比如：直接使用整数或者常量访问数组，但是使用变量去访问数组或字符串时，就无法提前发现错误。
需要go语言在运行时阻止不合法的访问

|  | arr[4]: invalid array index 4 (out of bounds for 3-element array) |
|  | arr[i]: panic: runtime error: index out of range [4] with length 3 |


1
2
3
4
5
6

越界操作会由运行时的runtime.panicIndex和runtime.goPanicIndex触发程序的运行时错误，并导致程序崩溃退出

|  | TEXT runtime·panicIndex(SB),NOSPLIT,$0-8 |
|  |  MOVL AX, x+0(FP) |
|  |  MOVL CX, y+4(FP) |
|  |  JMP runtime·goPanicIndex(SB) |
|  |  |
|  | func goPanicIndex(x int, y int) { |
|  | panicCheck1(getcallerpc(), "index out of range") |
|  | panic(boundsError{x: int64(x), signed: true, y: y, code: boundsIndex}) |
|  | } |


1
2
3
4
5
6
7
8
9
10
11
12
13

当数组的访问操作，OINDEX 成功通过编译器检查后，会被转换成几个SSA指令，

|  | package check |
|  |  |
|  | func outOfRange() int { |
|  |  arr := [3]int{1, 2, 3} |
|  |  i := 4 |
|  |  elem := arr[i] |
|  | return elem |
|  | } |
|  |  |
|  | $ GOSSAFUNC=outOfRange go build array.go |
|  | dumped SSA to ./ssa.html |


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

start阶段生成的SSA代码就是优化之前的第一版中间代码。
elem := arr[i]中间代码如下

|  | b1: |
|  |  ... |
|  |  v22 (6) = LocalAddr <*[3]int> {arr} v2 v20 |
|  | v23 (6) = IsInBounds  v21 v11 |
|  | If v23 → b2 b3 (likely) (6) |
|  |  |
|  | b2: ← b1- |
|  |  v26 (6) = PtrIndex <*int> v22 v21 |
|  | v27 (6) = Copy  v20 |
|  | v28 (6) = Load  v26 v27 (elem[int]) |
|  |  ... |
|  | Ret v30 (+7) |
|  |  |
|  | b3: ← b1- |
|  |  v24 (6) = Copy  v20 |
|  | v25 (6) = PanicBounds  [0] v21 v11 v24 |
|  | Exit v25 (6) |


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

对数组访问操作生成了判断数组上限的指令 IsInBounds 以及当条件不满足时，触发程序崩溃的PanicBounds指令。

编译器会将PanicBounds指令转换成runtime.panicIndex函数。当数组下标没有越界时，编译器会先获取数组的内存地址和访问的下标。利用PtrIndex计算出目标元素的地址。最后使用Load操作将指针中的元素加载到内存中。

编译器无法判断下标是否越界，会将PanicBounds指令交给运行时进行判断。
改成整数访问，中间代码如下

|  | b1: |
|  |  ... |
|  |  v21 (5) = LocalAddr <*[3]int> {arr} v2 v20 |
|  | v22 (5) = PtrIndex <*int> v21 v14 |
|  | v23 (5) = Load  v22 v20 (elem[int]) |
|  |  ... |


1
2
3
4
5
6
7
8
9
10

赋值的过程中会先确定目标数组的地址，再通过 PtrIndex 获取目标元素的地址，最后使用 Store 指令将数据存入地址中，从上面的这些 SSA 代码中我们可以看出 数组寻址和赋值都是在编译阶段完成的，没有运行时的参与。

|  | b1: |
|  |  ... |
|  |  v21 (5) = LocalAddr <*[3]int> {arr} v2 v19 |
|  | v22 (5) = PtrIndex <*int> v21 v13 |
|  | v23 (5) = Store  {int} v22 v20 v19 |
|  |  ... |


1
2
3
4
5
6
7
8
9
10

切片

数组在go语言中没那么常用，更常用的数据结构是切片， 即动态数组，长度不固定，可以向切片中追加元素。它会在容量不足时自动扩容。

声明方式不需要指定切片中的元素个数，只需要指定元素类型

|  | [] int |
|  | [] interface{}  |


1
2
3
4
5
6

编译期生成类型只包含切片中的元素类型。

|  | func NewSlice(elem *Type) *Type { |
|  |  if t := elem.Cache.slice; t != nil { |
|  |  if t.Elem() != elem { |
|  |  Fatalf("elem mismatch") |
|  |  } |
|  |  return t |
|  |  } |
|  |  |
|  | t := New(TSLICE) |
|  | t.Extra = Slice{Elem: elem} |
|  |  elem.Cache.slice = t |
|  |  return t |
|  | } |


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

编译期间的切片是types.Slice类型的，运行时切片有reflect.SliceHeader结构体表示

|  | type SliceHeader struct { |
|  |  Data uintptr # 指向数组的指针 |
|  |  Len int # 当前切片的长度 |
|  |  Cap int # 当前切片的容量 |
|  | } |


1
2
3
4
5
6
7
8
9

Data是一片连续的内存空间。这片内存空间用于存储切片中的全部元素。
切片与数组的关系非常密切。切片引入了一个抽象层。提供了对数组中部分连续片段的引用。而作为数组的引用。我们可以在运行区间修改它的长度和范围。当切片底层数组长度不足时就会触发扩容，切片指向的数组可能会发生变化。但是上层感知不到。上层只与切片打交道。

切片初始化

|  | arr[0:3] or slice[0:3] # 通过下班获取一部分 |
|  | slice := [] int {1,2,3} # 字面量初始化 |
|  | slice := make([]int, 10) # make创建 |


1
2
3
4
5
6
7

• 使用下标
  最接近汇编语言的方式。转换成OpSliceMack操作。

|  | // ch03/op\_slice\_make.go |
|  | package opslicemake |
|  |  |
|  | func newSlice() []int { |
|  |  arr := [3]int{1, 2, 3} |
|  |  slice := arr[0:1] |
|  | return slice |
|  | } |


1
2
3
4
5
6
7
8
9
10
11
12

slice := arr[0:1] 对应如下的SSA中间代码

|  | v27 (+5) = SliceMake <[]int> v11 v14 v17 |
|  |  |
|  | name &arr[*[3]int]: v11 |
|  | name slice.ptr[*int]: v11 |
|  | name slice.len[int]: v14 |
|  | name slice.cap[int]: v17 |


1
2
3
4
5
6
7
8
9
10

SliceMake 操作接收四个参数： 元素类型、数组指针、切片大小、 容量。
下标初始化不会拷贝原数组或原切片中的数据，只会创建一个指向原数组的切片结构体。所以修改新切片的数据也会修改原切片。

• 字面量
  []int{1,2,3}, 编译期间会展开如下代码片段

|  | var vstat [3]int |
|  | vstat[0] = 1 |
|  | vstat[1] = 2 |
|  | vstat[2] = 3 |
|  | var vauto *[3]int = new([3]int) |
|  | *vauto = vstat |
|  | slice := vauto[:] |


1
2
3
4
5
6
7
8
9
10
11

1. 根据切片中的元素数量对底层数组的大小进行推断并创建一个数组
   2）将这些字面量元素存储到初始化数组中。
   3）创建一个同样指向【3】int类型的数组指针
   4）将静态存储区的数组vstat 复制给vauto指针所在的地址
   5）通过[:] 操作获取一个底层使用vauto的切片。

• 关键字
  slice := make([]int, 10)
  使用字面量创建切片，大部分工作在编译期间完成，使用make关键字创建切片时，很多工作需要运行时的参与。
  调用方法必须向make函数传入切片的大小以及可选的容量。gc.typecheck1函数会检验入参。检查len是否传入，还会保证cap一定大于或等于len.还会将OMAKE节点转换为OMAKESLICE。
  go.walker会依据来个条件转换OMAKESLICE类型的节点
  1.切片的大小和容量是否足够小
  2.切片是否发生了逃逸，最终在堆上初始化。
  当切片发生逃逸或者非常大时，运行时需要runtime.makeslice在堆上初始化切片。
  如果切片不会发生逃逸并且切片非常小的时候，make([] int, 3,4)会直接被转换成如下代码
  var arr [4]int n := arr[:3]
  创建切片的运行时函数runtime.makeslice

|  | func makeslice(et *\_type, len, cap int) unsafe.Pointer { |
|  |  mem, overflow := math.MulUintptr(et.size, uintptr(cap)) |
|  | if overflow || mem > maxAlloc || len < 0 || len > cap { |
|  |  mem, overflow := math.MulUintptr(et.size, uintptr(len)) |
|  | if overflow || mem > maxAlloc || len < 0 { |
|  |  panicmakeslicelen() |
|  |  } |
|  |  panicmakeslicecap() |
|  |  } |
|  |  |
|  | return mallocgc(mem, et, true) |
|  | } |


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

主要工作是计算切片占用的内存空间并在堆上申请一片连续的内存。
内存空间 = 切片中元素的大小 * 切片容量
虽然编译期间可以检查出很多错误，但是在创建切片的过程中如果发生了以下错误会直接触发运行时错误并崩溃。
1.内存空间的大小发生了溢出
2.申请的内存大于最大可分配的内存
3.传入的长度小于0 或者大于容量。
mallocgc是用于申请内存的函数，这个函数比较复杂，
如果遇到了较小的对象会直接初始化在Go语音调度器里面的P结构中。而大于32KB的对象会在堆上初始化，

访问元素

使用len和cap获取长度或者容量是切片最常见的操作。
对应俩个特殊操作 OLEN 和 OCAP.
SSA生成阶段会转换成OpSliceLen 和 OpSliceCap。可能会触发decompose builtin阶段的优化，len(slice) / cap(slice)在一些情况下会直接替换成切片的长度或者容量。不需要在运行时获取。

|  | (SlicePtr (SliceMake ptr \_ \_ )) -> ptr |
|  | (SliceLen (SliceMake \_ len \_)) -> len |
|  | (SliceCap (SliceMake \_ \_ cap)) -> cap |


1
2
3
4
5
6
7

除了获取切片的长度和容量之外，访问切片中元素使用的OINDEX操作也会在中间代码生成期间转换成对地址的直接访问.
切片操作基本都是在编译期间完成的。除了访问切片的长度、容量或者其中的元素之外。
编译期间会将包含range关键字的遍历转换成形式更简单的循环。

追加和扩容

使用append关键字向切片中追加元素。
中间代码生成阶段的gc.state.append方法会根据返回值是否会覆盖原变量，进入俩种流程。
如果append返回的新切片不需要赋值回原有的变量。进入如下

|  | // append(slice, 1, 2, 3) |
|  | ptr, len, cap := slice |
|  | newlen := len + 3 |
|  | if newlen > cap { |
|  |  ptr, len, cap = growslice(slice, newlen) |
|  |  newlen = len + 3 |
|  | } |
|  | *(ptr+len) = 1 |
|  | *(ptr+len+1) = 2 |
|  | *(ptr+len+2) = 3 |
|  | return makeslice(ptr, newlen, cap) |


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

如果追加后切片的大小大于容量，那么就会调用 growslice对切片进行扩容。然后依次将新的元素依次加入切片。

如果使用slice = append(slice，1,2,3)。那么append后的切片会覆盖原切片。

|  | // slice = append(slice, 1, 2, 3) |
|  | a := &slice |
|  | ptr, len, cap := slice |
|  | newlen := len + 3 |
|  | if uint(newlen) > uint(cap) { |
|  |  newptr, len, newcap = growslice(slice, newlen) |
|  |  vardef(a) |
|  |  *a.cap = newcap |
|  |  *a.ptr = newptr |
|  | } |
|  | newlen = len + 3 |
|  | *a.len = newlen |
|  | *(ptr+len) = 1 |
|  | *(ptr+len+1) = 2 |
|  | *(ptr+len+2) = 3 |


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

是否覆盖原变量的逻辑其实差不多。最大的区别在于得到的新切片是否会赋值回原变量。
如果我们选择覆盖原有的变量。就不需要担心切片发生拷贝影响性能。

切片容量不足的处理流程。growslice.
扩容是为切片分配新的内存空间并拷贝原始切片中元素的过程。

|  | func growslice(et *\_type, old slice, cap int) slice { |
|  |  newcap := old.cap |
|  |  doublecap := newcap + newcap |
|  | if cap > doublecap { |
|  |  newcap = cap |
|  |  } else { |
|  | if old.len < 1024 { |
|  |  newcap = doublecap |
|  |  } else { |
|  | for 0 < newcap && newcap < cap { |
|  |  newcap += newcap / 4 |
|  |  } |
|  | if newcap <= 0 { |
|  |  newcap = cap |
|  |  } |
|  |  } |
|  |  } |


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

根据不同的容量选择不同的策略
1.如果期望容量大于当前容量的俩倍，就会使用期望容量
2.如果当前切片的长度小于1024，就会将容量翻倍。
3.如果当前切片的长度大于1024，那么就增加25%的容量。

拷贝切片

copy(a,b)
gc.copyany分俩种情况进行处理。
如果当前copy不是在运行时调用的。直接替换成下面的代码

|  | n := len(a) |
|  | if n > len(b) { |
|  |  n = len(b) |
|  | } |
|  | if a.ptr != b.ptr { |
|  |  memmove(a.ptr, b.ptr, n*sizeof(elem(a)))  |
|  | } |


1
2
3
4
5
6
7
8
9
10
11

运行 时发生，调用runtime.slicecopy

|  | func slicecopy(to, fm slice, width uintptr) int { |
|  | if fm.len == 0 || to.len == 0 { |
|  | return 0 |
|  |  } |
|  |  n := fm.len |
|  | if to.len < n { |
|  |  n = to.len |
|  |  } |
|  | if width == 0 { |
|  | return n |
|  |  } |
|  |  ... |
|  |  |
|  |  size := uintptr(n) * width |
|  | if size == 1 { |
|  |  *(*byte)(to.array) = *(*byte)(fm.array) |
|  |  } else { |
|  |  memmove(to.array, fm.array, size) |
|  |  } |
|  | return n |
|  | } |


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

都通过runtime.memmove将整块内存的内容拷贝到目标的内存区域中：

哈希表

go语言的哈希的实现原理。
数组表示元素的序列。
哈希表示的是键值对之间的映射关系。

设计原理

O(1)的读写性能。
提供了键值之间的映射。想要实现一个性能优异的哈希表。需要注意俩个关键点—哈希函数和冲突解决方法

• 哈希函数

哈希函数的选择在很大程度上 能够决定哈希表的读写性能。
理想的情况下，哈希函数应该能够将不同键 映射到不同的索引上。这就要求 哈希函数的输出范围 > 输入范围
键的数量会远远大于映射的范围。理想情况很难存在。

比较实际的方式是让哈希函数的结果 尽可能的均匀分布。然后通过工程上的手段解决哈希碰撞的问题。
不均匀的哈希函数

• 冲突解决
  通常情况下，哈希函数的输入范围一定远远大于输出范围。
  所以一定会遇到冲突。冲突不一定是哈希完全相等。可能是部分相等。比如：前4个字节相同。
• 开放寻址法
  开放寻址法 是一种在哈希表中解决哈希碰撞的方法。核心思想是依次探测和比较数组中的元素以判断目标键值对 是否存在于哈希表中。
  底层数据结构必须是数组。数组长度有限。所以向哈希表写入（author, draven）会从如下的索引开始遍历
  index := hash('author') % array.len
  如果发生了冲突。会将键值对写入到下一个索引不为空的位置。
  
  读取数据
  
  开放地址法中对性能影响最大的是装载因子。它是数组中元素的数量与 数组大小的比值。随着装载因子的增加。线性探测的平均用时就会逐渐增加。会影响哈希表的读写性能。当装载率超过70%之后。哈希表的性能就会急剧下降。达到100%,就会完全失效。
• 拉链法
  拉链法是哈希表最常见的实现方法。 数据结构使用数组+链表。还会引入红黑树优化性能

哈希函数会选择一个桶，和开放地址法一样，就是对哈希返回的结果取模。
选择了2号桶后就可以遍历当前桶中的链表。在遍历链表的时候会遇到以下俩种情况
1.找到键相同的键值对- 更新值
2.没有找到-在链表末尾追加新的键值对
拉链法的装载因子
装载因子：= 元素数量 / 桶数量
当装载因子变大是，读写性能也就越差。

数据结构

go语言运行时同时使用了多个数据结构组合表示哈希表。runtime.hmap是最核心的结构体。

|  | type hmap struct { |
|  | count int # 当前哈希表中的元素数量 |
|  |  flags uint8 #  |
|  | B  uint8 # 表示当前哈希表持有的buckets 数量。 |
|  |  noverflow uint16 |
|  |  hash0 uint32 # 哈希的种子。为哈希函数的结果引入 随机性 |
|  |  |
|  | buckets  unsafe.Pointer |
|  |  oldbuckets unsafe.Pointer # 保存之前的buckets的字段 |
|  |  nevacuate uintptr |
|  |  |
|  | extra *mapextra |
|  | } |
|  |  |
|  | type mapextra struct { |
|  |  overflow *[]*bmap |
|  |  oldoverflow *[]*bmap |
|  |  nextOverflow *bmap |
|  | } |
|  |  |


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

每一个bmap都能够存储8个键值对。当哈希表中存储的数据过多。单个桶已经装满就会使用 extra.nextOverflow中桶存储移除的数据。
上述俩种不同的桶在内存中是连续存储的。分为正常桶（黄色桶）和溢出桶（绿色桶）
bmap，源代码中 只包含一个tophash字段。

|  | type bmap struct { |
|  |  tophash [bucketCnt]uint8 |
|  | } |


1
2
3
4
5
6
7

在运行期间不止包含tophash字段

|  | type bmap struct { |
|  |  topbits [8]uint8 |
|  |  keys [8]keytype |
|  |  values [8]valuetype |
|  |  pad uintptr |
|  |  overflow uintptr |
|  | } |


1
2
3
4
5
6
7
8
9
10
11

哈希表初始化

• 字面量
  key:value的语法来表示键值对

|  | hash := map[string]int{ |
|  | "1": 2, |
|  | "3": 4, |
|  | "5": 6, |
|  | } |


1
2
3
4
5
6
7
8
9

gc.maplit

|  | func maplit(n *Node, m *Node, init *Nodes) { |
|  |  a := nod(OMAKE, nil, nil) |
|  |  a.Esc = n.Esc |
|  |  a.List.Set2(typenod(n.Type), nodintconst(int64(n.List.Len()))) |
|  |  litas(m, a, init) |
|  |  |
|  |  entries := n.List.Slice() |
|  | if len(entries) > 25 { # 哈希表数量小于25个时，一次直接加入到哈希表中 |
|  |  ... |
|  | return |
|  |  } |
|  |  |
|  | // Build list of var[c] = expr. |
|  | // Use temporaries so that mapassign1 can have addressable key, elem. |
|  |  ... |
|  | } |


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

超过了25个，会创建俩个数组分别存储键值。会通过如下for循环加入哈希

|  | hash := make(map[string]int, 26) |
|  | vstatk := []string{"1", "2", "3", ... ， "26"} |
|  | vstatv := []int{1, 2, 3, ... , 26} |
|  | for i := 0; i < len(vstak); i++ { |
|  |  hash[vstatk[i]] = vstatv[i] |
|  | } |


1
2
3
4
5
6
7
8
9
10

• 运行时
  当创建的哈希表被分配到栈上，并且容量小于BUCKETSIZE = 8时，GO语言在编译阶段会使用如下方式快速初始化哈希。

|  | var h *hmap |
|  | var hv hmap |
|  | var bv bmap |
|  | h := &hv |
|  | b := &bv |
|  | h.buckets = b |
|  | h.hash0 = fashtrand0() |


1
2
3
4
5
6
7
8
9
10
11

读写操作

哈希表的访问一般都是通过下标或者遍历进行的。

|  | \_ = hash[key] |
|  |  |
|  | for k, v := range hash { |
|  | // k, v |
|  | } |


1
2
3
4
5
6
7
8
9

• 访问
  在编译类型检查期间，hash[key] 以及类似的 操作都会被转换成哈希的 OINDEXMAP操作。
  中间代码生成阶段会在gc.walkexpr 中间这些OINDEXMAP操作转换成如下代码

|  | v := hash[key] // => v := *mapaccess1(maptype, hash, &key) |
|  | v, ok := hash[key] // => v, ok := mapaccess2(maptype, hash, &key) |


1
2
3
4
5
6

runtime.mapaccess1 会先通过哈希表设置的哈希函数、、种子获取当前键对应的哈希。再通过bucketMask和add拿到该键值对所在的桶序号和哈希高位的8位数字。

小结

Go 语言使用拉链法来解决哈希碰撞的问题实现了哈希表，它的访问、写入和删除等操作都在编译期间转换成了运行时的函数或者方法。哈希在每一个桶中存储键对应哈希的前 8 位，当对哈希进行操作时，这些 tophash 就成为可以帮助哈希快速遍历桶中元素的缓存。

哈希表的每个桶都只能存储 8 个键值对，一旦当前哈希的某个桶超出 8 个，新的键值对就会存储到哈希的溢出桶中。随着键值对数量的增加，溢出桶的数量和哈希的装载因子也会逐渐升高，超过一定范围就会触发扩容，扩容会将桶的数量翻倍，元素再分配的过程也是在调用写操作时增量进行的，不会造成性能的瞬时巨大抖动。

字符串

如果是代码中存在的字符串，编译器会将其标记成只读数据SRODATA.

|  | $ cat main.go |
|  | package main |
|  |  |
|  | func main() { |
|  |  str := "hello" |
|  | println([]byte(str)) |
|  | } |
|  |  |
|  | $ GOOS=linux GOARCH=amd64 go tool compile -S main.go |
|  | ... |
|  | go.string."hello" SRODATA dupok size=5 # SRODATA标记 |
|  | 0x0000 68 65 6c 6c 6f hello |
|  | ... |


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

只读意味着字符串会被分配到只读的内存空间。
可以通过在string 和 []byte 类型之间反复转换实现修改。
1.先讲这段内存拷贝到堆或者栈上。
2.将变量的类型转换成[] byte后，并修改字节数据
3.将修改后的字节数组转回string.

字符串数据结构

|  | type StringHeader struct { |
|  |  Data uintptr # 指向字节数组的指针 |
|  |  Len int # 数组大小 |
|  | } |


1
2
3
4
5
6
7
8

与切片相比，只少了一个表示容量的Cap字段。字符串就是一个只读的切片类型。
所有在字符串上的写入操作都是通过拷贝实现的。

字符串 解析过程

解析器会在词法分析阶段解析字符串。会对源文件中的字符串进行切片和分组。将原有的字符流转换成Token序列。
俩种声明

|  | str1 := "this is a string" |
|  | str2 := `this is another |
|  | string` |


1
2
3
4
5
6
7

双引号和反引号。
双引号：只能用于单行字符串的初始化。如果内部出现双引号需要\符合转义。
反引号：可以摆脱单行的限制。双引号不再负责标记字符串的开始和结束。在遇到json或者其他复杂数据格式的场景下非常方便。

字符串拼接

+符号， 会将该符号对应的OADD节点转换为OADDSTR类型的节点。然后调用gc.addstr函数生成用于拼接字符串的代码

|  | func walkexpr(n *Node, init *Nodes) *Node { |
|  | switch n.Op { |
|  | ... |
|  | case OADDSTR: |
|  |  n = addstr(n, init) |
|  |  } |
|  | } |


1
2
3
4
5
6
7
8
9
10
11

类型转换

解析 和 序列化json等数据格式是，需要将数据在string和[]byte之间来回转换。
从字节数组到字符串的转换需要使用runtime.slicebytesostring函数。例如：string(bytes),
长度为0和长度为1 的字节数组，处理起来比较简单。

|  | func slicebytetostring(buf *tmpBuf, b []byte) (str string) { |
|  |  l := len(b) |
|  | if l == 0 { |
|  | return "" |
|  |  } |
|  | if l == 1 { |
|  |  stringStructOf(&str).str = unsafe.Pointer(&staticbytes[b[0]]) |
|  |  stringStructOf(&str).len = 1 |
|  | return |
|  |  } |
|  | var p unsafe.Pointer |
|  | if buf != nil && len(b) <= len(buf) { |
|  |  p = unsafe.Pointer(buf) |
|  |  } else { |
|  |  p = mallocgc(uintptr(len(b)), nil, false) |
|  |  } |
|  |  stringStructOf(&str).str = p |
|  |  stringStructOf(&str).len = len(b) |
|  |  memmove(p, (*(*slice)(unsafe.Pointer(&b))).array, uintptr(len(b))) |
|  | return |
|  | } |


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

处理过后会根据传入的缓冲区大小决定是否需要为新字符串分配一片内存空间。

字符串转换成[]byte类型时，需要使用runtime.stringtoslicebyte函数，

|  | func stringtoslicebyte(buf *tmpBuf, s string) []byte { |
|  | var b []byte |
|  | if buf != nil && len(s) <= len(buf) { |
|  |  *buf = tmpBuf{} |
|  |  b = buf[:len(s)] |
|  |  } else { |
|  |  b = rawbyteslice(len(s)) |
|  |  } |
|  | copy(b, s) |
|  | return b |
|  | } |


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

语言基础

函数调用

函数是go语言的一等公民。

调用惯例

somefunction(arg0,arg1)
调用惯例是调用方和被调用方对于参数和返回值传递的约定。

• C语言
  示例

|  | // ch04/my\_function.c |
|  | int my\_function(int arg1, int arg2) { |
|  | return arg1 + arg2; |
|  | } |
|  |  |
|  | int main() { |
|  | int i = my\_function(1, 2); |
|  | } |


1
2
3
4
5
6
7
8
9
10
11
12

编译成汇编

|  | main: |
|  |  pushq %rbp |
|  |  movq %rsp, %rbp |
|  |  subq $16, %rsp |
|  |  movl $2, %esi // 设置第二个参数 |
|  |  movl $1, %edi // 设置第一个参数 |
|  |  call my\_function |
|  |  movl %eax, -4(%rbp) |
|  | my\_function: |
|  |  pushq %rbp |
|  |  movq %rsp, %rbp |
|  |  movl %edi, -4(%rbp) // 取出第一个参数，放到栈上 |
|  |  movl %esi, -8(%rbp) // 取出第二个参数，放到栈上 |
|  |  movl -8(%rbp), %eax // eax = esi = 1 |
|  |  movl -4(%rbp), %edx // edx = edi = 2 |
|  |  addl %edx, %eax // eax = eax + edx = 1 + 2 = 3 |
|  |  popq %rbp |


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

调用过程：
1.调用方main函数将my_function的俩个参数分别存到edi和esi寄存器中。
2.在my_function调用时，它会将寄存器edi和esi中的数据存储到eax和edx俩个寄存器中。随后通过汇编指令addl 计算俩个入参之和。
3.在my_fuction调用后，使用寄存器eax 传奇返回值。然后存储到栈上的i变量中。

当my_function函数的入参增加至8个时。会得到不同的汇编代码。

|  | main: |
|  |  pushq %rbp |
|  |  movq %rsp, %rbp |
|  |  subq $16, %rsp // 为参数传递申请 16 字节的栈空间 |
|  |  movl $8, 8(%rsp) // 传递第 8 个参数 |
|  |  movl $7, (%rsp) // 传递第 7 个参数 |
|  |  movl $6, %r9d |
|  |  movl $5, %r8d |
|  |  movl $4, %ecx |
|  |  movl $3, %edx |
|  |  movl $2, %esi |
|  |  movl $1, %edi |
|  |  call my\_function |


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

前6个参数会使用edi、esi、edx、ecx、r8d\r9d 六个寄存器传递。
最后的俩个参数通过栈传递。

rbp寄存器会存储函数调用栈的基址指针。main函数的栈空间的其实地址。而另一个寄存器rsp存储的是main函数调用栈结束的位置。
这俩个寄存器共同表示了函数的栈空间。

在调用my_function之前。main函数通过sub1 $16，%rsp指令分配了16个字节的站地址。随后将第6个以上的参数按照从右到左的顺序存入栈中。余下的6个参数通过寄存器传递。

|  | my\_function: |
|  |  pushq %rbp |
|  |  movq %rsp, %rbp |
|  |  movl %edi, -4(%rbp) // rbp-4 = edi = 1 |
|  |  movl %esi, -8(%rbp) // rbp-8 = esi = 2 |
|  |  ... |
|  |  movl -8(%rbp), %eax // eax = 2 |
|  |  movl -4(%rbp), %edx // edx = 1 |
|  |  addl %eax, %edx // edx = eax + edx = 3 |
|  |  ... |
|  |  movl 16(%rbp), %eax // eax = 7 |
|  |  addl %eax, %edx // edx = eax + edx = 28 |
|  |  movl 24(%rbp), %eax // eax = 8 |
|  |  addl %edx, %eax // edx = eax + edx = 36 |
|  |  popq %rbp |


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

my_function会先将寄存器中的全部数据转移到栈上。然后利用eax寄存器计算所有入参的和并返回结果。
函数的返回值是通过eax寄存器进行传递的。由于只使用一个寄存器存储返回值。所以C语言的函数不能同时返回多个值。

• Go语言

|  | package main |
|  |  |
|  | func myFunction(a, b int) (int, int) { |
|  | return a + b, a - b |
|  | } |
|  |  |
|  | func main() { |
|  |  myFunction(66, 77) |
|  | } |


1
2
3
4
5
6
7
8
9
10
11
12
13

|  | "".main STEXT size=68 args=0x0 locals=0x28 |
|  | 0x0000 00000 (main.go:7) MOVQ (TLS), CX |
|  | 0x0009 00009 (main.go:7) CMPQ SP, 16(CX) |
|  | 0x000d 00013 (main.go:7) JLS 61 |
|  | 0x000f 00015 (main.go:7) SUBQ $40, SP // 分配 40 字节栈空间 |
|  | 0x0013 00019 (main.go:7) MOVQ BP, 32(SP) // 将基址指针存储到栈上 |
|  | 0x0018 00024 (main.go:7) LEAQ 32(SP), BP |
|  | 0x001d 00029 (main.go:8) MOVQ $66, (SP) // 第一个参数 |
|  | 0x0025 00037 (main.go:8) MOVQ $77, 8(SP) // 第二个参数 |
|  | 0x002e 00046 (main.go:8) CALL "".myFunction(SB) |
|  | 0x0033 00051 (main.go:9) MOVQ 32(SP), BP |
|  | 0x0038 00056 (main.go:9) ADDQ $40, SP |
|  | 0x003c 00060 (main.go:9) RET |


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

|  | "".myFunction STEXT nosplit size=49 args=0x20 locals=0x0 |
|  | 0x0000 00000 (main.go:3) MOVQ $0, "".~r2+24(SP) // 初始化第一个返回值 |
|  | 0x0009 00009 (main.go:3) MOVQ $0, "".~r3+32(SP) // 初始化第二个返回值 |
|  | 0x0012 00018 (main.go:4) MOVQ "".a+8(SP), AX // AX = 66 |
|  | 0x0017 00023 (main.go:4) ADDQ "".b+16(SP), AX // AX = AX + 77 = 143 |
|  | 0x001c 00028 (main.go:4) MOVQ AX, "".~r2+24(SP) // (24)SP = AX = 143 |
|  | 0x0021 00033 (main.go:4) MOVQ "".a+8(SP), AX // AX = 66 |
|  | 0x0026 00038 (main.go:4) SUBQ "".b+16(SP), AX // AX = AX - 77 = -11 |
|  | 0x002b 00043 (main.go:4) MOVQ AX, "".~r3+32(SP) // (32)SP = AX = -11 |
|  | 0x0030 00048 (main.go:4) RET |


1
2
3
4
5
6
7
8
9
10
11
12
13
14

Go语言使用栈传递参数和接收返回值。所以只需要在栈上多分配一些内存就可以返回多个值。

参数传递

值传递还是引用传递。

• 传值： 函数调用会对参数进行拷贝，被调用方和调用方俩者持有不相关的俩份数据
• 传引用：持有相同的数据
  不同的语言会选择不同的方式传递参数。GO语言选择了传值得方式。无论是基本类型、结构体、还是指针。都会对传递的参数进行拷贝。
• 整型和数组

整型变量i和数组arr.

|  | func myFunction(i int, arr [2]int) { |
|  |  fmt.Printf("in my\_funci
1
2
3