The interview questions

Recently, the author of Go 101 published 11 Go interview questions, which were very interesting, and planned to write a series of detailed analysis of each question. Welcome to your attention.

Read the following section about Slice to get a better understanding of the features and considerations of slice.

package main import "fmt" func main() { a := [...] int{0, 1, 2, 3} x := a[:1] y := a[2:] x = append(x, y...) x = append(x, y...) fmt.Println(a, x) }Copy the code
  • A: [0 1 2 3] [0 2 3 3 3]
  • B: [0 2 3 3] [0 2 3 3 3]
  • C: [0 1 2 3] [0 2 3 2 3]
  • D: [0 2 3 3] [0 2 3 2 3]

Leave your answers in the comments section. There are several reasons for this question:

  1. sliceWhat is the underlying data structure of? tosliceAssign. What exactly is assigned?
  2. through:Operation get newsliceAnd the originalsliceWhat is the relationship? newsliceWhat is the length and capacity of?
  3. appendWhat exactly is going on behind the scenes?
  4. sliceWhat is the capacity expansion mechanism?

parsing

Let’s answer each of these questions one by one.

Slice’s underlying data structure

talk is cheap, show me the code. Slice source code directly:

Slice is defined in SRC/Runtime /slice.go on line 15. .

SRC /unsafe.go (line 184); / / a Pointer is defined in SRC /unsafe.go (line 184). .

type slice struct {
    array unsafe.Pointer
    len   int
    cap   int
}

type Pointer *ArbitraryType
Copy the code

Slice is actually a structure type containing three fields, respectively

  • Array: is a pointer to an array in which the sliced data is actually stored.
  • Len: The length of the slice.
  • Cap: The capacity of a slice. It indicates the maximum number of elements that a slice can store. If the current capacity is exceeded, the slice will be automatically expanded.

So assigning values to slice is actually assigning values to the three fields in slice. This may seem like a valid line of crap, but trust me, remembering this line will help you understand very clearly how the values of the three fields in slice and the data in the underlying array that Slice points to change when you make changes to slice.

: The split operator

