Dig101:Go之读懂map的底层设计

Dig101: dig more, simplified more and know more

在golang中,map是一个不可或缺的存在。

它作为哈希表,简单易用,既能自动处理哈希碰撞,又能自动扩容或重新内存整理,避免读写性能的下降。

这些都要归功于其内部实现的精妙。本文尝试去通过源码去分析一下其背后的故事。

我们不会过多在源码分析上展开,只结合代码示例对其背后设计实现上做些总结,希望可以简单明了一些。

希望看完后,会让你对 map 的理解有一些帮助。网上也有很多不错的源码分析,会附到文末,感兴趣的同学自行查看下。

(本文分析基于 Mac 平台上go1.14beta1版本。长文预警 … )

Read More

Dig101-Go之灵活的slice

Dig101: dig more, simplified more and know more

Slice作为go常用的数据类型,在日常编码中非常常见。
相对于数组的定长不可变,slice使用起来就灵活了许多。

0x01 slice 到底是什么?

首先我们看下源码中slice结构的定义

1
2
3
4
5
6
// src/runtime/slice.go
type slice struct {
array unsafe.Pointer
len int
cap int
}

slice数据结构如上,Data指向底层引用的数组内存地址, len是已用长度,cap是总容量。
为验证如上所述,我们尝试声明一个slice a,获取 a的sliceHeader头信息,并用%p获取&a, sh, a, a[0]的地址
看看他们的地址是否相同。

1
2
3
4
5
6
7
8
a := make([]int, 1, 3)
//reflect.SliceHeader 为 slice运行时数据结构
sh := (*reflect.SliceHeader)(unsafe.Pointer(&a))
fmt.Printf("slice header: %#v\naddress of a: %p &a[0]: %p | &a: %p sh:%p ",
sh, a, &a[0],&a, sh)

//slice header: &reflect.SliceHeader{Data:0xc000018260, Len:1, Cap:3}
//address of a: 0xc000018260 &a[0]: 0xc000018260 | &a: 0xc00000c080 sh:0xc00000c080

结果发现a和&a[0]地址相同。 这个好理解,切片指向地址即对应底层引用数组首个元素地址
&a和sh及sh.Data指向地址相同。这个是因为这三个地址是指slice自身地址。
这里【slice自身地址不同于slice指向的底层数据结构地址】, 清楚这一点对于后边的一些问题会更容易判断。

Read More

Dig101-Go之for-range排坑指南

好久没写了,打算今年做个Dig101系列,挖一挖技术背后的故事。

Dig101: dig more, simplified more and know more

golang常用的遍历方式,有两种: for 和 for-range。
而for-range使用中有些坑常会遇到,今天我们一起来捋一捋。

0x01 遍历取不到所有元素指针?

如下代码想从数组遍历获取一个指针元素切片集合

1
2
3
4
5
6
7
8
arr := [2]int{1, 2}
res := []*int{}
for _, v := range arr {
res = append(res, &v)
}
//expect: 1 2
fmt.Println(*res[0],*res[1])
//but output: 2 2

答案是【取不到】
同样代码对切片[]int{1, 2}map[int]int{1:1, 2:2}遍历也不符合预期。
问题出在哪里?

Read More

golang的Mutex锁如何实现

概述

golang中锁实现的整体思路是利用类似信号量的P,V操作 (互斥锁:Mutex)
来对有限个goroutine争夺资源的共享。

在获取资源accquire是执行P,对锁标志位sema-1,其他获取资源时发现资源位为0则需阻塞等待
释放资源release是执行V,对锁标志位sema+1。
此时若无阻塞等待的goroutine则直接释放,否则需唤醒一个阻塞goroutine。

为实现上诉操作定义了以下结构

1
2
3
4
5
6
7
8
9
10
11
type Mutex struct {
state int32 //倒数(右到左)三位分别是 锁、唤醒、饥饿的标志位;剩余29位是当前阻塞等待锁的goroutine个数
sema uint32 //信号量标记位
}
const (
mutexLocked = 1 << iota // mutex is locked
mutexWoken
mutexStarving
mutexWaiterShift = iota
starvationThresholdNs = 1e6 //饥饿模式阈值:超1ms获取不到锁则进入饥饿模式
)

其中饥饿标志位引入是为了解决goroutine过长时间阻塞问题

互斥锁有正常模式和饥饿模式两种

1.正常模式下
阻塞排队的goroutine先进先出,被唤醒的goroutine和新来的goroutine争夺锁,新来的goroutine
因已经在cpu执行过而占有优势,更容易获得锁。

2.饥饿模式下
阻塞超过1ms还没抢到锁则转入饥饿模式
此模式下,新来的goroutine只能排队尾,不争夺锁,不自旋等待;
锁释放后会直接移交给队首goroutine。

3.恢复正常模式
满足以下任意一个条件时
1)等候时间小于1ms
2)阻塞队列为空时

Read More

go源码分析之内存分配

go源码分析之内存池

概述

go自带内存管理,主要是内存池和垃圾回收两部分。因为其对内存的管理在性能和空间利用率上的高效,go内存大多数情况不需要用户自己去管理内存,让程序员减少了很多在内存管理的心智成本。虽然如此,本文还是借着源码,分析下go的内存管理中内存池分配时如何实现的,希望对大家了解有所帮助。如有问题,欢迎探讨指正。
(源码基于go 1.10.3)

首先,内存分配模型基于tcmalloc,Tcmalloc是Google gperftools里的组件之一。全名是 thread cache malloc(线程缓存分配器),其内存管理分为线程内存和中央堆两部分。在并行程序下分配小对象(<=32k)的效率很高。
Tcmalloc核心思想是把内存分成多级来降低锁的粒度。每个线程都会有一个cache,用于无锁分配小对象,当内存不足分配小对象,就去central申请,在不足就去heap申请,heap最终是向操作系统申请。
这样的分配模型,维护一个用户态的内存池,不仅提高了内存在频繁分配、释放时的效率,而且有效地减少内存碎片。

下面我们依次看下go中内存如何划分,主要的一些内存结构,最后在结合源码看一下主要的内存分配流程。

Read More