Изменения функции 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