Post

golang append 관련 실험

Posted
By fransoaardi 6 min read

introduction

  • golang 의 slice, array 관련해서 몇가지 실험해보고 싶은것이 생겼다.
  • slice/array 관련된 내용들은 계속 작성할 예정이다.
  • 아래는 append 의 growth rate 는 어떻게될까? 에서 시작한 실험이다.

experiments

1. append 의 growth rate

  • append 는 capacity 가 넘어가는 경우에, slice internal 이 가리키던 array 를 새로 create 해서 이전에 가리키던 array 를 copy 하기 때문에 비효율적이라고 한다. buffer growth 가 얼마나 자주 일어나기에 비효율적이라고 하는것일까?
1
2
3
4
5
6
7
8
9

var x []int
for i := 0; i < 3; i++ {
    x = append(x, i)
}

y := make([]int, 3)
for i := 0; i < 3; i++ {
    y[i] = i
}

benchmark

  • 어떤 일들이 더 일어날지 예상이 되어서, benchmark 까지 하고싶진 않지만 일단은 비교해보는게 유의미할 것 같아서 아래와 같이 결과를 공유한다.
  • make 로 미리 선언하는게 더 빠르다. (당연한 결과이다)
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
27
28

package main

import (
	"testing"
)

func BenchmarkAddAppend(b *testing.B) {
	var x []int
	for i := 0; i < b.N; i++ {
		x = append(x, i)
	}
}

func BenchmarkMakeAndAdd(b *testing.B) {
	x := make([]int, b.N)
	for i := 0; i < b.N; i++ {
		x[i] = i
	}
}

// Output:
goos: darwin
goarch: amd64
BenchmarkAddAppend
BenchmarkAddAppend-16     	68318664	        19.1 ns/op
BenchmarkMakeAndAdd
BenchmarkMakeAndAdd-16    	1000000000	        10.5 ns/op
PASS

sample code

  • 아래와 같이 sample code 를 작성해보았다.
  • int32 slice 를 선언, lenth, capacity 둘다 0 인 상태로 append 를 이용해서 slice 에 담았다.
  • 매번 append 를 할때마다 slice 가 가리키는 array 의 0번 index 의 주소를 비교해서 buffer growth 가 일어났는지 확인해보았다.
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
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49

func appendTester() {
	x32 := []int32{}

	var a *int32
	var lastCap float64 = 1

	fmt.Printf("length: %v capacity: %v\n", len(x32), cap(x32))
	for i := 0; i < 100000; i++ {
		x32 = append(x32, int32(i))
		if a != &x32[0] {
			a = &x32[0]
			if i > 1 {
				fmt.Printf("slicePtr:(%p) arr[0]Ptr:(%p) arr[1]Ptr:(%p) len:(%v) cap:(%v) growthRate(%v)\n", &x32, &x32[0], &x32[1], len(x32), cap(x32), float64(cap(x32))/lastCap)
				lastCap = float64(cap(x32))
			} else {
				fmt.Printf("%p %p\t\t%v %v\n", &x32, &x32[0], len(x32), cap(x32))
			}
		}
    }
}

