Discover Insane Possibility
of Go Slice Usage
from Runtime Source Code

• A programmer from game company in Taiwan
• Backend (and temporary frontend) engineer
• Usually develop something related to my work in Python, Ruby, ECMAScript, Golang, C#
• ECMAScript hater since Netscape is dead
• Built CDN-aware game asset update system
• Professional small vehicle driver
• Draw cute anime character in spare time

4. What is Slice?
   • Array
   • Slice

5. Source Code of Slice Implementation
   • Runtime
     • Slice Structure
       • Caution
     • Utility Functions
     • Where is append()?
   • Compile Time
     • Slice Operation
       • Accessing Slice Elements
       • Re-slicing
     • Machine Code Optimization

6. Insane Slice Application
   • SliceTricks
   • Application in Algorithm
   • One More Thing
7. Conclusion
8. Resource
9. Q&A

Array

var a [4]int
a[0] = 1
i := a[0]
// i == 1
 
// a[2] == 0, the zero value of the int type

Array Structure

Array Literal

b := [2]string{"Penn", "Teller"}
 
// make the compiler count the array elements
b := [...]string{"Penn", "Teller"}

Slice

func make([]T, len, cap) []T
 
var s []byte
s = make([]byte, 5, 5)
// s == []byte{0, 0, 0, 0, 0}

Slice

s := make([]byte, 5)
 
len(s) == 5
cap(s) == 5

Slice Structure

Slice Literal

letters := []string{"a", "b", "c", "d"}

Runtime

https://github.com/golang/go/blob/go1.16.5/src/runtime/slice.go

Slice Structure

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

Caution

• Underlying arrays of slices are mutable
• Slices themselves are immutable
• Call by value

Utility Functions

func makeslice(et *_type, len, cap int) unsafe.Pointer
func growslice(et *_type, old slice, cap int) slice
func slicecopy(toPtr unsafe.Pointer, toLen int, fromPtr unsafe.Pointer, fromLen int, width uintptr)
 
append() // where?

Where is append()?

https://github.com/golang/go/blob/go1.16.5/src/cmd/compile/internal/gc/ssa.go#L2841

Compile Time

https://github.com/golang/go/blob/go1.16.5/src/cmd/compile/internal/gc/ssa.go#L5458

Slice Operation

• Accessing slice elements
• Re-slicing

Accessing Slice Elements

• slice
• string
• pointer

val := s[2]
s[3] = val

Re-slicing

• slice
• string
• pointer

// i : begin index (include)
// j : end index (exclude)
// k : index of capacity boundary (exclude)
s := v[i:j:k]

Boundary Checking

// k <= cap(v)
// j <= k
s := v[i:j:k]

• "len(s) > len(v)"
  • if capacity of underlying array is enough
    • string doesn't have cap property

New Slice Caculation

// Calculate the base pointer (rptr) for the new slice.
//
// Generate the following code assuming that indexes are in bounds.
// The masking is to make sure that we don't generate a slice
// that points to the next object in memory. We cannot just set
// the pointer to nil because then we would create a nil slice or
// string.
//
//     rcap = k - i
//     rlen = j - i
//     rptr = ptr + (mask(rcap) & (i * stride))
//
// Where mask(x) is 0 if x==0 and -1 if x>0 and stride is the width
// of the element type.

Machine Code Optimization

• Re-slicing
  • Not atomic
  • Instruction might be interleaved in optimized assembly code
  • Discard boundary checking operation
    • If compiler detects that overflow will not happen

SliceTricks

• Official
  • https://github.com/golang/go/wiki/SliceTricks
• Graphics by @ueokande
  • https://ueokande.github.io/go-slice-tricks/

AppendVector

a = append(a, b...)

Copy

b = make([]T, len(a))
copy(b, a)

b = append([]T(nil), a...)

b = append(a[:0:0], a...)

Cut

a = append(a[:i], a[j:]...)

Delete

a = append(a[:i], a[i+1:]...)

a = a[:i+copy(a[i:], a[i+1:])]

Delete without preserving order

a[i] = a[len(a)-1] 
a = a[:len(a)-1]

Cut (GC)

copy(a[i:], a[j:])
for k, n := len(a)-j+i, len(a); k < n; k++ {
	a[k] = nil // or the zero value of T
}
a = a[:len(a)-j+i]

Delete (GC)

copy(a[i:], a[i+1:])
a[len(a)-1] = nil // or the zero value of T
a = a[:len(a)-1]

Delete without preserving order (GC)

a[i] = a[len(a)-1]
a[len(a)-1] = nil
a = a[:len(a)-1]

Expand

a = append(a[:i], append(make([]T, j), a[i:]...)...)

Extend

a = append(a, make([]T, j)...)

Filter (in place)

n := 0
for _, x := range a {
	if keep(x) {
		a[n] = x
		n++
	}
}
a = a[:n]

Insert

a = append(a[:i], append([]T{x}, a[i:]...)...)

InsertVector

a = append(a[:i], append(b, a[i:]...)...)

Push

a = append(a, x)

Pop

x, a = a[len(a)-1], a[:len(a)-1]

Push Front/Unshift

a = append([]T{x}, a...)

Pop Front/Shift

x, a = a[0], a[1:]

Application in Algorithm

QuickSort

func QuickSort(a []int) {
	if len(a) <= 1 {
		return
	}
 
	pivot := rand.Int() % len(a)
 
	left, right := 0, len(a)-1
	a[pivot], a[right] = a[right], a[pivot]
	for i, _ := range a[:right] {
		if a[i] < a[right] {
			a[left], a[i] = a[i], a[left]
			left++
		}
	}
	a[left], a[right] = a[right], a[left]
 
	QuickSort(a[:left])
	QuickSort(a[left+1:])
}

One More Thing

Slice Capacity append()

s := []int{1, 2, 3, 4, 5, 6, 7, 8}
fmt.Printf("s == %v\n\n", s)
 
s2 := s[1:4:5]
fmt.Printf("s2 == %v\n\n", s2)
 
s2 = append(s2, 15)
fmt.Printf("s == %v\n", s)
fmt.Printf("s2 == %v\n\n", s2)
 
s3 := s2[:4:4]
fmt.Printf("s3 == %v\n\n", s3)
 
s2 = append(s2, 16)
fmt.Printf("s == %v\n", s)
fmt.Printf("s2 == %v\n\n", s2)

Result

s == [1 2 3 4 5 6 7 8]

s2 == [2 3 4]

s == [1 2 3 4 15 6 7 8]
s2 == [2 3 4 15]

s3 == [2 3 4 15]

s == [1 2 3 4 15 6 7 8]
s2 == [2 3 4 15 16]

Slice is Invincible

• Accessing slice elements
• Re-slicing
• append()

Bless

成為 slice 大師Become slice master

郭學聰 Hsueh-Tsung Kuo2021_07_31

Reference

• Slice introduction
  • https://blog.golang.org/slices-intro
• Slice source code
  • https://github.com/golang/go/blob/go1.16.5/src/runtime/slice.go
  • https://github.com/golang/go/blob/go1.16.5/src/cmd/compile/internal/gc/ssa.go
• SliceTricks
  • Official
    • https://github.com/golang/go/wiki/SliceTricks
  • Graphics by @ueokande
    • https://ueokande.github.io/go-slice-tricks/

Utility

• Slides
  • Editor: HackMD
  • Presentation: Mozilla FireFox
• Recording
  • OBS Studio
  • Panasonic DC-GH5
    • LEICA DG SUMMILUX 15mm/F1.7
• Video Editing & Compositing
  • AviSynth official builds