Detailed analysis of golang slice principle

Slice parsing

When our code is knocked down[]When it is parsed by the go compiler into a slice node on the abstract syntax tree, it is initialized into a slice expressionSliceType:

// go/src/cmd/compile/internal/syntax/
// TypeSpec = identifier [ TypeParams ] [ "=" ] Type .
func (p *parser) typeDecl(group *Group) Decl {
    ...
    if  == _Lbrack {
        //  "[" ...
        // array/slice type or type parameter list
        pos := ()
        ()
        switch  {
        ...
        case _Rbrack:
            //  "[" "]" ...
            ()
             = (pos)
        ...
        }
    } 
    ...
}
func (p *parser) sliceType(pos Pos) Expr {
    t := new(SliceType)
     = pos
     = p.type_()
    return t
}
// go/src/cmd/compile/internal/syntax/
type (
    ...
  // []Elem
    SliceType struct {
        Elem Expr
        expr
    }
  ...
)

Compile-time slice definition isSliceStructure, attributes contain only elements of the same typeElem, compile time throughNewSlice()Functions are created:

// go/src/cmd/compile/internal/types/
type Slice struct {
    Elem *Type // element type
}
func NewSlice(elem *Type) *Type {
    if t := ; t != nil {
        if () != elem {
            ("elem mismatch")
        }
        if () != () || () != () {
            ("Incorrect HasTParam/HasShape flag for cached slice type")
        }
        return t
    }
    t := newType(TSLICE)
     = Slice{Elem: elem}
     = t
    if () {
        (true)
    }
    if () {
        (true)
    }
    return t
}

Initialization of slices

There are two ways to initialize slices. One is to declare, initialization is called literal initialization, and the other is calledmakeinitialization,

For example:

litSlic := []int{1,2,3,4}  // Literal initializationmakeSlic := make([]int,0)  // makeinitialization

Literal initialization

The initialization of slice literals is traversed after the abstract syntax tree is generated.walkThe stage was completed. passwalkComplitMethod, first type check will be performed, and the number of slice elements will be calculated.length, and then passslicelitMethods complete specific initialization work. The entire process will first create an array to store in a static area(static array)and create a new slice in the heap area(auto array), and then copy the data from the static area to the heap area(copy the static array to the auto array), the elements in the slice will be assigned one by one according to the index position. This process speeds up the initialization of slices when the program starts.

// go/src/cmd/compile/internal/walk/
// walkCompLit walks a composite literal node:
// OARRAYLIT, OSLICELIT, OMAPLIT, OSTRUCTLIT (all CompLitExpr), or OPTRLIT (AddrExpr).
func walkCompLit(n , init *)  {
    if isStaticCompositeLiteral(n) && !(()) {
        n := n.(*) // not OPTRLIT
        // n can be directly represented in the read-only data section.
        // Make direct reference to the static data. See issue 12841.
        vstat := readonlystaticname(())
        fixedlit(inInitFunction, initKindStatic, n, vstat, init)
        return (vstat)
    }
    var_ := (())
    anylit(n, var_, init)
    return var_
}

During type checking, the process of calculating the slice length is:

// go/src/cmd/compile/internal/typecheck/
func tcCompLit(n *) (res ) {
    ...
    t := ()
    (t != nil, (), "missing type in composite literal")

    switch () {
    ...
    case :
        length := typecheckarraylit((), -1, , "slice literal")
        ()
         = length
    ...
  }
    return n
}

The specific initialization process of slices is:

Create an array in a static storage area;
Assign the array to a constant part;
Create an automatic pointer, that is, slice allocation to the heap area and point to the array;
Copy the data in the array from the static area to the heap area of the slice;
Assign values to each slice element according to the index position;
Finally, the slice assigned to the heap area is assigned to the defined variable;

The source code also states the entire process through comments.

