Golang slice

Golang slice content

Differences in initialization methods

var s [] int // s will be initialized to nil
s := []int{} // s is initialized to a slice of size 0
s := make([]int, initial length)// s will be filled with zero, which will be added after the initial length using the append method
Copy the code

Automatic slice expansion method

/** Automatic slice expansion has some strange problems. To put it simply, its capacity increase and ratio are not a simple fixed proportion or fixed value, but an indefinite length of data. Go Version go1.15.13 Linux/AMD64: */
package main
import (
"fmt"
)
func main(a) {
   s := make([]int.0)
   oldCap := cap(s)
   for i := 0; i < 1024*64; i++ {
      s = append(s, i)
      newCap := cap(s)
      ifnewCap ! = oldCap { fmt.Printf("before cap = %-4d | after append %-4d cap = %-4d raise = %-4d ratio = %.4f\n",  oldCap, i, newCap, newCap - oldCap,  float64(newCap)/float64(oldCap))
         oldCap = newCap
      }
   }
}
Copy the code

The test results are as follows:

before cap = 0     |  after append 0     cap = 1     raise = 1    ratio = +Inf
before cap = 1     |  after append 1     cap = 2     raise = 1    ratio = 2.0000
before cap = 2     |  after append 2     cap = 4     raise = 2    ratio = 2.0000
before cap = 4     |  after append 4     cap = 8     raise = 4    ratio = 2.0000
before cap = 8     |  after append 8     cap = 16    raise = 8    ratio = 2.0000
before cap = 16    |  after append 16    cap = 32    raise = 16   ratio = 2.0000
before cap = 32    |  after append 32    cap = 64    raise = 32   ratio = 2.0000
before cap = 64    |  after append 64    cap = 128   raise = 64   ratio = 2.0000
before cap = 128   |  after append 128   cap = 256   raise = 128  ratio = 2.0000
before cap = 256   |  after append 256   cap = 512   raise = 256  ratio = 2.0000
before cap = 512   |  after append 512   cap = 1024  raise = 512  ratio = 2.0000
before cap = 1024  |  after append 1024  cap = 1280  raise = 256  ratio = 1.2500
before cap = 1280  |  after append 1280  cap1696 raise = 416 ratio = 1.3250 beforecap = 1696  |  after append 1696  capRaise = 608 ratio = 1.3585 beforecap = 2304  |  after append 2304  cap = 3072  raise = 768  ratio = 1.3333
before cap = 3072  |  after append 3072  cap = 4096  raise = 1024 ratio = 1.3333
before cap = 4096  |  after append 4096  cap = 5120  raise = 1024 ratio = 1.2500
before cap = 5120  |  after append 5120  cap = 7168  raise = 2048 ratio = 1.4000
before cap = 7168  |  after append 7168  cap = 9216  raise = 2048 ratio = 1.2857
before cap = 9216  |  after append 9216  cap = 12288  raise = 3072 ratio = 1.3333
before cap = 12288  |  after append 12288  cap = 15360  raise = 3072 ratio = 1.2500
before cap = 15360  |  after append 15360  cap = 19456  raise = 4096 ratio = 1.2667
before cap = 19456  |  after append 19456  cap = 24576  raise = 5120 ratio = 1.2632
before cap = 24576  |  after append 24576  cap = 30720  raise = 6144 ratio = 1.2500
before cap = 30720  |  after append 30720  cap38912 raise = 8192 ratio = 1.2667 beforecap = 38912  |  after append 38912  cap = 49152  raise = 10240 ratio = 1.2632
before cap = 49152  |  after append 49152  cap = 61440  raise = 12288 ratio = 1.2500
Copy the code

After reviewing the source code, it is found that the actual capacity adjustment method is shown as: when the original array size is less than 1024, it is directly doubled, otherwise it is always increased by 0.25

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

Then, according to the pattern of data types in Slice, the memory required for the new capacity will be rounded up and the capacity will be modified based on the following code:

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

Therefore, there are a lot of 1.33 ratio in the above expansion process, which is actually caused by the subsequent expansion.

Problems with using slice as a function parameter

Using slice as a function parameter is very convenient and avoids the problem of passing array type values without changing the original data, but it also needs to be careful to expand the slice function. Since slice is essentially a pointer and len, cap forms a body of data.

// Slice type nature
type slice struct {
    array unsafe.Pointer
    len   int
    cap   int
}
Copy the code

If the location of the incoming slice and outgoing slice addresses changes during expansion, the original slice remains unchanged and the new slice will be reclaimed in the next round of reclamation. The test code and test results are as follows:

package main
import (
   "fmt"
)

func ModifySlice(slice [] int, i int)[] int {
   slice[0] = 1
   // Outputs the address position and result before append
   fmt.Printf("before append: slice at %p, slice is ", &slice )
   fmt.Println(slice)
   slice = append(slice, i)
   fmt.Printf("after append: slice at %p, slice is ", &slice )
   fmt.Println(slice)
   return  slice
}

func main(a)  {
   s := make([] int.3)
   for i := 0; i < 10; i++{
      ModifySlice(s,i )
      // Outputs the address position and result outside the function
      fmt.Printf("out of function: slice at %p, slice is", &s )
      fmt.Println(s)
   }
}
Copy the code
before append: slice at 0xc0000ae040, slice is [1 0 0]
after append: slice at 0xc0000ae040, slice is [1 0 0 0]
out of function: slice at 0xc0000ae020, slice is[1 0 0]
before append: slice at 0xc0000ae0c0, slice is [1 0 0]
after append: slice at 0xc0000ae0c0, slice is [1 0 0 1]
out of function: slice at 0xc0000ae020, slice is[1 0 0]
before append: slice at 0xc0000ae140, slice is [1 0 0]
after append: slice at 0xc0000ae140, slice is [1 0 0 2]
out of function: slice at 0xc0000ae020, slice is[1 0 0]
before append: slice at 0xc0000ae1c0, slice is [1 0 0]
after append: slice at 0xc0000ae1c0, slice is [1 0 0 3]
out of function: slice at 0xc0000ae020, slice is[1 0 0]
before append: slice at 0xc0000ae240, slice is [1 0 0]
after append: slice at 0xc0000ae240, slice is [1 0 0 4]
out of function: slice at 0xc0000ae020, slice is[1 0 0]
before append: slice at 0xc0000ae2c0, slice is [1 0 0]
after append: slice at 0xc0000ae2c0, slice is [1 0 0 5]
out of function: slice at 0xc0000ae020, slice is[1 0 0]
before append: slice at 0xc0000ae340, slice is [1 0 0]
after append: slice at 0xc0000ae340, slice is [1 0 0 6]
out of function: slice at 0xc0000ae020, slice is[1 0 0]
before append: slice at 0xc0000ae3c0, slice is [1 0 0]
after append: slice at 0xc0000ae3c0, slice is [1 0 0 7]
out of function: slice at 0xc0000ae020, slice is[1 0 0]
before append: slice at 0xc0000ae440, slice is [1 0 0]
after append: slice at 0xc0000ae440, slice is [1 0 0 8]
out of function: slice at 0xc0000ae020, slice is[1 0 0]
before append: slice at 0xc0000ae4c0, slice is [1 0 0]
after append: slice at 0xc0000ae4c0, slice is [1 0 0 9]
out of function: slice at 0xc0000ae020, slice is[1 0 0]
Copy the code

It can be seen that the slice datatype argument passes a reference to an address, while the append method will change the address of slice if it expands. This can cause some changes in production not to take effect. Golang is essentially pass-by-value, there is no pass-by-reference, which means that passing a pointer to a slice is actually fine, but passing a slice value is.