《深入解析Go》笔记

栏目: Go · 发布时间: 5年前

内容简介:在 GitHub 上找到一本解读 Go 实现细节的好书,名叫大致看了一遍,简单做了些笔记。这本书的代码来自 Go 1.3,所以还有一部分由 C 语言写成。

在 GitHub 上找到一本解读 Go 实现细节的好书,名叫 《深入解析 Go》

大致看了一遍,简单做了些笔记。

这本书的代码来自 Go 1.3,所以还有一部分由 C 语言写成。

这份笔记里的代码来自 Go 1.12.5,数据结构全部由 Go 语言实现。

数据结构

string 和 slice 都是引用类型,可能开在栈上,也可能开在堆上;

channel 和 map 是引用类型,但一定开在堆上,栈中只有指针。

string 底层结构

src/reflect/value.go

type StringHeader struct {
    Data uintptr
    Len  int
}

string 是不可变数据结构,任何对 string 的操作都会产生一个新的 string. 因此,需要拼接的时候尽量使用 bytes.Buffer ,或 strings.Join 这种用了 Buffer 的函数。

slice 底层结构

src/reflect/value.go

type SliceHeader struct {
    Data uintptr
    Len  int
    Cap  int
}

注意,两个数据结构的底层数据全部共享。

关于 slice 的扩容,可以参见 《深入解析 Go 中 Slice 底层实现》

有一个小用法:对切片做 slice 操作时,末位的下标可以超过原 slice 的 len,但不能超过 cap.

a := make([]int, 2, 10)
b := a[:5]

map 底层结构

src/runtime/map.go

type hmap struct {
    // Note: the format of the hmap is also encoded in cmd/compile/internal/gc/reflect.go.
    // Make sure this stays in sync with the compiler's definition.
    count     int // # live cells == size of map.  Must be first (used by len() builtin)
    flags     uint8
    B         uint8  // log_2 of # of buckets (can hold up to loadFactor * 2^B items)
    noverflow uint16 // approximate number of overflow buckets; see incrnoverflow for details
    hash0     uint32 // hash seed

    buckets    unsafe.Pointer // array of 2^B Buckets. may be nil if count==0.
    oldbuckets unsafe.Pointer // previous bucket array of half the size, non-nil only when growing
    nevacuate  uintptr        // progress counter for evacuation (buckets less than this have been evacuated)

    extra *mapextra // optional fields
}

type bmap struct {
    // tophash generally contains the top byte of the hash value
    // for each key in this bucket. If tophash[0] < minTopHash,
    // tophash[0] is a bucket evacuation state instead.
    // 用于 hash 的快速比较,当 hash 相等的时候还会跟原 key 进行一次匹配。
    tophash [bucketCnt]uint8
    // Followed by bucketCnt keys and then bucketCnt values.
    // NOTE: packing all the keys together and then all the values together makes the
    // code a bit more complicated than alternating key/value/key/value/... but it allows
    // us to eliminate padding which would be needed for, e.g., map[int64]int8.
    // Followed by an overflow pointer.
}

注意看上面的 NOTE 里的 KV 排列结构,这样做有利于内存对齐。

bmap 后面的内存分配未在结构体中定义,需要拿 KV 的时候要通过 unsafe.Pointer 根据 offset 去拿。

mapaccess1mapaccess2 .

哈希表在每次扩容时,容量会增大到原来的两倍,也就是从 2^B2^(B+1) 。为了保证运行效率,会将 key 的搬迁操作平摊到每一次写操作(insert & remove)上,每次操作时迁移 1-2 个键值对。查找时会先在 old—buckets 中找,找不到再去新的 buckets 中找。

map 使用快速的 murmurhash 作为哈希算法。

map 解决冲突的方法是链地址法的改进形式。

在创建 bmap 时,会分配一个数组,都可以容纳 8 个键值对。发生哈希冲突时,都会将新的键值对放入添加到数组里。如果数组放满了,则会新建一个 bmap ,通过 overflow 指针来链接到当前 bucket 节点后面。

