Preface
What will the following program output?
package main
import "fmt"
func f(s []string, level int) {
if level > 5 {
return
}
s = append(s, fmt.Sprint(level))
f(s, level+1)
fmt.Println("level:", level, "slice:", s)
}
func main() {
f(nil, 0)
}
Its output is:
level: 5 slice: [0 1 2 3 4 5]
level: 4 slice: [0 1 2 3 4]
level: 3 slice: [0 1 2 3]
level: 2 slice: [0 1 2]
level: 1 slice: [0 1]
level: 0 slice: [0]
If you have any doubts about the output, you need to understand the content of this article
-
If you know the results, you still need to understand the content of this article, because this article is a complete introduction
Typical use of slices
The trap of slicing
Escape analysis of slices
Expansion of slices
Research on slice in compile and run time
If you know everything, just slide to the bottom and double-click 666
Basic operation of slicing
Slicing is to some extent similar to arrays in other languages (such as C), but slicing in go has many unique features
Slice represents a variable length sequence in which each element has the same type.
A slice type is generally written as [] t, where T represents the type of elements in slice; slice syntax is similar to array, but there is no fixed length.
There is a close relationship between arrays and slice. A slice is a lightweight data structure that provides access to array subsequence (or all) elements. A slice consists of three parts at runtime: pointer, length and capacity.
type SliceHeader struct {
Data uintptr
Len int
Cap int
}
Pointer to the address of the underlying array element corresponding to the first slice element
Length corresponds to the number of elements in slice; length cannot exceed capacity
The capacity is generally the length from the beginning of slice to the end of bottom layer data
Slice declaration
//Slice declaration 1 / / nil
var slice1 []int
//Slice declaration 2
var slice2 []int = make([]int,5)
var slice3 []int = make([]int,5,7)
numbers:= []int{1,2,3,4,5,6,7,8}
Slice cutting
numbers:= []int{1,2,3,4,5,6,7,8}
//From subscript 1 to subscript 4, but excluding subscript 4
numbers1 :=numbers[1:4]
//From subscript 0 to subscript 3, excluding subscript 3
numbers2 :=numbers[:3]
//From subscript 3 to end
numbers3 :=numbers[3:]
Length and capacity of slices
The built-in len and cap functions return the length and capacity of slice respectively
slice6 := make([]int,0)
fmt.Printf("len=%d,cap=%d,slice=%v\n",len(slice4),cap(slice4),slice4)
Copy comparison between slice and array
A copy of an array is a copy. Changes to the replica do not affect the original array
However, the copy of slice is very special. The copy of slice is only for the copy of slice structure at runtime. The copy of slice still points to the same array. Therefore, changes to the replica affect the original slice.
Here is a simple example
/ / array is of value type
a := [4]int{1, 2, 3, 4}
/ / slice is a reference type
b := []int{100, 200, 300}
c := a
d := b
c[1] = 200
d[0] = 1
//output: c[1 200 3 4] a[1 2 3 4]
fmt.Println("a=", a, "c=", c)
//output: d[1 200 300] b[1 200 300]
fmt.Println("b=", b, "d=", d)
Slice append element: append
numbers := make([]int, 0, 20)
//append an element
numbers = append(numbers, 0)
//append multiple elements
numbers = append(numbers, 1, 2, 3, 4, 5, 6, 7)
//append add slice
s1 := []int{100, 200, 300, 400, 500, 600, 700}
numbers = append(numbers, s1...)
//now:[0 1 2 3 4 5 6 7 100 200 300 400 500 600 700]
Classic case: slice delete
//Delete first element
numbers = numbers[1:]
//Delete last element
numbers = numbers[:len(numbers)-1]
//Delete the middle element
a := int(len(numbers) / 2)
numbers = append(numbers[:a], numbers[a+1:]...)
Classic case: slice reversal
// reverse reverses a slice of ints in place.
func reverse(s []int) {
for i, j := 0, len(s)-1; i < j; i, j = i+1, j-1 {
s[i], s[j] = s[j], s[i]
}
}
Slice properties at compile time
Create a new slice at compile time. The type of elements in the slice is determined during compilation
func NewSlice(elem *Type) *Type {
if t := elem.Cache.slice; t != nil {
if t.Elem() != elem {
Fatalf("elem mismatch")
}
return t
}
t := New(TSLICE)
t.Extra = Slice{Elem: elem}
elem.Cache.slice = t
return t
}
Type of slice
// Slice contains Type fields specific to slice types.
type Slice struct {
Elem *Type // element type
}
Compile time: literal initialization
When we create a new slice with literal amount [] int{1, 2, 3}, we will create an array ([3]int{1,2,3}) to store in the static area. A variable is also created.
Core logic in slicelit function
// go/src/cmd/compile/internal/gc/sinit.go
func slicelit(ctxt initContext, n *Node, var_ *Node, init *Nodes)
The abstract process is as follows:
var vstat [3]int
vstat[0] = 1
vstat[1] = 2
vstat[2] = 3
var vauto *[3]int = new([3]int)
*vauto = vstat
slice := vauto[:]
The notes in the source code are as follows:
// recipe for var = []t{...}
// 1. make a static array
// var vstat [...]t
// 2. assign (data statements) the constant part
// vstat = constpart{}
// 3. make an auto pointer to array and allocate heap to it
// var vauto *[...]t = new([...]t)
// 4. copy the static array to the auto array
// *vauto = vstat
// 5. for each dynamic part assign to the array
// vauto[i] = dynamic part
// 6. assign slice of allocated heap to var
// var = vauto[:]
Compile time: make initialization
For example, make([]int,3,4)
Using the make keyword, in the typecheck1 type checking phase, the op operation of Node node becomes OMAKESLICE, and the storage length of left Node is 3, and the storage capacity of right Node is 4
func typecheck1(n *Node, top int) (res *Node) {
switch t.Etype {
case TSLICE:
if i >= len(args) {
yyerror("missing len argument to make(%v)", t)
n.Type = nil
return n
}
l = args[i]
i++
l = typecheck(l, ctxExpr)
var r *Node
if i < len(args) {
r = args[i]
i++
r = typecheck(r, ctxExpr)
}
if l.Type == nil || (r != nil && r.Type == nil) {
n.Type = nil
return n
}
if !checkmake(t, "len", l) || r != nil && !checkmake(t, "cap", r) {
n.Type = nil
return n
}
n.Left = l
n.Right = r
n.Op = OMAKESLICE
Let's analyze the escape problem of compile time memory. If make initializes a slice that is too large, this space will escape to the heap and be allocated by the runtime. If a space is small, it will be allocated in the stack.
This threshold value is defined in / usr/local/go/src/cmd/compile/internal/gc, which can be updated by flag smallframes. The default value is 64KB.
So the effect of make ([] int641023) is quite different from that of make ([] int641023). Is this the last straw to overwhelm the camel?
// maximum size of implicit variables that we will allocate on the stack.
// p := new(T) allocating T on the stack
// p := &T{} allocating T on the stack
// s := make([]T, n) allocating [n]T on the stack
// s := []byte("...") allocating [n]byte on the stack
// Note: the flag smallframes can update this value.
maxImplicitStackVarSize = int64(64 * 1024)
The core logic is located in go/src/cmd/compile/internal/gc/walk.go, and n.Esc represents whether the variable escapes or not
func walkexpr(n *Node, init *Nodes) *Node{
case OMAKESLICE:
...
if n.Esc == EscNone {
// var arr [r]T
// n = arr[:l]
i := indexconst(r)
if i < 0 {
Fatalf("walkexpr: invalid index %v", r)
}
t = types.NewArray(t.Elem(), i) // [r]T
var_ := temp(t)
a := nod(OAS, var_, nil) // zero temp
a = typecheck(a, ctxStmt)
init.Append(a)
r := nod(OSLICE, var_, nil) // arr[:l]
r.SetSliceBounds(nil, l, nil)
r = conv(r, n.Type) // in case n.Type is named.
r = typecheck(r, ctxExpr)
r = walkexpr(r, init)
n = r
} else {
if t.Elem().NotInHeap() {
yyerror("%v is go:notinheap; heap allocation disallowed", t.Elem())
}
len, cap := l, r
fnname := "makeslice64"
argtype := types.Types[TINT64]
m := nod(OSLICEHEADER, nil, nil)
m.Type = t
fn := syslook(fnname)
m.Left = mkcall1(fn, types.Types[TUNSAFEPTR], init, typename(t.Elem()), conv(len, argtype), conv(cap, argtype))
m.Left.SetNonNil(true)
m.List.Set2(conv(len, types.Types[TINT]), conv(cap, types.Types[TINT]))
m = typecheck(m, ctxExpr)
m = walkexpr(m, init)
n = m
}
For the above code analysis, if there is no escape, it is allocated in the stack.
Abstract as:
arr := [r]T
ss := arr[:l]
If escape occurs, the runtime calls makeslice64 or makeslice is allocated in the heap. When the length and capacity of slice is less than the maximum value of int type, makeslice will be called, otherwise makeslice64 will be called to create slice.
makeslice64 finally calls makeslice, which is relatively simple. Finally, the size of the mallocgc application is called type size * capacity cap.
// go/src/runtime/slice.go
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 {
// NOTE: Produce a 'len out of range' error instead of a
// 'cap out of range' error when someone does make([]T, bignumber).
// 'cap out of range' is true too, but since the cap is only being
// supplied implicitly, saying len is clearer.
// See golang.org/issue/4085.
mem, overflow := math.MulUintptr(et.size, uintptr(len))
if overflow || mem > maxAlloc || len < 0 {
panicmakeslicelen()
}
panicmakeslicecap()
}
return mallocgc(mem, et, true)
}
func makeslice64(et *_type, len64, cap64 int64) unsafe.Pointer {
len := int(len64)
if int64(len) != len64 {
panicmakeslicelen()
}
cap := int(cap64)
if int64(cap) != cap64 {
panicmakeslicecap()
}
return makeslice(et, len, cap)
}
Expansion of slices
In Go, slicing append means adding elements, but you need to expand if you do not use append. The following code does not need to expand
a:= make([]int,3,4)
append(a,1)
When the capacity of slice append in Go exceeds the existing capacity, you need to expand the capacity, for example:
a:= make([]int,3,3)
append(a,1)
The core logic is located in the go/src/runtime/slice.go growslice function
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 0 < newcap && newcap < cap {
newcap += newcap / 4
}
if newcap <= 0 {
newcap = cap
}
}
}
...
}
-
The above code shows the core logic of capacity expansion. The strategy of slice capacity expansion in Go is as follows:
First of all, if the new application capacity (cap) is more than twice the old capacity (old.cap), the final capacity (newcap) is the new application capacity (cap)
Otherwise, if the length of the old slice is less than 1024, the final capacity (newcap) is twice the old capacity (old.cap), i.e. (newcap=doublecap)
Otherwise, if the length of the old slice is greater than or equal to 1024, the final capacity (newcap) will increase by 1 / 4 from the old capacity (old.cap), i.e. (newcap=old.cap,for {newcap += newcap/4}) until the final capacity (newcap) is greater than or equal to the newly applied capacity (CAP), i.e. (newcap > = cap)
If the calculated value of the final capacity (cap) overflows, the final capacity (cap) is the newly applied capacity (cap)
Then, according to the size of slice type, different memory allocation sizes are determined. It is mainly used for memory alignment. Therefore, the requested memory may be larger than the actual et.size * newcap
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)
}
The final core is to apply for memory. Note that a new slice does not necessarily mean a new address.
Depending on whether the slice type et.ptrdata is a pointer, different logic needs to be executed.
if et.ptrdata == 0 {
p = mallocgc(capmem, nil, false)
// The append() that calls growslice is going to overwrite from old.len to cap (which will be the new length).
// Only clear the part that will not be overwritten.
memclrNoHeapPointers(add(p, newlenmem), capmem-newlenmem)
} else {
// Note: can't use rawmem (which avoids zeroing of memory), because then GC can scan uninitialized memory.
p = mallocgc(capmem, et, true)
if lenmem > 0 && writeBarrier.enabled {
// Only shade the pointers in old.array since we know the destination slice p
// only contains nil pointers because it has been cleared during alloc.
bulkBarrierPreWriteSrcOnly(uintptr(p), uintptr(old.array), lenmem)
}
}
memmove(p, old.array, lenmem)
return slice{p, old.len, newcap}
When the slice type is not a pointer, only the later value of the memory needs to be cleared after memory allocation. memmove(p, old.array, lenmem) function is used to assign the value of old slice to the new slice
The abstract representation of the whole process is as follows
old = make([]int,3,3)
new = append(old,1) => new = malloc(newcap * sizeof(int)) a[4] = 0
new[1] = old[1]
new[2] = old[2]
new[3] = old[3]
When the slice type is pointer, the pointer needs to be written to the current process buffer. This place involves the write barrier in the GC recovery mechanism, which will be described later.
Slice cutting
For array subscript truncation, as shown below, it can be proved from multiple dimensions that slice truncation generates a new slice, but the underlying data source is the same.
old := make([]int64,3,3)
new := old[1:3]
fmt.Printf("%p %p",arr,slice)
The output is:
0xc000018140 0xc000018148
The address difference between them is exactly 8 bytes, which is not accidental, but because they point to the same data source, just the difference of int64 size.
In addition, we can see some clues from the generated assembly process
GOSSAFUNC=main GOOS=linux GOARCH=amd64 go tool compile main.go
In the initial stage of ssa, start, old: = make ([] int64,3,3) corresponds to slicemake < [] int > V10 V15 V15. Slicemake operation needs to pass array pointer, length and capacity.
And new: = old [1:3] corresponds to slicemake < [] int > v34 V28 V29. The passed pointer v34 is exactly the position after the original Ptr + 8 bytes
The following is a more vivid diagram showing that slices refer to the same data source:
Copy of slices
Because replication of slices does not change the underlying data source to which it points. But sometimes we want to build a new array, even the underlying data source is brand new. You can use the copy function at this time
Slice for value copy: copy
//Create target slice
numbers1 := make([]int, len(numbers), cap(numbers)*2)
//Copy the elements of numbers to numbers1
count := copy(numbers1, numbers)
Slice to array
slice := []byte("abcdefgh")
var arr [4]byte
copy(arr[:], slice[:4])
//Or directly as follows, this involves a feature that only min(len(arr),len(slice) can be copied
copy(arr[:], slice)
The copy function will decide which way to use when compiling, and the normal way will call memmove directly
func copyany(n *Node, init *Nodes, runtimecall bool) *Node {
...
if runtimecall {
if n.Right.Type.IsString() {
fn := syslook("slicestringcopy")
fn = substArgTypes(fn, n.Left.Type, n.Right.Type)
return mkcall1(fn, n.Type, init, n.Left, n.Right)
}
fn := syslook("slicecopy")
fn = substArgTypes(fn, n.Left.Type, n.Right.Type)
return mkcall1(fn, n.Type, init, n.Left, n.Right, nodintconst(n.Left.Type.Elem().Width))
}
...
fn := syslook("memmove")
fn = substArgTypes(fn, nl.Type.Elem(), nl.Type.Elem())
nwid := temp(types.Types[TUINTPTR])
setwid := nod(OAS, nwid, conv(nlen, types.Types[TUINTPTR]))
ne.Nbody.Append(setwid)
nwid = nod(OMUL, nwid, nodintconst(nl.Type.Elem().Width))
call := mkcall1(fn, nil, init, nto, nfrm, nwid)
}
The abstract representation is:
init {
n := len(a)
if n > len(b) { n = len(b) }
if a.ptr != b.ptr { memmove(a.ptr, b.ptr, n*sizeof(elem(a))) }
}
Unless it's the way of CO program call, go copy(numbers1, numbers) or (with race and other detection added & & not compiling go runtime code) will call the runtime slicestringcopy or slicecopy instead
case OCOPY:
n = copyany(n, init, instrumenting && !compiling_runtime)
case OGO:
switch n.Left.Op {
case OCOPY:
n.Left = copyany(n.Left, &n.Ninit, true)
slicestringcopy or slicecopy are still essentially memmove calls, which only make additional race conflicts and other judgments.
func slicecopy(to, fm slice, width uintptr) int {
...
if raceenabled {
callerpc := getcallerpc()
pc := funcPC(slicecopy)
racewriterangepc(to.array, uintptr(n*int(width)), callerpc, pc)
racereadrangepc(fm.array, uintptr(n*int(width)), callerpc, pc)
}
if msanenabled {
msanwrite(to.array, uintptr(n*int(width)))
msanread(fm.array, uintptr(n*int(width)))
}
size := uintptr(n) * width
if size == 1 { // common case worth about 2x to do here
// TODO: is this still worth it with new memmove impl?
*(*byte)(to.array) = *(*byte)(fm.array) // known to be a byte pointer
} else {
memmove(to.array, fm.array, size)
}
return n
}
summary
Slicing is an important data result in go language. Unlike other languages, it maintains the underlying memory, length and capacity
There are obvious differences between slice and array assignment copy. Slice references the same underlying data when assigning copy and subscript truncation
If you want to copy the slice completely, use the copy function. The logic is to create a new memory and copy it. In extreme cases, its impact on performance needs to be considered
Initialization of slice literal, array stored in static area. In the initialization mode of slice make, if make initializes a slice larger than 64KB, this space will escape to the heap and call makeslice at runtime to create. Slices smaller than 64KB are initialized in the stack
-
When the capacity of slice append in Go exceeds the existing capacity, it needs to be expanded. The strategy is as follows:
First of all, if the new application capacity (cap) is more than twice the old capacity (old.cap), the final capacity (newcap) is the new application capacity (cap)
Otherwise, if the length of the old slice is less than 1024, the final capacity (newcap) is twice the old capacity (old.cap), i.e. (newcap=doublecap)
Otherwise, if the length of the old slice is greater than or equal to 1024, the final capacity (newcap) will increase by 1 / 4 from the old capacity (old.cap), i.e. (newcap=old.cap,for {newcap += newcap/4}) until the final capacity (newcap) is greater than or equal to the newly applied capacity (CAP), i.e. (newcap > = cap)
If the calculated value of the final capacity (cap) overflows, the final capacity (cap) is the newly applied capacity (cap)
The slice address returned after the slice append in Go is not necessarily the original or the new memory address, so we must be careful of the possible traps it may encounter. Generally, a = append(a,T) is used to ensure security.
Preceding text
golang quick start [2.1]-go language development environment configuration windows
golang quick start [2.2]-go language development environment configuration - macOS
golang quick start [2.3]-go language development environment configuration linux
Getting started with golang [5.1] - how the go language works - linker
Getting started with golang [5.2] - how the go language works - memory overview
Quick start to golang [5.3] - how the go language works - memory allocation
Quick start to golang [6.1] - integrated development environment - details of goland
Quick start to golang [6.2] - integrated development environment - emacs details
Quick start to golang [7.1] - project and dependency management gopath
Quick start to golang [7.2] - Northern hell magic skill - go module unique skill
Quick start to golang [8.4]- constant and implicit type conversion
Quick start to golang [9.1] -- Deep string storage, compilation and operation
Quick start to golang [9.2] - deep array usage, traps and compile time
reference material
Project links
The author knows
blog