数据结构

2020-07-16  本文已影响0人  isuntong

数组

初始化

数组元素个数会影响其初始化方式

当数组中元素的个数小于四个时，cmd/compile/internal/gc.fixedlit 函数接受的 kind 是 initKindLocalCode，上述代码会将原有的初始化语句 [3]int{1, 2, 3} 拆分成一个声明变量的表达式和几个赋值表达式，这些表达式会完成对数组的初始化：

var arr [3]int
arr[0] = 1
arr[1] = 2
arr[2] = 3

但是如果当前数组的元素大于 4 个，anylit 方法会先获取一个唯一的 staticname，然后调用 cmd/compile/internal/gc.fixedlit 函数在静态存储区初始化数组中的元素并将临时变量赋值给当前的数组：

func anylit(n *Node, var_ *Node, init *Nodes) {
    t := n.Type
    switch n.Op {
    case OSTRUCTLIT, OARRAYLIT:
        if n.List.Len() > 4 {
            vstat := staticname(t)
            vstat.Name.SetReadonly(true)

            fixedlit(inNonInitFunction, initKindStatic, n, vstat, init)

            a := nod(OAS, var_, vstat)
            a = typecheck(a, ctxStmt)
            a = walkexpr(a, init)
            init.Append(a)
            break
        }

        ...
    }
}

假设我们在代码中初始化 [5]int{1, 2, 3, 4, 5} 数组，那么我们可以将上述过程理解成以下的伪代码：

var arr [5]int
statictmp_0[0] = 1
statictmp_0[1] = 2
statictmp_0[2] = 3
statictmp_0[3] = 4
statictmp_0[4] = 5
arr = statictmp_0

总结起来，如果数组中元素的个数小于或者等于 4 个，那么所有的变量会直接在栈上初始化，如果数组元素大于 4 个，变量就会在静态存储区初始化然后拷贝到栈上，这些转换后的代码才会继续进入中间代码生成和机器码生成两个阶段，最后生成可以执行的二进制文件。

切片

长度和容量简单测试

sl := make([]int,3,5)
    fmt.Printf("%T\n", sl) //[]int
    fmt.Println(len(sl),cap(sl)) //3 5

    //panic: runtime error: index out of range [3] with length 3
    //sl[3] = 4
    //fmt.Println(len(sl),cap(sl))

    sl = append(sl, 1,2,3,4)
    fmt.Println(len(sl),cap(sl)) //7 10

    sl = append(sl, 5,6,7,8)
    fmt.Println(len(sl),cap(sl)) //11 20

    //不panic了
    sl[3] = 1
    fmt.Println(len(sl),cap(sl)) //11 20

扩容

在分配内存空间之前需要先确定新的切片容量，Go 语言根据切片的当前容量选择不同的策略进行扩容：

  1. 如果期望容量大于当前容量的两倍就会使用期望容量；
  2. 如果当前切片容量小于 1024 就会将容量翻倍；
  3. 如果当前切片容量大于 1024 就会每次增加 25% 的容量，直到新容量大于期望容量

确定了切片的容量之后，就可以计算切片中新数组占用的内存了，计算的方法就是将目标容量和元素大小相乘，计算新容量时可能会发生溢出或者请求的内存超过上限，在这时就会直接 panic

源码src/runtime/slice.go

newcap := old.cap
    doublecap := newcap + newcap
    if cap > doublecap {
        newcap = cap
    } else {
        if old.len < 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
            }
        }
    }

验证一下：

c := make([]int, 1024, 1024)
    fmt.Println(len(c), cap(c)) //1024 1024

    c = append(c, 1)
    fmt.Println(len(c), cap(c)) //1025 1280 --256 25%

    d := make([]int, 255, 255)
    c = append(c, d...)
    fmt.Println(len(c), cap(c)) //1280 1280

    c = append(c, 1)
    fmt.Println(len(c), cap(c)) //1281 1696 --416 32.5% ?

    d = make([]int, 415, 415)
    c = append(c, d...)
    fmt.Println(len(c), cap(c)) //1696 1696

    c = append(c, 1)
    fmt.Println(len(c), cap(c)) //1697 2304 --608 35.8% ?

为什么多出来一些？

后面还有经常被人忽略的代码