关于查找、插入和删除的细节,请见 该书相关章节

一个需要注意的点:在 bmap 链中,相同的 Key 可能会存在于两个 bucket 里,而前面 bucket 的值会直接覆盖后面 bucket 的值。在进行更新操作时,如果前面 bucket 不存在该键,但是数组包含空位,则直接在该 bucket 中插入,而不会再去链表后面的 bucket 中查找并更新。查找操作亦然。 怎么说,这个机制有点像 docker 镜像中的不同层的文件覆盖机制。

channel

src/runtime/chan.go

type hchan struct {
    qcount   uint           // 环形队列的总数量
    dataqsiz uint           // 环形队列大小
    buf      unsafe.Pointer // 环形队列
    elemsize uint16
    closed   uint32
    elemtype *_type // 元素类型
    sendx    uint   // 缓存区的发送指针(也就是缓冲区尾)
    recvx    uint   // 缓冲区的接收索引(也就是缓冲区头)
    recvq    waitq  // 因接收而阻塞的等待队列
    sendq    waitq  // 因发送而阻塞的等待队列

    // lock protects all fields in hchan, as well as several
    // fields in sudogs blocked on this channel.
    //
    // Do not change another G's status while holding this lock
    // (in particular, do not ready a G), as this can deadlock
    // with stack shrinking.
    lock mutex
}
type waitq struct {
    first *sudog
    last  *sudog
}
type sudog struct {
    // The following fields are protected by the hchan.lock of the
    // channel this sudog is blocking on. shrinkstack depends on
    // this for sudogs involved in channel ops.

    g *g

    // isSelect indicates g is participating in a select, so
    // g.selectDone must be CAS'd to win the wake-up race.
    isSelect bool
    next     *sudog
    prev     *sudog
    elem     unsafe.Pointer // data element (may point to stack)
                            // 存储 goroutine 的

    // The following fields are never accessed concurrently.
    // For channels, waitlink is only accessed by g.
    // For semaphores, all fields (including the ones above)
    // are only accessed when holding a semaRoot lock.

    acquiretime int64
    releasetime int64
    ticket      uint32
    parent      *sudog // semaRoot binary tree
    waitlink    *sudog // g.waiting list or semaRoot
    waittail    *sudog // semaRoot
    c           *hchan // channel
}

以前 channel 的缓冲区会在 hchan 之后的内存中创建,现在将它们分开了。

对 channel 进行读写操作的时候,会根据缓冲区的状态、以及读 / 写链表来决定是否要阻塞当前 goroutine,阻塞的话会将当前的 G 挂载链表中。

interface

// 带方法的接口
type iface struct {
    tab  *itab
    data unsafe.Pointer
}

type itab struct {
    inter *interfacetype
    _type *_type
    hash  uint32 // copy of _type.hash. Used for type switches.
    _     [4]byte
    fun   [1]uintptr // variable sized. fun[0]==0 means _type does not implement inter.
}
// fun 中会保存接口值背后具体类型的方法

// 空接口
type eface struct {
    _type *_type
    data  unsafe.Pointer
}

TypeUncommonType 会记录某个 具体类型 实现的方法;

interfaceItabInterfaceType 中的方法表,记录了接口所声明的方法;

itabfun 数组,记录了具体的函数指针,用作接口值的方法缓存。

在接口值赋值时,会将 UncommonTypeInterfaceType 中的方法表进行比对;如果比对成功的话,会将 UncommonType 中的方法指针拷贝到 itabfun 中,方便方法调用时对方法进行查找。

方法调用

a.F(b) 会在编译时直接转换为 A.F(a, b)

当一个类型被匿名嵌入结构体时,它的方法会被拷贝到嵌入结构体的 Type 的方法表中。这个过程在编译时就可以完成。

接口的方法调用要通过 itab.fun 中的函数指针来确定具体调用的方法。方法拷贝的过程是在运行时完成的,所以接口的方法调用的成本要略高于一般方法调用。

