go 建议：运行时：在AppendNewCap中添加返回新容量的功能，如果使用给定数量的元素进行追加操作,

8tntrjer 于 4个月前发布在 Go

关注(0)|答案(3)|浏览(36)

动机

我想实现一个可以增长(即不限于任何元素数量)的循环队列。这样的实现似乎相当简单——我有一个元素切片，记住队列中第一个元素的索引并循环。
当我需要内部切片增长时，问题就出现了。如果那是一个普通的数组，我只需要使用 append 并让语言来处理切片应该增长多少。不幸的是，在这种情况下这是不可能的，因为追加的元素属于循环缓冲区的末尾，而不是数组的末尾。
我可以自己用任意常数实现切片增长，我仍然可以达到 O(1) 的摊销时间复杂度。但我希望能够利用 append 及其容量增长算法。原因是标准 append 用于切片容量增长的数字是根据实际的语言实现以及许多用例的知识进行微调的。有很大的可能性，语言选择的增长因子将导致比我选择的任何因素更高的性能。

建议的解决方案

请暴露一个函数，该函数将在 append 个 n 元素后返回新切片的大小。签名可能如下所示：

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

其中 currCap 将是切片的当前容量，newElemCnt 将是追加到切片的元素数量。这个函数可以由 growslice 函数调用。
使用这种方法，人们可以手动分配具有适当容量的新循环缓冲区，并手动将所有现有元素复制到新切片中。换句话说，可以用额外的逻辑重新实现 append 。在上面的队列示例中，额外的逻辑将是循环队列重新分配 - 循环缓冲区中的第一个元素将被复制到新分配切片的索引 [0] 中。这样的实现将与库 append 一样快，但它将允许程序员有更多的灵活性。

来源：https://github.com/golang/go/issues/55978

3条答案

按热度按时间

9rygscc11#

当前的运行时函数已经考虑了元素大小，所以你还需要将它作为参数传递。
你可以创建一个初始化函数，通过一次添加一个元素并观察结果来为你计算这些值。如下所示：

package main

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

赞(0）回复(0）举报 4个月前

jxct1oxe2#

当前运行时的函数已经考虑到了元素大小，所以你也需要传入这个参数。
好的，添加元素大小参数应该不会成为问题：

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

预期的使用方式可能是这样的：

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

我希望调用 runtime 函数不需要 unsafe 函数，这样不会有问题吧？
你可以有一个初始化函数，通过一次添加一个元素并观察结果来为你计算这些值。如下所示：
我想到了这个方法，但不幸的是这似乎不可能实现。
首先，这样一个测量特定切片容量增长的函数不会被编译器优化为无操作。因此，程序实际上每次运行时都需要分配这样一个切片。这在较大的数组中可能会产生非平凡的性能影响。
但是，即使我们忽略你的建议的性能影响，你仍然需要设置一些测量的最大值：例如，假设在当前实现中，切片容量超过 1024 后的新容量具有确定的公式。因此，根据当前 append 的实现，我们测量测试切片的容量直到 1024,找出容量增长应该是多少。对于大于 1024 的容量，我们只使用明确定义的公式。但是，如果容量超过 1024 个元素(甚至 1024 个元素边界)的方式在未来版本的 Go 中发生变化，我们的代码将不再与 append 的新行为保持一致。总之，你提出的测量建议没有真正的上限。
基于这个观察，我认为使任何这样的自定义 append 算法向前兼容(与 append 的未来行为一致)的唯一方法是将这个计算函数从 runtime 包中暴露出来。