Changes to the append function in Go 1.18

Most recently, Go 1.18 was released, and generics became the highlight of the program. But there are already enough articles about this fact, and I have nothing to add to them. However, I could not find any post about this piece of release:

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.

So, under the hood of append, the formula for increasing the slice has changed a bit, namely when you need to allocate a new base array. And it is less susceptible to sudden changes in distribution behavior. And I would like to draw your attention to this change)

As it was before?

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
			}
		}
	}
	...
}

If the required capacity cap more than double the size of the old container old.capthen the required capacity cap will be used as new newcap .
Otherwise, if the old capacity old.cap less than 1024. Final capacity newcap there will be a 2-fold increase in the old capacity (old.cap), that is newcap = doublecap
If both previous conditions are not met and the length of the old slice is greater than or equal to 1024, the final capacity newcap starts from the old container old.cap and cyclically increases by 1/4 of the original, where newcap = old.cap, для {newcap + = newcap / 4} until the final capacity newcap the capacity will not become larger than the required capacity capi.e newcap >= cap

Breaking monotony

The old formula led to some oddities, below is an example showing an unexpected change in distribution behavior.

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

New order

Changes in the formula occurred from line 20 in the example

It was:

	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
		}

It became:

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
		}

So now the threshold 256 , which roughly corresponds to the total number of reallocations when adding, to end up with a very large slice. (Released less when added to containers [256,1024] and more with containers [1024,…]).

And the cutoff magnification changed from newcap += newcap / 4 on the newcap += (newcap + 3*threshold) / 4. Which made the capacity increase smoother.

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

This is how the output from the “Violation of monotonicity” block has changed:

I also attach a link to a discussion of the unexpected behavior of the old formula algorithm, during which they came to changes in the formula:

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