Go 1.22 中的新功能:slices.Concat

Go 1.22 的第二个候选发布版即将发布。在上一篇博文中,我介绍了我为 Go 1.22 所做的 reflect.TypeFor 工作。这一次,我将介绍我是如何提出并实现 slices.Concat 的。

下面是 slices.Concat 的签名(signature ):

// Concat 返回一个新的片段,将传入的片段连接起来。
func Concat[S ~[]E, E any](slices ...S) S

事实上,我早在 2021 年 5 月就提出了这个建议。在随后关于在切片软件包中添加什么功能的讨论中,这个建议被轻易否决了、

决议:决定不在初始设置中添加 Concat。如果有重要证据,我们可以随时重新考虑。

就上下文而言,slices 包本身直到 Go 1.21 才被添加到 Go 标准库中。在此之前,它只能以外部 golang.org/x/exp/slices 包的预览形式提供。在将其永久加入标准库之前,slices 软件包刻意保持了小巧和集中,重点在于获得实际经验。不过,最终我为 slices.Concat 写了一份新的提案,并获得了提案审查小组的批准,因此我也实现了它。

当前的 slices 软件包让我感到紧张的一点是,在循环中滥用 O(N) 函数,很容易使软件意外地变成二次函数。在 slices.DeleteFunc 添加之前,我快速扫描了 SourceGraph 上列出的 Go 代码,发现大约四分之一的 slices.Delete 使用都是在循环中完成的,这可能会导致四次性能下降,因为切片会被一遍又一遍地扫描和复制。

这种性能问题很隐蔽,因为对于小切片来说,性能影响可能可以忽略不计,但对于一个只有十倍大的切片来说,处理时间可能要长上百倍,这就导致程序在测试中运行正常,但在生产中就会瘫痪。我之所以喜欢 slices.Concat,是因为代码读者应该比较清楚性能的影响。如果程序员想在一个循环中使用 append slices.Insert 将一堆分片连接在一起,希望他们会注意到 slices.Concat 的存在,并改用它。

slices.Concat 的实现中有些奇怪的地方,如果你还不知道它为什么存在,可能需要解释一下。为了高效地将片段连接在一起,slices.Concat 会分配一个足够长的新片段来容纳所有连接的部分,而不是边分配边添加,这样就有可能在创建新片段时进行多次分配。但是,获取所有部分长度的代码中有一个看似多余的检查:

size := 0
for _, s := range slices {
	size += len(s)
	if size < 0 {
		panic("len out of range")
	}
}

之所以要在每个循环中检查大小是否小于零,是为了测试切片长度是否溢出。如果连接片段中的条目数过多,它可能会绕一圈并变成负数。

溢出错误可能相当隐蔽。早在 2006 年,乔希-布洛克(Josh Bloch)就写过一篇关于二进制搜索常见实现中的溢出错误的文章,大约二十年来,人们一直没有注意到这个错误:

当数组的长度(以元素为单位)达到或超过 230(大约十亿个元素)时,这个错误就会显现出来。这在 80 年代编写《Programming Pearls》时是不可想象的,但如今在谷歌和其他地方却很常见。本特利在《编程珍珠》中说:”虽然第一个二进制搜索发表于 1946 年,但直到 1962 年才出现第一个对所有 n 值都能正确工作的二进制搜索”。事实上,至少在主流编程语言中,很少有正确的版本问世。

希望 slices.Concat 不会出现这种特殊的溢出问题,但测试这段代码是一个有趣的挑战。如何在 64 位机器上创建一个长度接近溢出所需的切片,而又不使用数百万兆字节的 RAM 进行测试?答案就是使用 struct{} 的片段,除了片段头之外,它不会占用额外的内存。

值得注意的是,如果只想连接两个片段,则无需使用 slices.Concat。您可以使用带有 …扩展运算符的内置追加功能:

Concat := append(s1, s2...)

Concat 建议的早期版本包含一个目标片参数,如 append。(Concat(dest []T, ss ...[]T) []T.)为什么 slices.Concat 的最终版本没有目的地参数,以允许用户重用现有的切片作为后盾?

这个问题又回到了所谓的别名问题上。如果连接到一个零片或某个容量不足以容纳所有连接部分的片上,那么就不会有任何问题,因为必须创建一个新片,并将所有部分复制到该片上。但是,如果要将一个片段的各个部分连接到自己身上呢?请看这个例子:

s := []int{1, 2, 3, 4}
_ = slices.ConcatWithDestination(s[:0], s[3:4], s[2:3], s[1:2], s[0:1])
// What is s now?

如果只是简单地执行 slices.ConcatWithDestination,就会先将片段开头的 1 复制到片段末尾,然后再将其替换为 4,这样就会出现 4、3、3、4 而不是预期的 4、3、2、1。

因此,slices.Insert slices.Replace 也有这个问题。解决方法并不太妙。代码最终使用不安全包来检查切片是否重叠。如果重叠,就会将值旋转到位,从而避免分配:

// The hard case - v overlaps c or d. We can't just shift up
// the data because we'd move or clobber the values we're trying
// to insert.
// So instead, write v on top of d, then rotate.
copy(s[n:], v)

// Now we have
// s: aaaaaaaabbbbccccccccvvvv
//            ^   ^       ^   ^
//            i  i+m      n  n+m

rotateRight(s[i:], m)

// Now we have
// s: aaaaaaaavvvvbbbbcccccccc
//            ^   ^       ^   ^
//            i  i+m      n  n+m
// That's the result we want.
return s

Keith Randall 写了一个版本的 slices.Concat,它可以使别名检查正常工作,但它比 slices.Insertslices.Replace 增加了更多的代码,因为在连接时,所有的片段都有可能重叠。

最后,我们决定只返回一个新的片段,这样会使 slices.Concat 的实现更简单,并有助于防止意外别名片段和获得意外结果的问题,因此我们放弃了目标片段参数。

大卫-蔡斯(David Chase)在上一集 Go Time 中很好地解释了为什么防止片段别名很重要。

我非常喜欢 Fortran。让 Fortran 快速运行的是一件很小很小的事情,而且通常在程序中也是如此。比如说,当你将一对片段传递给一个函数时,Fortran 会说–你可以假装它们[不]重叠。如果它们重叠了,那就不是 Fortran 了。[…]

但它能让你随意进行矢量化、各种矢量化转换、并行化转换和重新排序。这也是 Fortran 为什么这么快的关键所在。

如果一个片没有别名,那么编译器和 CPU 就不必担心写入片的一部分会影响到另一个片,因此读写可以按照任意顺序进行,这样速度就会快很多。不幸的是,Go 无法在其类型系统中表示别名,因此编译器不能假定某个片没有别名。如果 Go 2 有更强大的类型系统,我们可以考虑改变这一点。

slices.Concat 就介绍到这里。订阅以了解 cmp.Or 背后的故事,即将推出。

本文文字及图片出自 What’s New in Go 1.22: slices.Concat

阅读余下内容
 

发表回复

您的电子邮箱地址不会被公开。 必填项已用*标注


京ICP备12002735号