GoのスライスのCapacityの増加を見積るサンプルコード

大きなスライスを扱うときは、ユーザー数依存だったりと正確なCapacityが分からないため、管理はGoにお任せしてしまいがちです。
せっかくなのでスライスのCapacityを越えてappendしたとき、GoがどれくらいCapacityを増加するのか調べてみようと思いました。
ですが、下記のサイトによくまとめられておりました。。。

https://qiita.com/yukiarrr/items/4fb8eb37aecf609a592e

というわけで、上記のサイトを参考にしつつGo内部のキャパシティ計算を行っているコードを抜粋して、手元で動かして試せるようにしてみました。
これでsliceのCapacity見積りができそうです。

※x86-64前提で抜粋しています。

https://play.golang.org/p/SSbrUelBjDF

package main

import (
	"fmt"
	"reflect"
)

const deBruijn64ctz = 0x0218a392cd3d5dbf

var deBruijnIdx64ctz = [64]byte{
	0, 1, 2, 7, 3, 13, 8, 19,
	4, 25, 14, 28, 9, 34, 20, 40,
	5, 17, 26, 38, 15, 46, 29, 48,
	10, 31, 35, 54, 21, 50, 41, 57,
	63, 6, 12, 18, 24, 27, 33, 39,
	16, 37, 45, 47, 30, 53, 49, 56,
	62, 11, 23, 32, 36, 44, 52, 55,
	61, 22, 43, 51, 60, 42, 59, 58,
}

func Ctz64(x uint64) int {
	x &= -x                       // isolate low-order bit
	y := x * deBruijn64ctz >> 58  // extract part of deBruijn sequence
	i := int(deBruijnIdx64ctz[y]) // convert to bit index
	z := int((x - 1) >> 57 & 64)  // adjustment if zero
	return i + z
}

func alignUp(n, a uintptr) uintptr {
	return (n + a - 1) &^ (a - 1)
}
func divRoundUp(n, a uintptr) uintptr {
	// a is generally a power of two. This will get inlined and
	// the compiler will optimize the division.
	return (n + a - 1) / a
}

const (
	_MaxSmallSize   = 32768
	smallSizeDiv    = 8
	smallSizeMax    = 1024
	largeSizeDiv    = 128
	_NumSizeClasses = 67
	_PageShift      = 13
	_PageSize       = 1 << _PageShift
)

var class_to_size = [_NumSizeClasses]uint16{0, 8, 16, 32, 48, 64, 80, 96, 112, 128, 144, 160, 176, 192, 208, 224, 240, 256, 288, 320, 352, 384, 416, 448, 480, 512, 576, 640, 704, 768, 896, 1024, 1152, 1280, 1408, 1536, 1792, 2048, 2304, 2688, 3072, 3200, 3456, 4096, 4864, 5376, 6144, 6528, 6784, 6912, 8192, 9472, 9728, 10240, 10880, 12288, 13568, 14336, 16384, 18432, 19072, 20480, 21760, 24576, 27264, 28672, 32768}
var size_to_class8 = [smallSizeMax/smallSizeDiv + 1]uint8{0, 1, 2, 3, 3, 4, 4, 5, 5, 6, 6, 7, 7, 8, 8, 9, 9, 10, 10, 11, 11, 12, 12, 13, 13, 14, 14, 15, 15, 16, 16, 17, 17, 18, 18, 18, 18, 19, 19, 19, 19, 20, 20, 20, 20, 21, 21, 21, 21, 22, 22, 22, 22, 23, 23, 23, 23, 24, 24, 24, 24, 25, 25, 25, 25, 26, 26, 26, 26, 26, 26, 26, 26, 27, 27, 27, 27, 27, 27, 27, 27, 28, 28, 28, 28, 28, 28, 28, 28, 29, 29, 29, 29, 29, 29, 29, 29, 30, 30, 30, 30, 30, 30, 30, 30, 30, 30, 30, 30, 30, 30, 30, 30, 31, 31, 31, 31, 31, 31, 31, 31, 31, 31, 31, 31, 31, 31, 31, 31}
var size_to_class128 = [(_MaxSmallSize-smallSizeMax)/largeSizeDiv + 1]uint8{31, 32, 33, 34, 35, 36, 36, 37, 37, 38, 38, 39, 39, 39, 40, 40, 40, 41, 42, 42, 43, 43, 43, 43, 43, 44, 44, 44, 44, 44, 44, 45, 45, 45, 45, 46, 46, 46, 46, 46, 46, 47, 47, 47, 48, 48, 49, 50, 50, 50, 50, 50, 50, 50, 50, 50, 50, 51, 51, 51, 51, 51, 51, 51, 51, 51, 51, 52, 52, 53, 53, 53, 53, 54, 54, 54, 54, 54, 55, 55, 55, 55, 55, 55, 55, 55, 55, 55, 55, 56, 56, 56, 56, 56, 56, 56, 56, 56, 56, 57, 57, 57, 57, 57, 57, 58, 58, 58, 58, 58, 58, 58, 58, 58, 58, 58, 58, 58, 58, 58, 58, 59, 59, 59, 59, 59, 59, 59, 59, 59, 59, 59, 59, 59, 59, 59, 59, 60, 60, 60, 60, 60, 61, 61, 61, 61, 61, 61, 61, 61, 61, 61, 61, 62, 62, 62, 62, 62, 62, 62, 62, 62, 62, 63, 63, 63, 63, 63, 63, 63, 63, 63, 63, 63, 63, 63, 63, 63, 63, 63, 63, 63, 63, 63, 63, 64, 64, 64, 64, 64, 64, 64, 64, 64, 64, 64, 64, 64, 64, 64, 64, 64, 64, 64, 64, 64, 65, 65, 65, 65, 65, 65, 65, 65, 65, 65, 65, 66, 66, 66, 66, 66, 66, 66, 66, 66, 66, 66, 66, 66, 66, 66, 66, 66, 66, 66, 66, 66, 66, 66, 66, 66, 66, 66, 66, 66, 66, 66, 66}