// go/src/cmd/compile/internal/walk/
func anylit(n , var_ , init *) {
    t := ()
    switch () {
  ...
  case :
        n := n.(*)
        slicelit(inInitFunction, n, var_, init)
  ...
  }
}
func slicelit(ctxt initContext, n *, var_ , init *) {
    // make an array type corresponding the number of elements we have
    t := (().Elem(), )
    (t)

    if ctxt == inNonInitFunction {
        // put everything into static array
        vstat := (t)

        fixedlit(ctxt, initKindStatic, n, vstat, init)
        fixedlit(ctxt, initKindDynamic, n, vstat, init)

        // copy static to slice
        var_ = (var_)
        name, offset, ok := (var_)
        if !ok ||  !=  {
            ("slicelit: %v", var_)
        }
        (name, offset, (), ())
        return
    }

    // 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[:]
    //
    // an optimization is done if there is no constant part
    //  3. var vauto *[...]t = new([...]t)
    //  5. vauto[i] = dynamic part
    //  6. var = vauto[:]

    // if the literal contains constants,
    // make static initialized array (1),(2)
    var vstat 

    mode := getdyn(n, true)
    if mode&initConst != 0 && !isSmallSliceLit(n) {
        if ctxt == inInitFunction {
            vstat = readonlystaticname(t)
        } else {
            vstat = (t)
        }
        fixedlit(ctxt, initKindStatic, n, vstat, init)
    }

    // make new auto *array (3 declare)
    vauto := ((t))

    // set auto to point at new temp or heap (3 assign)
    var a 
    if x := ; x != nil {
        // temp allocated during  for dddarg
        if !(t, ()) {
            panic("dotdotdot base type does not match order's assigned type")
        }
        a = initStackTemp(init, x, vstat)
    } else if () ==  {
        a = initStackTemp(init, (t), vstat)
    } else {
        a = (, , (t))
    }
    appendWalkStmt(init, (, vauto, a))

    if vstat != nil &&  == nil && () !=  {
        // If we allocated on the heap with ONEW, copy the static to the
        // heap (4). We skip this for stack temporaries, because
        // initStackTemp already handled the copy.
        a = (, vauto)
        appendWalkStmt(init, (, a, vstat))
    }

    // put dynamics into array (5)
    var index int64
    for _, value := range  {
        if () ==  {
            kv := value.(*)
            index = ()
            if index < 0 {
                ("slicelit: invalid index %v", )
            }
            value = 
        }
        a := (, vauto, (index))
        (true)
        index++
        // TODO need to check bounds?
        switch () {
        case :
            break
        case , :
            value := value.(*)
            k := initKindDynamic
            if vstat == nil {
                // Generate both static and dynamic initializations.
                // See issue #31987.
                k = initKindLocalCode
            }
            fixedlit(ctxt, k, value, a, init)
            continue
        }
        if vstat != nil && (value) { // already set by copy from static value
            continue
        }
        // build list of vauto[c] = expr
        (value)
        as := (, a, value)
        appendWalkStmt(init, orderStmtInPlace((as), map[string][]*{}))
    }
    // make slice out of heap (6)
    a = (, var_, (, , vauto, nil, nil, nil))
    appendWalkStmt(init, orderStmtInPlace((a), map[string][]*{}))
}

Make initialization

When usingmakeWhen an initialization of a slice, it will be parsed into aOMAKESLICEoperate:

