1.12 slice

This is a historical learning note and may contain outdated or incomplete understanding.

1. What Is a Slice?

An array that supports dynamic growth.

2. Why Do We Need Slices?

An array has a fixed number of elements and cannot grow dynamically.

3. How to Use Slices

3.1. Basic Usage

func TestSlice2(t *testing.T) {
	var a []int
	a = append(a, 1)                 // append one element
	a = append(a, 2, 3, 4)           // append multiple elements
	a = append(a, []int{5, 6, 7}...) // append another slice; it must be expanded

	fmt.Println(a)

	a = a[:len(a)-1] // remove the last element
	fmt.Println(a)

	fmt.Println(a[0])

	a[0] = 9999
	fmt.Println(a[0])
}

// Output
[1 2 3 4 5 6 7]
[1 2 3 4 5 6]
1
9999

3.2. Passing a Slice to a Function

func testSlices(slices []int) {
	slices[0] = 2
	fmt.Println(&slices, slices)
}

func TestSlice1(t *testing.T) {
	ints := make([]int, 1)
	testSlices(ints)
	fmt.Println(&ints, ints)
}

// Output
&[2] [2]
&[2] [2]

Although changes to the backing array are visible through the caller’s slice, an append may make the callee’s slice point to a new backing array. Therefore, when a function may append, return the resulting slice.

func testSlices(slices []int) {
	fmt.Println(len(slices), cap(slices), slices)
	slices = append(slices, 1) // length increases and slices changes
	slices[0] = 4
	fmt.Println(len(slices), cap(slices), slices)
}

func TestSlice3(t *testing.T) {
	ints := make([]int, 1)
	testSlices(ints)
	fmt.Println(len(ints), cap(ints), ints)
}

// Output
1 1 [0]
2 2 [4 1]
1 1 [0]

3.3. nil Slice and Empty Slice

A declared slice or one created with new is a nil slice, while one created with make is an empty slice.

func TestSlice4(t *testing.T) {
	var slice []int
	fmt.Println(slice == nil, slice, len(slice), cap(slice))

	slice2 := *new([]int)
	fmt.Println(slice2 == nil, slice2, len(slice2), cap(slice2))

	slice3 := make([]int, 0, 0)
	fmt.Println(slice3 == nil, slice3, len(slice3), cap(slice3))

	fmt.Println(reflect.DeepEqual(slice, slice2), reflect.DeepEqual(slice, slice3))
}

// Output
true [] 0 0
true [] 0 0
false [] 0 0
true false

3.4. A nil Slice Can Be Appended to Directly

Both a nil slice and an empty slice can obtain backing-array storage through append. Ultimately the runtime allocates memory through the Go memory manager and associates it with the original nil or empty slice, turning it into a slice backed by real storage.

3.5. A Slice Itself Is Immutable

The slice descriptor itself is copied as a value, but if its backing array is exposed, that array can be modified.

func TestSlice5(t *testing.T) {
	s := []int{1, 1, 1}
	f(s)
	fmt.Println(s)
}

func f(s []int) {
	for i := range s {
		s[i] += 1
	}
}

// Output
[2 2 2]

3.6. Copy

Copy elements from src to dst. The number copied is the smaller of the two lengths, and copy does not trigger growth.

4. Slice Internals

4.1. Data Structure

// runtime/slice.go
type slice struct {
	array unsafe.Pointer // pointer to the backing array
	len   int            // number of used elements
	cap   int            // total capacity: used + unused
}

4.2. Creation

4.2.1. new

var ints []int // equivalent in zero-value effect to using new([]int) and dereferencing it

4.2.2. make

ints := make([]int, 2, 5)

func main() {
	slice := make([]int, 5, 10) // length 5, capacity 10
	slice[2] = 2                // set the element at index 2 to 2
	fmt.Println(slice)
}

Use go tool compile -S main.go to print the assembly.

