Slice structure

Slice is an array in Golang that points to a contiguous fragment with a pointer, so it is essentially a reference type. A slice occupies 24 bytes in golang

A = make([]int, 0) unsafe.sizeof (a) // 24 var c int unsafe.sizeof (c) // 8Copy the code

In the Runtime slice.go, a struct for slice is defined

type slice struct {
    array unsafe.Pointer	// 8 bytes
    len   int				// 8 bytes
    capInt // 8 bytes // Confirm, slice size 24}Copy the code
  • Array is a PTR that points to a real array
  • Len refers to the number of existing elements in the slice
  • Cap refers to the space currently allocated

Ready to debug

How does Golang initialize a slice

package main

import "fmt"

func main() {
    a := make([]int, 0)
    a = append(a, 2, 3, 4)
    fmt.Println(a)
}
Copy the code

Slice the initialization

Using DLV debugging, after disassembly:

(dlv) disassemble
TEXT main.main(SB) /Users/such/gomodule/runtime/main.go
main.go:5       0x10b70f0       65488b0c2530000000              mov rcx, qword ptr gs:[0x30]
main.go:5       0x10b70f9       488d4424e8                      lea rax, ptr [rsp-0x18]
main.go:5       0x10b70fe       483b4110                        cmp rax, qword ptr [rcx+0x10]
main.go:5       0x10b7102       0f8637010000                    jbe 0x10b723f      main.go:5       0x10b7108*      4881ec98000000                  sub rsp, 0x98
main.go:5       0x10b710f       4889ac2490000000                mov qword ptr [rsp+0x90], rbp
main.go:5       0x10b7117       488dac2490000000                lea rbp, ptr [rsp+0x90]
main.go:6       0x10b711f       488d051a0e0100                  lea rax, ptr [rip+0x10e1a]
main.go:6       0x10b7126       48890424                        mov qword ptr [rsp], rax
main.go:6       0x10b712a       0f57c0                          xorps xmm0, xmm0
main.go:6       0x10b712d       0f11442408                      movups xmmword ptr [rsp+0x8], xmm0
main.go:6       0x10b7132       e8b99af8ff                      ** call $runtime.makeslice **
main.go:6       0x10b7137       488b442418                      mov rax, qword ptr [rsp+0x18]
main.go:6       0x10b713c       4889442460                      mov qword ptr [rsp+0x60], rax
main.go:6       0x10b7141       0f57c0                          xorps xmm0, xmm0
main.go:6       0x10b7144       0f11442468                      movups xmmword ptr [rsp+0x68], xmm0
...
Copy the code

In a stack of instructions, you can see that a call to call $Runtime.makeslice should initialize slice

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)}Copy the code

Makeslice returns the memory address of the array field that creates the value.

Println (uintptr(0), ^uintptr(0)) // 0 var c int = 1 println(^c, ^uint64(0)) // -2 18446744073709551615Copy the code

Verify from these lines that the signed 1, binary: 0001, xor after: 1110, the highest bit 1 is negative, representing -2; 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000 1111, 1111, 1111, 1111, 1111, 1111, 1111, 1111, 1111, 1111, because it’s unsigned, it’s converted to base 10, So 2 to the 64-1 is 18446744073709551615. In fact, the uintptr(0) refers to the current machine (32-bit, uint32; 64-bit, uint64). So we can print the current A

(dlv) p a
[]int len: 1, cap: 0, [0]
Copy the code

Slice capacity

=>      main.go:7       0x10b7149       eb00                            jmp 0x10b714b
        main.go:7       0x10b714b       488d0dee0d0100                  lea rcx, ptr [rip+0x10dee]
        main.go:7       0x10b7152       48890c24                        mov qword ptr [rsp], rcx
        main.go:7       0x10b7156       4889442408                      mov qword ptr [rsp+0x8], rax
        main.go:7       0x10b715b       0f57c0                          xorps xmm0, xmm0
        main.go:7       0x10b715e       0f11442410                      movups xmmword ptr [rsp+0x10], xmm0
        main.go:7       0x10b7163       48c744242003000000              mov qword ptr [rsp+0x20], 0x3
        main.go:7       0x10b716c       e84f9bf8ff                      call $runtime.growslice
        main.go:7       0x10b7171       488b442428                      mov rax, qword ptr [rsp+0x28]
        main.go:7       0x10b7176       488b4c2430                      mov rcx, qword ptr [rsp+0x30]
        main.go:7       0x10b717b       488b542438                      mov rdx, qword ptr [rsp+0x38]
        main.go:7       0x10b7180       4883c103                        add rcx, 0x3
        main.go:7       0x10b7184       eb00                            jmp 0x10b7186
        main.go:7       0x10b7186       48c70002000000                  mov qword ptr [rax], 0x2
        main.go:7       0x10b718d       48c7400803000000                mov qword ptr [rax+0x8], 0x3
        main.go:7       0x10b7195       48c7401004000000                mov qword ptr [rax+0x10], 0x4
        main.go:7       0x10b719d       4889442460                      mov qword ptr [rsp+0x60], rax
        main.go:7       0x10b71a2       48894c2468                      mov qword ptr [rsp+0x68], rcx
        main.go:7       0x10b71a7       4889542470                      mov qword 
		...
Copy the code

To append a slice, call Runtime. growslice

