string类型
string类型的底层数据结构（本质是一个只读的字节切片，使用UTF-8字符编码)
// StringHeader is the runtime representation of a string.
type StringHeader struct {
Data uintptr // 指向实际存储字符串字节的数组的指针
Len int // 字符串长度（字符串的字节数)
}
字符串底层的切片数据不可改，但是可以对字符串的引用修改。
s1 := "abc"
ptr := (*reflect.StringHeader)(unsafe.Pointer(&s1))
fmt.Println(ptr)
//字符串data地址
fmt.Println(unsafe.Pointer(ptr.Data)) // 0x100be23b3
// 获取data地址所指向的数据
fmt.Println((*[3]byte)(unsafe.Pointer(ptr.Data))) // &[97 98 99]
Q: 为什么将string类型设置为不可变？
A: string类型作为程序代码设计中非常常见类型高频使用，string的不可变性可以避免string的并发安全问题，可以被多个G共享安全使用；string本身底层还包含字符串字节数组长度，对应O(1)复杂度获取字符串长度；对应的代价就是对字符串修改，会占用字符串副本，产生额外内存空间占用。
string的拼接方式
string拼接方式有很多种，包括以下几种：
连接符+拼接 ： 每次拼接会产生新对象，开辟新内存空间存放数据，旧数据还可能被GC，大量数据拼接会产生性能问题。
字符串格式化函数fmt.Sprintf拼接：每次操作也需要创建新对象，并强转为string类型，释放数据，性能也不是特别好。
预分配的bytes.Buffer拼接：可以通过函数Grow预先分配指定大小的内存区，再将数据写入新内存区，可以避免多次的内存分配性能消耗，性能较好。
func (b *Buffer) String() string {
return string(b.buf[b.off:])
}
- 预分配strings.Builder拼接：原理和bytes.Buffer一致，都是预先分配内存大小，但是通过0拷贝方式将字节数据转换为string，性能较高于bytes.Buffer。
func (b *Builder) String() string {
return *(*string)(unsafe.Pointer(&b.buf))
}
- 预分配[]byte : 利用了slice类型扩容功能。
- strings.join函数拼接: 底层使用了strings.Builder操作，性能相当。
string切片导致的内存泄漏问题
string的切片操作导致的内存泄漏，通常是因为：
对字符串进行截取时，指向了同一个块内存空间。（slice切片截取后，底层数据还是引用原有的数据对象）
某些场景下，就会导致无法释放原始字符串的引用，从而原始字符串无法被gc, 截取的slice会持有原始字符串数据内存，当截取slice不在使用时候，也无法释放原始字符串的内存。
eg: 例如有一个很大字符串x(len=1000), 分别有两个对象y1, y2对x进行截取(len=20)，如果y1持续一直存活，y2在执行完回收后，x会因为y1的引用而一直存活，得不到释放。
如果想用一个小的截取大字符串的操作，就使用会产生内存拷贝的方式，产生新的内存地址，不产生原始字符串的内存地址引用，从而解决这个问题。
func StringSlice(s string) string {
s1 := string([]byte[s:20])
ptr := (*reflect.StringHeader)(unsafe.Pointer(&s1))
fmt.Println("StringSlice:", unsafe.Pointer(ptr))
return s1
)
// 或者是通过strings.Builder
func stringSliceBuilder(s string) string {
var sb bytes.Buffer
sb.Grow(len(s))
sb.WriteString(s)
ptr := (*reflect.StringHeader)(unsafe.Pointer(&s))
fmt.Println("stringSliceBuilder:",unsafe.Pointer(&ptr))
return sb.String()
}
字符串转成byte切片内存拷贝问题
在字符串string和[]byte类型转换过程中，是会存在内存拷贝的。即，会新创建一块内存地址来存放拷贝数据。两者底层并不指向相同的数据结构。
s := strings.Repeat("1", 1<<20)
ptr := (*reflect.StringHeader)(unsafe.Pointer(&s))
fmt.Println("s pointer", unsafe.Pointer(ptr.Data))
// 字符串 => slice([]byte)
s1 := []byte(s)
ptr1 := (*reflect.StringHeader)(unsafe.Pointer(&s1))
fmt.Println("s1 pointer", unsafe.Pointer(ptr1.Data))
// slice([]byte) => string
s2 := string(s1)
//fmt.Println(s2)
ptr2 := (*reflect.StringHeader)(unsafe.Pointer(&s2))
fmt.Println("s2 pointer", unsafe.Pointer(ptr2.Data))
// output
s pointer 0x14000180000
s1 pointer 0x14000280000
s2 pointer 0x14000380000
零拷贝的方式： 在string和[]byte互相转换过程中，并不会发生内存拷贝。实质是通过反射机制获取底层的数据项来完成。
fmt.Println("=========零拷贝方式=========")
// []byte => string
s3 := *(*string)(unsafe.Pointer(&s1))
ptr = (*reflect.StringHeader)(unsafe.Pointer(&s3))
fmt.Println("s3", unsafe.Pointer(ptr.Data))
// string => []byte
s4 := *(*[]byte)(unsafe.Pointer(&s))
ptr = (*reflect.StringHeader)(unsafe.Pointer(&s4))
fmt.Println("s4", unsafe.Pointer(ptr.Data))
// 通过函数，构建struct
func string2bytes(s string) []byte {
strHeader := (*reflect.StringHeader)(unsafe.Pointer(&s))
b := *(*[]byte)(unsafe.Pointer(&reflect.SliceHeader{
Data: strHeader.Data,
Len: strHeader.Len,
Cap: strHeader.Len,
}))
return b
}
slice切片
源代码中，表示slice类型的：
// SliceHeader is the runtime representation of a slice.
type SliceHeader struct {
Data uintptr
Len int
Cap int
}
type slice struct {
array unsafe.Pointer
len int
cap int
}
其中reflect包中的SliceHeader是对外的，可通过reflect包访问，而runtime包下的slice则是内部使用的，两者都能表达slice的内存布局结构。
数组的缺点
- 元素个数不可变
- 传值开销大（在函数入参传递过程中，值拷贝在大数组数据会有性能问题）
切片的特性
- 切片的元素个数是可变的
- 切片传值的过程，入参传递的是底层数据所指向的指针地址，传值开销小。（相同的底层引用，内部修改会影响原始值）
slice的传值
slice做为入参函数传递过程中，存在以下几种情况：
- 如果使用=符号赋值，则两者指针地址一样
- 函数入参和函数外的slice对象的指针地址是一样。
- 在函数内， 对slice入参数重新赋值（=赋值或者append操作），入参slice底部值会指向新的数据，原始slice不会影响。
- 在函数内， 对slice入参数进行遍历循环修改值，则函数内的更新，会影响原始slice，因为两者的指向一致。
func main() {
s := []int{1, 2, 3}
log.Printf("s:%p", s)
s1 := s
log.Printf("s1:%p", s1)
f3(s)
log.Printf("main after f3 s:%v,ptr:%p", s, s)
f4(s)
log.Printf("main after f4 s:%v,ptr:%p", s, s)
f5(s)
log.Printf("main after f5 s:%v,ptr:%p", s, s)
}
func f3(param []int) {
log.Printf("f3 init param:%p", param)
s3 := []int{4, 5, 6}
param = s3
log.Printf("f3 update param:%p", param)
}
func f4(param []int) {
log.Printf("f4 init param:%p", param)
param = append(param, 4)
log.Printf("f4 append param:%p", param)
}
func f5(param []int) {
log.Printf("f5 init param:%p", param)
for i, _ := range param {
if i == 0 {
param[i] = 10
}
}
log.Printf("f5 loop param:%p", param)
}
// output输出结果
s:0x140000b0000
s1:0x140000b0000
f3 init param:0x140000b0000
f3 update param:0x140000b0018
main after f3 s:[1 2 3],ptr:0x140000b0000
f4 init param:0x140000b0000
f4 append param:0x140000c0030
main after f4 s:[1 2 3],ptr:0x140000b0000
f5 init param:0x140000b0000
f5 loop param:0x140000b0000
main after f5 s:[10 2 3],ptr:0x140000b0000
slice的扩容
slice是一种动态数组，它可以动态增长和缩小。
触发时机：当切片的长度超过其容量时，切片会自动扩容。这通常发生在使用 append 函数向切片中添加元素时。
扩容整体步骤：
- 计算容量：根据规则，计算新slice的容量。
- 申请内存: 根据容量和slice元素类型大小，计算需要的内存空间大小，申请内存空间。
- 旧切片数据复制迁移: 将旧切片中元素数据进行拷贝到新的容器中。
- 旧切片数据处理。
slice的扩容的逻辑，在源代码方法** growslice**中可查看详情。
func growslice(et *_type, old slice, cap int) slice {
...
newcap := old.cap
doublecap := newcap + newcap
if cap > doublecap {
newcap = cap
} else {
if old.cap < 1024 {
newcap = doublecap
} else {
// Check 0 < newcap to detect overflow
// and prevent an infinite loop.
for 0 < newcap && newcap < cap {
newcap += newcap / 4
}
// Set newcap to the requested cap when
// the newcap calculation overflowed.
if newcap <= 0 {
newcap = cap
}
}
}
...
...
}
常规扩容的规则：不同SDK版本的扩容规则会有些许差异。
GO1.17
- 如果期望容量大于当前容量的两倍就会使用期望容量。
- 如果当前切片的长度小于 1024 就会将容量翻倍；
- 如果当前切片的长度大于等于 1024 就会每次增加 25% 的容量，直到新容量大于期望容量；
GO1.18+
- 如果期望容量大于当前容量的两倍就会使用期望容量；
- 如果当前切片的长度小于阈值（默认 256）就会将容量翻倍；
- 如果当前切片的长度大于等于阈值（默认 256），就会每次增加 25% 的容量，基准是 newcap + 3*threshold，直到新容量大于期望容量；
注意： growslice 的后半部分还有更进一步的优化（内存对齐等），靠的是 roundupsize 函数，在计算完 newcap 值之后，还会有一个步骤计算最终的容量：
capmem=roundupsize(uintptr(new cap) * ptrsize)
new cap = int(capmem/ptrSize)
chan中的select选择器
select是用来监听channel有关的IO操作，本质是实现了多路IO复用机制。底层结构是所有的case语句一起组成的scase的结构数组。
// Select case descriptor.
// Known to compiler.
// Changes here must also be made in src/cmd/compile/internal/walk/select.go's scasetype.
type scase struct {
c *hchan // chan
elem unsafe.Pointer // data element, 读或者写缓冲区地址
}
type hchan struct {
qcount uint // total data in the queue
dataqsiz uint // size of the circular queue
buf unsafe.Pointer // points to an array of dataqsiz elements
elemsize uint16
closed uint32
elemtype *_type // element type
sendx uint // send index
recvx uint // receive index
recvq waitq // list of recv waiters
sendq waitq // list of send waiters
// 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
}
Go中的select语句针对的是channel的io监听，主要的逻辑在源代码selectgo函数中。
// selectgo implements the select statement.
//
// cas0 points to an array of type [ncases]scase, and order0 points to
// an array of type [2*ncases]uint16 where ncases must be <= 65536.
// Both reside on the goroutine's stack (regardless of any escaping in
// selectgo).
//
// For race detector builds, pc0 points to an array of type
// [ncases]uintptr (also on the stack); for other builds, it's set to
// nil.
//
// selectgo returns the index of the chosen scase, which matches the
// ordinal position of its respective select{recv,send,default} call.
// Also, if the chosen scase was a receive operation, it reports whether
// a value was received.
func selectgo(cas0 *scase, order0 *uint16, pc0 *uintptr, nsends, nrecvs int, block bool) (int, bool) {
...
}
- 遍历所有的case语句，如果所有的case都未就绪(不可读，不可写), 则走default，如果没有default，则会阻塞。
- 如果有就绪channel，则跳出循环进行管道操作并返回。（返回的是被选择的scase索引，这个索引就是需要执行的case分支）
select特性
- select后不能有语句，且仅支持管道，而且是单携程操作
- select- case分支中不能使用fallthrough语句
- 每个case语句仅能处理一个管道，要么读，要么写。
- 多个非阻塞case操作中每次将只有一个被随机选择执行。
- 所有case操作均阻塞则执行default分支。
channel底层原理
channel是用于在多个协程之间安全高效的共享数据的通道。是一个类似队列的数据结构，使用一个环形数组(circular buffer) 来存储数据。
channel的数据结构： 底层3个FIFO先进先出队列。（sendq待发送者队列，recvq待接收者队列，buffer循环队列)
锁和条件变量：为了确保并发安全，底层使用lock和条件变量支持同步，控制channel的读写操作，保证多个G之间的竞争安全。
缓冲与阻塞：有无缓冲区，以及读写的阻塞。
数据复制：channel在传递数据过程中，会产生数据对象的复制。为了并发安全，每个G都有自己的数据副本，避免共享影响。
channel的关闭: channel关闭通知接收方check检查。
channel发送和接收数据的具体过程:
本质上channel是一个有锁的环形队列。多个G通过同一个channel进行元素读写传递，都是会产生复制过程（直接值部，读写可以会产生2次值复制。
GO的并发模型是CSP（communication sequential process 通信顺序进程），通过通信来共享内存。
channel的发送
锁定整个通道（读是否可以？）
确定通道是否可以写入？
a. 先判断recvq等待接收队列是否为空（等待队列是N个sudog)，不为空直接从recvq中取出G，写入数据，唤醒G，结束发送过程。
b. 如果缓冲区有空余位置，直接写入数据导缓冲区
c. 如果缓冲区数据满了，则需要将发送的数据的G先放到sendq中（形成sudog)，从而进入睡眠状态，等待被唤醒。写入数据后释放锁
channel的接收
获取channel的全局锁
根据sendq等待发送队列是否为空以及有无缓冲区，缓冲区是否已满来决定
a. 如果发送等待队列有g, 无缓冲区，直接唤醒g,并取出g的数据复制读取分配给接收变量。
b. 有等待发送的g, 并且缓冲区已满，则从缓冲区队列首部取数据, 再从sendq中取出数据存入缓冲队列。
c. 如果没有sendq, 且缓冲区有数据，直接读取缓冲区数据
d. 没有sendq， 没有缓冲区或者缓冲区为空，则直接将g存入recvq队列。等待有数据接收的唤醒。结束读取后释放锁。
channel的死锁
- for...range循环中遍历channel时，未正常关闭channel导致的死锁。
func main() {
ch := make(chan int, 2) // 创建一个容量为2的有缓冲channel
// 向channel写入数据
ch <- 1
ch <- 2
// close(ch) // 解决办法，关闭channel，for range就能结束
var wg sync.WaitGroup
wg.Add(2)
// 两个协程从channel读取数据
go func() {
defer wg.Done()
// 在for...range循环中遍历channel时，如果channel没有被关闭，
// 两个协程将会一直阻塞在for...range循环中，等待更多的数据被发送到channel，这可能导致死锁
for i := range ch {
fmt.Println("协程1 读取:", i)
}
}()
go func() {
defer wg.Done()
for i := range ch {
fmt.Println("协程2 读取:", i)
}
}()
// 死锁，2个协程在读取完channel中的元素后没有退出
// 主协程在等待协程完成，而协程在等待更多的数据或channel关闭。
wg.Wait() // 等待协程完成
}
waitgroup实现原理
// SDK 1.60
type WaitGroup struct {
noCopy noCopy
// 64-bit value: high 32 bits are counter, low 32 bits are waiter count.
// 64-bit atomic operations require 64-bit alignment, but 32-bit
// compilers do not ensure it. So we allocate 12 bytes and then use
// the aligned 8 bytes in them as state, and the other 4 as storage
// for the sema.
state1 [3]uint32
}
// sdk 1.80
type WaitGroup struct {
noCopy noCopy
// 64-bit value: high 32 bits are counter, low 32 bits are waiter count.
// 64-bit atomic operations require 64-bit alignment, but 32-bit
// compilers only guarantee that 64-bit fields are 32-bit aligned.
// For this reason on 32 bit architectures we need to check in state()
// if state1 is aligned or not, and dynamically "swap" the field order if
// needed.
state1 uint64
state2 uint32
}
// 1.20
type WaitGroup struct {
noCopy noCopy
// 高32位用来表示还未执行完成的协程个数，低32位表示调用阻塞wait等待的个数
state atomic.Uint64 // high 32 bits are counter, low 32 bits are waiter count.
// 信号量，用于控制wg的add操作和wait操作逻辑上次数限制(PV操作）
sema uint32
}
// 标记不可以拷贝复制，编译器限制
type noCopy struct{}
// Lock is a no-op used by -copylocks checker from `go vet`.
func (*noCopy) Lock() {}
func (*noCopy) Unlock() {}
waitgroup作用：WaitGroup 需要等待一组操作完成之后再执行，因此需要等待所有操作完成之后才能继续执行。
为了实现这个功能，WaitGroup 使用了2个计数器+ 1个信号量：
- counter
来记录还有多少个操作没有完成，如果 counter 的值为 0，则表示所有操作已经完成。 - waiter
记录当前有多少个协程正在等待操作完成。
当我们创建一个 WaitGroup 实例时，该实例的任务计数器和等待计数器都被初始化为 0。
waitgroup的计数器在不同sdk版本存储设计方式不一样，有64bit高低32位分别存储的方式用来做计数器使用，而在并发下的多个不同协程
的通信就是使用了信号量(PV)来实现通知唤醒。waiter 是等待者的个数，因为一般只执行一次 Wait 函数，所以 waiter 数一般是1。
等待协程需要等待所有任务完成之后才能继续执行，所以等待协程在任务未完成时会被阻塞，当任务全部完成后，自动被唤醒
WaitGroup使用 state2 用于实现信号量机制。通过调用 runtime_Semacquire() 和runtime_Semrelease() 函数，可以在不阻塞线程的情况下进行等待和通知操作。
这两个函数是 Go 运行时提供的底层信号量操作。runtime_Semacquire 用于等待信号量，如果信号量的计数大于零，则减少计数并继续执行；否则，协程将被阻塞。runtime_Semrelease 用于释放信号量，增加信号量的计数，并唤醒等待的协程。
map底层原理
通常我们会使用三种方式进行 map 的创建:
- 字面量: 例如m := map[int]int{1:1} => 对应汇编代码函数makemap_small
- 通过 make 方式，但不指定大小: m := make(map[int]int) => 对应汇编代码函数 makemap64
- 通过 make 方式，但指定大小: m := make(map[int]int, 3) => 对应汇编代码函数 makemap
// A header for a Go map.
type hmap struct {
// Note: the format of the hmap is also encoded in cmd/compile/internal/reflectdata/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
}
总体来说，对于map的读写操作都是分为以下几步：
- 通过hash算法，计算key的值，得到二进制值X；
- 根据X的低B位(hmap中的B字段），得到对应map的存储的bucket[index]。
- 定位到具体bucket后,根据X的高8位的值，遍历bucket tophash区域值比较，选定key
- 如果找不到，又存在溢出桶(overvlow bucket),则再对溢出桶进行遍历定位。
golang 将key的哈希值分成低位和高位两部分，低位哈希值用于确定 key 所在的桶序号，高位哈希值用于初步确定key是否在桶中。map 中已存在的 key 的高位哈希会被保存在bmap 的tophash中，除此以外，tophash 还可以用于保存一些标记。
Q: map源代码中每个bucket的对象，只是一个包含8个数组长度类型的数值，来表示key被hash后的tophash值。那么bucket中的key和value对象是如何存储和表示的？
// A bucket for a Go map.
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.
tophash [bucketCnt]uint8
}
A： 并没有看到有关保存key、value的结构，是因为哈希表中 key 和 value 类型并不固定，所以这里很难确定要用什么类型去定义字段。推导后的 bmap结构如下，这里其实就是一个完整的桶结构，包含了 tophash，key，value 和溢出桶指针。
type bmap struct {
topbits [8]uint8
keys [8]keytype
elems [8]valuetype
overflow uintptr
}
对于字段overflow的特殊说明：
- 当 key 和 value中不包含指针时，overflow是uintptr类型，而包含指针时，是 unsafe.Pointer类型。
uintptr 类型不会被 GC 认为是引用，而 unsafe.Pointer类型会认为是引用。
如果 key 和 value 中不包含指针，那么就将桶标记为不含指针(uintptr类型)，从而避免扫描整个 map(uintptr不被认为是引用，不会扫描)。
但是这样有个问题: 如果桶中有溢出桶，overflow 应该指向对应的溢出桶地址，但是由于 uintptr 类型不被认为是引用，这部分内存可能就会被 GC 回收掉。
为了避免这个问题，需要有个地方能够直接引用这些溢出桶，也就是hmap 的extra字段，该字段为mapextra类型。
type mapextra struct {
overflow *[]*bmap. // 指向所有的溢出桶，只用于 key 和 value 中不含指针的场景
oldoverflow *[]*bmap // 指向所有旧桶的溢出桶，只用于 key 和 value 中不含指针的场景
// nextOverflow holds a pointer to a free overflow bucket.
nextOverflow *bmap // 指向所有的预分配的溢出桶，预分配的用完了值就变成nil
}
map有几个特点需要注意：
- map是无序的，写入和读出的顺序是不确定的。
- map不是并发安全的，多线程对map的操作，需要额外的同步操作才能保证数据一致性。
- 如果 k-v 能用不含指针的类型，就尽量不用指针，可以减轻 GC 压力
- 使用delete 删除map中的 key 时不会真的释放内存，只是做个标记
- map 本质上是使用了拉链法去解决哈希冲突问题，区别在于链上的每个节点可以保存 8 个 k-v。