What is a slice

Slice is essentially a dynamic array, similar to Java’s ArrayList. Unlike ordinary arrays, slice is dynamically long. As the size increases, the size of the array increases

The data structure

The data structure can be seen under Runtime /slice.go

type slice struct {
	array unsafe.Pointer
	len   int
	cap   int
}
Copy the code

There are three parameters

  • Array Pointer to an array
  • Len is the current length
  • Cap Specifies the size of the array

Define the way

//len,cap
a := make([]int.0.10)
//
b := []int{}
//
b := *new([]int)
Copy the code

All three definitions are essentially allocating memory by calling the mallocgc() method, but the details are different in the middle

Source code analysis

First look at the source code for the make definition method

func makeslice(et *_type, len.cap int) unsafe.Pointer {
	mem, overflow := math.MulUintptr(et.size, uintptr(cap))
	if overflow || mem > maxAlloc || len < 0 || len > cap {
		mem, overflow := math.MulUintptr(et.size, uintptr(len))
		if overflow || mem > maxAlloc || len < 0 {
			panicmakeslicelen()
		}
		panicmakeslicecap()
	}

	return mallocgc(mem, et, true)}Copy the code

It looks very complicated, but in fact all the previous errors, such as length less than 0, capacity less than length

The most important is the last sentence, allocating memory.

Look at the source code for the last two definitions

func newobject(typ *_type) unsafe.Pointer {
	return mallocgc(typ.size, typ, true)}Copy the code

They’re all calling this method

Add data

The append method is used to add data. Unlike Java’s add() method, it returns a new slice object with a different address each time. However, the address of the original index location remains unchanged until expansion.

capacity

When it comes to adding data, it comes to expanding.

Look directly at the source runtime.growslice

newcap := old.cap
	doublecap := newcap + newcap
	// The cap is old.cap+ the number of new elements
	if cap > doublecap {
		newcap = cap
	} else {
		if old.len < 1024 {
			newcap = doublecap
		} else {
			for newcap < cap {
				newcap += newcap / 4}}}Copy the code

This is the go expansion rule, which is a little complicated to explain

In conclusion:

The normal thing is to double up

Cap is the size of the old array + the number of newly added elements, i.e. at least the expanded value

If the doubling does not reach the cap, the new array will be the cap

If the double expansion reaches this minimum, the capacity is expanded based on whether the number of elements in the old array is less than 1024

If the value is less than 1024, double the capacity.

If the cap is greater than or equal to 1024, iterate by 1.25 until the cap is reached or exceeded

For example

s := []int{1.2}
s = append(s,4.5.6)
fmt.Printf("%d %d".len(s),cap(s))
Copy the code

If you follow the normal understanding of double capacity, it should output 5,8, but it does not

Because 2 + 3 > 4 (oldcap + valueNum > 2 * oldcap)

So newcap should be 5

Memory alignment

If you thought the last example output was 5,5, you’re wrong

It actually outputs 5,6

The reason why there’s a 6 is because there’s a memory alignment mechanism, right

The following code is too long to look at

	switch {
	case et.size == 1:
		lenmem = uintptr(old.len)
		newlenmem = uintptr(cap)
		capmem = roundupsize(uintptr(newcap))
		overflow = uintptr(newcap) > maxAlloc
		newcap = int(capmem)
	case et.size == sys.PtrSize:
		lenmem = uintptr(old.len) * sys.PtrSize
		newlenmem = uintptr(cap) * sys.PtrSize
		capmem = roundupsize(uintptr(newcap) * sys.PtrSize)
		overflow = uintptr(newcap) > maxAlloc/sys.PtrSize
		newcap = int(capmem / sys.PtrSize)
	case isPowerOfTwo(et.size):
		var shift uintptr
		if sys.PtrSize == 8 {
			// Mask shift for better code generation.
			shift = uintptr(sys.Ctz64(uint64(et.size))) & 63
		} else {
			shift = uintptr(sys.Ctz32(uint32(et.size))) & 31
		}
		lenmem = uintptr(old.len) << shift
		newlenmem = uintptr(cap) << shift
		capmem = roundupsize(uintptr(newcap) << shift)
		overflow = uintptr(newcap) > (maxAlloc >> shift)
		newcap = int(capmem >> shift)
	default:
		lenmem = uintptr(old.len) * et.size
		newlenmem = uintptr(cap) * et.size
		capmem, overflow = math.MulUintptr(et.size, uintptr(newcap))
		capmem = roundupsize(capmem)
		newcap = int(capmem / et.size)
	}
Copy the code

The most important thing above is

roundupsize(uintptr(newcap))
Copy the code

The memory alignment will be based on et.size, but the size will change from 5 to 6

Why memory alignment

Somewhat similar to alignment padding for JVM objects

Baidu explained as

  • Platform (portability) reason: Not all hardware platforms can access arbitrary data at arbitrary addresses. For example, a specific hardware platform only allows a specific type of data to be obtained at a specific address. Otherwise, exceptions may occur
  • Performance reasons: If unaligned memory is accessed, the CPU makes two memory visits and takes an additional clock cycle to process alignment and computation. Memory that is aligned by itself requires only one access to complete the read action

My understanding is that if the alignment is not correct, it is difficult to read the content at one time, and you need to delete the content read. For 64-bit systems, it is more efficient to read every 8 bits.

If they are not aligned, they can either read one bit only. Or it reads every 8 bits, and if it doesn’t align, it cuts, which is less efficient

conclusion

I am on the way to learn Java go, there are some excerpts and their own understanding of the article, there are inevitably negligence and mistakes, I hope you can correct