Go-02-Slice

Go 语言的函数参数传递，只有值传递，没有引用传递

数组与切片

在 Go 中，与 C 数组变量隐式作为指针使用不同，Go 数组是值类型，赋值和函数传参操作都会复制整个数组数据

func main() {
	arrayA := [2]int{100, 200}
	var arrayB [2]int

	arrayB = arrayA

	fmt.Printf("arrayA : %p , %p, %p, %v\n", &arrayA, &arrayA[0], &arrayA[1], arrayA)
	fmt.Printf("arrayB : %p , %p, %p, %v\n", &arrayB, &arrayB[0], &arrayB[1], arrayB)
	arrayA[0] = 200
	testArray(arrayA)
	fmt.Println(arrayA)
	fmt.Println(arrayB)
	testArray(arrayB)
}

func testArray(x [2]int) {
	fmt.Printf("func Array : %p , %p, %p, %v\n", &x, &x[0], &x[1], x)
	x[0] = 300
}

//运行结果为：
arrayA : 0xc00010c010 , 0xc00010c010, 0xc00010c018, [100 200]
arrayB : 0xc00010c020 , 0xc00010c020, 0xc00010c028, [100 200]
func Array : 0xc00010c060 , 0xc00010c060, 0xc00010c068, [200 200]
[200 200]
[100 200]
func Array : 0xc00010c0a0 , 0xc00010c0a0, 0xc00010c0a8, [100 200]

分析：

1. 当直接使用 arrayB = arrayA 进行的是值复制，也就是说Go数组是值类型
2. 将数组赋值给函数的时候，也是对整个数组进行复制，函数内改变值并不会改变外面的数组

上面的例子换成切片会怎么样？

func main() {
	arrayA := []int{100, 200, 300}
	arrayB := arrayA[0:2]

	fmt.Printf("arrayA : %p , %p, %p, %v\n", &arrayA, &arrayA[0], &arrayA[1], arrayA)
	fmt.Printf("arrayB : %p , %p, %p, %v, %d\n", &arrayB, &arrayB[0], &arrayB[1], arrayB, cap(arrayB))
	arrayA[0] = 200
	testArray(arrayB)
	fmt.Printf("arrayA : %p , %p, %p, %v\n", &arrayA, &arrayA[0], &arrayA[1], arrayA)
	fmt.Printf("arrayB : %p , %p, %p, %v, %d\n", &arrayB, &arrayB[0], &arrayB[1], arrayB, cap(arrayB))
}

func testArray(x []int) {
	fmt.Printf("func Array : %p , %p, %p, %v %d\n", &x, &x[0], &x[1], x, cap(x))
	x[0] = 300
	x = append(x, 400)
	fmt.Printf("func Array : %p , %p, %p, %v %d\n", &x, &x[0], &x[1], x, cap(x))
}

//运行结果为:
arrayA : 0xc00000c060 , 0xc000014140, 0xc000014148, [100 200 300]
arrayB : 0xc00000c080 , 0xc000014140, 0xc000014148, [100 200], 3
func Array : 0xc00000c0e0 , 0xc000014140, 0xc000014148, [200 200] 3
func Array : 0xc00000c0e0 , 0xc000014140, 0xc000014148, [300 200 400] 3
arrayA : 0xc00000c060 , 0xc000014140, 0xc000014148, [300 200 400]
arrayB : 0xc00000c080 , 0xc000014140, 0xc000014148, [300 200], 3

分析：

1. 当直接使用 arrayB = arrayA 进行的是其实是值复制，地址空间不一致，但是指向的内存空间一致
2. 切片做参数传递的时候,但函数内容修改切片内容并不会影响外部切片，改变底层数组会影响外部切片

切片数据结构

切片（slice）切片是一个引用类型，是对数组一个连续片段的引用。这个片段是由起始和终止索引标识的一些项的子集。终止索引标识的项不包括在切片内(左闭右开)。切片提供了一个与指向数组的动态窗口。

给定项的切片索引可能比相关数组的相同元素的索引小。和数组不同的是，切片的长度可以在运行时修改，最小为 0 最大为相关数组的长度：切片是一个长度可变的数组