// go/src/cmd/compile/internal/walk/
func walkExpr1(n , init *)  {
    switch () {
    ...
    case :
        n := n.(*)
        return walkMakeSlice(n, init)
    ...
}

ifmakeInitializing a larger slice will escape to the heap, and if a smaller slice is allocated, it will be allocated directly on the stack.

existwalkMakeSliceIn the function, if the capacity of the slice is not specifiedCap, then the initial capacity is equal to the length of the slice.
If the initialization of the slice does not occur memory escape occurs() == , an array of the same capacity will be created in memory firstNewArray(), and then transfer the values in the array by slice lengtharr[:l]Assign slices.
If memory escape occurs, the slice calls the runtime functionmakesliceandmakeslice64Initialization of slices is done in the heap.

// go/src/cmd/compile/internal/walk/
func walkMakeSlice(n *, init *)  {
    l := 
    r := 
    if r == nil {
        r = safeExpr(l, init)
        l = r
    }
    ...
    if () ==  {
        if why := (n); why != "" {
            ("%v has EscNone, but %v", n, why)
        }
        // var arr [r]T
        // n = arr[:l]
        i := (r)
        if i < 0 {
            ("walkExpr: invalid index %v", r)
        }
        ...
        t = ((), i) // [r]T
        var_ := (t)
        appendWalkStmt(init, (, var_, nil))  // zero temp
        r := (, , var_, nil, l, nil) // arr[:l]
        // The conv is necessary in case  is named.
        return walkExpr(((r, ())), init)
    }
    // n escapes; set up a call to makeslice.
    // When len and cap can fit into int, use makeslice instead of
    // makeslice64, which is faster and shorter on 32 bit platforms.
    len, cap := l, r
    fnname := "makeslice64"
    argtype := [types.TINT64]
    // Type checking guarantees that TIDEAL len/cap are positive and fit in an int.
    // The case of len or cap overflow when converting TUINT or TUINTPTR to TINT
    // will be handled by the negative range checks in makeslice during runtime.
    if (().IsKind() || ().Size() <= [].Size()) &&
        (().IsKind() || ().Size() <= [].Size()) {
        fnname = "makeslice"
        argtype = []
    }
    fn := (fnname)
    ptr := mkcall1(fn, [], init, (()), (len, argtype), (cap, argtype))
    ()
    len = (len, [])
    cap = (cap, [])
    sh := (, t, ptr, len, cap)
    return walkExpr((sh), init)
}

Whether the slice is initialized in the stack or the heap is determined by a critical value. Critical valuemaxImplicitStackVarSizeThe default is 64kb. From the source code below, you can see that explicit variable declarationsexplicit variable declarations and implicit variablesimplicit variablesThe critical value of escape is different.

When we usevar variable declarationas well as:=Assign operationWhen the memory escape threshold is10M, Objects smaller than this value will be allocated on the stack.
When we use the following operation, the critical value of memory escape is64kb, objects smaller than this value will be allocated on the stack.

p := new(T)          
p := &T{}           
s := make([]T, n)    
s := []byte("...")

// go/src/cmd/compile/internal/ir/
var (
    // maximum size variable which we will allocate on the stack.
    // This limit is for explicit variable declarations like "var x T" or "x := ...".
    // Note: the flag smallframes can update this value.
    MaxStackVarSize = int64(10 * 1024 * 1024)
    // 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)
    // MaxSmallArraySize is the maximum size of an array which is considered small.
    // Small arrays will be initialized directly with a sequence of constant stores.
    // Large arrays will be initialized by copying from a static temp.
    // 256 bytes was chosen to minimize generated code + statictmp size.
    MaxSmallArraySize = int64(256)
)

The make initialization of the slice belongs tos := make([]T, n)Operation, when the memory allocated by the slice element is greater than64kbWhen , the slice will escape to the heap for initialization. The runtime function will be called at this timemakesliceTo complete this process:

// go/src/runtime/
func makeslice(et *_type, len, cap int)  {
    mem, overflow := (, 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 /issue/4085.
        mem, overflow := (, uintptr(len))
        if overflow || mem > maxAlloc || len < 0 {
            panicmakeslicelen()
        }
        panicmakeslicecap()
    }
    return mallocgc(mem, et, true)
}

According to the runtime structure definition of the slice, the bottom layer of the runtime slice structure maintains the length of the slicelen,capacitycapand pointers to array dataarray:

// go/src/runtime/
type slice struct {
    array 
    len   int
    cap   int
}
// or// go/src/reflect/
// SliceHeader is the runtime representation of a slice.
type SliceHeader struct {
    Data uintptr
    Len  int
    Cap  int
}

Slice interception

From the runtime structure of the slice, it is known that the underlying data of the slice is an array, and the slice itself just holds a pointer to the modified array data. Therefore, when we intercept the slice, the new slice still points to the underlying data of the original slice. When the original slice data is updated, it means that the data at the same index position of the new slice also changes:

slic := []int{1, 2, 3, 4, 5}
slic1 := slic[:2]
("slic1: %v\n", slic1)
slic[0] = 0
("slic: %v\n", slic)
("slic1: %v\n", slic1)
// slic1: [1 2]
// slic: [0 2 3 4 5]
// slic1: [0 2]

After the slice intercept, although the underlying data has not changed, the data range pointed to has changed, which is manifested as the slice length and capacity after the intercept will change accordingly.:

The length is the range of intercept
Capacity is the range from the start position of the intercept to the end of the original slice

slic := []int{1, 2, 3, 4, 5}
slic1 := slic[:2]
slic2 := slic[2:]
("len(slic): %v\n", len(slic))
("cap(slic): %v\n", cap(slic))
("len(slic1): %v\n", len(slic1))
("cap(slic1): %v\n", cap(slic1))
("len(slic2): %v\n", len(slic2))
("cap(slic2): %v\n", cap(slic2))
// len(slic): 5
// cap(slic): 5

// len(slic1): 2
// cap(slic1): 5

// len(slic2): 3
// cap(slic2): 3

Therefore, the slice intercepts change the underlying data pointer, length and capacity, and the array data pointed to by the data pointer has not changed. The assignment copy of the slice is equivalent to the full slice, the bottom layerdataThe pointer still points to the same array address, and the length and capacity remain unchanged:

slic := []int{1, 2, 3, 4, 5}
s := slic  // Equivalent to s := slic[:]

When a slice is passed as a parameter, even if the slice contains a large amount of data, it is only a copy of the slice data address, and the copy cost is lower.

Copying of slices

When we want to copy a slice in full, we can use the built-incopyFunction, the effect is similar to "deep copy".

slic := []int{1, 2, 3, 4, 5}
var slic1 []int
copy(slic1, slic)
("slic: %p\n", slic)
("slic1: %p\n", slic1)
// slic: 0xc0000aa030
// slic1: 0x0

After full copy, the new slice points to the new memory address. The copy of the slice will be called at runtimeslicecopy()Function, bymemmoveMove data to the new memory address:

// go/src/runtime/
func slicecopy(toPtr , toLen int, fromPtr , fromLen int, width uintptr) int {
    if fromLen == 0 || toLen == 0 {
        return 0
    }

    n := fromLen
    if toLen < n {
        n = toLen
    }
    ...
    if size == 1 { // common case worth about 2x to do here
        // TODO: is this still worth it with new memmove impl?
        *(*byte)(toPtr) = *(*byte)(fromPtr) // known to be a byte pointer
    } else {
        memmove(toPtr, fromPtr, size)
    }
    return n
}

Slice expansion

The number of slice elements can be changed dynamically. After the slice is initialized, an initialization capacity will be determined. When the capacity is insufficient, it will pass during runtime.growsliceExpand capacity:

func growslice(et *_type, old slice, cap int) slice {
    ...
    newcap := 
    doublecap := newcap + newcap
    if cap > doublecap {
        newcap = cap
    } else {
        const threshold = 256
        if  < threshold {
            newcap = doublecap
        } else {
            // Check 0 < newcap to detect overflow
            // and prevent an infinite loop.
            for 0 < newcap && newcap < cap {
                // Transition from growing 2x for small slices
                // to growing 1.25x for large slices. This formula
                // gives a smooth-ish transition between the two.
                newcap += (newcap + 3*threshold) / 4
            }
            // Set newcap to the requested cap when
            // the newcap calculation overflowed.
            if newcap <= 0 {
                newcap = cap
            }
        }
    }
    ...
    memmove(p, , lenmem)
    return slice{p, , newcap}
}

From the code of growslice, we can see:

When the capacity of newly applied (cap) is greater than twice the old capacity (), the final capacity (newcap) is the capacity of the newly applied application;
When the capacity of newly applied (cap) Less than twice the old capacity ()hour,
- If the old capacity is less than 256, the final capacity is twice the old capacity;
- If the old capacity is greater than or equal to 256, the formula will be followednewcap += (newcap + 3*threshold) / 4to determine the final capacity. The actual manifestation is:

When the slice length is less than or equal to 1024, the final capacity is twice that of the old capacity;
When the slice length is greater than 1024, the final capacity is 1.25 times the old capacity, and as the length increases, it is greater than 1.25 times;
After expansion, it will be passedmemmove()Functions move the old array to the new address, so the new slice after expansion is generally different from the original address.

Example:

var slic []int
oldCap := cap(slic)
for i := 0; i < 2048; i++ {
  slic = append(slic, i)
  newCap := cap(slic)
  grow := float32(newCap) / float32(oldCap)
  if newCap != oldCap {
    ("len(slic):%v cap(slic):%v grow:%v %p\n", len(slic), cap(slic), grow, slic)
  }
  oldCap = newCap
}
// len(slic):1     cap(slic):1     grow:+Inf       0xc0000140c0
// len(slic):2     cap(slic):2     grow:2          0xc0000140e0
// len(slic):3     cap(slic):4     grow:2          0xc000020100
// len(slic):5     cap(slic):8     grow:2          0xc00001e340
// len(slic):9     cap(slic):16    grow:2          0xc000026080
// len(slic):17    cap(slic):32    grow:2          0xc00007e000
// len(slic):33    cap(slic):64    grow:2          0xc000100000
// len(slic):65    cap(slic):128   grow:2          0xc000102000
// len(slic):129   cap(slic):256   grow:2          0xc000104000
// len(slic):257   cap(slic):512   grow:2          0xc000106000
// len(slic):513   cap(slic):1024  grow:2          0xc000108000
// len(slic):1025  cap(slic):1280  grow:1.25       0xc00010a000
// len(slic):1281  cap(slic):1696  grow:1.325      0xc000114000
// len(slic):1697  cap(slic):2304  grow:1.3584906  0xc00011e000

Summarize

Slices are defined asSlicestructure, and throughNewSlice()Functions are created;

type Slice struct {
  Elem *Type // element type
}

The runtime of the slice is defined assliceStructure, the underlying layer maintains pointers to array data, slice length and capacity;

type slice struct {
  array 
  len   int
  cap   int
}

When the slice literal is initialized, the length of the slice will be calculated during the type checking stage at compile time, and then the underlying array will be created when walking through the syntax tree, and each literal element in the slice will be assigned to the array by index, and the slice's data pointer will point to the array;
When the slice make is initialized, the runtime will be calledmakesliceFunctions allocate memory, and when the memory usage is greater than 64kb, it will escape to the heap;
After the slice is intercepted, the underlying array data does not change, but the data range pointed to changes, which is manifested as the slice length and capacity after the intercepted will change accordingly:
- The length is the range of intercept
- Capacity is the range from the start position of the intercept to the end of the original slice
usecopyWhen copying a slice, it will be called at runtimeslicecopy()Function, bymemmoveMove the data to the new memory address;
Slice expansion is through runtimegrowsliceFunctions are completed generally manifested as:
- When the slice length is less than or equal to 1024, the final capacity is twice that of the old capacity;
- When the slice length is greater than 1024, the final capacity is 1.25 times the old capacity, and slowly greater than 1.25 times as the length increases;
- It will be passed when expandingmemmove()The function moves the old array to the new address, so the address will change after expansion.

This is the end of this article about the detailed analysis of the principle of golang slicing. For more related golang slicing, please search for my previous articles or continue browsing the related articles below. I hope everyone will support me in the future!