• Golang slice 通过growslice调用nextslicecap计算扩容


    先来看一段代码

    1. code:
    2. e := []int64{1, 2, 3}
    3. fmt.Println("cap of e before:", cap(e))
    4. e = append(e, 4, 5, 6, 7)
    5. fmt.Println("cap of e after:", cap(e))
    6. output:
    7. cap of e before: 3
    8. cap of e after: 8

    为什么容量是8?

    append了的4个元素,如果是原来的2倍也才6个,小于长度7,所以容量赋值长度7

    内存分配,为了高效使用需要对齐,找到合适的span对象

     capmem =   roundupsize(uintptr(newcap) * ptrSize) ptrSize 8字节

    capmem =     roundupsize(7*8) 

    capmem =  64

     newcap = int(capmem /   ptrSize) 

    newcap = 8

    1. _MaxSmallSize = 32768
    2. smallSizeDiv = 8
    3. smallSizeMax = 1024
    4. largeSizeDiv = 128
    5. _NumSizeClasses = 68
    6. _PageShift = 13
    7. maxObjsPerSpan = 1024
    8. )
    9. var class_to_size = [_NumSizeClasses]uint16{0, 8, 16, 24, 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}
    10. var class_to_allocnpages = [_NumSizeClasses]uint8{0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 2, 1, 2, 1, 2, 1, 3, 2, 3, 1, 3, 2, 3, 4, 5, 6, 1, 7, 6, 5, 4, 3, 5, 7, 2, 9, 7, 5, 8, 3, 10, 7, 4}
    11. var class_to_divmagic = [_NumSizeClasses]uint32{0, ^uint32(0)/8 + 1, ^uint32(0)/16 + 1, ^uint32(0)/24 + 1, ^uint32(0)/32 + 1, ^uint32(0)/48 + 1, ^uint32(0)/64 + 1, ^uint32(0)/80 + 1, ^uint32(0)/96 + 1, ^uint32(0)/112 + 1, ^uint32(0)/128 + 1, ^uint32(0)/144 + 1, ^uint32(0)/160 + 1, ^uint32(0)/176 + 1, ^uint32(0)/192 + 1, ^uint32(0)/208 + 1, ^uint32(0)/224 + 1, ^uint32(0)/240 + 1, ^uint32(0)/256 + 1, ^uint32(0)/288 + 1, ^uint32(0)/320 + 1, ^uint32(0)/352 + 1, ^uint32(0)/384 + 1, ^uint32(0)/416 + 1, ^uint32(0)/448 + 1, ^uint32(0)/480 + 1, ^uint32(0)/512 + 1, ^uint32(0)/576 + 1, ^uint32(0)/640 + 1, ^uint32(0)/704 + 1, ^uint32(0)/768 + 1, ^uint32(0)/896 + 1, ^uint32(0)/1024 + 1, ^uint32(0)/1152 + 1, ^uint32(0)/1280 + 1, ^uint32(0)/1408 + 1, ^uint32(0)/1536 + 1, ^uint32(0)/1792 + 1, ^uint32(0)/2048 + 1, ^uint32(0)/2304 + 1, ^uint32(0)/2688 + 1, ^uint32(0)/3072 + 1, ^uint32(0)/3200 + 1, ^uint32(0)/3456 + 1, ^uint32(0)/4096 + 1, ^uint32(0)/4864 + 1, ^uint32(0)/5376 + 1, ^uint32(0)/6144 + 1, ^uint32(0)/6528 + 1, ^uint32(0)/6784 + 1, ^uint32(0)/6912 + 1, ^uint32(0)/8192 + 1, ^uint32(0)/9472 + 1, ^uint32(0)/9728 + 1, ^uint32(0)/10240 + 1, ^uint32(0)/10880 + 1, ^uint32(0)/12288 + 1, ^uint32(0)/13568 + 1, ^uint32(0)/14336 + 1, ^uint32(0)/16384 + 1, ^uint32(0)/18432 + 1, ^uint32(0)/19072 + 1, ^uint32(0)/20480 + 1, ^uint32(0)/21760 + 1, ^uint32(0)/24576 + 1, ^uint32(0)/27264 + 1, ^uint32(0)/28672 + 1, ^uint32(0)/32768 + 1}
    12. var size_to_class8 = [smallSizeMax/smallSizeDiv + 1]uint8{0, 1, 2, 3, 4, 5, 5, 6, 6, 7, 7, 8, 8, 9, 9, 10, 10, 11, 11, 12, 12, 13, 13, 14, 14, 15, 15, 16, 16, 17, 17, 18, 18, 19, 19, 19, 19, 20, 20, 20, 20, 21, 21, 21, 21, 22, 22, 22, 22, 23, 23, 23, 23, 24, 24, 24, 24, 25, 25, 25, 25, 26, 26, 26, 26, 27, 27, 27, 27, 27, 27, 27, 27, 28, 28, 28, 28, 28, 28, 28, 28, 29, 29, 29, 29, 29, 29, 29, 29, 30, 30, 30, 30, 30, 30, 30, 30, 31, 31, 31, 31, 31, 31, 31, 31, 31, 31, 31, 31, 31, 31, 31, 31, 32, 32, 32, 32, 32, 32, 32, 32, 32, 32, 32, 32, 32, 32, 32, 32}
    13. var size_to_class128 = [(_MaxSmallSize-smallSizeMax)/largeSizeDiv + 1]uint8{32, 33, 34, 35, 36, 37, 37, 38, 38, 39, 39, 40, 40, 40, 41, 41, 41, 42, 43, 43, 44, 44, 44, 44, 44, 45, 45, 45, 45, 45, 45, 46, 46, 46, 46, 47, 47, 47, 47, 47, 47, 48, 48, 48, 49, 49, 50, 51, 51, 51, 51, 51, 51, 51, 51, 51, 51, 52, 52, 52, 52, 52, 52, 52, 52, 52, 52, 53, 53, 54, 54, 54, 54, 55, 55, 55, 55, 55, 56, 56, 56, 56, 56, 56, 56, 56, 56, 56, 56, 57, 57, 57, 57, 57, 57, 57, 57, 57, 57, 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, 60, 60, 60, 60, 60, 60, 60, 60, 60, 60, 60, 61, 61, 61, 61, 61, 62, 62, 62, 62, 62, 62, 62, 62, 62, 62, 62, 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, 64, 65, 65, 65, 65, 65, 65, 65, 65, 65, 65, 65, 65, 65, 65, 65, 65, 65, 65, 65, 65, 65, 66, 66, 66, 66, 66, 66, 66, 66, 66, 66, 66, 67, 67, 67, 67, 67, 67, 67, 67, 67, 67, 67, 67, 67, 67, 67, 67, 67, 67, 67, 67, 67, 67, 67, 67, 67, 67, 67, 67, 67, 67, 67, 67}
    14. func divRoundUp(n, a uintptr) uintptr {
    15. // a is generally a power of two. This will get inlined and
    16. // the compiler will optimize the division.
    17. return (n + a - 1) / a
    18. }
    19. func roundupsize(size uintptr) uintptr {
    20. if size < _MaxSmallSize {
    21. if size <= smallSizeMax-8 {
    22. return uintptr(class_to_size[size_to_class8[divRoundUp(size, smallSizeDiv)]])
    23. } else {
    24. return uintptr(class_to_size[size_to_class128[divRoundUp(size-smallSizeMax, largeSizeDiv)]])
    25. }
    26. }
    27. if size+_PageSize < size {
    28. return size
    29. }
    30. return alignUp(size, _PageSize)
    31. }

    计算容量

    < 256 容量*2,反之

    容量 += 容量+3*256 >> 2 (二进制中右移n位,相当于除以2的n次方_

    举例512扩容

    512 += (512 + 256 * 3)>>2

    cap = 512 + 320 = 832 

    1. func nextslicecap(newLen, oldCap int) int {
    2. newcap := oldCap
    3. doublecap := newcap + newcap
    4. if newLen > doublecap {
    5. return newLen
    6. }
    7. const threshold = 256
    8. if oldCap < threshold {
    9. return doublecap
    10. }
    11. for {
    12. // Transition from growing 2x for small slices
    13. // to growing 1.25x for large slices. This formula
    14. // gives a smooth-ish transition between the two.
    15. newcap += (newcap + 3*threshold) >> 2
    16. // We need to check `newcap >= newLen` and whether `newcap` overflowed.
    17. // newLen is guaranteed to be larger than zero, hence
    18. // when newcap overflows then `uint(newcap) > uint(newLen)`.
    19. // This allows to check for both with the same comparison.
    20. if uint(newcap) >= uint(newLen) {
    21. break
    22. }
    23. }
    24. // Set newcap to the requested cap when
    25. // the newcap calculation overflowed.
    26. if newcap <= 0 {
    27. return newLen
    28. }
    29. return newcap
    30. }
    31. func growslice(oldPtr unsafe.Pointer, newLen, oldCap, num int, et *_type) slice {
    32. ...
    33. newcap := nextslicecap(newLen, oldCap)
    34. var overflow bool
    35. var lenmem, newlenmem, capmem uintptr
    36. // Specialize for common values of et.Size.
    37. // For 1 we don't need any division/multiplication.
    38. // For goarch.PtrSize, compiler will optimize division/multiplication into a shift by a constant.
    39. // For powers of 2, use a variable shift.
    40. switch {
    41. case et.Size_ == 1:
    42. lenmem = uintptr(oldLen)
    43. newlenmem = uintptr(newLen)
    44. capmem = roundupsize(uintptr(newcap))
    45. overflow = uintptr(newcap) > maxAlloc
    46. newcap = int(capmem)
    47. case et.Size_ == goarch.PtrSize:
    48. lenmem = uintptr(oldLen) * goarch.PtrSize
    49. newlenmem = uintptr(newLen) * goarch.PtrSize
    50. capmem = roundupsize(uintptr(newcap) * goarch.PtrSize)
    51. overflow = uintptr(newcap) > maxAlloc/goarch.PtrSize
    52. newcap = int(capmem / goarch.PtrSize)
    53. case isPowerOfTwo(et.Size_):
    54. var shift uintptr
    55. if goarch.PtrSize == 8 {
    56. // Mask shift for better code generation.
    57. shift = uintptr(sys.TrailingZeros64(uint64(et.Size_))) & 63
    58. } else {
    59. shift = uintptr(sys.TrailingZeros32(uint32(et.Size_))) & 31
    60. }
    61. lenmem = uintptr(oldLen) << shift
    62. newlenmem = uintptr(newLen) << shift
    63. capmem = roundupsize(uintptr(newcap) << shift)
    64. overflow = uintptr(newcap) > (maxAlloc >> shift)
    65. newcap = int(capmem >> shift)
    66. capmem = uintptr(newcap) << shift
    67. default:
    68. lenmem = uintptr(oldLen) * et.Size_
    69. newlenmem = uintptr(newLen) * et.Size_
    70. capmem, overflow = math.MulUintptr(et.Size_, uintptr(newcap))
    71. capmem = roundupsize(capmem)
    72. newcap = int(capmem / et.Size_)
    73. capmem = uintptr(newcap) * et.Size_
    74. }
    75. ...
    76. memmove(p, oldPtr, lenmem)
    77. return slice{p, newLen, newcap}
    78. }

  • 相关阅读:
    常用xshell中使用的linux命令
    dhtmlx.gantt 8.0.6 Crack dhtmlx.甘特图
    Javaweb之javascript的详细解析
    Docker搭建私有仓库
    测试人生 | 97年双非学历的小哥哥,2线城市涨薪100%,我酸了......
    湖南大学大二STC单片机实训学习记录
    [WinUI 3] 如何利用 D3D11 在 SwapChainPanel 控件上绘制 OpenGL(UWP通用)
    防火墙第三天——恶意软件、反病毒技术。。。
    SLAM ORB-SLAM2(5)例程了解
    前端食堂技术周刊第 46 期:Chrome 三方 cookie 计划、npm 引入更多安全增强功能、Awesome Bun
  • 原文地址:https://blog.csdn.net/lucifer_qiao/article/details/132987088