type slice struct {
	array unsafe.Pointer		//指向数组的指针
	len   int								//当前切片长度
	cap   int								//当前切片容量
}

uintptr is an integer type that is large enough to hold the bit pattern of any pointer

unsafe.Pointer 通用指针,类似C中的 void *

切片创建

首先这里会有一个常见函数，math.MulUintptr 将两个参数相乘来判断是否溢出

//MulUintptr返回a * b以及乘法是否溢出。在受支持的平台上，这是编译器固有的功能。
//true 越界;false 没有越界
func MulUintptr(a, b uintptr) (uintptr, bool) {
	if a|b < 1<<(4*sys.PtrSize) || a == 0 {
		return a * b, false
	}
	overflow := b > MaxUintptr/a
	return a * b, overflow
}

解析：

1. sys.PtrSize 在64位机器中为8

   const PtrSize = 4 << (^uintptr(0) >> 63)           // unsafe.Sizeof(uintptr(0)) but an ideal const
   const MaxUintptr = ^uintptr(0)

2. < 1<<(4*sys.PtrSize)相当于< 1<<32 ,而8位计算机中最大的是 2^64-1,所以判断a和b都小于2^32即可

3. 否则 b > MaxUintptr/a 如果 b 大于最大值除以a,则说明 a*b 超过最大值即越界

make与字面量切片

支持通过make或字面量的方式进行创建切片

slice1 := make([]int, 4, 6)	//make
slice2 := []int{1,2,3,4}		//字面量，注意[]内不要写容量，否则是数组

再来看分片函数 makeslice

func makeslice(et *_type, len, cap int) unsafe.Pointer {
	mem, overflow := math.MulUintptr(et.size, uintptr(cap))
	if overflow || mem > maxAlloc || len < 0 || len > cap {
		mem, overflow := math.MulUintptr(et.size, uintptr(len))
		if overflow || mem > maxAlloc || len < 0 {
			panicmakeslicelen()
		}
		panicmakeslicecap()
	}

  // 分配内存 
  // 小对象从当前P 的cache中空闲数据中分配
  // 大的对象 (size > 32KB) 直接从heap中分配
  // runtime/malloc.go
	return mallocgc(mem, et, true)
}

解析：

1. 根据 数据类型大小 x 切片容量 判断是否会越界

2. 如果 越界或超过最大分配长度maxAlloc(32位与64位不一致)，长度大于容器。则尝试 根据 数据类型大小 x 切片长度 判断溢出

3. 如果 长度大于最大长度，则 panicmakeslicelen: panic报错 makeslice: len out of range

4. 如果 长度大于容量 则 panicmakeslicecap: panic报错 makeslice: cap out of range

5. 否则分配内存：

   func mallocgc(size uintptr, typ *_type, needzero bool) unsafe.Pointer {}

6. 所以切片其实分配了容量大小的内存，只是访问不到，也被初始化

空切片与nil切片

var slice []int						 //nil切片
silce := make( []int , 0 ) //空切片
slice := []int{ }          //空切片

空切片和 nil 切片的区别在于：空切片指向的地址不是nil，指向的是一个内存地址，但是它没有分配任何内存空间，即底层元素包含0个元素。

不管是使用 nil 切片还是空切片，对其调用内置函数 append，len 和 cap 的效果都是一样的

切片扩容

扩容原理

growslice用来处理在使用append时候的切片扩容，那么它的规则如下：

