Suppose I have a slice slice of type int. While declaring, I set the third argument to size, which I believe reserves memory for at least size ints by setting the cap parameter of the slice.
slice:=make([]int,0,size)
Now, suppose I have an integer variable value. To add it to the slice at the end, I use
slice=append(slice,value)
If the number of elements currently in the slice is less than size, then there will be no need to copy the entire underlying array to a new location in order to add the new element.
Further, if I want to prepend value to slice, as suggested here and here, I use
slice=append([]int{value},slice...)
My question is, what happens in this case? If the number of elements is still less than size, how are the elements stored in the memory? Assuming a contiguous allocation when the make() function was invoked, are all existing elements right shifted to free the first space for value? Or is memory reallocated and all elements copied?
The reason for asking is that I would like my program to be as fast as possible, and would like to know if this is a possible cause for slowing it down. If it is so, is there any alternative way of prepending that would be more time efficient?
The builtin append() always appends elements to a slice. You cannot use it (alone) to prepend elements.
Having said that, if you have a slice capacity bigger than length (has "free" space after its elements) to which you want to prepend an element, you may reslice the original slice, copy all elements to an index one higher to make room for the new element, then set the element to the 0th index. This will require no new allocation. This is how it could look like:
func prepend(dest []int, value int) []int {
if cap(dest) > len(dest) {
dest = dest[:len(dest)+1]
copy(dest[1:], dest)
dest[0] = value
return dest
}
// No room, new slice need to be allocated:
// Use some extra space for future:
res := make([]int, len(dest)+1, len(dest)+5)
res[0] = value
copy(res[1:], dest)
return res
}
Testing it:
s := make([]int, 0, 5)
s = append(s, 1, 2, 3, 4)
fmt.Println(s)
s = prepend(s, 9)
fmt.Println(s)
s = prepend(s, 8)
fmt.Println(s)
Output (try it on the Go Playground):
[1 2 3 4]
[9 1 2 3 4]
[8 9 1 2 3 4]
Note: if no room for the new element, since performance does matter now, we didn't just do:
res := append([]int{value}, dest...)
Because it does more allocations and copying than needed: allocates a slice for the literal ([]int{value}), then append() allocates a new when appending dest to it.
Instead our solution allocates just one new array (by make(), even reserving some space for future growth), then just set value as the first element and copy dest (the previous elements).
If you need to prepend many times, a normal slice may not be the right choice. A faster alternative would be to use a linked list, to which prepending an element requires no allocations of slices / arrays and copying, you just create a new node element, and you designate it to be the root by pointing it to the old root (first element).
The standard library provides a general implementation in the container/list package.
Sticking to normal slices and arrays, there is another solution.
If you're willing to manage a larger backing array (or slice) yourself, you can do so by leaving free space before the slice you use. When prepending, you can create a new slice value from the backing larger array or slice which starts at an index that leaves room for 1 element to be prepended.
Without completeness, just for demonstration:
var backing = make([]int, 15) // 15 elements
var start int
func prepend(dest []int, value int) []int {
if start == 0 {
// No more room for new value, must allocate bigger backing array:
newbacking := make([]int, len(backing)+5)
start = 5
copy(newbacking[5:], backing)
backing = newbacking
}
start--
dest = backing[start : start+len(dest)+1]
dest[0] = value
return dest
}
Testing / using it:
start = 5
s := backing[start:start] // empty slice, starting at idx=5
s = append(s, 1, 2, 3, 4)
fmt.Println(s)
s = prepend(s, 9)
fmt.Println(s)
s = prepend(s, 8)
fmt.Println(s)
// Prepend more to test reallocation:
for i := 10; i < 15; i++ {
s = prepend(s, i)
}
fmt.Println(s)
Output (try it on the Go Playground):
[1 2 3 4]
[9 1 2 3 4]
[8 9 1 2 3 4]
[14 13 12 11 10 8 9 1 2 3 4]
Analysis: this solution makes no allocations and no copying when there is room in the backing slice to prepend the value! All that happens is it creates a new slice from the backing slice that covers the destination +1 space for the value to be prepended, sets it and returns this slice value. You can't really get better than this.
If there is no room, then it allocates a larger backing slice, copies over the content of the old, and then does the "normal" prepending.
Idea: imagine that you always store elements in a slice in backward order.
Storing your elements in backward order in a slice means a prepand becomes append!
So to "prepand" an element, you can simply use append(s, value). And that's all.
Yes, this has its limited uses (e.g. append to a slice stored in reverse order has the same issues and complexity as a "normal" slice and prepand operation), and you lose many conveniences (ability to list elements using for range just to name one), but performance wise nothing beats prepanding a value just by using append().
Note: iterating over the elements that stores elements in backward order has to use a downward loop, e.g.:
for i := len(s) - 1; i >= 0; i-- {
// do something with s[i]
}
Final note: all these solutions can easily be extended to prepend a slice instead of just a value. Generally the additional space when reslicing is not +1 but +len(values), and not simply setting dst[0] = value but instead a call to copy(dst, values).
The "prepend" call will need to allocate an array and copy all elements because a slice in Go is defined as a starting point, a size and an allocation (with the allocation being counted from the starting point).
There is no way a slice can know that the element before the first one can be used to extend the slice.
What will happen with
slice = append([]int{value}, slice...)
is
value is allocated (probably on stack)append call is doneappend sees that there is not enough room to extend the single-element slice so allocates a new array and copies all the elementsIf appending/removing at both ends of a large container is the common use case for your application then you need a deque container. It is unfortunately unavailable in Go and impossible to write efficiently for generic contained types while maintaining usability (because Go still lacks generics).
You can however implement a deque for your specific case and this is easy (for example if you have a large container with a known upper bound may be a circular buffer is all you need and that is just a couple of lines of code away).
I'm very new to Go, so may be the following is very bad Go code... but it's an attempt to implement a deque using a growing circular buffer (depending on the use case this may be or may be not a good solution)
type Deque struct {
buffer []interface{}
f, b, n int
}
func (d *Deque) resize() {
new_buffer := make([]interface{}, 2*(1+d.n))
j := d.f
for i := 0; i < d.n; i++ {
new_buffer[i] = d.buffer[j]
d.buffer[j] = nil
j++
if j == len(d.buffer) {
j = 0
}
}
d.f = 0
d.b = d.n
d.buffer = new_buffer
}
func (d *Deque) push_back(x interface{}) {
if d.n == len(d.buffer) {
d.resize()
}
d.buffer[d.b] = x
d.b++
if d.b == len(d.buffer) {
d.b = 0
}
d.n++
}
func (d *Deque) push_front(x interface{}) {
if d.n == len(d.buffer) {
d.resize()
}
if d.f == 0 {
d.f = len(d.buffer)
}
d.f--
d.buffer[d.f] = x
d.n++
}
func (d *Deque) pop_back() interface{} {
if d.n == 0 {
panic("Cannot pop from an empty deque")
}
if d.b == 0 {
d.b = len(d.buffer)
}
d.b--
x := d.buffer[d.b]
d.buffer[d.b] = nil
d.n--
return x
}
func (d *Deque) pop_front() interface{} {
if d.n == 0 {
panic("Cannot pop from an empty deque")
}
x := d.buffer[d.f]
d.buffer[d.f] = nil
d.f++
if d.f == len(d.buffer) {
d.f = 0
}
d.n--
return x
}