GoLang's slice bottom layer and expansion rules
1. Structure
In the first part, where are the elements stored? In the second part, how many elements are stored and how many elements can be stored
2. Variable declaration int type slice
For example, declare an [] int, and the variable ints is composed of three parts on the right. The element of slice should be stored in a continuous memory, which is actually an array. Data is the starting address of the underlying array, but only the slice structure has been allocated, and the underlying array has not been allocated on the right, so data=nil, the number of storage is 0, and the capacity is 0
3.make defines the int type slice
3.len equals 0
var sNil []int //The underlying array points to nil var sEmpty = make([]int, 0) //The underlying array points to a memory address, but there is no space allocated to it fmt.Println(len(sNil), len(sEmpty), cap(sNil), cap(sEmpty))//Output: 0
3.2len is not equal to 0
If this variable is defined in the way of make, it will not only allocate these three parts of the structure, but also open up a section of memory as its underlying array. Make will open up a section of memory containing five shaping elements for ints, and initialize them to the shaping default value of 0. However, at present, this slice variable only stores two elements, so data points to the position in the diagram, len is 2 and cap is 5
func main() {
var ints []int = make([]int, 2, 5)
fmt.Println(ints)//Output: [0]
}
Next, let's try adding an element to append. Since two elements have been saved, the new one is the third one, and len is modified to 3
func main() {
var ints []int = make([]int, 2, 5)
fmt.Println(len(ints), cap(ints)) //Output: 2 5
fmt.Println(ints)//Output: [0]
ints = append(ints, 1)
fmt.Println(len(ints), cap(ints))//Output: 3 5
fmt.Println(ints)//Output: [0 1]
}
The stored elements can be read and written safely, but beyond this range is cross-border access, and panic will occur
4.new defines the string type slice
ner, a sice variable, will also allocate these three parts of the structure, but it is not responsible for the allocation of the underlying array, so data=nil, the number of storage is 0, and the capacity is 0. The return value of new is the starting address of the slice structure, so ps is an address. At this time, the slice variable has no underlying array, so (*) [0]="eggo" is not allowed
So who assigned him the underlying array? Using append to add elements through append, he will open up the underlying array for slice. Here, an array of string elements needs to be accommodated. The string type is composed of two parts, one is the starting address of the content (the value is to the content of the string), and the other is the byte length
5. Underlying array of slice
Array is the storage of elements of the same kind of data one by one;
Int slice, the bottom layer is the int array; The bottom layer of string type is string array;
However, for slice, the data does not have to point to the beginning of the array
For slice data, it is not necessary to point to the beginning of the array. Examples are as follows: the variable arr is an integer array with a capacity of 10. The array capacity will not change after being declared. We can associate different slices to the same array, that is, var s 1 [int] =arr[1:4], and they will share the bottom array;
The elements of s1 are 1, 2 and 3. These three elements are added to f1, but the capacity starts from data and ends at the bottom array, with a total of 9 elements; The elements of s2 are three elements from index 7 to the end; slice accesses and modifies the elements of the underlying array
For s1, if you access s1[3], that is, arr[4], the access is out of bounds
func main() {
arr := []int{2, 3, 5, 7, 11, 13}
fmt.Println(arr)
sli1 := arr[1:4]
fmt.Println(sli1) //[3 5 7]
fmt.Println(len(sli1)) //3
fmt.Println(cap(sli1)) //5
sli2 := arr[0:4]
fmt.Println(sli2) //[2 3 5 7]
fmt.Println(len(sli2)) //4
fmt.Println(cap(sli2)) //6
sli3 := arr[2:3]
fmt.Println(sli3) //[5]
fmt.Println(len(sli3)) //1
fmt.Println(cap(sli3)) //4
sli3[0] = 100
fmt.Println(sli3)//[100]
fmt.Println(arr)//[2 3 100 7 11 13]
}
You can modify the range or add elements through append to expand the range of readable and writable ranges
At this time, if you add elements to s2, the original underlying array can no longer be used. You have to open up a new array. Copy the original number and add new elements. Change the number of elements to 4 and expand the capacity to 6
func main() {
arr := []int{2, 3, 5, 7, 11, 13}
slie := arr[4:]
slie[0] = 100
fmt.Println(arr) //Output: [2 3 5 7 100 13]
slie = append(slie, 200)
slie[0] = 1000
fmt.Println(arr)//Output: [2 3 5 7 100 13]
}
6.slice expansion rules
oldcap: capacity before capacity expansion
cap: minimum capacity required
newcap: estimated capacity;
- Calculate the estimated capacity expansion: if the capacity doubled before capacity expansion is still less than the minimum capacity (5), the estimated capacity is equal to the minimum capacity required. Otherwise, it needs to be subdivided; If the number of elements before expansion is less than 1024, it will be doubled directly. If the number of elements before expansion is greater than or equal to 1024, it will be expanded by a quarter, that is, to 1.25 times of the original
- The estimated capacity is the "number" of estimated elements. How much memory does it need for so many elements? This is linked to the element type. Multiply the estimated capacity by the element type size to get the required memory. Of course, it is not ok to allocate so much memory directly. In short, it is because the application for memory allocation is not directly negotiated with the operating system, but with the memory management module of the language itself, The memory management module will apply for a batch of memory from the operating system in advance and manage it according to the common specifications. When we apply for memory, it will help us match the large enough and closest specifications. This is what we need to do in the third step, that is, estimate the matching of the applied memory to the appropriate memory specifications;
- In the above example, when the estimated capacity is 5 and 64 bits, you need to apply for 40 bytes to store the expanded underlying array, but the actual application will match 48 bytes. How many elements can such a large memory hold? In this example, each element occupies 8 bytes, and a total of 6 can be installed. This is the capacity after capacity expansion
7. Example of string slice expansion
A is a slice of string type, and each element occupies 16 bytes under 64 bits;
-
Step 1: before capacity expansion, the capacity is 3. Add an element and expand the capacity to at least 4. Double the original capacity, that is, 3 * 2 is greater than 4 and 3 is less than 1024. Double it directly. The estimated capacity newcap is 6;
-
The second step is to multiply the estimated capacity by the element size, that is, 6 * 16 = 96 bytes
-
Step 3: match the memory specification to 96 bytes, so the capacity after final expansion is 6
8.slice source code
Slice under runtime Go can see
type slice struct {
array unsafe.Pointer
len int
cap int
}
/*
Initialization function makeslice:
math.MulUintptr: Calculate the required memory space according to the element size and capacity cap
mallocgc: For memory allocation, 32K is used as a critical value. The small one is allocated in the cache of P and the large one is allocated in the heap heap
*/
func makeslice(et *_type, len, cap int) unsafe.Pointer {}
/*
When the length is less than 1024, the cap is doubled; When it is greater than 1024, increase by 1 / 4. But this is not absolute. We will try our best to optimize it according to the type of element
*/
func growslice(et *_type, old slice, cap int) slice {}
/*
Copy slicecopy:
The core function is memmove, from = > to move the data of size, and size is the element size * the number of smaller lengths in from and to
*/
func slicecopy(toPtr unsafe.Pointer, toLen int, fromPtr unsafe.Pointer, fromLen int, width uintptr) int {}
9. Capacity expansion and address reallocation
var s = make([]int, 2, 2) s[0] = 1 fmt.Println(unsafe.Pointer(&s[0])) //0xc0000aa090 s[1] = 2 fmt.Println(unsafe.Pointer(&s[0])) //0xc0000aa090 // Tip: after capacity expansion, the address of slice array will be reassigned s = append(s, 3) fmt.Println(unsafe.Pointer(&s[0])) //0xc0000a80a0
var s = make([]int, 2, 2) s[0] = 1 s[1] = 2 fmt.Println(unsafe.Pointer(&s)) //0xc000004078 fmt.Println(unsafe.Pointer(&s[0])) //0xc0000160d0
10. Intercept slices but point to the same underlying array
var s = make([]int, 2, 2) s[0] = 1 s[1] = 2 fmt.Println(unsafe.Pointer(&s)) //0xc000004078 fmt.Println(unsafe.Pointer(&s[0])) //0xc0000160d0 a := s[:2] fmt.Println(unsafe.Pointer(&a)) //0xc000004090 fmt.Println(unsafe.Pointer(&a[0])) //0xc0000160b0
11.copy slice
var s = make([]int, 2, 2) b := make([]int, 2) // Tip: if you want to copy slice, use the copy method copy(b, s) //copy will reallocate the memory of the underlying array fmt.Println(unsafe.Pointer(&s[0])) //0xc0000160b0 fmt.Println(unsafe.Pointer(&b[0])) //0xc0000160c0