The: split operator has several characteristics:

  1. : Data interception can be performed on arrays or slices, and the result is a new slice.

  2. newsliceIn the structurearrayPointer to a primitive array or primitivesliceThe length of the new slice is:The value on the right minus the value on the left, the capacity of the new slice is the capacity of the original slice minus:The number on the left.

  3. The default value is 0 if no number is written to the left of:, and the default value is the length of the split array or slice if no number is written to the right.

    A: = make (int [], 0, 4) / / a is zero, the length of the capacity is 4 b: = [:] / / equivalent to b: = [at] a, b is zero, the length of the capacity is 4 c: = a [1] / / equivalent to the c: (1-0) = a, b is 1, the length of the Panic: runtime error: Slice bounds out of range e := a[1:4] e := a[1:4] e := a[1:4] E := a[1:4Copy the code

  4. The value to the right of the split operator has an upper limit, which can occur in two cases

  • If you split an array, the upper limit is the length of the array to be split.
  • If the slice is being divided, the upper limit is the capacity of the slice being divided. Note that this is not the same as subscripting. If a subscript index is used to access a slice, the maximum value of the subscript index is (the length of the slice -1), not the size of the slice.

A picture is worth a thousand words. Let’s explain the mechanism of slice segmentation through the following example.

The following figure shows the slice structure. PTR represents the array pointer pointing to the underlying array. Len and Cap are the length and capacity of the slice respectively.

Step1: create a slice s with length and capacity 5 by using s := make([]byte, 5, 5).



Step2: Now slicesDo the segmentations2 := s[2:4]And get a new slices2, the structure is as follows.

  • s2I’m still pointing to the original slicesThe underlying array points to a position with index 2.
  • s2The length of thelen(s2)It’s 2 becauses2 := s[2:4]I just took a slicesTwo elements with subscript indexes of 2 and 3.
  • s2The capacity of thecap(s2)It’s 3, because froms2Point to the end of the underlying array, which can hold three elements.
  • Because the length is 2, so onlys2[0]ands2[1]Is valid subscript index access. But with capacity three,s2[0:3]Is a valid partition expression.

Step3: Segment section S S3 := s2[:cap(s2)], and obtain a new section S3 with the structure as follows:

  • s3Pointing to the slices2The underlying array, as wellsThe underlying array pointing to the starting position iss2Is the starting position of the array index 2.
  • s3The length of thelen(s3)It’s 3 becauses3 := s2[:cap(s2)]The slices were takens2Three elements with subindexes 0, 1, and 2.
  • s3The capacity of thecap(s3)It’s 3, because froms3Point to the end of the underlying array, which can hold three elements.

So do arrays or slices:The new slice created by the split operation still points to the original underlying array and does not copy the elements of the original underlying array into the new memory space.

Because they point to the same memory space, changes to the original array or slice will affect the value of the new slice, and vice versa.

Append mechanism

To understand the mechanics of Append, read the source code.

// The append built-in function appends elements to the end of a slice. If // it has sufficient capacity, the destination is resliced to accommodate the // new elements. If it does not, a new underlying array will be allocated. // Append returns the updated slice. It is therefore necessary to store the //  result of append, often in the variable holding the slice itself: // slice = append(slice, elem1, elem2) // slice = append(slice, anotherSlice...) // As a special case, it is legal to append a string to a byte slice, like this: // slice = append([]byte("hello "), "world"...) func append(slice []Type, elems ... Type) []TypeCopy the code

  • The append function returns a slice. Append adds a new element to the end of the original slice, which is the end of the length of the slice, not the end of the size of the slice.

    Func test() {make([]int, 0, 4) b := append(a, 1) // b=[1] Println(a, b, c) // [] [2] [2]}Copy the code

  • If the original slice is large enough to contain the new element, the append function returns the values of the three fields in the slice structure:

    • The value of the array pointer field remains the same as the value of the array pointer to the original slice, that is, whether appEnd returns the slice in the underlying array of the original slice or points to the underlying array of the original slice
    • The len length field is incremented by N elements and the length increases by N
    • Cap capacity unchanged

  • If the original slice does not have enough capacity to store the appEnd element, Go allocates a new chunk of memory with more capacity, copies all the elements in the original slice, and finally adds new elements to the new memory. The append function returns the values of the three fields in the slice structure:

    • The value of the array pointer field has changed. Instead of pointing to the underlying array of the original slice, it points to a new memory space
    • The len length field is incremented by N elements and the length increases by N
    • Cap capacity will increase

Note: Append does not change the value of the original slice, and the length and capacity of the original slice remain unchanged, unless append’s return value is assigned to the original slice.

So the question is, by what rule is the capacity of the new slice calculated?

Slice expansion mechanism

Slice’s scaling mechanism changes as Go releases iterate. So far, most of the comments on the Internet are as follows:

When the original slice capacity is less than 1024, the new slice capacity is doubled. When the original slice capacity exceeds 1024, the new slice capacity becomes 1.25 times of the original capacity.

And I’m telling you explicitly that this conclusion is wrong.

SRC /runtime/slice.go growslice function: github.com/golang/go/…. .

The capacity expansion implementation code of Go 1.18 is as follows, et is the element type in the slice, old is the original slice, cap is equal to the length of the original slice + the number of new elements in append.

func growslice(et *_type, old slice, cap int) slice {
    // ...
    newcap := old.cap
    doublecap := newcap + newcap
    if cap > doublecap {
        newcap = cap
    } else {
        const threshold = 256
        if old.cap < 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
            }
        }
    }

    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 == goarch.PtrSize:
        lenmem = uintptr(old.len) * goarch.PtrSize
        newlenmem = uintptr(cap) * goarch.PtrSize
        capmem = roundupsize(uintptr(newcap) * goarch.PtrSize)
        overflow = uintptr(newcap) > maxAlloc/goarch.PtrSize
        newcap = int(capmem / goarch.PtrSize)
    case isPowerOfTwo(et.size):
        var shift uintptr
        if goarch.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)
    }
    // ...
    return slice{p, old.len, newcap}
}
Copy the code

