Изменения функции append в Go 1.18

Совсем недавно произошел релиз Go 1.18, гвоздем программы стали дженерики. Но про этот факт уже достаточно статей, а мне нечего к ним добавить. Однако, я не смог найти ни одного поста про этот кусочек релиза:

The built-in function append now uses a slightly different formula when deciding how much to grow a slice when it must allocate a new underlying array. The new formula is less prone to sudden transitions in allocation behavior.

Итак под капотом append немного поменялась формула увеличения среза, а именно когда нужно выделить новый базовый массив. И она менее подвержена внезапным изменениям в поведении распределения. И мне хотелось бы привлечь ваше внимание к этому изменению)

Как было раньше?

func growslice(et *_type, old slice, cap int) slice {
    ...

	if cap < old.cap {
		panic(errorString("growslice: cap out of range"))
	}

	if et.size == 0 {
		// append should not create a slice with nil pointer but non-zero len.
		// We assume that append doesn't need to preserve old.array in this case.
		return slice{unsafe.Pointer(&zerobase), old.len, cap}
	}

	newcap := old.cap
	doublecap := newcap + newcap

	if cap > doublecap {
		newcap = cap
	} else {
		if old.cap < 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
			}
		}
	}
	...
}

1. Если требуемая емкость cap больше двойного размера старой емкости old.cap, то требуемая емкость cap будет использована в качестве новой newcap .

2. В противном случае, если старая емкость old.cap меньше 1024. Конечной емкостью newcap будет увеличение в 2 раза старой емкости (old.cap), то есть newcap = doublecap

3. Если оба предыдущих условия не выполнены, а длина старого среза больше или равна 1024, окончательная емкость newcap начинается со старой емкости old.cap и циклически увеличивается на 1/4 от исходной, где newcap = old.cap, для {newcap + = newcap / 4} до тех пор, пока конечной емкостью newcap не станет емкость большая требуемой емкости cap, то есть newcap >= cap

Нарушение монотонности

Старая формула приводила к некоторым странностям, ниже пример демонстрирующий неожиданное изменение в поведении распределения.

func main() {
	for i := 0; i < 2000; i += 100 {
		fmt.Println(i, cap(append(make([]bool, i), true)))
	}
}

0 8
100 208
200 416
300 640
400 896
500 1024
600 1280
700 1408
800 1792
900 2048
1000 2048
1100 1408 <- нарушение монотонности (предыдущее значение больше) 
1200 1536
1300 1792
1400 1792
1500 2048
1600 2048
1700 2304
1800 2304
1900 2688
1000 2048

https://go.dev/play/p/RJbEkmFsPKM?v=goprev

Новый порядок

Изменения в формуле произошли с 20 строчки в примере

Было:

	if old.cap < 1024 {
		newcap = doublecap
	} else {
		// Check 0 < newcap to detect overflow
		// and prevent an infinite loop.
		for 0 < newcap && newcap < cap {
			newcap += newcap / 4
		}

Стало:

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
		}

Итак теперь порог 256 , что примерно соответствовует общему количеству перераспределений при добавлении, чтобы в конечном итоге сделать очень большой срез. (Выделяется меньше при добавлении к емкостям [256,1024] и больше с емкостями [1024,...]).

А увеличение среза сменилось с newcap += newcap / 4 на newcap += (newcap + 3*threshold) / 4. Что сделало увеличение емкости более плавным.

starting cap    growth factor
256             2.0
512             1.63
1024            1.44
2048            1.35
4096            1.30

Вот так поменялся вывод из блока "Нарушение монотонности":

0 8
100 208
200 416
300 576
400 704
500 896
600 1024
700 1152
800 1280
900 1408
1000 1536
1100 1792
1200 1792
1300 2048
1400 2048
1500 2304
1600 2304
1700 2688
1800 2688
1900 2688

Также прикрепляю ссылку на обсуждение неожиданного поведения старой алгоритма формулы, в ходе которого пришли к изменениям в формуле:

https://groups.google.com/g/golang-nuts/c/UaVlMQ8Nz3o

Ниже ссылки для ознакомления с изменениями:

https://tip.golang.org/doc/go1.18

https://github.com/golang/go/blob/master/src/runtime/slice.go