var overflow bool
    var lenmem, newlenmem, capmem uintptr
    // Specialize for common values of et.size.
    // For 1 we don't need any division/multiplication.
    // For sys.PtrSize, compiler will optimize division/multiplication into a shift by a constant.
    // For powers of 2, use a variable shift.
    switch {
    case et.size == 1:
        lenmem = uintptr(old.len)
        newlenmem = uintptr(cap)
        capmem = roundupsize(uintptr(newcap))
        overflow = uintptr(newcap) > maxAlloc
        newcap = int(capmem)
    case et.size == sys.PtrSize:
        lenmem = uintptr(old.len) * sys.PtrSize
        newlenmem = uintptr(cap) * sys.PtrSize
        capmem = roundupsize(uintptr(newcap) * sys.PtrSize)
        overflow = uintptr(newcap) > maxAlloc/sys.PtrSize
        newcap = int(capmem / sys.PtrSize)
    case isPowerOfTwo(et.size):
        var shift uintptr
        if sys.PtrSize == 8 {
            // Mask shift for better code generation.
            shift = uintptr(sys.Ctz64(uint64(et.size))) & 63
        } else {
            shift = uintptr(sys.Ctz32(uint32(et.size))) & 31
        }
        lenmem = uintptr(old.len) << shift
        newlenmem = uintptr(cap) << shift
        capmem = roundupsize(uintptr(newcap) << shift)
        overflow = uintptr(newcap) > (maxAlloc >> shift)
        newcap = int(capmem >> shift)
    default:
        lenmem = uintptr(old.len) * et.size
        newlenmem = uintptr(cap) * et.size
        capmem, overflow = math.MulUintptr(et.size, uintptr(newcap))
        capmem = roundupsize(capmem)
        newcap = int(capmem / et.size)
    }

    // The check of overflow in addition to capmem > maxAlloc is needed
    // to prevent an overflow which can be used to trigger a segfault
    // on 32bit architectures with this example program:
    //
    // type T [1<<27 + 1]int64
    //
    // var d T
    // var s []T
    //
    // func main() {
    //   s = append(s, d, d, d, d)
    //   print(len(s), "\n")
    // }
    if overflow || capmem > maxAlloc {
        panic(errorString("growslice: cap out of range"))
    }

    var p unsafe.Pointer
    if et.ptrdata == 0 {
        p = mallocgc(capmem, nil, false)
        // The append() that calls growslice is going to overwrite from old.len to cap (which will be the new length).
        // Only clear the part that will not be overwritten.
        memclrNoHeapPointers(add(p, newlenmem), capmem-newlenmem)
    } else {
        // Note: can't use rawmem (which avoids zeroing of memory), because then GC can scan uninitialized memory.
        p = mallocgc(capmem, et, true)
        if lenmem > 0 && writeBarrier.enabled {
            // Only shade the pointers in old.array since we know the destination slice p
            // only contains nil pointers because it has been cleared during alloc.
            bulkBarrierPreWriteSrcOnly(uintptr(p), uintptr(old.array), lenmem)
        }
    }
    memmove(p, old.array, lenmem)

    return slice{p, old.len, newcap}

用以下命令查看的Go语言程序对应的伪汇编代码：

go tool compile -S xxx.go

因为存在内存对齐，newcap需要配合et.size一起传入roundupsize中，寻找最近最合适的内存大小分配，再除以et.size，得到对齐后的newcap

func roundupsize(size uintptr) uintptr {
    if size < _MaxSmallSize {
        if size <= smallSizeMax-8 {
            return uintptr(class_to_size[size_to_class8[(size+smallSizeDiv-1)/smallSizeDiv]])
        } else {
            return uintptr(class_to_size[size_to_class128[(size-smallSizeMax+largeSizeDiv-1)/largeSizeDiv]])
        }
    }
    if size+_PageSize < size {
        return size
    }
    return alignUp(size, _PageSize)
}

