Изменения функции append в Go 1.1813.04.2022 22:31

Совсем недавно произошел релиз 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
			}
		}
	}
	...
}

Если требуемая емкость cap больше двойного размера старой емкости old.cap, то требуемая емкость cap будет использована в качестве новой newcap .
В противном случае, если старая емкость old.cap меньше 1024. Конечной емкостью newcap будет увеличение в 2 раза старой емкости (old.cap), то есть newcap = doublecap
Если оба предыдущих условия не выполнены, а длина старого среза больше или равна 1024, окончательная емкость newcap начинается со старой емкости old.cap и циклически увеличивается на ¼ от исходной, где 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

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

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

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