func growslice(et *_type, old slice, cap int) slice {
	if raceenabled {
		callerpc := getcallerpc()
		racereadrangepc(old.array, uintptr(old.len*int(et.size)), callerpc, funcPC(growslice))
	}
	if msanenabled {
		msanread(old.array, uintptr(old.len*int(et.size)))
	}
	//当新容量比旧容量还有小的时候，直接panic报错
	if cap < old.cap {
		panic(errorString("growslice: cap out of range"))
	}

	if et.size == 0 {
		//如果切片元素大小为0，还调用了扩容方法，那么就新生成一个新的容量的切片返回
		return slice{unsafe.Pointer(&zerobase), old.len, cap}
	}
	
	newcap := old.cap
	doublecap := newcap + newcap
	if cap > doublecap {  		//1. 当指定容量大于旧切片2倍，则使用指定容量
		newcap = cap
	} else { 									//2. 指定容量小于旧切片2倍
		if old.len < 1024 {			
			newcap = doublecap		//2.1. 如果旧切片长度小于1024，则使用容量为旧容量两倍
		} else {
      //2.2. 如果旧切片长度大于1024且小于指定容量，则新容量循环增加自身的四分之一直到大于指定容量
			for 0 < newcap && newcap < cap {
				newcap += newcap / 4
			}
			if newcap <= 0 {			//2.3. 如果旧切片长度等于0，则新容量等于旧容量
				newcap = cap
			}
		}
	}

	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)
	}

	if overflow || capmem > maxAlloc {
		panic(errorString("growslice: cap out of range"))
	}

	var p unsafe.Pointer
	if et.ptrdata == 0 {
    //先将 P 地址加上新的容量得到新切片容量的地址，然后将新切片容量地址后面的 capmem-newlenmem 个 bytes 这块内存初始化。为之后继续 append() 操作腾出空间
		p = mallocgc(capmem, nil, false)
    // memclrNoHeapPointers clears n bytes starting at ptr
		memclrNoHeapPointers(add(p, newlenmem), capmem-newlenmem)
	} else {
		// 重新申请 capmen 这个大的内存地址，并且初始化为0值
		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-et.size+et.ptrdata)
		}
	}
  //将 lenmem 这个多个 bytes 从 old.array地址 拷贝到 p 的地址处
	memmove(p, old.array, lenmem)

	return slice{p, old.len, newcap} //返回新切片
}

上述就是扩容的实现。主要需要关注的有两点:

1. 扩容时候的策略
   • 如果新申请容量（cap）大于2倍的旧容量（old.cap），最终容量（newcap）就是新申请的容量（cap）
   • 如果旧切片的长度小于1024，则最终容量(newcap)就是旧容量(old.cap)的两倍，即（newcap=doublecap）
   • 如果旧切片长度大于等于1024，则最终容量（newcap）从旧容量（old.cap）开始循环增加原来的 1/4，即（newcap=old.cap,for {newcap += newcap/4}）直到最终容量（newcap）大于等于新申请的容量(cap)，即（newcap >= cap）
   • 如果最终容量（cap）计算值溢出，则最终容量（cap）就是新申请容量（cap）
2. 扩容是生成全新的内存地址还是在原来的地址后追加

扩容实例

实例1：

func main() {
    s := make([]int, 0)
    oldCap := cap(s)
    for i := 0; i < 2048; i++ {
        s = append(s, i)
        newCap := cap(s)
        if newCap != oldCap {
            fmt.Printf("[%d -> %4d] cap = %-4d  |  after append %-4d  cap = %-4d\n", 0, i-1, oldCap, i, newCap)
            oldCap = newCap
        }
    }
}

//运行结果为:
[0 ->    0] cap = 1     |  after append 1     cap = 2   
[0 ->    1] cap = 2     |  after append 2     cap = 4   
[0 ->    3] cap = 4     |  after append 4     cap = 8   
[0 ->    7] cap = 8     |  after append 8     cap = 16  
[0 ->   15] cap = 16    |  after append 16    cap = 32  
[0 ->   31] cap = 32    |  after append 32    cap = 64  
[0 ->   63] cap = 64    |  after append 64    cap = 128 
[0 ->  127] cap = 128   |  after append 128   cap = 256 
[0 ->  255] cap = 256   |  after append 256   cap = 512 
[0 ->  511] cap = 512   |  after append 512   cap = 1024
[0 -> 1023] cap = 1024  |  after append 1024  cap = 1280
[0 -> 1279] cap = 1280  |  after append 1280  cap = 1696
[0 -> 1695] cap = 1696  |  after append 1696  cap = 2304

分析：

1. 1280/1024 = 1.25 , 1696/1024 = 1.325, 2304/1696=1.3584,为什么每次增加的倍数都不一样呢？
   • 因为 newcap += newcap / 4 并不是固定倍数，还需要考虑到 roundupsize(uintptr(newcap))

实例2：

