Slice uses summaries that are constantly updated on my Github

introduce

We all know that array is a fixed-length array, and slice is an extension of array. In essence, it is implemented based on array. The main feature is that once you define a slice variable, you don’t need to worry about its capacity. This article documents the underlying implementation of Slice without covering the basic use of Slice.

Slice structure

  • An array in slice is a pointer to an array
  • Len represents the length of the elements in this slice
  • Cap is the capacity of slice
  • Refer to the Golang Slice source code 
        type slice struct {
        array unsafe.Pointer
        len   int
        cap   int
    }
Copy the code

Slice capacity

Int {1,2,3,4,5,6} s = append(s, 6)Copy the code
  • If the new slice size is more than twice the current size, the size grows to the new size
  • If the current slice cap is less than 1024, increase by 2x each time, otherwise increase by 1/4 each time. Until the growing size exceeds or equals the new size
  • The implementation of append assigns the slice array value to the newly requested array in memory
  • Expansion source code implementation

performance

  • The benefit of slice scaling is that data is stored in continuous memory, which is much faster than random access. The immediate performance improvement is a much higher cache hit ratio, which is why Slice does not implement dynamic linked lists
  • We know that copying memory data has an overhead, and the biggest overhead is not in memmove data, but in creating a new memory malloc and the subsequent GC pressure
  • Copying contiguous memory is fast, and as cap gets bigger, the total cost of copying is still O(N), but the constant gets bigger
  • If you don’t want to copy, then you don’t have contiguous memory. In this case, the random access overhead will be: linked list O(N), doubled block chain O(LogN), a second level table with a large constant O(1).
  • When you have a rough idea of the maximum amount of space you need (and most of the time you do), reserve the corresponding cap for make
  • If the amount of space required is large and uncertain each time, there is a trade-off between wasted memory and cpu-consuming MALloc + GC
  • A list lookup starts with the first element, so it takes more time than an array, because it improves read performance

choose

  • Slice is flexible and performs well in most cases
  • However, there are special cases where the size of slice is very large and the contents of slice need to be changed frequently when using a List is more appropriate

Pay attention to the point

If you understand the above, you should not be surprised to see the output of this code

s := []byte{1.23.4.5.67.7}
s1 := s[2:3]
s1[0] = 100
fmt.Printf("s:%+v\n", s)
// s:[1 23 100 5 67 7]
Copy the code

Yes, the value of the third bit of slice S, 4, is replaced with 100 because the underlying array pointer to slice S1 points to the third bit of slice S, so manipulating s1 affects slice S