preface

There has long been a saying about Slice’s expansion rules:

  • If the original slice capacity is less than 1024, the size of the original slice is doubled.

  • If the original slice capacity is greater than or equal to 1024, the slice capacity will be expanded 1.25 times until the required capacity is met.

The above two rules I believe you have seen in many places, the origin of the saying has been lost to know. Even in the interview experience that many people give, this is what they say to the interviewer.

Unfortunately, this is wrong.

case

If I had the following code, what would it say?

nums := make([]int.17)
nums = append(nums, 1)
fmt.Printf("cap: %d, len: %d\n".cap(nums), len(nums))
Copy the code

A lot of people would say, well, it’s easy, cap is 34, len is 18.

In fact, the real output is as follows:

cap: 36, len: 18
Copy the code

Wait a minute. It’s so different from what we know. Don’t worry, keep reading.

appendExpansion mechanism

Looking at the slice source code, you can find the following code:

go/src/runtime/slice.go

func growslice(et *_type, old slice, cap int) slice {
	/ /... Leave out some judgments
	newcap := old.cap
	doublecap := newcap + newcap
	if cap > doublecap {
		newcap = cap
	} else {
		if old.len < 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}}}/ /...
}
Copy the code

Cap indicates the minimum size required for slice, such as nums := make([]int, 16). If you want to append an element, the minimum size must be 17. Cap is 17.

The code rules are as follows:

  • When cap is greater than twice the original capacity, the new capacity becomes CAP;

  • When cap is less than two times of the original capacity and the original capacity is less than 1024, the new capacity is doubled.

  • If the CAP is less than twice the original capacity and the original capacity is greater than or equal to 1024, expand the cap by 1.25 times until the cap meets the requirements.

Up until now it’s been fine, pretty much what we used to think. However, if you look further, you can see the problem.

go/src/runtime/slice.go

func growslice(et *_type, old slice, cap int) slice {
	switch {
	case et.size == 1:
    	/ /...
		capmem = roundupsize(uintptr(newcap))
        / /...
	case et.size == sys.PtrSize:
    	/ /...
		capmem = roundupsize(uintptr(newcap) * sys.PtrSize)
        / /...
	case isPowerOfTwo(et.size):
        / /...
		capmem = roundupsize(uintptr(newcap) << shift)
        / /...
	default:
    	/ /...
		capmem = roundupsize(capmem)
        / /...}}Copy the code

Et. size is the number of bytes in a slice element. Roundupsize is used for memory alignment.

go/src/runtime/msize.go:

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)
}
Copy the code

Size_to_class8 and size_to_class are used to get spanClass.

Class_to_size is used to get the size of an object divided by a span.

As for the specific meaning and data content of the above variables, you can consult the source code to obtain.

After memory alignment, the resulting capacity is what we end up with.

conclusion

Slice’s alignment rules are not as simple as we think. It’s not just about doubling or expanding by 1.25, but also about the size of the required capacity and the original capacity, as well as the impact of memory alignment.

Specific alignment rules can be manually refer to the relevant source code, if there is incorrect or to supplement, welcome to exchange.