func growslice(et *_type, old slice, cap int) slice {
	if cap < old.cap {
		panic(errorString("growslice: cap out of range"))}if et.size == 0 {
		// append should not create a slice with nil pointer but non-zero len.
		// We assume that append doesn't need to preserve old.array in this case. return slice{unsafe.Pointer(&zerobase), old.len, cap} } 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 } } } var overflow bool var lenmem, newlenmem, capmem uintptr // Specialize for common values of et.size. // For 1 we don't need any division/multiplication.
	// For sys.PtrSize, compiler will optimize division/multiplication into a shift by a constant.
	// For powers of 2, use a variable shift.
	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)
	}

	if overflow || capmem > maxAlloc {
		panic(errorString("growslice: cap out of range"))
	}

	var p unsafe.Pointer
	ifP = mallocGC (capmem, nil,false) // Clear the unused address memclrNoHeapPointers(add(p, newlenmem), capmem-newlenmem)}else {
		p = mallocgc(capmem, et, true)
		iflenmem > 0 && writeBarrier.enabled { bulkBarrierPreWriteSrcOnly(uintptr(p), uintptr(old.array), Lenmem)}} // Copy size lenmem btyes, from old.array to p memmove(p, old.array, lenmem)return slice{p, old.len, newcap}
Copy the code

Specific expansion strategies:

  • If the requested capacity (CAP) is greater than 2 times the original capacity (old.cap) or less than 1024, newCap = old.cap + old.cap
  • Otherwise, calculatenewcap += newcap / 4, know that newCap is not less than the capacity to apply, if overflow, newCap = cap (capacity to apply)

After expansion, the address is recalculated based on the size of t.size. The len of the new slice is the CAP of the original slice (expansion is required only when the len of the new slice exceeds the CAP). Copy lenmem bytes from old.array (lenmem) to P.

a := make([]int, 0)
a = append(a, 1)
println("1 times:", len(a), cap(a))	// 1 times: 1 1

a = append(a, 2, 3)
println("2 times:", len(a), cap(a))	// 2 times: 3 4

a = append(a, 4)
println("3 times:", len(a), cap(a))	// 3 times4 4:Copy the code

As can be seen:

  1. ifappendAfter thelenIs greater thancapThat is, expand to greater thanlenThe first multiple of 2 of PI
  2. ifappendAfter thelenIs greater thancapAnd less thancapTwo times,capI’m going to double that
  3. ifappendAfter thelenLess thancap, directly append

Slice pollution

With Slice, some problems may be unknowingly created.

a := []int{1, 2, 3, 4, 5}
shadow := a[1:3]
shadow = append(shadow, 100)
fmt.Println(shadow, a)
// [2 3 100] [1 2 3 100 5]
Copy the code

The result was surprising, but logical. In the structure of a, array is the memory address pointing to the array [1,2,3,4,5], shadow is the memory address pointing to [2,3]. After adding to shadow, it directly modifies the real array, indirectly affecting all slices pointing to the array. So you can change the above code to:

a := []int{1, 2, 3, 4, 5}
shadow := append([]int{}, a[1:3]...)
shadow = append(shadow, 100)
fmt.Println(shadow, a)
// [2 3 100] [1 2 3 4 5]
Copy the code

If (1,2,3,4,5) returns a (1,2,3,4,5), the memory used by the lock cannot be freed.

Black magic

Knowing that Slice is itself a pointer to a real array, Golang provides unsafe for pointer manipulation.

a := []int{1, 2, 3, 4, 5} shadow := a[1:3] shadowPtr := uintptr(unsafe.Pointer(&shadow[0])) offset := unsafe.Sizeof(int(0)) fmt.Println(*(*int)(unsafe.Pointer(shadowPtr - offset))) // 1 fmt.Println(*(*int)(unsafe.Pointer(shadowPtr + 2*offset))) / / 4Copy the code

ShadowPtr is the position of the first subscript of A. An int is 8 bytes on 64-bit machines, offset forward by 1 offset, and is the 0th subscript 1 of A. Offset back by 2 offsets, the third subscript of A, 4.

Concurrent security

Slice is a non-coroutine safe data type and can be lost if multiple Goroutines are created to read and write to slice concurrently. Look at a piece of code

package main

import (
	"fmt"
	"sync"
)

func main () {
    a := make([]int, 0)
    var wg sync.WaitGroup
    for i := 0; i < 10000; i++ {
        wg.Add(1)
        go func(i int) {
            a = append(a, i)
            wg.Done()
        }(i)
    }
    wg.Wait()
    fmt.Println(len(a))
}
// 9403 9876 9985 9491 ...
Copy the code

Execute it multiple times, and each time you get a different result, you’re definitely not going to get the 10,000 you want. To solve this problem, consider using a feature of the channel itself (blocking) to implement safe concurrent reads and writes in terms of coroutine safety.

func main() {
    a := make([]int, 0)
    buffer := make(chan int)
    go func() {
        for v := range buffer {
            a = append(a, v)
        }
    }()

    var wg sync.WaitGroup
    for i := 0; i < 10000; i++ {
        wg.Add(1)
        go func(i int) {
            buffer <- i
            wg.Done()
        }(i)
    }
    wg.Wait()
    fmt.Println(len(a))
}
// 10000
Copy the code