用 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 中。
1
2
3
4
5
| type slice struct {
array unsafe.Pointer
len int
cap int
}
|
此時，如果我們要把一個既有的 slice assign 給新的 slice 變數：
1
2
3
4
5
6
7
8
| nums := make([]int, 0)
nums = append(nums, 1)
nums = append(nums, 2)
nums = append(nums, 3)
nums = append(nums, 4)
nums = append(nums, 5)
newNums := nums
|
上述的 code 看起來好像是新建立了一個新的 slice newNums，不過剛剛有提到 slice 是 descriptor struct 型態，因此 newNums 其實是複製 nums struct member 的值，以致 newNums 和 nums 擁有相同的 length、capacity、array pointer，所以雖然是兩個 slice，但底層卻是共用同一個 array 記憶體區段。
1
2
| fmt.Printf("%p \n", &newNums[0]) // 0xc000018030
fmt.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 記憶體、另一個指向舊的：
1
2
3
4
5
6
7
8
9
10
11
| nums := make([]int, 0)
nums = append(nums, 1)
newNums := nums // both of them share the same array pointer
fmt.Printf("%p \n", &newNums[0]) // 0xc000018030
fmt.Printf("%p \n", &nums[0]) // 0xc000018030
newNums = append(newNums, 2) // Growing slices, creating a new array area for newNums
fmt.Printf("%p \n", &newNums[0]) // 0xc000018050
fmt.Printf("%p \n", &nums[0]) // 0xc000018030
|
至於 array 擴充後的記憶體空間是怎麼計算的呢？我們可以從 Golang source code 的 runtime.growslice 找到答案：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
| func growslice(et *_type, old slice, cap int) slice {
newcap := old.cap
doublecap := newcap + newcap
if cap > doublecap {
newcap = cap
} else {
const threshold = 256
if old.cap < threshold {
newcap = doublecap
} else {
// Check 0 < newcap to detect overflow
// and prevent an infinite loop.
for 0 < newcap && newcap < cap {
// Transition from growing 2x for small slices
// to growing 1.25x for large slices. This formula
// gives a smooth-ish transition between the two.
newcap += (newcap + 3*threshold) / 4
}
// Set newcap to the requested cap when
// the newcap calculation overflowed.
if newcap <= 0 {
newcap = cap
}
}
}
}
|
在 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 實作流程概念：
1
2
3
4
5
6
7
8
9
10
11
12
| func AppendByte(slice []byte, data ...byte) []byte {
m := len(slice)
n := m + len(data)
if n > cap(slice) {
newSlice := make([]byte, (n+1)*2)
copy(newSlice, slice)
slice = newSlice
}
slice = slice[0:n]
copy(slice[m:n], data) // append data to the existing array
return slice
}
|
除了 grow 流程之外，如果當前 array capacity 足夠的情況下，會將資料直接 append 到既有 array 空間中，並且將既有的 slice 回傳回去。
我們透過 objdump 出來的 machine code 來看 append function 具體的實作方式：
1
2
3
4
5
6
7
8
9
| 108a245: 48 8d 73 01 leaq 1(%rbx), %rsi # length value += 1
108a249: 48 8b 5c 24 40 movq 64(%rsp), %rbx
108a24e: eb 00 jmp 0x108a250 <_main.main+0xb0>
108a250: 48 8d 14 d8 leaq (%rax,%rbx,8), %rdx # %rax store the array pointer
108a254: 48 8d 52 08 leaq 8(%rdx), %rdx # append 2 value to array
108a258: 48 c7 02 02 00 00 00 movq $2, (%rdx) # append 2 value to array
108a25f: 48 89 44 24 68 movq %rax, 104(%rsp) # update array pointer of slice descriptor
108a264: 48 89 74 24 70 movq %rsi, 112(%rsp) # update length value of slice descriptor
108a269: 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 的變化：
1
2
3
4
5
6
7
8
| nums := make([]int, 0)
nums = append(nums, 1)
nums = append(nums, 2)
nums = append(nums, 3)
nums = append(nums, 4)
nums = append(nums, 5)
newNums := append(nums, 6)
newNums = append(newNums, 7)
|
其中，我們觀察 append number 5 和 6 之間的 machine code：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
| 108a343: 49 c7 00 05 00 00 00 movq $5, (%r8)
108a34a: 48 89 44 24 68 movq %rax, 104(%rsp) # nums struct
108a34f: 48 89 54 24 70 movq %rdx, 112(%rsp)
108a354: 48 89 4c 24 78 movq %rcx, 120(%rsp)
108a359: 48 8d 72 01 leaq 1(%rdx), %rsi
108a35d: 0f 1f 00 nopl (%rax)
108a360: 48 39 f1 cmpq %rsi, %rcx
108a363: 73 02 jae 0x108a367 <_main.main+0x1c7>
108a365: eb 02 jmp 0x108a369 <_main.main+0x1c9>
108a367: eb 27 jmp 0x108a390 <_main.main+0x1f0>
108a369: 48 89 54 24 40 movq %rdx, 64(%rsp)
108a36e: 48 89 c3 movq %rax, %rbx
108a371: 48 89 cf movq %rcx, %rdi
108a374: 48 8d 05 85 73 00 00 leaq 29573(%rip), %rax # setup args for growslice
108a37b: 48 89 d1 movq %rdx, %rcx # setup args for growslice
108a37e: 66 90 nop
108a380: e8 fb 9f fb ff callq 0x1044380 <_runtime.growslice>
108a385: 48 8d 73 01 leaq 1(%rbx), %rsi # %rbx is the return value from growslice
108a389: 48 8b 54 24 40 movq 64(%rsp), %rdx # retrive the length of slice
108a38e: eb 00 jmp 0x108a390 <_main.main+0x1f0>
108a390: 48 8d 14 d0 leaq (%rax,%rdx,8), %rdx # append value to slice
108a394: 48 c7 02 06 00 00 00 movq $6, (%rdx) # append value to slice
108a39b: 48 89 84 24 80 00 00 00 movq %rax, 128(%rsp) # newNums
108a3a3: 48 89 b4 24 88 00 00 00 movq %rsi, 136(%rsp)
108a3ab: 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 中的資料，進而造成後續結果不如預期。
舉一個簡單的例子：
1
2
3
4
5
6
7
8
9
10
| nums := make([]int, 0)
nums = append(nums, 1)
nums = append(nums, 2)
nums = append(nums, 3)
nums = append(nums, 4)
nums = append(nums, 5)
newNums := append(nums, 6)
nums = append(nums, 7)
newNums2 := append(newNums, 8)
|
如果不清楚 Golang append function 的實作方式，有可能會誤以為上述的 code 其結果會是：
1
2
3
| nums = [1 2 3 4 5 7]
newNums = [1 2 3 4 5 6]
newNums2 = [1 2 3 4 5 6 8]
|
但實際上出來的結果會是：
1
2
3
| nums = [1 2 3 4 5 7]
newNums = [1 2 3 4 5 7]
newNums2 = [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：
1
2
3
4
5
6
7
8
9
10
11
| nums := make([]int, 0)
nums = append(nums, 1)
nums = append(nums, 2)
nums = append(nums, 3)
nums = append(nums, 4)
nums = append(nums, 5)
newNums := make([]int, len(nums), len(nums)+1)
copy(newNums, nums)
newNums = append(newNums, 6)
nums = append(nums, 7)
|
由於 nums 和 newNums 擁有獨立的 array 空間，所以會得出我們預期的結果。
Happy New Year!