[Go] slice 크기 조정 - append() 함수의 숨겨진 내부 동작

최근에 golang을 살펴보는 중 slice에서의 재밌는 동작을 하나 보게 되었다. 

 

보통 동적 배열에 새로운 요소를 계속 추가하다가 요소 개수가 다 차면 두 배로 길이를 늘려주고 복사하여 기존 내용을 넣어준다고 알고 있다. Go에서도 slice에 대한 내용 중 비슷하게 두배로 늘려준다는 내용을 발견했다. 

 

하지만 재밌는 점은 실제 1000개의 요소를 slice에 append하면서 append한 결과의 slice capacity를 보니 2의 승수를 따르지 않는 구간이 나타난다는 점이었다. 

 

내 예상대로면 0짜리 capacity에 새롭게 요소를 넣어주는 동작을 1000번 반복한다면 

아래와 같이 slice의 capacity를 늘려주는 동작을 할 것이라고 예상했다. 

1 2 4 8 16 64 128 256 512 1024 

즉 10번의 리사이징과 1024의 capacity그리고 1000 짜리 length를 가질 줄 알았다. 

 

하지만 결과는 예상과 달랐다.

 

대신 아래와 같은 capacity 리사이징 결과를 얻었다. 

1 2 4 8 16 32 64 128 256 512 848 1280 

총 12번의 리사이징이었다.

여기서 848과 1280은 왜 등장한걸까? 궁금했다.  512에서 1024로 넘어갈 줄 알았는데 그러지 않았다. 

그래서 왜 2의 배수를 따르지 않고 해당 넘버가 나왔는지에 대해 알아보았다. 

---

 

리사이징은 append함수로 새로운 요소를 집어넣었지만 공간이 부족할때 새로 집어넣을때 하게되는 동작이다. 

 

append함수는 go표준 라이브러리 내 builtin.go에 정의되어있다. 

 

 

 

재밌는건 이곳에 append함수의 func 정의만 있을 뿐 구현체인 함수 바디는 없다. 

 

찾아보니 golang은 builtin.go에 func 정의만 해두고 go 컴파일러가 해당 정의를 가져다가 사용한다고 한다. 그래서 이 경우에는 go표준 라이브러리 내 runtime 경로를 살피보면 된다. 그리고 runtime 경로를 살피면 slice.go를 발견할 수 있다. 

slice와 관련된 기능이 이곳에 정의된 것이다. 

 

slice.go를 보면 누가봐도 slice 리사이징을 할 것 같은 함수가 바로 보인다. 

 

바로 growSlice 함수이다. 

 

해당 함수를 보면 아주 재밌는 코드와 주석이 있다. 

 

아래와 같다. 참고로 위 아래 자잘한 코드는  (...)처리했다. 

 

