Go 数据结构之 Slice (三)

前言

Golang 数据结构之 Slice (二)
上一篇文章介绍了一下扩容的基本情况，这一篇文章分析了 growslice 函数的源码

源码

我们看看 growslice函数的源码，可以分成三部分：

func growslice(et *_type, old slice, cap int) slice {
	if raceenabled {
		callerpc := getcallerpc(unsafe.Pointer(&et))
		racereadrangepc(old.array, uintptr(old.len*int(et.size)), callerpc, funcPC(growslice))
	}
	if msanenabled {
		msanread(old.array, uintptr(old.len*int(et.size)))
	}

	if et.size == 0 {
		if cap < old.cap {
			panic(errorString("growslice: cap out of range"))
		}
		// append should not create a slice with nil pointer but non-zero len.
		// We assume that append doesn't need to preserve old.array in this case.
		return slice{unsafe.Pointer(&zerobase), old.len, cap}
	}

	newcap := old.cap
	doublecap := newcap + newcap
	if cap > doublecap {
		newcap = cap
	} else {
		if old.len < 1024 {
			newcap = doublecap
		} else {
			for newcap < cap {
				newcap += newcap / 4
			}
		}
	}

	var lenmem, newlenmem, capmem uintptr
	const ptrSize = unsafe.Sizeof((*byte)(nil))
	switch et.size {
	case 1:
		lenmem = uintptr(old.len)
		newlenmem = uintptr(cap)
		capmem = roundupsize(uintptr(newcap))
		newcap = int(capmem)
	case ptrSize:
		lenmem = uintptr(old.len) * ptrSize
		newlenmem = uintptr(cap) * ptrSize
		capmem = roundupsize(uintptr(newcap) * ptrSize)
		newcap = int(capmem / ptrSize)
	default:
		lenmem = uintptr(old.len) * et.size
		newlenmem = uintptr(cap) * et.size
		capmem = roundupsize(uintptr(newcap) * et.size)
		newcap = int(capmem / et.size)
	}

	if cap < old.cap || uintptr(newcap) > maxSliceCap(et.size) {
		panic(errorString("growslice: cap out of range"))
	}

	var p unsafe.Pointer
	if et.kind&kindNoPointers != 0 {
		p = mallocgc(capmem, nil, false)
		memmove(p, old.array, lenmem)
		// 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 !writeBarrier.enabled {
			memmove(p, old.array, lenmem)
		} else {
			for i := uintptr(0); i < lenmem; i += et.size {
				typedmemmove(et, add(p, i), add(old.array, i))
			}
		}
	}

	return slice{p, old.len, newcap}
}

zerobase 策略

func growslice(et *_type, old slice, cap int) slice {
	// 省略～～～
	if et.size == 0 {
		if cap < old.cap {
			panic(errorString("growslice: cap out of range"))
		}
		// append should not create a slice with nil pointer but non-zero len.
		// We assume that append doesn't need to preserve old.array in this case.
		return slice{unsafe.Pointer(&zerobase), old.len, cap}
	}
	// 省略～～～

• 如果 size 为 0 ，若将要扩容的容量比原本的容量小，则抛出异常（不能缩小）
• 否则，将重新生成一个新的 Slice 返回，其 Pointer 指向一个 0 byte 地址。

容量计算

func growslice(et *_type, old slice, cap int) slice {
	//省略～～～
	
    // 新容量默认为原有容量
    newcap := old.cap
    doublecap := newcap + newcap
    // 如果新容量大于旧容量的两倍，则直接按照新容量大小申请
    if cap > doublecap {
		newcap = cap
    } else {
        // 如果原有长度小于1024，则新容量是旧容量的2倍
        if old.len < 1024 {
            newcap = doublecap
        } else {
            // 按照原有容量的 1/4 增加，直到满足新容量的需要
            for 0 < newcap && newcap < cap {
                newcap += newcap / 4
            }
            // 检查容量是否溢出。
            if newcap <= 0 {
                newcap = cap
            }
        }
    }
    
	//省略～～～
}

• 若 cap 大于 doublecap，则扩容后容量大小为 新 Slice 的容量;
• 若 len 小于 1024 个，在扩容时，增长因子为 1（也就是增加 1 倍）
• 若 len 大于 1024 个，在扩容时，增长因子为 0.25（原本容量的四分之一）

总的来说，就是 len 小于 1024 时，增长 2 倍。大于 1024 时，增长 1.25 倍

内存对齐

func growslice(et *_type, old slice, cap int) slice {
	//省略～～～
	
    var overflow bool
    var lenmem, newlenmem, capmem uintptr
    
    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 {
            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)
    }
}

//省略～～～

对于不同的slice元素大小，选择不同的计算方法，获取原来 Slice 长度和计算假定扩容后的新 Slice 元素长度、容量大小以及指针地址（用于后续操作）

数据拷贝

func growslice(et *_type, old slice, cap int) slice {
	//省略～～～

	//确定新 Slice 容量大于老 Sice，并且新容量内存小于指定的最大内存、没有溢出。否则抛出异常
	if cap < old.cap || uintptr(newcap) > maxSliceCap(et.size) {
			panic(errorString("growslice: cap out of range"))
		}

	var p unsafe.Pointer
	if et.kind&kindNoPointers != 0 {
		p = mallocgc(capmem, nil, false)
		memmove(p, old.array, lenmem)
		// 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 !writeBarrier.enabled {
			memmove(p, old.array, lenmem)
		} else {
			for i := uintptr(0); i < lenmem; i += et.size {
				typedmemmove(et, add(p, i), add(old.array, i))
			}
		}
	}

	return slice{p, old.len, newcap}
}

若元素类型为 kindNoPointers，也就是非指针类型。则在原来的 Slice 后面继续扩容

1. 根据先前计算的 capmem，在老 Slice cap 后继续申请内存空间；
2. 将 old.array 上的 n 个 bytes（根据 lenmem）拷贝到新的内存空间上
3. 新内存空间（p）加上新 Slice cap 的容量地址。最终得到完整的新 Slice cap 内存地址 add(p, newlenmem) （ptr）
4. 从 ptr 开始重新初始化 n 个 bytes（capmem-newlenmem）

拷贝数据是这两个主要函数

// 拷贝数据
memmove(p, old.array, lenmem)
// 返回新的切片
return slice{p, old.len, newcap}