// main function definition, stack frame size 96B
0x0000 00000 (main.go:5)TEXT    "".main(SB), $96-0
0x0000 00000 (main.go:5)MOVQ    (TLS), CX
0x0009 00009 (main.go:5)CMPQ    SP, 16(CX)
0x000d 00013 (main.go:5)JLS     228
0x0013 00019 (main.go:5)SUBQ    $96, SP
0x0017 00023 (main.go:5)MOVQ    BP, 88(SP)
0x001c 00028 (main.go:5)LEAQ    88(SP), BP
0x0021 00033 (main.go:5)FUNCDATA    $0, gclocals·69c1753bd5f81501d95132d08af04464(SB)
0x0021 00033 (main.go:5)FUNCDATA    $1, gclocals·57cc5e9a024203768cbab1c731570886(SB)
0x0021 00033 (main.go:5)LEAQ    type.int(SB), AX
0x0028 00040 (main.go:6)MOVQ    AX, (SP)
0x002c 00044 (main.go:6)MOVQ    $5, 8(SP)
0x0035 00053 (main.go:6)MOVQ    $10, 16(SP)
0x003e 00062 (main.go:6)PCDATA  $0, $0
// create slice
0x003e 00062 (main.go:6)CALL    runtime.makeslice(SB)
0x0043 00067 (main.go:6)MOVQ    24(SP), AX
0x0048 00072 (main.go:6)MOVQ    32(SP), CX
0x004d 00077 (main.go:6)MOVQ    40(SP), DX
0x0052 00082 (main.go:7)CMPQ    CX, $2
0x0056 00086 (main.go:7)JLS     221
0x005c 00092 (main.go:7)MOVQ    $2, 16(AX)
0x0064 00100 (main.go:8)MOVQ    AX, ""..autotmp_2+64(SP)
0x0069 00105 (main.go:8)MOVQ    CX, ""..autotmp_2+72(SP)
0x006e 00110 (main.go:8)MOVQ    DX, ""..autotmp_2+80(SP)
0x0073 00115 (main.go:8)MOVQ    $0, ""..autotmp_1+48(SP)
0x007c 00124 (main.go:8)MOVQ    $0, ""..autotmp_1+56(SP)
0x0085 00133 (main.go:8)LEAQ    type.[]int(SB), AX
0x008c 00140 (main.go:8)MOVQ    AX, (SP)
0x0090 00144 (main.go:8)LEAQ    ""..autotmp_2+64(SP), AX
0x0095 00149 (main.go:8)MOVQ    AX, 8(SP)
0x009a 00154 (main.go:8)PCDATA  $0, $1
// type conversion. fmt.Println requires converting the slice
0x009a 00154 (main.go:8)CALL    runtime.convT2Eslice(SB)
0x009f 00159 (main.go:8)MOVQ    16(SP), AX
0x00a4 00164 (main.go:8)MOVQ    24(SP), CX
0x00a9 00169 (main.go:8)MOVQ    AX, ""..autotmp_1+48(SP)
0x00ae 00174 (main.go:8)MOVQ    CX, ""..autotmp_1+56(SP)
0x00b3 00179 (main.go:8)LEAQ    ""..autotmp_1+48(SP), AX
0x00b8 00184 (main.go:8)MOVQ    AX, (SP)
0x00bc 00188 (main.go:8)MOVQ    $1, 8(SP)
0x00c5 00197 (main.go:8)MOVQ    $1, 16(SP)
0x00ce 00206 (main.go:8)PCDATA  $0, $1
// print function
0x00ce 00206 (main.go:8)CALL    fmt.Println(SB)
0x00d3 00211 (main.go:9)MOVQ    88(SP), BP
0x00d8 00216 (main.go:9)ADDQ    $96, SP
0x00dc 00220 (main.go:9)RET
0x00dd 00221 (main.go:7)PCDATA  $0, $0
0x00dd 00221 (main.go:7)CALL    runtime.panicindex(SB)
0x00e2 00226 (main.go:7)UNDEF
0x00e4 00228 (main.go:7)NOP
0x00e4 00228 (main.go:5)PCDATA  $0, $-1
// stack growth. At function entry, the runtime checks whether the current stack has enough space.
// If not, it calls this function to grow the stack.
0x00e4 00228 (main.go:5)CALL    runtime.morestack_noctxt(SB)
0x00e9 00233 (main.go:5)JMP     0

The function that creates the slice type is cmd/compile/internal/types.NewSlice.

func NewSlice(elem *Type) *Type {
	if t := elem.Cache.slice; t != nil {
		if t.Elem() != elem {
			Fatalf("elem mismatch")
		}
		return t
	}

	t := New(TSLICE)
	// only contains the element type
	t.Extra = Slice{Elem: elem}
	elem.Cache.slice = t
	return t
}

Argument checking is handled by cmd/compile/internal/gc.typecheck1.

