By the end of this article, you should be able to answer the following frequently asked interview questions
- The underlying implementation of Go Slice
- Difference between Go Array and Slice
- Go slice Deep copy and shallow copy
- What is the Go Slice expansion mechanism?
- Why is Go Slice non-thread-safe?
Realize the principle of
Slice is an array with no fixed length. The underlying structure is a structure containing the following three attributes
A slice occupies 24 bytes in golang
type slice struct {
array unsafe.Pointer
len int
cap int
}
Copy the codeArray: contains a pointer to an array. The data is actually stored on the array to which the pointer points, taking 8 bytes
Len: Indicates the length of the current slice. It takes 8 bytes
Cap: the current slice capacity, which is also the length of the underlying array, 8 bytes
Slice is not really a dynamic array, but a reference type. Slice always points to an underlying array, and slice can be declared just like array, but of variable length. The syntax sugar in Golang allows us to create slice constructs automatically, just as we declare arrays
The default value range is 0 ~ len(slice)-1 when the slice element value is taken according to the index position. When the slice element value is generally output, it usually refers to slice[0:len(slice)-1]. The value in the underlying array can be output according to the subscript
The main features
Reference types
Golang has three commonly used advanced types, Slice, Map, and Channel, which are reference types that may modify the original content data when used as function parameters.
func sliceModify(s []int) { s[0] = 100 } func sliceAppend(s []int) []int { s = append(s, Func sliceAppendPtr(s *[]int) {*s = append(*s, 100) return} // Copy content is non-reference type (int, string, struct, etc.), cannot modify the original content data in the function; // The copied content is a reference type (interface, pointer, map, slice, chan, etc.) so that the original content data can be modified. Func TestSliceFn(t * testing.t) {// The argument is reference type slice: The len/cap of the outer slice does not change, S := []int{1, 1, 1} newS := sliceAppend(s) // t.log (s, len(s), cap(s)) // [1 1 1] 3 3 t.log (newS, Len (newS), cap(newS)) // [1 1 1 100] 4 6 s2 := make([]int, 0, 5) newS = sliceAppend(s2). len(s2), cap(s2)) // [] [100 0 0 0 0] 0 5 t.Log(newS, newS[0:5], len(newS), Cap (newS)) // [100] [100 00 00] 1 5 // Parameters are Pointers to reference type slice: Len /cap of the outer slice will change, SliceAppendPtr (&s) t.log(s, len(s), cap(s)) // [1 1 1 100] 4 6 sliceModify(s) t.log(s, len(s), cap(s)) // [100 1 1 100] 4 6 }Copy the codeGet all the sample code for this article
Slice state
Slices have three special states, including “zero slice”, “empty slice” and “nil slice”.
func TestSliceEmptyOrNil(t *testing.T) { var slice1 []int // slice1 is nil slice slice2 := make([]int, 0) // slcie2 is empty slice var slice3 = make([]int, 2) // slice3 is zero slice if slice1 == nil {t.log ("slice1 is nil.") // will print this line} if slice2 == nil {t.log ("slice2 is Nil.") // will not print this line} t.log (slice3) // [0 0]}Copy the codeNon-thread-safe
Slice does not support concurrent reads and writes, so it is not thread-safe. When multiple Goroutines are used to operate on a variable of type Slice, the output value is likely to be different each time, which is inconsistent with the expected value. Slice does not report errors in concurrent execution, but data is lost
/** ** Func TestSliceConcurrencySafe(t * TestSliceConcurrencySafe) {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() t.Log(len(a)) // not equal 10000 }Copy the codeIf you want to implement slice thread safety, there are two ways:
Method 1: Implement slice thread security by locking, which is suitable for scenarios that do not have high requirements on performance.
Func TestSliceConcurrencySafeByMutex (t * testing. T) {var lock sync. The Mutex / / Mutex a: = make (int [], 0) var wg sync.WaitGroup for i := 0; i < 10000; i++ { wg.Add(1) go func(i int) { defer wg.Done() lock.Lock() defer lock.Unlock() a = append(a, i) }(i) } wg.Wait() t.Log(len(a)) // equal 10000 }Copy the codeMethod 2: Implement slice thread security through channels, which is suitable for scenarios with high performance requirements.
func TestSliceConcurrencySafeByChanel(t *testing.T) { buffer := make(chan int) a := make([]int, 0) // consumer go func() {for v := range buffer {a = append(a, v)}}() i < 10000; i++ { wg.Add(1) go func(i int) { defer wg.Done() buffer <- i }(i) } wg.Wait() t.Log(len(a)) // equal 10000 }Copy the codeShared Storage Space
If multiple slices share the same underlying array, changes to one slice or the underlying array can affect the other slices
/ * * * * / slice Shared storage space func TestSliceShareMemory (t * testing in t) {slice1: string [] = {" 1 ", "2", "3", "4", "5", "6", "7", "eight", "9", "10", "11", "12"} Q2 := slice1[3:6] t.Log(Q2, len(Q2), cap(Q2)) // [4 5 6] 3 9 Q3 := slice1[5:8] t.Log(Q3, len(Q3), cap(Q3)) // [6 7 8] 3 7 Q3[0] = "Unkown" t.Log(Q2, Q3) // [4 5 Unkown] [Unkown 7 8] a := []int{1, 2, 3, 4, 5} shadow := a[1:3] t.log (shadow, a) // [2 3] [1 2 3 4 5] shadow = append(shadow, 100) // a) // [2 3 100] [1 2 3 100 5] }Copy the codeCommon operations
create
Slice can be created in four ways as follows:
Func TestSliceInit(t * testing.t) { Var slice1 []int t.log (len(slice1), cap(slice1)) // 0, 0 slice1 = append(slice1, 1) t.log (len(slice1), Cap (slice1)) // 1, 1, 24 Slice2 := []int{1, 2, 3, 4} t.log2 (len(slice2), cap(slice2)) // 4, 4, 24 Make slice3 := make([]int, 3, 5) // make([]T, cap) cap 5 t.Log(slice3[0], slice3[1], slice3[2]) // 0, 0, 0 // t.Log(slice3[3], slice3[4]) // panic: runtime error: Index out of range [3] with length 3 slice3 = append(slice3, 1) t.log (len(slice3), cap(slice3)) // 4, 5, 24 Arr := [100]int{} for I := range arr {arr[I] = I} slcie4 := arr[1:3] slice5 := make([]int, Len (slcie4)) copy(slice5, slcie4) t.og (Len (slcie4), cap(slcie4), unsafe.sizeof (slcie4)) //, 99, Unsafe.sizeof (slice5) // unsafe.sizeof (slice5)Copy the codeincrease
func TestSliceGrowing(t *testing.T) {
slice1 := []int{}
for i := 0; i < 10; i++ {
slice1 = append(slice1, i)
t.Log(len(slice1), cap(slice1))
}
// 1 1
// 2 2
// 3 4
// 4 4
// 5 8
// 6 8
// 7 8
// 8 8
// 9 16
// 10 16
}
Copy the codedelete
Func TestSliceDelete(t *testing.T) {slice1 := []int{1, 2, 3, 4, 5} var x int slice1 = slice1[len(slice1)-1], slice1[:len(slice1)-1] t.Log(x, slice1, len(slice1), Cap (slice1)) // 5 [1 2 3 4] 4 5 slice1 = Append (slice1[:2], slice1[3:]...) t.Log(slice1, len(slice1), cap(slice1)) // [1 2 4] 3 5 }Copy the codeTo find the
V := s[I] // subscript accessCopy the codeModify the
S [I] = 5 // Subscript modificationCopy the codeThe interception
/ / func TestSliceSubstr(t * test.t) {slice1 := []int{1, 2, 3, 4, 5} slice2 := slice1[:] // slice[left:right: Max] // left: omit default 0 // right: omit default len(slice1) // Max: Omit default len(slice1) // cap = max-left t.log (slice2, len(slice2), cap(slice2)) // 1 2 3 4 5] 5 5 slice3 := slice1[1:] t.Log(slice3, len(slice3), cap(slice3)) // [2 3 4 5] 4 4 slice4 := slice1[:2] t.Log(slice4, len(slice4), cap(slice4)) // [1 2] 2 5 slice5 := slice1[1:2] t.Log(slice5, len(slice5), cap(slice5)) // [2] 1 4 slice6 := slice1[:2:5] t.Log(slice6, len(slice6), cap(slice6)) // [1 2] 2 5 slice7 := slice1[1:2:2] t.Log(slice7, len(slice7), cap(slice7)) // [2] 1 1 }Copy the codetraverse
There are three ways to traverse slices
Func TestSliceTravel(t *testing.T) {slice1 := []int{1, 2, 3, 4} for I := 0; i < len(slice1); i++ { t.Log(slice1[i]) } for idx, e := range slice1 { t.Log(idx, e) } for _, e := range slice1 { t.Log(e) } }Copy the codereverse
func TestSliceReverse(t *testing.T) {
a := []int{1, 2, 3, 4, 5}
for left, right := 0, len(a)-1; left < right; left, right = left+1, right-1 {
a[left], a[right] = a[right], a[left]
}
t.Log(a, len(a), cap(a))
// [5 4 3 2 1] 5 5
}
Copy the codecopy
Development will often copy a variable to another variable, so this process, may be shallow copy, so today to help you distinguish the difference between the two copies and the specific difference
Deep copy
Copy the data itself, create a new object, the newly created object and the original object do not share memory, the newly created object in memory to open a new memory address, the new object value does not affect the original object value. Since the memory address is different, the memory address can be released separately
Value type data, default assignment operations are deep copy Array, Int, String, Struct, Float, Bool. If you want to implement deep copy of data of reference type, you need to do so through auxiliary functions
For example, the Golang deep copy copy method copies elements from the source Slice value to the destination Slice and returns the number of copied elements. Both types of copy must be the same. The final copy result of the copy method depends on the shorter slice. When the copy of the shorter slice is completed, the whole replication process is complete
/** * func TestSliceDeepCopy(t *testing.T) {slice1 := []int{1, 2, 3, 4, 5} slice2 := make([]int, 5, // [1 2 3 4 5] 5 5 t.log (slice2, len(slice2), cap(slice2)) // [1 2 3 4 5] 5 5 slice1[1] = 100 t.Log(slice1, len(slice1), cap(slice1)) // [1 100 3 4 5] 5 5 t.Log(slice2, len(slice2), cap(slice2)) // [1 2 3 4 5] 5 5 }Copy the codeShallow copy
In this case, the memory address of the new object is the same as that of the old object. When the value of the new object is modified, the old object will also change. When the memory address is released, the memory address is also released.
By default, all reference types of data are shallow copies, such as Slice and Map
The destination slice and the source slice point to the same underlying array, and any change in an array element affects both arrays.
Func TestSliceShadowCopy(t *testing.T) {slice1 := []int{1, 2, 3, 4, 5} For value type is deep copy) slice2 := slice1 t.logf ("%p", slice1) // 0xC00001C120 t.logf ("%p", slice2) // 0xC00001C120 // change both arrays simultaneously, This is a shallow copy, and without scaling, after modifying the elements of slice1, Slice1 [0] = 10 t.og (slice1, Len (slice1), cap(slice1)) // [10 2 3 4 5] 5 5 t.og (slice2, len(slice2), Cap (slice2)) // [10 2 3 4 5] 5 5 After the expansion, slice1 and slice2 no longer refer to the same array. After modifying the elements of slice1, Slice1 = append(slice1, 5, 6, 7, 8) slice1[0] = 11 // [11 2 3 4 5 5 6 7 8] 9 10 t.log (slice2, len(slice1), cap(slice1)) len(slice2), cap(slice2)) // [10 2 3 4 5] 5 5 }Copy the codeWhen a slice is copied, Pointers to the arrays in the slice are also copied. Both slices point to the same array before triggering the expansion logic, which then points to different arrays
capacity
Expansion occurs at slice Append when the Slice cap is not large enough to accommodate new elements
Source: github.com/golang/go/b…
Func growslice(et *_type, old slice, cap int) slice { newcap := old.cap doublecap := newcap + newcap if cap > doublecap { newcap = cap } else { if old.len < 1024 { newcap = doublecap } else { // Check 0 < newcap to detect overflow // and prevent an infinite loop. for 0 < newcap && newcap < cap { newcap += newcap / 4 } // Set newcap to the requested cap when // the newcap calculation overflowed. if newcap <= 0 {newCap = cap}}} // omit some subsequent... }Copy the code- If the newly applied capacity is larger than the original capacity twice, the capacity after expansion is equal to the newly applied capacity
- If the original slice length is less than 1024, it will be doubled each time
- If the original slice is greater than or equal to 1024, each expansion is 1.25 times the original slice
Memory leaks
Since slice’s underlying structure is an array, it is likely that the array is large, but the number of elements slice takes is small, resulting in the vast majority of the space occupied by the array being wasted
Case1:
For example, in the following code, if a large slice B is passed in and a small portion is referenced to the global quantity A, the unreferenced portion of B (after subscript 1) will not be released, causing a so-called memory leak.
Var a []int func test(b []int) {a = b[:1] var a []int func test(b []int) {a = b[:1]Copy the codeSo as long as the global quantity A is there, b will not be recycled.
How to avoid it?
Note in this scenario: if we use only a small part of a slice, the entire underlying array will also remain in memory. When the underlying array is large, or there are many such scenarios, memory can increase dramatically, causing crashes.
So in this scenario, we can copy the required shards into a new slice, reducing the memory footprint
var a []int
func test(b []int) {
a = make([]int, 1)
copy(a, b[:0])
return
}
Copy the codeCase2:
For example, the following code returns a small slice so that the larger underlying array cannot be recycled after the function exits
func test2() []int{
s = make([]int, 0, 10000)
for i := 0; i < 10000; i++ {
s = append(s, p)
}
s2 := s[100:102]
return s2
}
Copy the codeHow to avoid it?
Copy the required shards into a new slice to reduce memory footprint
func test2() []int{ s = make([]int, 0, 10000) for i := 0; i < 10000; I++ {// some calculations... s = append(s, p) } s2 := make([]int, 2) copy(s2, s[100:102]) return s2 }Copy the codeSlice versus array
The array is of a fixed length and must be initialized with a specified length, otherwise it is slicing
Arrays are value types. Assigning an array to another array is passing a deep copy. Both assignment and parameter passing copy the entire array and consume extra memory. Slice is a reference type. Assigning one slice to another passes a shallow copy. Assignment and function passing only copy Len and CAP, but share the same array at the bottom and consume no extra memory.
Int {1, 2, 3} a := [3]int{1, 2, 3} a := [3]int{1, 2, 3} b := [3]int{1, 2, 3} The bottom array is a c := a[:] for I := 0; i < len(a); I ++ {a[I] = a[I] + 1} // I ++ {a[I] = a[I] + 1} C values change FMT. Println (a) / / (2 and 4] FMT. Println (b) / / [1 2 3] FMT Println (c) / / (2 and 4)Copy the codeA := []int{1, 2, 3} a := []int{1, 2, 3} b := a[:] for I := 0; i < len(a); I ++ {a[I] = a[I] + 1} // I ++ {a[I] = a[I] + 1} C values change FMT. Println (a) / / (2 and 4] FMT. Println (b) / / (2 and 4] FMT. Println (c) / / (2 and 4)Copy the codeconclusion
- When creating slices, you can pre-allocate capacity based on actual requirements. This improves performance by avoiding capacity expansion during adding slices
- Adding elements to slices using append() may trigger expansion, and new slices will be generated after expansion
- When len() and cap() are used to calculate the length and capacity of slices, the time complexity is O(1), and slices need not be traversed
- Slicing is not thread-safe, and if you want to achieve thread-safe, you can lock or use channels
- When a large array is used as a function parameter, the entire array data will be copied, consuming too much memory. Slice or pointer is recommended
- When slice is used as a function parameter, the array pointing to the slice can be changed, but len and Cap cannot be changed. To change the slice itself, either return the changed slice or take the slice pointer as a function parameter.
- If only a small part of a larger slice is used, you are advised to copy the required slices to a new slice to reduce memory usage
This article is published by OpenWrite!