// Output:
slicePtr:(0xc0000a6020) arr[0]Ptr:(0xc0000b4030) arr[1]Ptr:(0xc0000b4034) len:(3) cap:(4) growthRate(4)
slicePtr:(0xc0000a6020) arr[0]Ptr:(0xc0000b6040) arr[1]Ptr:(0xc0000b6044) len:(5) cap:(8) growthRate(2)
slicePtr:(0xc0000a6020) arr[0]Ptr:(0xc0000ba040) arr[1]Ptr:(0xc0000ba044) len:(9) cap:(16) growthRate(2)
slicePtr:(0xc0000a6020) arr[0]Ptr:(0xc0000bc080) arr[1]Ptr:(0xc0000bc084) len:(17) cap:(32) growthRate(2)
slicePtr:(0xc0000a6020) arr[0]Ptr:(0xc0000be000) arr[1]Ptr:(0xc0000be004) len:(33) cap:(64) growthRate(2)
slicePtr:(0xc0000a6020) arr[0]Ptr:(0xc0000c0000) arr[1]Ptr:(0xc0000c0004) len:(65) cap:(128) growthRate(2)
slicePtr:(0xc0000a6020) arr[0]Ptr:(0xc0000c2000) arr[1]Ptr:(0xc0000c2004) len:(129) cap:(256) growthRate(2)
slicePtr:(0xc0000a6020) arr[0]Ptr:(0xc0000c4000) arr[1]Ptr:(0xc0000c4004) len:(257) cap:(512) growthRate(2)
slicePtr:(0xc0000a6020) arr[0]Ptr:(0xc0000c6000) arr[1]Ptr:(0xc0000c6004) len:(513) cap:(1024) growthRate(2)
slicePtr:(0xc0000a6020) arr[0]Ptr:(0xc0000c8000) arr[1]Ptr:(0xc0000c8004) len:(1025) cap:(1344) growthRate(1.3125)
slicePtr:(0xc0000a6020) arr[0]Ptr:(0xc0000cc000) arr[1]Ptr:(0xc0000cc004) len:(1345) cap:(1696) growthRate(1.2619047619047619)
slicePtr:(0xc0000a6020) arr[0]Ptr:(0xc0000d6000) arr[1]Ptr:(0xc0000d6004) len:(1697) cap:(2368) growthRate(1.3962264150943395)
slicePtr:(0xc0000a6020) arr[0]Ptr:(0xc0000e4000) arr[1]Ptr:(0xc0000e4004) len:(2369) cap:(3072) growthRate(1.2972972972972974)
slicePtr:(0xc0000a6020) arr[0]Ptr:(0xc0000ea000) arr[1]Ptr:(0xc0000ea004) len:(3073) cap:(4096) growthRate(1.3333333333333333)
slicePtr:(0xc0000a6020) arr[0]Ptr:(0xc0000ee000) arr[1]Ptr:(0xc0000ee004) len:(4097) cap:(5120) growthRate(1.25)
slicePtr:(0xc0000a6020) arr[0]Ptr:(0xc000100000) arr[1]Ptr:(0xc000100004) len:(5121) cap:(6816) growthRate(1.33125)
slicePtr:(0xc0000a6020) arr[0]Ptr:(0xc000114000) arr[1]Ptr:(0xc000114004) len:(6817) cap:(10240) growthRate(1.5023474178403755)
slicePtr:(0xc0000a6020) arr[0]Ptr:(0xc00011e000) arr[1]Ptr:(0xc00011e004) len:(10241) cap:(14336) growthRate(1.4)
slicePtr:(0xc0000a6020) arr[0]Ptr:(0xc00012c000) arr[1]Ptr:(0xc00012c004) len:(14337) cap:(18432) growthRate(1.2857142857142858)
slicePtr:(0xc0000a6020) arr[0]Ptr:(0xc00013e000) arr[1]Ptr:(0xc00013e004) len:(18433) cap:(24576) growthRate(1.3333333333333333)
slicePtr:(0xc0000a6020) arr[0]Ptr:(0xc000156000) arr[1]Ptr:(0xc000156004) len:(24577) cap:(30720) growthRate(1.25)
slicePtr:(0xc0000a6020) arr[0]Ptr:(0xc000174000) arr[1]Ptr:(0xc000174004) len:(30721) cap:(38912) growthRate(1.2666666666666666)
slicePtr:(0xc0000a6020) arr[0]Ptr:(0xc00019a000) arr[1]Ptr:(0xc00019a004) len:(38913) cap:(49152) growthRate(1.263157894736842)
slicePtr:(0xc0000a6020) arr[0]Ptr:(0xc0001ca000) arr[1]Ptr:(0xc0001ca004) len:(49153) cap:(61440) growthRate(1.25)
slicePtr:(0xc0000a6020) arr[0]Ptr:(0xc000206000) arr[1]Ptr:(0xc000206004) len:(61441) cap:(77824) growthRate(1.2666666666666666)
slicePtr:(0xc0000a6020) arr[0]Ptr:(0xc000252000) arr[1]Ptr:(0xc000252004) len:(77825) cap:(98304) growthRate(1.263157894736842)
slicePtr:(0xc0000a6020) arr[0]Ptr:(0xc0002b2000) arr[1]Ptr:(0xc0002b2004) len:(98305) cap:(122880) growthRate(1.25)

lessons learned

  • slice 의 pointer address 는 바뀌지 않았다. (0xc0000a6020 로 동일함)
  • slice internal 에서 slice 가 가리키는 array 는 1024까지 2의 거듭제곱 형태로 capacity 가 늘어났다. (2, 4, 8, 16, … 1024)
  • 1024 이후로 1.2 ~ 1.5 의 growth rate 를 가지며 capacity 가 늘어났다.
    • 1024 -> 1344 늘어난 것은, diff 가 320 인데, 이는 (1024 + 256) /4 인데, cap 이 어떤 값으로 지정되어 아래의 growslice func 가 호출되었는지 확인이 필요할것같다.

https://go.googlesource.com/go/+/go1.15.6/src/runtime/slice.go

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

newcap := old.cap
doublecap := newcap + newcap
if cap > doublecap {
	newcap = cap
} else {
	if old.len < 1024 {
		newcap = doublecap
	} else {
		// Check 0 < newcap to detect overflow
		// and prevent an infinite loop.
		for 0 < newcap && newcap < cap {
			newcap += newcap / 4
		}
		// Set newcap to the requested cap when
		// the newcap calculation overflowed.
		if newcap <= 0 {
			newcap = cap
		}
	}
}
  • arr[0] 과 arr[1] 의 address 를 비교해보니 int32 라서 4byte 씩 차이가 있는것을 확인할 수 있다(arr[0]Ptr:(0xc0000b4030) arr[1]Ptr:(0xc0000b4034)). 추가로, 작성자의 local machine 에서는 int 가 int64 와 동일하게 8byte 씩 늘어났다.
  • The Go Programming Language by 앨런 도노반, 브라이언 커니건 75p에 따르면 이 선택은 컴파일러에 달렸다.

    int 는 지금까지 가장 널리 쓰이는 숫자 타입이다. 이 두 타입은 같은 크기로 32 비트나 64 비트이지만, 그중 어떤 것일지에 대해서는 가정할 수 없다. 동일한 하드웨어에서라도 다른 컴파일러는 서로 다른 선택을 할 수 있다.

Wiki
golang
This post is licensed under CC BY 4.0 by the author.

Comments powered by Disqus.