函数调用协议

Go 把返回值放在上一个栈帧最后的内存中,这样调用链前后的两个函数都可以触及到这段内存,以此来实现多值返回。

返回值2
返回值1
参数3
参数2
参数1 <- SP

go 关键字是个语法糖, go f(args) 可以看做 runtine.newproc(size, f, args)

同样 defer 也是语法糖,通过 runtine.deferprocruntine.deferreturn 来实现。

连续栈

一个程序中可能会有非常多的 goroutine,为了节省内存,每个 goroutine 一开始只会得到非常小的一块栈。

使用可变栈时,每次函数调用时,都会通过 SP 和 stackguard 检查栈的使用情况。

当栈不够大时,会进行栈扩张,开一块新栈,并把旧栈的内容复制过去。如果栈里有指针,而指针指向的是栈中的变量,那么在复制时会对指针的值加一个偏移,来保证指针指向的对象是被迁移过后的对象。

gc 时,如果检测到栈只用了不到 1/4 时,会将栈缩小为原来的 1/2.

闭包

Go 通过 escape analyze 来检查逃逸的值,从而确定该值是否应该在堆上创建,而不是在栈中。

func New() *T {
    var t T
    return &t
}

返回闭包时并不是单纯返回一个函数,而是返回了一个结构体,记录下函数返回地址和引用的环境中的变量地址。书中是有这样一个结构体的,但在我的源码里,这个数据结构应该是用汇编实现了。

Go 程序初始化

  • 系统初始化:初始化栈、设置本地线程存储(g)
  • 调度器初始化: runtime.schedinit
    根据 GOMAXPROCS 决定可用线程数;把 runtime.main 放入就绪线程队列;
    调用 runtime.mstartmstart 调用 schedule ,也就是一直运行的调度器。
  • schedule 选中 runtime.main
    • 通过 newm(sysmon, nil) 启动一个线程运行 sysmon ,用于处理网络 epoll
    • 通过 runtime.newproc 启动一个 G 执行 scavenger,用于垃圾回收
    • 调用 main.main 进入用户代码。

会单独启动一个线程(M)用于 poll() 。GC 都是 goroutine,这个任务的地位是高于 GC 的。

调度模型

Go 如何实现并发?

Go 通过 goroutine 和 channel 来实现 CSP 并发模型,从而实现并发。

  • goroutine 是 Go 语言中并发的执行单位。可以理解为轻量级的“线程”。
  • channel 是 Go 语言中各个并发结构体 (goroutine) 之前的通信机制。 通俗的讲,就是各个 goroutine 之间通信的“管道”,有点类似于 Linux 中的管道。

再深入一点,Go 线程模型的实现依靠 MPG 以及 Sched 结构体。

M 是 Machine,是对机器的抽象,一个 M 会关联一个物理线程;

P 是 Processor,代表 Go 代码执行是所需要的资源;

G 是 Goroutine,代表 Goroutine 的控制结构;

Sched 是调度实现中使用的数据结构。

多个 G 会以队列的形式挂靠在 P 上;当 G 与 M 绑定时,才能够执行 Go 代码。

调度时会采用抢占式调度模型以避免一个 goroutine 运行太长时间;某个 P 的队列变空时会从其它的 P 队列上偷 G,然后继续运行。

http://morsmachine.dk/go-scheduler

《深入解析Go》笔记

系统调用细节

当某个 goroutine 发起一次系统调用时,会调用 runtime.entersyscall

调度器会将 G 的状态设置为 Gsyscall 后放入就绪队列;

此时,p 会和 m 进行剥离,p 的状态被设为 Psyscall ,而 m 会去执行系统调用。

如果系统调用时非阻塞的,那么 m 会很快返回。返回时会调用 runtime.exitsyscall ,这个时候会去检查当前 m 的 P,如果 P 处于 Psyscall 且队列非空,则重新将 p 和 m 绑定,恢复 g 的状态为 Grunning ,继续运行。