func main() {
	slice := []int{10, 20, 30, 40}
	newSlice := append(slice, 50)
	fmt.Printf("Before slice %v, Pointer %p, Pointer0 %p, len %d, cap %d\n", slice, &slice, &slice[0], len(slice), cap(slice))
	fmt.Printf("Before newSlice = %v, Pointer = %p, Pointer0 %p, len = %d, cap = %d\n", newSlice, &newSlice, &newSlice[0], len(newSlice), cap(newSlice))
	newSlice[1] += 10
	fmt.Printf("After slice = %v, Pointer = %p, Pointer0 %p, len = %d, cap = %d\n", slice, &slice, &slice[0], len(slice), cap(slice))
	fmt.Printf("After newSlice = %v, Pointer = %p, Pointer0 %p, len = %d, cap = %d\n", newSlice, &newSlice, &newSlice[0], len(newSlice), cap(newSlice))
}

Before slice [10 20 30 40], Pointer 0xc00000c060, Pointer0 0xc000014140, len 4, cap 4
Before newSlice = [10 20 30 40 50], Pointer = 0xc00000c080, Pointer0 0xc000016140, len = 5, cap = 8
After slice = [10 20 30 40], Pointer = 0xc00000c060, Pointer0 0xc000014140, len = 4, cap = 4
After newSlice = [10 30 30 40 50], Pointer = 0xc00000c080, Pointer0 0xc000016140, len = 5, cap = 8

分析：

1. 当旧切片容量小于1024，新切片容量直接翻倍
2. 这里分配了一个新地址，修改新分片，旧分片并不会改变

实例2：

func main() {
	array := [4]int{10, 20, 30, 40}
	slice := array[0:2]
	newSlice := append(slice, 50)
	fmt.Printf("Before array %v, Poninter %p, Poninter0 %p \n", array, &array, &array[0])
	fmt.Printf("Before slice %v, Pointer %p, Pointer0 %p, len = %d, cap = %d\n", slice, &slice, &slice[0], len(slice), cap(slice))
	fmt.Printf("Before newSlice = %v, Pointer = %p, Pointer0 %p, len = %d, cap = %d\n", newSlice, &newSlice, &newSlice[0], len(newSlice), cap(newSlice))
	newSlice[1] += 10
	fmt.Printf("After slice = %v, Pointer = %p, Pointer0 %p, len = %d, cap = %d\n", slice, &slice, &slice[0], len(slice), cap(slice))
	fmt.Printf("After newSlice = %v, Pointer = %p, Pointer0 %p, len = %d, cap = %d\n", newSlice, &newSlice, &newSlice[0], len(newSlice), cap(newSlice))
	fmt.Printf("After array = %v, Poninter = %p, Pointer0 %p \n", array, &array, &array[0])
}

Before array [10 20 50 40], Poninter 0xc000014140, Poninter0 0xc000014140 
Before slice [10 20], Pointer 0xc00000c060, Pointer0 0xc000014140, len = 2, cap = 4
Before newSlice = [10 20 50], Pointer = 0xc00000c080, Pointer0 0xc000014140, len = 3, cap = 4
After slice = [10 30], Pointer = 0xc00000c060, Pointer0 0xc000014140, len = 2, cap = 4
After newSlice = [10 30 50], Pointer = 0xc00000c080, Pointer0 0xc000014140, len = 3, cap = 4
After array = [10 30 50 40], Poninter = 0xc000014140, Pointer0 0xc000014140

分析：

1. 与实例1进行对比：由于slice还有容量可以扩容，所以执行 append() 操作以后，会在原数组上直接操作，这种情况下，扩容以后的数组还是指向原来的数组
2. 实例1中由于没有容量进行扩容，所以执行append之后指向的就是一个全新的数组，修改值并不会影响原来的数组
3. 由于数组是值类型，而切片是应引用类型，所以看到 &array 与 &array[0]的地址是一样的。但是 &slice 与 &slice[0]的地址是不一样的。另外两者指向的第一个值地址都是一样的，指向同一片内存。

由于容量导致结果不一致，极易产生bug。

实例3：

