Principles of slice type in GO

04/04/2020 slice sources allocation


Principles of slice type in GO

How to use slices is described in GO blog. Let's take a look to a slice internals.

Slice — data type, array wrapper.

The differences between slice and array are:

  • Slice — pointer to array;
  • Slice's size can be changed;

In the go sources slice is represented by following structure:

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

len (length) — current slice length, cap (capacity) — the number of elements in the underlying array.

Both fields can be pass as parameter to the make function:

s := make(
	[]int, 
	10, // len 
	10, // cap
)

Capacity is the main parameter responsible for the memory allocations in slice. It is also responsible for append performance.

Let's take a look to a slice behaviour on append.

a := []int{1}
b := a[0:1]
b[0] = 0

fmt.Println(a)
// [0]

a[0] = 1

fmt.Println(b)
// [1]

We got b slice from a slice. Next, we can see both slices are pointed to the same underlying array.

Let's add appending to one of slices.

a := []int{1}
b := a[0:1]

a = append(a, 2)
a[0] = 10

fmt.Println(a, b)
// [10 2] [0]

After append slices have different values in first element. Now slices are pointed to different arrays.

One can understand the situation by the growslice function sources.

On cap change an underlying array data is always copied:

memmove(p, old.array, lenmem)

Now let's take a look to a real cap changes:

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
		}
	}
}

On slice length < 1024, memory size grows double.

In other case slice grows in a quarter.

Appending to slice has big impact to the memory:

  • On cap change, array will be copied;
  • Allocated memory will grow by the terms of internal GO logic;

To avoid allocations one must set initial slice as capacity big enough.

In next example the only changed thing is a slice capacity. But now after appending to the slice there is no capacity change. Both slices are still pointed to same array:

a := make([]int, 1, 2)
a[0] = 1

b := a[0:1]
b[0] = 0

fmt.Println(a, b)
// [0] [0]

a = append(a, 2)
a[0] = 10

fmt.Println(a, b)
// [10 2] [10] 

In go blog there is the described option to use different append function.
But the only thing we can do — make even more greedy allocations than GO does.

func AppendByte(slice []byte, data ...byte) []byte {
    m := len(slice)
    n := m + len(data)
    if n > cap(slice) { // if necessary, reallocate
        // allocate double what's needed, for future growth.
        newSlice := make([]byte, (n+1)*2)
        copy(newSlice, slice)
        slice = newSlice
    }
    slice = slice[0:n]
    copy(slice[m:n], data)
    return slice
}

One should be careful when new slice is created as a part of old one. The full old underlying array will remain in memory.

Related articles