Newcap is the capacity after expansion. The size of newCap is determined according to the length, capacity and number of elements to be added of the original slice. Finally, memory alignment is performed to obtain the final newCap.

The answer

Let’s go back to the original topic of this article and parse the results of each line of code line by line.

Extra meal: Copy mechanism

SRC /builtin/builtin.go /builtin.go /builtin.go /builtin.go /builtin.go /builtin.go

// The copy built-in function copies elements from a source slice into a
// destination slice. (As a special case, it also will copy bytes from a
// string to a slice of bytes.) The source and destination may overlap. Copy
// returns the number of elements copied, which will be the minimum of
// len(src) and len(dst).
func copy(dst, src []Type) int
Copy the code

Copy min(len(DST), len(SRC)) elements from the original slice SRC to the target slice DST.

The number of copied elements min(DST) and len(SRC) cannot exceed the length of the target slice len(DST). Therefore, after copy is executed, the length and capacity of the target slice remain unchanged.

Note: The memory space of the original slice and the target slice may overlap, and the value of the original slice may be changed after copy. Please refer to the following example.

Package main import "FMT" func main() {a := []int{1, 2, 3} b := a[1:] // [2 3] copy(a, b) FMT.Println(a, b) b) // [2 3 3] [3 3] }Copy the code

conclusion

For slice, keep in mind how the three fields in slice: pointer, length, and capacity change after modification.

  • Slice is a structure type that contains three fields: an array pointer to an array, length Len, and capacity CAP. Assigning to slice is a pointer to slice. The length and capacity fields are assigned separately.

  • The result of the: slice operator is a new slice. The array pointer in the new slice structure points to the original array or the underlying array of the original slice. The length of the new slice is the right value minus the left value, and the size of the new slice is the original size minus the left value.

  • The upper limit to the right of the split operator has two cases:

    • If you split an array, the upper limit is the length of the array to be split.
    • If the slice is being divided, the upper limit is the capacity of the slice being divided. Note that this is not the same as subscripting. If a subscript index is used to access a slice, the maximum value of the subscript index is (the length of the slice -1), not the size of the slice.

  • For append and copy operations, be aware of the logic behind the execution.

  • When printing a slice, it prints according to the length of the slice

    A := make([]int, 1, 4) // make([]int, 1, 4) // make([]int, 1, 4) // make([]int, 1, 4) // make([]int, 1, 4) // make([]int, 1, 4) // make([]int, 1, 4) // Println(a, b) // [0] [0 1]Copy the code

  • When a function passes an argument, Go does not pass a reference to this statement, only a value. Some articles on the Internet write that the parameters of Go slice, map and channel are passed by reference, which is wrong. Can you refer to my previous article that Go has reference variable and reference pass?

Open source address

Article and sample code open source address at GitHub: github.com/jincheng9/….

Public id: coding advanced

Personal website: Jincheng9.github. IO /

To consider

Leave two thought questions and feel free to leave your answers in the comments section.

  • Title 1:

    package main

import "fmt"

func main() {
    a := []int{1, 2}
    b := append(a, 3)

    c := append(b, 4)
    d := append(b, 5)

    fmt.Println(a, b, c[3], d[3])
}
Copy the code

  • Topic 2

    package main

import "fmt"

func main() {
    s := []int{1, 2}
    s = append(s, 4, 5, 6)
    fmt.Println(len(s), cap(s))
}
Copy the code

References

  • Go101.org/quizzes/sli…
  • Go. / dev/blog slices…
  • Github.com/golang/go/….
  • qcrao91.gitbook.io/go…