var size_to_class128 = [(_MaxSmallSize-smallSizeMax)/largeSizeDiv + 1]uint8{31, 32, 33, 34, 35, 36, 36, 37, 37, 38, 38, 39, 39, 39, 40, 40, 40, 41, 42, 42, 43, 43, 43, 43, 43, 44, 44, 44, 44, 44, 44, 45, 45, 45, 45, 46, 46, 46, 46, 46, 46, 47, 47, 47, 48, 48, 49, 50, 50, 50, 50, 50, 50, 50, 50, 50, 50, 51, 51, 51, 51, 51, 51, 51, 51, 51, 51, 52, 52, 53, 53, 53, 53, 54, 54, 54, 54, 54, 55, 55, 55, 55, 55, 55, 55, 55, 55, 55, 55, 56, 56, 56, 56, 56, 56, 56, 56, 56, 56, 57, 57, 57, 57, 57, 57, 58, 58, 58, 58, 58, 58, 58, 58, 58, 58, 58, 58, 58, 58, 58, 58, 59, 59, 59, 59, 59, 59, 59, 59, 59, 59, 59, 59, 59, 59, 59, 59, 60, 60, 60, 60, 60, 61, 61, 61, 61, 61, 61, 61, 61, 61, 61, 61, 62, 62, 62, 62, 62, 62, 62, 62, 62, 62, 63, 63, 63, 63, 63, 63, 63, 63, 63, 63, 63, 63, 63, 63, 63, 63, 63, 63, 63, 63, 63, 63, 64, 64, 64, 64, 64, 64, 64, 64, 64, 64, 64, 64, 64, 64, 64, 64, 64, 64, 64, 64, 64, 65, 65, 65, 65, 65, 65, 65, 65, 65, 65, 65, 66, 66, 66, 66, 66, 66, 66, 66, 66, 66, 66, 66, 66, 66, 66, 66, 66, 66, 66, 66, 66, 66, 66, 66, 66, 66, 66, 66, 66, 66, 66, 66}

var class_to_size = [_NumSizeClasses]uint16{0, 8, 16, 32, 48, 64, 80, 96, 112, 128, 144, 160, 176, 192, 208, 224, 240, 256, 288, 320, 352, 384, 416, 448, 480, 512, 576, 640, 704, 768, 896, 1024, 1152, 1280, 1408, 1536, 1792, 2048, 2304, 2688, 3072, 3200, 3456, 4096, 4864, 5376, 6144, 6528, 6784, 6912, 8192, 9472, 9728, 10240, 10880, 12288, 13568, 14336, 16384, 18432, 19072, 20480, 21760, 24576, 27264, 28672, 32768}

现在就可以解答我的疑惑了：

上面的例子中，我用的是int，通过unsafe.sizeof()得int的size是8，即et.size=8（开始以为是4，忘了自己操作系统是64位的了）

  1. 正常扩容1.25倍应占内存：8 * (1280+1280/4) = 8 * 1600 = 12800
  2. 匹配size_to_class128：(12800 - 1024 + 128 - 1) / 128 = 92 (127为了那些size不是2的倍数的，比如结构体什么的准备的，原本size/128的余数，加上127之后就可以再除128得到1，这样保证不会导致分配的内存不够用)
  3. 匹配class_to_size：size_to_class128下标92的地方是56，class_to_size下标56的地方是13568
  4. 得出实际分配容量：13568 / 8 = 1696

所以这次获取到的容量才是1696

class_to_size里的数据怎么来的？想必是经验使然吧...

copy

b := []int{666,777,888}
    //copy(sl,b)
    //fmt.Println(sl) //[666 777 888 1 2 3 4 5 6 7 8]
    //fmt.Println(b) //[666 777 888]

    copy(b,sl)
    fmt.Println(sl) //[666 777 888 1 2 3 4 5 6 7 8]
    fmt.Println(b) //[666 777 888]

    fmt.Println(len(b),cap(b)) //3 3
    b = append(b, 111,222,333)
    fmt.Println(len(b),cap(b)) //6 6

相比于依次对元素进行拷贝，这种方式能够提供更好的性能，但是需要注意的是，哪怕使用 memmove 对内存成块进行拷贝，但是这个操作还是会占用非常多的资源，在大切片上执行拷贝操作时一定要注意性能影响。

哈希表（Map）

make创建map是里面的size有卵用？
影响内存分配。无论size多少，len(map)都是0，cap(map)都不行

什么时候扩容

  1. 装载因子已经超过 6.5；
//loadFactorNum = 13    loadFactorDen = 2  所以是6.5，能装8个，6.5好像很不错


//触发扩容的时机
if !h.growing() && (overLoadFactor(h.count+1, h.B) || tooManyOverflowBuckets(h.noverflow, h.B)) {
    hashGrow(t, h)
    goto again // Growing the table invalidates everything, so try again
  }

// 装载因子超过 6.5
func overLoadFactor(count int, B uint8) bool {
  return count > bucketCnt && uintptr(count) > loadFactorNum*(bucketShift(B)/loadFactorDen)
}

