What are the similarities and differences between arrays and slices

Slice’s underlying data is an array. Slice is a wrapper around an array that describes a fragment of an array. Both can access individual elements with subscripts.

Arrays are of fixed length and cannot be changed once the length is defined. In Go, arrays are uncommon because their length is part of a type, limiting their expressiveness. For example, [3]int and [4]int are different types.

Slicing is very flexible and can be dynamically expanded. The type of slice has nothing to do with the length.

An array is a contiguous piece of memory. Slice is actually a structure containing three fields: length, capacity, and the underlying array. It’s a dynamic array, its length is not fixed, we can add elements to the slice, it will automatically expand when the capacity is insufficient.

// runtime/slice.go
type slice struct {
    array unsafe.Pointer // Element pointer
    len   int / / the length
    cap   int / / capacity
}
Copy the code

Slice’s data structure is as follows:

Note that the underlying array can be pointed to by multiple slices at the same time, so operations on elements of one slice can affect other slices.

case

package main
import "fmt"
func main(a) {
    slice := []int{0.1.2.3.4.5.6.7.8.9}
    s1 := slice[2:5]
    s2 := s1[2:6:7]
    s2 = append(s2, 100)
    s2 = append(s2, 200)
    s1[2] = 20
    fmt.Println(s1)
    fmt.Println(s2)
    fmt.Println(slice)
}
Copy the code

Results:

[2 3 20]
[4 5 6 7 100 200]
[0 1 2 3 20 5 6 7 100 9]
Copy the code

S1 runs from slice index 2 (closed interval) to index 5 (open interval, where the element actually fetches to index 4), with a length of 3 and a capacity of 8, which defaults to the end of the array. S2 goes from index 2 (closed interval) of S1 to index 6 (open interval, the element is actually taken to index 5), and has a capacity of 5 to index 7 (open interval, the element is actually taken to index 6).

Then, tos2Append element 100 to the end:

s2 = append(s2, 100)
Copy the code

S2 has just enough capacity. However, this modifies the element at the corresponding position in the original array. This change is visible in both Slice and S1.

Once again tos2Append element 200:

s2 = append(s2, 100)
Copy the code

At this point, the capacity of S2 is insufficient and it needs to be expanded. So S2 starts all over again, replicating the original elements in new locations to expand its capacity. In addition, in order to cope with the potential expansion of append in the future, S2 will leave some more buffer during the expansion and expand the new capacity to twice the original capacity, that is, 10.

Finally, modifys1Element at position 2 index:

s1[2] = 20
Copy the code

This time only affects the elements at the corresponding positions in the original array. It doesn’t affect S2 anymore, she’s already gone.

prints1“, will only print outs1Elements within length. So, only three elements are printed, even though its underlying array has more than three elements.

Copy section

When we copy a slice using copy(a, b), either compile-time or run-time, runtime.memmove copies the contents of the entire memory block to the target memory region.

Runtime.memmove provides better performance than copying elements sequentially. Note that the memory of a block copy occupies a large number of resources. Therefore, you must pay attention to the impact on performance when performing a copy operation on a large slice.

How does the size of slices grow

Expansion is usually not caused until an element is appended to slice. The append element calls the append function.

Let’s look at the prototype of the append function:

func append(slice []Type, elems ... Type) []Type
Copy the code

The append function takes variable length arguments, so you can append multiple values to slice, and you can use… To pass a slice, append a slice directly.

slice = append(slice, elem1, elem2)
slice = append(slice, anotherSlice...)
Copy the code

The append function returns a new slice, and the Go compiler does not allow calls to append without using the return value.

append(slice, elem1, elem2)
append(slice, anotherSlice...)
Copy the code

So the above usage is wrong and will not compile. Slice moves to the new memory location and the length of the new underlying array increases so that new elements can be placed. At the same time, the length of the new underlying array, the size of the new slice, is reserved to buffer for future append operations. Otherwise, every time an element is added, it will be migrated and the cost will be too high. The size of buffer reserved for a new slice is regular. Most articles on the Internet describe it this way:

When the original slice capacity is less than 1024, the new slice capacity is doubled. When the original slice capacity exceeds 1024, the new slice capacity becomes 1.25 times of the original capacity.

The above rule is wrong

When adding elements to slice, the growslice function is called if there is not enough space:

func growslice(et *_type, old slice, cap int) slice {
    / /...
    newcap := old.cap
    doublecap := newcap + newcap
    if cap > doublecap {
        newcap = cap
    } else {
        if old.len < 1024 {
            newcap = doublecap
        } else {
            for newcap < cap {
                newcap += newcap / 4}}}/ /...
    capmem = roundupsize(uintptr(newcap) * ptrSize)
    newcap = int(capmem / ptrSize)
}
Copy the code

If you just look at the first half, newCap’s rule is true in various articles on the web. In reality, the second half also does a memory alignment for NewCap, which is related to the memory allocation strategy. After memory alignment, the size of the new slice should be greater than or equal to 2 or 1.25 times the size of the old slice.

After that, the Go memory manager requests memory, copies the data from the old slice, and adds the append elements to the new underlying array.