func main() {
	s := make([]int, 0)
	oldCap := cap(s)
	for i := 0; i < 2048; i++ {
		s = append(s, i)
		newCap := cap(s)
		if newCap != oldCap {
			fmt.Printf("[%d -> %4d] cap = %-4d  |  after append %-4d  cap = %-4d\n", 0, i-1, oldCap, i, newCap)
			oldCap = newCap
		}
	}
}
//运行结果为:
[0 ->   -1] cap = 0     |  after append 0     cap = 1   
[0 ->    0] cap = 1     |  after append 1     cap = 2   
[0 ->    1] cap = 2     |  after append 2     cap = 4   
[0 ->    3] cap = 4     |  after append 4     cap = 8   
[0 ->    7] cap = 8     |  after append 8     cap = 16  
[0 ->   15] cap = 16    |  after append 16    cap = 32  
[0 ->   31] cap = 32    |  after append 32    cap = 64  
[0 ->   63] cap = 64    |  after append 64    cap = 128 
[0 ->  127] cap = 128   |  after append 128   cap = 256 
[0 ->  255] cap = 256   |  after append 256   cap = 512 
[0 ->  511] cap = 512   |  after append 512   cap = 1024
[0 -> 1023] cap = 1024  |  after append 1024  cap = 1280
[0 -> 1279] cap = 1280  |  after append 1280  cap = 1696
[0 -> 1695] cap = 1696  |  after append 1696  cap = 2304

分析：

切片拷贝

拷贝原理

func slicecopy(toPtr unsafe.Pointer, toLen int, fmPtr unsafe.Pointer, fmLen int, width uintptr) int {
	if fmLen == 0 || toLen == 0 {
		return 0
	}

	n := fmLen
	if toLen < n {
		n = toLen
	}

	if width == 0 {
		return n
	}

	if raceenabled { //竞争检测
		callerpc := getcallerpc()
		pc := funcPC(slicecopy)
		racereadrangepc(fmPtr, uintptr(n*int(width)), callerpc, pc)
		racewriterangepc(toPtr, uintptr(n*int(width)), callerpc, pc)
	}
	if msanenabled { // 如果开启了 The memory sanitizer (msan)
		msanread(fmPtr, uintptr(n*int(width)))
		msanwrite(toPtr, uintptr(n*int(width)))
	}

	size := uintptr(n) * width
	if size == 1 { // common case worth about 2x to do here
		// TODO: is this still worth it with new memmove impl?
    //如果只有一个元素，那么指针直接转换即可
		*(*byte)(toPtr) = *(*byte)(fmPtr) // known to be a byte pointer
	} else {
    //如果不止一个元素，那么就把 size 个 bytes 从 fm.array 地址开始，拷贝到 to.array 地址之后
		memmove(toPtr, fmPtr, size)
	}
	return n
}

拷贝实例

实例1：

func main() {
	array := []int{10, 20, 30, 40}
	slice := make([]int, 6)
	slice1 := make([]int, 3)
	n := copy(slice, array)
	m := copy(slice1, array)
	fmt.Println(n, slice)
	fmt.Println(m, slice1)
}

//运行结果
4 [10 20 30 40 0 0]
3 [10 20 30]

分析：

1. copy返回复制数目，slicecopy 方法最终结果取决于较短的那个切片，当较短的切片复制完成，整个复制过程就全部完成了

实例2：

func main() {
	slice := []int{10, 20, 30, 40}
	for index, value := range slice {
		fmt.Printf("value = %d , value-addr = %x , slice-addr = %x\n", value, &value, &slice[index])
	}
}

value = 10 , value-addr = c000018088 , slice-addr = c000014140
value = 20 , value-addr = c000018088 , slice-addr = c000014148
value = 30 , value-addr = c000018088 , slice-addr = c000014150
value = 40 , value-addr = c000018088 , slice-addr = c000014158

分析：

1. 如果用 range 的方式去遍历一个切片， Value 其实是切片里面的值拷贝。所以每次打印 Value 的地址都不变
2. 由于 Value 是值拷贝而非引用传递，所以直接改 Value 是达不到更改原切片值的目的的，需通过 &slice[index] 获取真实的地址

参考文献

1. https://halfrost.com/go_slice/
2. https://www.kancloud.cn/kancloud/the-way-to-go/72489