func roundupsize(size uintptr) uintptr {
	if size < _MaxSmallSize {
		if size <= smallSizeMax-8 {
			return uintptr(class_to_size[size_to_class8[divRoundUp(size, smallSizeDiv)]])
		} else {
			return uintptr(class_to_size[size_to_class128[divRoundUp(size-smallSizeMax, largeSizeDiv)]])
		}
	}
	if size+_PageSize < size {
		return size
	}
	return alignUp(size, _PageSize)
}

func isPowerOfTwo(x uintptr) bool {
	return x&(x-1) == 0
}

const MaxUintptr = ^uintptr(0)
const PtrSize = 8

func MulUintptr(a, b uintptr) (uintptr, bool) {
	if a|b < 1<<(4*PtrSize) || a == 0 {
		return a * b, false
	}
	overflow := b > MaxUintptr/a
	return a * b, overflow
}

func calcNewCap(size uintptr, oldcap, cap int) int {
	var capmem uintptr
	newcap := oldcap
	doublecap := newcap + newcap

	if cap > doublecap {
		newcap = cap
	} else {
		if oldcap < 1024 {
			newcap = doublecap
		} else {
			for 0 < newcap && newcap < cap {
				newcap += newcap / 4
			}
			if newcap <= 0 {
				newcap = cap
			}
		}
	}

	switch {
	case size == 1:
		capmem = roundupsize(uintptr(newcap))
		newcap = int(capmem)
	case size == PtrSize:
		capmem = roundupsize(uintptr(newcap) * PtrSize)
		newcap = int(capmem / PtrSize)
	case isPowerOfTwo(size):
		var shift uintptr
		shift = uintptr(Ctz64(uint64(size))) & 63
		capmem = roundupsize(uintptr(newcap) << shift)
		newcap = int(capmem >> shift)
	default:
		fmt.Println("default")
		capmem, _ = MulUintptr(size, uintptr(newcap))
		capmem = roundupsize(capmem)
		newcap = int(capmem / size)
	}
	return newcap
}

func main() {
	// int型以外で試す場合は以下のコードの型とappendする値を変更する
	var val int
	slice := make([]int, 0, 2)
	appendValue := 1

	rtype := reflect.TypeOf(val)
	prevCap := cap(slice)
	for i := 0; cap(slice) < 100000; i += 1 {
		if cap(slice) != prevCap {
			newcap := calcNewCap(rtype.Size(), prevCap, len(slice))
			fmt.Printf("Old Cap=%d, Actual New Cap=%d, Calc New Cap=%d\n", prevCap, cap(slice), newcap)
			fmt.Printf("Actual Diff=%d, Calc Diff=%d\n", cap(slice)-prevCap, newcap-prevCap)
			fmt.Println("---------------------------")
			prevCap = cap(slice)
		}
		slice = append(slice, appendValue)
	}
}