Finally, a new slice is returned to the growslice caller with the same length but an increased capacity.

【 extension 1】

package main
import "fmt"
func main(a) {
    s := []int{5}
    s = append(s, 7)
    s = append(s, 9)
    x := append(s, 11)
    y := append(s, 12)
    fmt.Println(s, x, y)
}
Copy the code
code Corresponding state of slice
s := []int{5} S has only one element,[5]
s = append(s, 7) S expands. The capacity becomes 2.[5, 7)
s = append(s, 9) S expands the capacity to 4.[5, 7, 9]. Notice, in this case, s has length 3 and only has 3 elements
x := append(s, 11) Since the underlying array of S still has space, it does not expand. So the underlying array becomes[5, 7, 9, 11]. Notice that s is equal to[5, 7, 9], the capacity is 4; x =[5, 7, 9, 11]And the capacity is 4. Here s doesn’t change
y := append(s, 12) Here we append the element to the end of the s element. Since s has length 3 and capacity 4, we simply add 12 to the underlying array index 3. Result: S =[5, 7, 9], y =[5, 7, 9, 12], x =[5, 7, 9, 12], the length of x and y are 4, and the capacity is also 4

So the final execution result of the program is:

[5 7 9] [5 7 9 12] [5 7 9 12]
Copy the code

Note that the append function returns a brand new slice and has no effect on the incoming slice.

【 extension 2】

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

The results are as follows:

len=5.cap=6
Copy the code

If the original slice length is less than 1024, the capacity is doubled each time, as summarized in various articles on the Internet. When you add element 4, the capacity becomes 4; Element 5 is added unchanged; Adding element 6 doubles the capacity to 8.

The result of the above code is:

len=5.cap=8
Copy the code

This is wrong! Let’s take a closer look at why this is so, and bring up the code again:

func growslice(et *_type, old slice, cap int) slice {
    / /...
    newcap := old.cap
    doublecap := newcap + newcap
    if cap > doublecap {
        newcap = cap
    } else {
        / /...
    }
    / /...
    capmem = roundupsize(uintptr(newcap) * sys.PtrSize)
    newcap = int(capmem / sys.PtrSize)
}
Copy the code

This function takes, in turn, the type of the element, the old slice, and the minimum size of the new slice.

In this example, s has only 2 elements, len and cap are both 2. After append three elements, the length is 5, and the minimum size is 5, i.e. when growslice is called, the third argument passed in should be 5. The cap = 5. On the other hand, Doublecap is twice the size of slice, equal to 4. The first if condition is satisfied, so newCap becomes 5.

Then we call roundupsize, passing in 40. (ptrSize in code refers to the size of a pointer, 8 on 64-bit machines)

Roundupsize = roundupsize

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

const _MaxSmallSize = 32768
const smallSizeMax = 1024
const smallSizeDiv = 8
Copy the code

Obviously, we will eventually return the result of this formula:

class_to_size[size_to_class8[(size+smallSizeDiv- 1)/smallSizeDiv]]
Copy the code

These are two slices of memory allocation in the Go source code. Class_to_size Obtains the size of an object divided by span by spanClass. Size_to_class8 represents the spanClass that gets it by size.

var size_to_class8 = [smallSizeMax/smallSizeDiv + 1]uint8{0.1.2.3.3.4.4.5.5.6.6.7.7.8.8.9.9.10.10.11.11.12.12.13.13.14.14.15.15.16.16.17.17.18.18.18.18.19.19.19.19.20.20.20.20.21.21.21.21.22.22.22.22.23.23.23.23.24.24.24.24.25.25.25.25.26.26.26.26.26.26.26.26.27.27.27.27.27.27.27.27.28.28.28.28.28.28.28.28.29.29.29.29.29.29.29.29.30.30.30.30.30.30.30.30.30.30.30.30.30.30.30.30.31.31.31.31.31.31.31.31.31.31.31.31.31.31.31.31}
var class_to_size = [_NumSizeClasses]uint16{0.8.16.32.48.64.80.96.112.128.144.160.176.192.208.224.240.256.288.320.352.384.416.448.480.512.576.640.704.768.896.1024.1152.1280.1408.1536.1792.2048.2304.2688.3072.3200.3456.4096.4864.5376.6144.6528.6784.6912.8192.9472.9728.10240.10880.12288.13568.14336.16384.18432.19072.20480.21760.24576.27264.28672.32768}
Copy the code

The size we passed in is equal to 40. (size+ smallsizediv-1)/smallSizeDiv = 5; Get the element with index 5 in size_to_class8 to be 4; Gets the element with index 4 in class_to_size as 48.

Finally, the new slice has a capacity of 6:

newcap = int(capmem / ptrSize) / / 6
Copy the code

【 extension 3】

What happens when you add elements to a nil slice? Why is that?

In fact, nil slice or empty slice can be called append function to get the underlying array expansion. The result is a call to mallocGC to request a chunk of memory from Go’s memory manager, which then assigns the original nil or empty slice, and then transforms into a “real” slice.