// overflow buckets 太多
func tooManyOverflowBuckets(noverflow uint16, B uint8) bool {
  if B > 15 {
    B = 15
  }
  return noverflow >= uint16(1)<<(B&15)
}
}
  1. 哈希使用了太多溢出桶；
    我理解是好多hash低B位相同，把一个桶搞得一大堆溢出桶，此时count马上就要比桶数的6.5倍要大了，又删掉了这些kv。又插入了一大堆hash低B位相同的key跑到到另一个桶里，导致又出来很多溢出桶。虽然删除时移除key，val，使cell为nil，但是桶还是在，严重影响了后续操作，需要遍历很多溢出桶，像链表了。重新分配是bucket不变（不算溢出桶哦），重新各回各家，各找各妈。

以下为复制的解释

第 1 点：我们知道，每个 bucket 有 8 个空位，在没有溢出，且所有的桶都装满了的情况下，装载因子算出来的结果是 8。因此当装载因子超过 6.5 时，表明很多 bucket 都快要装满了，查找效率和插入效率都变低了。在这个时候进行扩容是有必要的。

第 2 点：是对第 1 点的补充。就是说在装载因子比较小的情况下，这时候 map 的查找和插入效率也很低，而第 1 点识别不出来这种情况。表面现象就是计算装载因子的分子比较小，即 map 里元素总数少，但是 bucket 数量多（真实分配的 bucket 数量多，包括大量的 overflow bucket）。

不难想像造成这种情况的原因：不停地插入、删除元素。先插入很多元素，导致创建了很多 bucket，但是装载因子达不到第 1 点的临界值，未触发扩容来缓解这种情况。之后，删除元素降低元素总数量，再插入很多元素，导致创建很多的 overflow bucket，但就是不会触犯第 1 点的规定，你能拿我怎么办？overflow bucket 数量太多，导致 key 会很分散，查找插入效率低得吓人，因此出台第 2 点规定。这就像是一座空城，房子很多，但是住户很少，都分散了，找起人来很困难。

对于命中条件 1，2 的限制，都会发生扩容。但是扩容的策略并不相同，毕竟两种条件应对的场景不同。

对于条件 1，元素太多，而 bucket 数量太少，很简单：将 B 加 1，bucket 最大数量（2^B）直接变成原来 bucket 数量的 2 倍。于是，就有新老 bucket 了。注意，这时候元素都在老 bucket 里，还没迁移到新的 bucket 来。而且，新 bucket 只是最大数量变为原来最大数量（2^B）的 2 倍（2^B * 2）。

对于条件 2，其实元素没那么多，但是 overflow bucket 数特别多，说明很多 bucket 都没装满。解决办法就是开辟一个新 bucket 空间，将老 bucket 中的元素移动到新 bucket，使得同一个 bucket 中的 key 排列地更紧密。这样，原来，在 overflow bucket 中的 key 可以移动到 bucket 中来。结果是节省空间，提高 bucket 利用率，map 的查找和插入效率自然就会提升。

对于条件 2 的解决方案，曹大的博客里还提出了一个极端的情况：如果插入 map 的 key 哈希都一样，就会落到同一个 bucket 里，超过 8 个就会产生 overflow bucket，结果也会造成 overflow bucket 数过多。移动元素其实解决不了问题，因为这时整个哈希表已经退化成了一个链表，操作效率变成了 O(n)。

gc和指针
当 map 的 key 和 value 都不是指针，并且 size 都小于 128 字节的情况下，会把 bmap 标记为不含指针，这样可以避免 gc 时扫描整个 hmap。但是，我们看 bmap 其实有一个 overflow 的字段，是指针类型的，破坏了 bmap 不含指针的设想，这时会把 overflow 移动到 extra 字段来。

// A header for a Go map.
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
}

// mapextra holds fields that are not present on all maps.
type mapextra struct {
    // If both key and elem do not contain pointers and are inline, then we mark bucket
    // type as containing no pointers. This avoids scanning such maps.
    // However, bmap.overflow is a pointer. In order to keep overflow buckets
    // alive, we store pointers to all overflow buckets in hmap.extra.overflow and hmap.extra.oldoverflow.
    // overflow and oldoverflow are only used if key and elem do not contain pointers.
    // overflow contains overflow buckets for hmap.buckets.
    // oldoverflow contains overflow buckets for hmap.oldbuckets.
    // The indirection allows to store a pointer to the slice in hiter.
    overflow    *[]*bmap
    oldoverflow *[]*bmap

    // nextOverflow holds a pointer to a free overflow bucket.
    nextOverflow *bmap
}

