proposal: runtime: add AppendNewCap to return new capacity if append is used with a given number of elements

[jan-dubsky]

Motivation

I wanted to implement circular queue that can grow (i.e. is not limited to any number of elements). Such an implementation seemed to be pretty straightforward - I have a slice of elements, I remember index of the first element in the queue and circle around.

The problem comes when I need the internal slice to grow. If that was a plain array, I'd just use append and let the language to take care of how much the slice should grow. Unfortunately in this case it's not possible because the appended element belongs to the end of the circular buffer, not to the end of the array.

I can implement the slice growing on myself with an arbitrary constant and I will still get to O(1) amortized time complexity. But I'd want to be able to leverage append and its capacity growth algorithm. The reasoning is that the numbers standard append uses for slice capacity grow are fine-tuned based on real language implementation as well as knowledge of many use-cases. There is quite a big chance that the growth factor chosen by language will result in much higher performance than any factor chosen by me.

Proposed solution

Please expose a function that would return new size of a slice after append of n elements. The signature could look like following:

# TODO: Find better name.
func AppendNewCap(currCap int, newElemCnt int) int

Where currCap would be current capacity of a slice and newElemCnt would be number of elements appended to the slice. this function could be then called by growslice function.

Using this method, one would be able to manually allocate the new circular buffer with appropriate capacity and manually copy all existing elements to the new slice. In other words, one could reimplement append with additional logic. In the queue example above, the additional logic would be the circular queue reallocation - the first element in the circular buffer would be copied to index [0] of the newly allocated slice. Such an implementation would be then as fast as library append but it would allow much more flexibility to the programmer.

[randall77]

The current runtime function for this takes into account element size, so you'd have to pass that in as well.

You could have an init function that calculates these values for you by appending an element at a time and seeing what happens. Something like below:

package main

func main() {
	var a []byte
	for i := 0; i < 40; i++ {
		a = append(a, 3)
		a = a[:cap(a)]
		println(cap(a))
	}
}

[jan-dubsky]

The current runtime function for this takes into account element size, so you'd have to pass that in as well.

Ok, that shouldn't be an issue to add element size parameter:

func AppendNewCap(currCap int, newElemCnt int, elemSize uintptr) int

The expected usage could be something as:

newCap := AppendNewCap(len(curr), len(curr) + len(toAppend), unsafe.Sizeof(myStruct))

I hope it would not be an issue that an unsafe function would be required to call a runtime function, would it?

You could have an init function that calculates these values for you by appending an element at a time and seeing what happens. Something like below:

I thought of this and unfortunately this doesn't seem to be possible.

First of all, such a function measuring capacity growth of a specific slice wouldn't be optimized by the compiler to no-op. Consequently, the program would really have to allocate such an slice every time it runs. Which could have non-trivial performance impact especially in cases of bigger arrays.

But even when we ignore the performance impact of your proposal, you would still have to set some maximum of the measurement: Let's for example say that in the current implementation, the new capacity of a slice after append has a deterministic formula once slice capacity exceeds 1024. Consequently, based on current implementation of append, we measure capacities of our test slice up to 1024 and find out what the capacity growth should be. For capacities above 1024, we just use the well-defined formula. But if the way how capacity above 1024 elements (or even the 1024 elements boundary) changes in future versions of Go, our code will no longer be consistent with the new behaviour of append. To sum it up, there is no real upper bound where the measurement proposed by you should end.

Based on this observation I believe that the only way how to maky any such custom append algorithm forward compatible (read consistent with even future behaviour of append) is to expose this calculation function from the runtime package.

[earthboundkid]

FWIW, in my deque package, I use append specifically to get the cap behavior of append. The same also occurred when I wrote a slice.Grow-like function for []byte. If a function like this existed, it would be simpler to just call runtime.AppendNewCap instead.