func growslice(oldPtr unsafe.Pointer, newLen, oldCap, num int, et *_type) slice {
...
...
	newcap := oldCap
	doublecap := newcap + newcap
	print("doubleCap: ", doublecap, "\n")
    if newLen > doublecap {
            newcap = newLen
        } else {
            const threshold = 256
            if oldCap < threshold {
                newcap = doublecap
            } else {
                // Check 0 < newcap to detect overflow
                // and prevent an infinite loop.
                for 0 < newcap && newcap < newLen {
                    // Transition from growing 2x for small slices
                    // to growing 1.25x for large slices. This formula
                    // gives a smooth-ish transition between the two.
                    print("Here?\n")
                    newcap += (newcap + 3*threshold) / 4
                }
...
...

 

 

코드를 보면 작은 사이즈의 slice의 경우에는 2x씩 커지지만 큰 slice의 경우에는 1.25x만큼 커지도록 즉 smooth하게 자라나도록 한다고 써져있다. 그래서 newcap += (newcap + 3 * threshold) / 4가 있는 것이다. 사실 이 코드가 정확히 1.25x만큼 커지는 것은 아니고 어느정도 slice 사이즈가 커질수록 1.25라는 수치에 근접해진다. 

 

여기서 newcap 변수가 바로 새로 할당할 리사이징 slice의 capacity 값이다. 

그리고 아까 위에서 말한대로 1024가 아니라 1280이라는 값이 나왔길래 이 부분을 값을 찍어보면서 확인해보았다. 그런데 여기서 얻은 newcap 값이 1280이 아니게 나왔다. 대신 1252라는 값이 나왔다. 

 

그렇다면 1280 capacity는 또 한번의 보정을 거친 것이라고 추측할 수 있었다. 

 

해당 함수(growSlice)의 아래쪽에서 이와 같은 보정과 관련된 코드를 발견했다. 

 

(이쪽에도 사실 글과 무관한 꽤나 볼만한 아주 많다. 하지만 보다가 하루가 다 갈것같아서 이 글에 대한 내용까지만 정리해두고 나머진 이후에 좀 더 살펴볼까한다.)

 

switch {
	case et.Size_ == 1:
		print("1\n")
		lenmem = uintptr(oldLen)
		newlenmem = uintptr(newLen)
		capmem = roundupsize(uintptr(newcap))
		overflow = uintptr(newcap) > maxAlloc
		newcap = int(capmem)
		println("capmem: ", capmem, "\n")
		println("goarch.PtrSize: ", goarch.PtrSize)
		println("newcap: ", newcap, "\n")
	case et.Size_ == goarch.PtrSize:
		print("2\n")
		lenmem = uintptr(oldLen) * goarch.PtrSize
		newlenmem = uintptr(newLen) * goarch.PtrSize
		capmem = roundupsize(uintptr(newcap) * goarch.PtrSize)
		overflow = uintptr(newcap) > maxAlloc/goarch.PtrSize
		println("capmem: ", capmem, "\n")
		println("goarch.PtrSize: ", goarch.PtrSize)
		newcap = int(capmem / goarch.PtrSize)
		print("newcap: ", newcap, "\n")

 

 

위 같은 코드가 있는데, 여기보면 capmen을 계산할때 roundupsize라는 함수를 통해 할당하고 있다. 

그리고 맨 밑에서 다시 newcap을 int(capmem/ goarch.PtrSize)를 통해서 재할당한다. 그러므로 capmem을 포인터 사이즈(64비트 머신에서 8바이트)로 나눈 값이 최종 newcap이 되는 것이다. 

(미리 말해두자면 여기서 찍는 최종 newcap값은 1280이 나온다.)

 

 

그래서 roundupsize 함수의 구현체를 보면 다음과 같다. 

 

// Returns size of the memory block that mallocgc will allocate if you ask for the size.
func roundupsize(size uintptr) uintptr {
	if size < _MaxSmallSize {
		print("roundupsize 1\n")
		if size <= smallSizeMax-8 {
			print("roundupsize 1 - a size: ", size, "\n")
			return uintptr(class_to_size[size_to_class8[divRoundUp(size, smallSizeDiv)]])
		} else {
			print("roundupsize 1 - a size: ", size, "\n")
			return uintptr(class_to_size[size_to_class128[divRoundUp(size-smallSizeMax, largeSizeDiv)]])
		}
	}
	if size+_PageSize < size {
		print("roundupsize 2\n")
		return size
	}
	print("roundupsize 3\n")
	return alignUp(size, _PageSize)
}

 

 

여기서 divRoundUp은 항상 첫번째 인자를 두번째 인자로 나눴을때  나누어떨어지지 않으면 항상 올림 값이 되도록 하는 코드이다. 

이후 size_to_class8 배열에서 값을 가져오고, 가져온 값을 class_to_size 배열의 인덱스 값으로 사용한다. 

이렇게 값을 만들어서 리턴해주는 것이다. 

 

이 과정은 메모리 블락 사이즈로 만들어서 주는 코드라고 보면 된다. (일종의 최적화 코드인 듯하다)

 

그래서 이 코드로 나온 값이 10240이고 해당 값을 외부에서 goarch.PtrSize인 8로 나눠줘서 최종적으로 newcap이 1280이 나오는 것이다. 그리고 이 값이 slice의 capacity가 되는 것이다. 

 

참고로 이 배열의(class_to_size) 인덱스에 해당하는 값 정의는 sizeclasses.go에 정의된 내용을 따르는 것으로 golang에서 사전에 정의된 값에 따라 나오는 결과이다. 이미 모든 값을 정해놓았다. 그래서 golang에서 정의된 규칙에 따라서 이와 같이 slice capacity가 정해지는 것이고 이는 이는 아마 최적화와 관련이 있을 것이라고 생각된다. 왜냐면 해당 파일에 오브젝트 사이즈에 따른 낭비율 등이 미리 정의되어있고 그에 따른 값을 던져주는 것이기 때문이다. 

 

꽤나 재밌는 과정이었다. 

 

간단한 디버깅을 해보다가 여기까지 오게 되었는데 golang에는 재밌는 내용이 많은 것 같다. 

 

잘못된 내용이 있으면 의견바란다.