Skip to content

The support of builtin slice manipulations in Go is incomplete

Jump to bottom
Go101 edited this page Dec 29, 2022 · 29 revisions

Go provides three built-in functions to manipulate slices:

  1. make is used to create a slice with specified length and capacity. All the elements are set to their zero values.
  2. copy is used to copy some elements from one slice to another if the two slices have identical element types.1.
  3. append is used to append some elements to a base slice and result a new slice. The new slice might share elements with the base slices or not, depending on the capacity of the base slice is large enough to hold the appended elements.

In fact, the copy function is not much essential, for it can be implemented by using append:

// Assume element type is T.
func copy(dest, src []T) int {
	if len(dest) < len(src) {
		_ = append(dest[:0], src[:len(dest)]...)
		return len(dest)
	} else {
		_ = append(dest[:0], src...)
		return len(src)
	}
}

Meanwhile, the three functions can't handle all situations in the most efficient way.

Case 1: when we want to merge N slices as one new slice.

Assume N is 3, the code is like:

func merge(x, y, z []T) []T {
	r := make([]T, 0, len(x) + len(y) + len(z))
	r = append(r, x...)
	r = append(r, y...)
	r = append(r, z...)
	return r
}

There are three problems of the above merge implementation:

  1. the code is verbose.
  2. the make call sets all elements as zero values, which is totally unnecessary for this specified situation.

It looks it is possible for compilers to make an optimization to avoid the second problem for simple cases, but as of Go toolchain 1.16, this has not been done yet.

To avoid the first problem, a merge function call can be rewritten as one dirty line append(x[:len(x):len(x)], append(y[:len(y):len(y)], z...)...). But the one line implementation might need at most two allocations and some elements are unnecessarily copied twice.

Does Go needs a builtin func merge(...[]T) []T function?

Some similar proposals:

Case 2: there is not a simple way to decap slices

See:

Case 3: not a simple and safe way to check whether or not elements of two slices overlap

The wireguard-go project provides an unsafe way to do this:

func AnyOverlap(x, y []byte) bool {
	return len(x) > 0 && len(y) > 0 &&
		uintptr(unsafe.Pointer(&x[0])) <= uintptr(unsafe.Pointer(&y[len(y)-1])) &&
		uintptr(unsafe.Pointer(&y[0])) <= uintptr(unsafe.Pointer(&x[len(x)-1]))
}

This unsafe way might be really unsafe, for no official confirmed valid patterns will guarantee this implementation is a valid unsafe use.

Case 4: no safe ways to derive an array pointer (or an array) from a slice

Another missed functionality is deriving an array pointer from a slice safely without duplicating the underlying elements. Or, it would be great if it is possible to initialize an array from a slice:

// S values can be used as map keys
type S struct {
    Foo [6]int
}

func f(v []int)
    var p = (*[2]byte)(v) // might panic at runtime (or result a nil), if v's capacity < 2
    ... // use p
    var a = [5]int(v) // might panic at runtime, if v's capacity < 5
    ... // use a
    var s = S {
        Foo: [6]int(v), // might panic at runtime, if v's capacity < 6
    }
    ... // use s
}

[Update]: deriving an array pointer from a slice has been supported since Go 1.17.

Please follow the official Twitter account of Go 101, @zigo_101, to learn some Go details, facts, tips, etc, and read some Go articles from time to time.

Go 101 is a series of books about Go programming.

Books in Go 101 series

Tapir started writing the Go 101 books and maintaining the go101.org website since 2016. New contents will continue being added to the books and the website from time to time. If you would like to, you can also support Go 101 by playing Tapir's games (for both Android and iPhone/iPad):

All wiki articles

Clone this wiki locally