用 Golang 刷 leetcode 題目時，如果不太清楚 Golang slice 與相關 function 的運作原理，很容易踩到坑，尤其是使用其他高階語言的開發者，剛轉換到 Golang 時會覺得為什麼同樣的程式邏輯，但是出來的結果卻不一樣。因此本篇簡單說明 Golang 最常使用到的 slice append function 運作原理，並且使用 objdump 來觀察記憶體操作狀況。
Slice internal
首先推薦先閱讀 Golang blog Go Slices: usage and internals，雖然距離文章發布的日期已久遠，但是 slice internal 結構還是可以參考。文中很重要的一個概念是：A slice is a descriptor of an array segment.， 雖然我們使用 slice 方式很像 array ，但實際上 slice 是一個 descriptor struct ，其中會有一個 array pointer 指向真正存放數值的 array 中。
1type slice struct {
2 array unsafe.Pointer
3 len int
4 cap int
5}
此時，如果我們要把一個既有的 slice assign 給新的 slice 變數：
1nums := make([]int, 0)
2nums = append(nums, 1)
3nums = append(nums, 2)
4nums = append(nums, 3)
5nums = append(nums, 4)
6nums = append(nums, 5)
7
8newNums := nums
上述的 code 看起來好像是新建立了一個新的 slice newNums，不過剛剛有提到 slice 是 descriptor struct 型態，因此 newNums 其實是複製 nums struct member 的值，以致 newNums 和 nums 擁有相同的 length、capacity、array pointer，所以雖然是兩個 slice，但底層卻是共用同一個 array 記憶體區段。
1fmt.Printf("%p \n", &newNums[0]) // 0xc000018030
2fmt.Printf("%p \n", &nums[0]) // 0xc000018030
而這個概念在 slice 指向的 array 空間不夠，需要擴充 array 空間時，情況就會不一樣了。在 Go Slices: usage and internals 中有提到：
To increase the capacity of a slice one must create a new, larger slice and copy the contents of the original slice into it.
遇到這種情況，剛剛提及的 nums 和 newNums 變數，就會因為新 allocate 一塊較大的 array 記憶體區段的擴充流程，導致 nums 和 newNums 的 array pointer 不再是指向同一個 array 記憶體，而是會一個指向新的 array 記憶體、另一個指向舊的：
1nums := make([]int, 0)
2nums = append(nums, 1)
3newNums := nums // both of them share the same array pointer
4
5fmt.Printf("%p \n", &newNums[0]) // 0xc000018030
6fmt.Printf("%p \n", &nums[0]) // 0xc000018030
7
8newNums = append(newNums, 2) // Growing slices, creating a new array area for newNums
9
10fmt.Printf("%p \n", &newNums[0]) // 0xc000018050
11fmt.Printf("%p \n", &nums[0]) // 0xc000018030
至於 array 擴充後的記憶體空間是怎麼計算的呢？我們可以從 Golang source code 的 runtime.growslice 找到答案：
1func growslice(et *_type, old slice, cap int) slice {
2 newcap := old.cap
3 doublecap := newcap + newcap
4 if cap > doublecap {
5 newcap = cap
6 } else {
7 const threshold = 256
8 if old.cap < threshold {
9 newcap = doublecap
10 } else {
11 // Check 0 < newcap to detect overflow
12 // and prevent an infinite loop.
13 for 0 < newcap && newcap < cap {
14 // Transition from growing 2x for small slices
15 // to growing 1.25x for large slices. This formula
16 // gives a smooth-ish transition between the two.
17 newcap += (newcap + 3*threshold) / 4
18 }
19 // Set newcap to the requested cap when
20 // the newcap calculation overflowed.
21 if newcap <= 0 {
22 newcap = cap
23 }
24 }
25 }
26}
在 capacity < 256 情況下， capacity 擴充是用 2 倍的方式來增加，也就是 1 -> 2 -> 4 -> 8 -> 16 等，而當 capacity 超過 256 時，此時擴充所需要的記憶體空間相對較大，因此僅會以 1.25 倍的方式增加。
Slice append function
有了上述的概念後，可以知道關鍵在於 slice 指向的 array 擴充時間點，其中最常見的應用場景就是我們使用 slice append function 在 slice 中加入新的數值，此時如果指向的 array 空間不足，就會觸發 growslice allocate 一個新的 array 空間。
而在 Go Slices: usage and internals 有提及簡單的 append function 實作流程概念：
1func AppendByte(slice []byte, data ...byte) []byte {
2 m := len(slice)
3 n := m + len(data)
4 if n > cap(slice) {
5 newSlice := make([]byte, (n+1)*2)
6 copy(newSlice, slice)
7 slice = newSlice
8 }
9 slice = slice[0:n]
10 copy(slice[m:n], data) // append data to the existing array
11 return slice
12}
除了 grow 流程之外，如果當前 array capacity 足夠的情況下，會將資料直接 append 到既有 array 空間中，並且將既有的 slice 回傳回去。
我們透過 objdump 出來的 machine code 來看 append function 具體的實作方式：
1108a245: 48 8d 73 01 leaq 1(%rbx), %rsi # length value += 1
2108a249: 48 8b 5c 24 40 movq 64(%rsp), %rbx
3108a24e: eb 00 jmp 0x108a250 <_main.main+0xb0>
4108a250: 48 8d 14 d8 leaq (%rax,%rbx,8), %rdx # %rax store the array pointer
5108a254: 48 8d 52 08 leaq 8(%rdx), %rdx # append 2 value to array
6108a258: 48 c7 02 02 00 00 00 movq $2, (%rdx) # append 2 value to array
7108a25f: 48 89 44 24 68 movq %rax, 104(%rsp) # update array pointer of slice descriptor
8108a264: 48 89 74 24 70 movq %rsi, 112(%rsp) # update length value of slice descriptor
9108a269: 48 89 4c 24 78 movq %rcx, 120(%rsp) # update capacity of slice descriptor
如果有觸發 growslice 擴充 array 空間，則會在建立新的 array 後，將資料 append 到新 array 中，並且更新 slice descriptor 的 array pointer 、length、以及 capacity；反之，如果原有的 array 空間足夠，則會將資料 append 到原有的 array 中，並調整 length 的數值。
這次我們一樣建立 nums 和 newNums 兩個 slice，並且搭配 append function，來觀察其底層 array 的變化：
1nums := make([]int, 0)
2nums = append(nums, 1)
3nums = append(nums, 2)
4nums = append(nums, 3)
5nums = append(nums, 4)
6nums = append(nums, 5)
7newNums := append(nums, 6)
8newNums = append(newNums, 7)
其中，我們觀察 append number 5 和 6 之間的 machine code：
1108a343: 49 c7 00 05 00 00 00 movq $5, (%r8)
2108a34a: 48 89 44 24 68 movq %rax, 104(%rsp) # nums struct
3108a34f: 48 89 54 24 70 movq %rdx, 112(%rsp)
4108a354: 48 89 4c 24 78 movq %rcx, 120(%rsp)
5108a359: 48 8d 72 01 leaq 1(%rdx), %rsi
6108a35d: 0f 1f 00 nopl (%rax)
7108a360: 48 39 f1 cmpq %rsi, %rcx
8108a363: 73 02 jae 0x108a367 <_main.main+0x1c7>
9108a365: eb 02 jmp 0x108a369 <_main.main+0x1c9>
10108a367: eb 27 jmp 0x108a390 <_main.main+0x1f0>
11108a369: 48 89 54 24 40 movq %rdx, 64(%rsp)
12108a36e: 48 89 c3 movq %rax, %rbx
13108a371: 48 89 cf movq %rcx, %rdi
14108a374: 48 8d 05 85 73 00 00 leaq 29573(%rip), %rax # setup args for growslice
15108a37b: 48 89 d1 movq %rdx, %rcx # setup args for growslice
16108a37e: 66 90 nop
17108a380: e8 fb 9f fb ff callq 0x1044380 <_runtime.growslice>
18108a385: 48 8d 73 01 leaq 1(%rbx), %rsi # %rbx is the return value from growslice
19108a389: 48 8b 54 24 40 movq 64(%rsp), %rdx # retrive the length of slice
20108a38e: eb 00 jmp 0x108a390 <_main.main+0x1f0>
21108a390: 48 8d 14 d0 leaq (%rax,%rdx,8), %rdx # append value to slice
22108a394: 48 c7 02 06 00 00 00 movq $6, (%rdx) # append value to slice
23108a39b: 48 89 84 24 80 00 00 00 movq %rax, 128(%rsp) # newNums
24108a3a3: 48 89 b4 24 88 00 00 00 movq %rsi, 136(%rsp)
25108a3ab: 48 89 8c 24 90 00 00 00 movq %rcx, 144(%rsp)
nums 和 newNums 是兩個 slice 變數，可以看到其表示的地址也有所不同，因此在 newNums = append(newNums, 7) 僅會更新 newNums 的 pointer、length、與 capacity。但是，即使他們的 length 和 capacity 的數值是各自儲存，卻有可能是共用同一個 array，這也會造成如果誤用 slice asign 和 append function，將有可能會覆蓋掉既有 array 中的資料，進而造成後續結果不如預期。
舉一個簡單的例子：
1nums := make([]int, 0)
2nums = append(nums, 1)
3nums = append(nums, 2)
4nums = append(nums, 3)
5nums = append(nums, 4)
6nums = append(nums, 5)
7
8newNums := append(nums, 6)
9nums = append(nums, 7)
10newNums2 := append(newNums, 8)
如果不清楚 Golang append function 的實作方式，有可能會誤以為上述的 code 其結果會是：
1nums = [1 2 3 4 5 7]
2newNums = [1 2 3 4 5 6]
3newNums2 = [1 2 3 4 5 6 8]
但實際上出來的結果會是：
1nums = [1 2 3 4 5 7]
2newNums = [1 2 3 4 5 7]
3newNums2 = [1 2 3 4 5 7 8]
其結果不如預期的原因在於 nums、newNums、newNums2 三個 slice 變數的 array pointer 都指向同一個 array，這也導致在執行 nums = append(nums, 7) 時，會將上一步 newNums := append(nums, 6) append 到 array 的 6 給覆蓋掉成 7，最終造成 6 資料消失的情況。
而要避免這樣的錯誤發生，就是要確保不同的 slice 擁有不同的 array pointer，可以透過新建立一個 newNums slice (因為其 pointer 指向的 array 地址也會不同)，並且將 nums slice 的資料複製到 newNums slice，再進行 append：
1nums := make([]int, 0)
2nums = append(nums, 1)
3nums = append(nums, 2)
4nums = append(nums, 3)
5nums = append(nums, 4)
6nums = append(nums, 5)
7
8newNums := make([]int, len(nums), len(nums)+1)
9copy(newNums, nums)
10newNums = append(newNums, 6)
11nums = append(nums, 7)
由於 nums 和 newNums 擁有獨立的 array 空間，所以會得出我們預期的結果。
Happy New Year!