func typecheck1(n *Node, top int) (res *Node) {
	switch n.Op {
	...
	case OMAKE:
		args := n.List.Slice()

		i := 1
		switch t.Etype {
		case TSLICE:
		    // len must be provided
			if i >= len(args) {
				yyerror("missing len argument to make(%v)", t)
				return n
			}

			l = args[i]
			i++
			var r *Node
			if i < len(args) {
				r = args[i]
			}
			...
			// ensure cap is greater than or equal to len
			if Isconst(l, CTINT) && r != nil && Isconst(r, CTINT) && l.Val().U.(*Mpint).Cmp(r.Val().U.(*Mpint)) > 0 {
				yyerror("len larger than cap in make(%v)", t)
				return n
			}

			n.Left = l
			n.Right = r
			n.Op = OMAKESLICE
		}
	...
	}
}

At runtime, runtime.makeslice is called.

func makeslice(et *_type, len, cap int) unsafe.Pointer {
	// calculate the memory occupied by the slice and allocate a contiguous region on the heap
	mem, overflow := math.MulUintptr(et.size, uintptr(cap))
	if overflow || mem > maxAlloc || len < 0 || len > cap {
		// memory size = element size × slice capacity
		mem, overflow := math.MulUintptr(et.size, uintptr(len))
		if overflow || mem > maxAlloc || len < 0 {
			panicmakeslicelen()
		}
		panicmakeslicecap()
	}

	return mallocgc(mem, et, true)
}

4.2.3. Creating a Slice from an Array

slice := array[5:7]

4.3. Append

If the new slice returned by append does not need to be assigned back to the original variable, the processing flow is as follows.

// append(slice, 1, 2, 3)
// get its array pointer, length, and capacity
ptr, len, cap := slice
newlen := len + 3
// if the new length exceeds the capacity, runtime.growslice grows the slice
// and the new elements are then written in sequence
if newlen > cap {
    ptr, len, cap = growslice(slice, newlen)
    newlen = len + 3
}
*(ptr+len) = 1
*(ptr+len+1) = 2
*(ptr+len+2) = 3
return makeslice(ptr, newlen, cap)

If the slice returned by append overwrites the original slice variable:

// slice = append(slice, 1, 2, 3)
a := &slice
ptr, len, cap := slice
newlen := len + 3
if uint(newlen) > uint(cap) {
   newptr, len, newcap = growslice(slice, newlen)
   vardef(a)
   // do not assign back to the original variable here
   *a.cap = newcap
   *a.ptr = newptr
}
newlen = len + 3
*a.len = newlen
*(ptr+len) = 1
*(ptr+len+1) = 2
*(ptr+len+2) = 3

4.3.1. Growth Rules

func growslice(et *_type, old slice, cap int) slice {
	newcap := old.cap
	doublecap := newcap + newcap
	// if the requested capacity is greater than twice the current capacity,
	// use the requested capacity
	if cap > doublecap {
		newcap = cap
	} else {
		// if the current slice length is less than 1024, double the capacity
		if old.len < 1024 {
			newcap = doublecap
		} else {
			// if the current slice length is greater than 1024,
			// increase capacity by 25% each time until it reaches the requested capacity
			for 0 < newcap && newcap < cap {
				newcap += newcap / 4
			}
			if newcap <= 0 {
				newcap = cap
			}
		}
	}

If the requested new size is more than twice the current size, the size grows directly to the requested size. Otherwise, repeatedly apply the following rule: if the current size is below 1024, double it; otherwise increase it by one quarter each time, until the resulting size is at least the requested size.

Capacity growth
Allocated memory size
- Is it simply capacity × element size? No. It must match the runtime’s memory size classes.

4.4. Access

len and cap are handled by cmd/compile/internal/gc.epxr.

func (s *state) expr(n *Node) *ssa.Value {
	switch n.Op {
	case OLEN, OCAP:
		switch {
		case n.Left.Type.IsSlice():
			op := ssa.OpSliceLen
			if n.Op == OCAP {
				op = ssa.OpSliceCap
			}
			return s.newValue1(op, types.Types[TINT], s.expr(n.Left))
		...
		}
	...
	}
}

Indexed access:

func (s *state) expr(n *Node) *ssa.Value {
	switch n.Op {
	case OINDEX:
		switch {
		case n.Left.Type.IsSlice():
			p := s.addr(n, false)
			return s.load(n.Left.Type.Elem(), p)
		...
	}
	...
}