// 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
    // Followed by bucketCnt keys and then bucketCnt elems.
    // NOTE: packing all the keys together and then all the elems together makes the
    // code a bit more complicated than alternating key/elem/key/elem/... but it allows
    // us to eliminate padding which would be needed for, e.g., map[int64]int8.
    // Followed by an overflow pointer.
}

为什么没有指针gc就不会扫描整个map

参考资料：
很多可挖掘的地方
正在看的文档

4. 字符串

Go语言中的字符串其实是一个只读的字节数组，“hello”字符串在内存中的存储方式：

代码中存在的字符串，会在编译期间被1标记成只读数据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
    0x0000 68 65 6c 6c 6f                                   hello
...

只读只意味着字符串会分配到只读的内存空间并且这块内存不会被修改，但是在运行时我们其实还是可以将这段内存拷贝到堆或者栈上，将变量的类型转换成 []byte 之后就可以进行，修改后通过类型转换就可以变回 string，Go 语言只是不支持直接修改 string 类型变量的内存空间。

4.1 数据结构

我们会经常会说字符串是一个只读的切片类型，这是因为切片在 Go 语言的运行时表示与字符串高度相似。

type StringHeader struct {
    Data uintptr
    Len  int
}

type SliceHeader struct {
    Data uintptr
    Len  int
    Cap  int
}

与切片的结构体相比，字符串少了一个表示容量的 Cap 字段，因为字符串作为只读的类型，我们并不会直接向字符串直接追加元素改变其本身的内存空间，所有在字符串上执行的写入操作实际都是通过 拷贝 实现的。

4.2 解析过程

声明：

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

4.3 拼接

正常情况下，运行时会调用 copy 将输入的多个字符串拷贝到目标字符串所在的内存空间中，新的字符串是一片新的内存空间，与原来的字符串也没有任何关联，一旦需要拼接的字符串非常大，拷贝带来的性能损失就是无法忽略的

为什么字符串重新赋值后地址不变

因为字符串在 Go 语言中的接口其实非常简单，每一个字符串在运行时都会使用如下的 StringHeader 结构体表示，在运行时包的内部其实有一个私有的结构 stringHeader，它有着完全相同的结构只是用于存储数据的 Data 字段使用了 unsafe.Pointer 类型：

修改值只是修改了Data指针的指向，但是结构体的地址无变化

https://www.cnblogs.com/erenming/p/12072949.html

虽然字符串并非切片，但是支持切片操作。对于同一字面量，不同的字符串变量指向相同的底层数组，这是因为字符串是只读的，为了节省内存，相同字面量的字符串通常对应于同一字符串常量。例如：

s := "hello, world"
s1 := "hello, world"
s2 := "hello, world"[7:]
fmt.Printf("%d \n", (*reflect.StringHeader)(unsafe.Pointer(&s)).Data) // 17598361
fmt.Printf("%d \n", (*reflect.StringHeader)(unsafe.Pointer(&s1)).Data) // 17598361
fmt.Printf("%d \n", (*reflect.StringHeader)(unsafe.Pointer(&s2)).Data) // 17598368

可以看到，三者均指向同一个底层数组。对于s1, s2由于是同一字符串常量hello, world，故指向一个底层数组，以h为起始位置；而s2是字面量hello, world的切片操作后生成的字符串，也指向同一字节底层数组，不过是以w为起始位置。

字符串怎么组织的？怎么判断是否已有这个字符串的？

切片赋值

b:=a只是把Data的指针赋值过去，此时b的任何修改都会影响a

但是b扩容之后就会改变Data的值，此时b的修改就又不会影响a了

为了避免影响可以使用copy函数

相比于依次对元素进行拷贝，这种方式能够提供更好的性能，但是需要注意的是，哪怕使用 memmove 对内存成块进行拷贝，但是这个操作还是会占用非常多的资源，在大切片上执行拷贝操作时一定要注意性能影响。

PS：只会赋值目标切片的长度，如果目标切片声明为sl5:=[]int{}，那什么都不复制过去，不会自动扩容。目标切片长度更长的话，保留尾部值不变；目标切片更短的话，则就改变这些。

值传递还是引用传递

golang默认都是采用值传递，即拷贝传递
有些值天生就是指针（slice、map、channel）

上一篇下一篇

猜你喜欢

热点阅读