如果 goroutine 发起的是阻塞的系统调用,则会调用 runtime.entersyscallblock

entersyscall 不同的是, entersyscallblock 会调用 releasephandoffp

releasep 将当前的 M 与 M 关联的 P 剥离,M 会负责去执行系统调用;

执行 handoffp 会让 P 尝试挂靠到其它空闲的 M 上继续执行。

如果 P 上没有 G 了,P 会被设置为 Pidle ;如果没有空闲的 M 了,则会调用 startm 来让 P 与新的 M 绑定后继续执行。

当系统调用完成时,要让发起调用的 G 来继续执行。这时 G 会去找可用的 P。如果当前不存在 Pidle 的 P,调度器将会把 G 变成 Grunnable ,将它挂到全局的就绪 G 队列中,然后停止当前 m 并调用 schedule 函数。

换句话说,block 的时候,可能 m 上的 P 会空闲,等 m 返回后还可以继续挂载执行,此时 M-P-G 的绑定原样恢复。整个逻辑就有点像非阻塞调用。如果 m 上的 P 去干别的了(比如又找了个新的 M 继续执行),那么当前 m 会将信息传递给 G,改变 G 的状态,然后 m 自己退出(因为所有的 P 都有 M 了)

内存管理

内存池

每个线程都会有自己的本地内存,当线程内存不够时会向全局分配链中申请内存。

Go 会为每个 M 在 MCache 中存储一些空闲的小内存块;作为备用分配存储。当 MCache 用完后,会从 MCentral 自由链拿 一些 对象进行补充; MCentral 为空时,又会从 Mheap 中拿一些对象进行补充。这样的多级批量补充机制减小了全局内存加锁的开销。

  • 当程序需要小对象(小于 32K)时,会直接从 MCache 中分配,对象被回收后控制内存返回给全局控制堆( MHeap );
    MCache 中分配避免了在全局控制堆上频繁加锁。
  • 当需要大对象时,会直接从全局控制堆上以页(4KB)为单位进行分配。因此大对象总是页对齐的。

垃圾回收

Go 语言使用标记清除算法来完成垃圾回收,整个回收过程会 stop the world.

标记阶段从 root 区域出发,扫描所有直接或间接引用的对象;清除阶段直接扫描堆区,对未被标记的对象进行回收。

由于标记过程是一个树形的操作,所以这个过程被并行化,以提升速度。

网络

Go 通过运行时层面对 epoll/kqueue 的封装来实现非阻塞 io.

封装层次:

net

runtime.main 启动时,会运行 newm(sysmon, nil) ,而 sysmon 就会每隔一段时间执行 runtime.epoll 。sysmon 的地位要比 gc 重要的多,而且会频繁执行,所以会单独为它分配一个系统线程(m)来运行。


以上所述就是小编给大家介绍的《《深入解析Go》笔记》,希望对大家有所帮助,如果大家有任何疑问请给我留言,小编会及时回复大家的。在此也非常感谢大家对 码农网 的支持!

查看所有标签

猜你喜欢:

本站部分资源来源于网络,本站转载出于传递更多信息之目的,版权归原作者或者来源机构所有,如转载稿涉及版权问题,请联系我们

Android开发艺术探索

Android开发艺术探索

任玉刚 / 电子工业出版社 / 2015-9-1 / CNY 79.00

《Android开发艺术探索》是一本Android进阶类书籍,采用理论、源码和实践相结合的方式来阐述高水准的Android应用开发要点。《Android开发艺术探索》从三个方面来组织内容。第一,介绍Android开发者不容易掌握的一些知识点;第二,结合Android源代码和应用层开发过程,融会贯通,介绍一些比较深入的知识点;第三,介绍一些核心技术和Android的性能优化思想。 《Andro......一起来看看 《Android开发艺术探索》 这本书的介绍吧!

在线进制转换器
在线进制转换器

各进制数互转换器

随机密码生成器
随机密码生成器

多种字符组合密码

HTML 编码/解码
HTML 编码/解码

HTML 编码/解码