Robust generic functions on slices

本文是由 Go Team 的 Valentin Deleplace 在 2024年2月22日发表于 go official blog,原文地址:https://go.dev/blog/generic-slice-functions

切片包提供了适用于任何类型切片的函数。在这篇博客文章中,我们将讨论如何通过理解切片在内存中的表示方式以及这如何影响垃圾回收器,从而更有效地使用这些函数。并且,我们将介绍我们最近如何调整这些函数,使它们更加便于使用。

使用类型参数,我们可以为所有可比较元素的切片编写一次函数,例如slices.Index

1
2
3
4
5
6
7
8
9
10
// Index 返回 v 在 s 中首次出现的索引,
// 如果不存在,则返回 -1。
func Index[S ~[]E, E comparable](s S, v E) int {
for i := range s {
if v == s[i] {
return i
}
}
return -1
}

不再需要为每种不同类型的元素重新实现Index

切片包包含许多开箱即用的函数,用于执行切片上的常见操作:

1
2
3
4
5
6
7
s := []string{"Bat", "Fox", "Owl", "Fox"}
s2 := slices.Clone(s)
slices.Sort(s2)
fmt.Println(s2) // [Bat Fox Fox Owl]
s2 = slices.Compact(s2)
fmt.Println(s2) // [Bat Fox Owl]
fmt.Println(slices.Equal(s, s2)) // false

几个新函数(Insert, Replace, Delete 等)会修改切片。为了理解它们的工作原理以及如何正确使用它们,我们需要检查切片的底层结构。

切片是数组的一部分视图。在内部,切片包含一个指向数组的指针、长度和容量。两个切片可以有相同的底层数组,并且可以查看重叠的部分。

例如,这个切片s是大小为6的数组中4个元素的视图:

如果一个函数更改了作为参数传递的切片的长度,那么它需要返回一个新的切片给调用者。如果不需要增长,底层数组可能保持不变。这解释了为什么appendslices.Compact返回一个值,而仅仅重新排序元素的slices.Sort却不返回。

考虑删除切片的一部分的任务。在泛型之前,从切片s中删除部分s[2:5]的标准方法是调用append函数来复制末端部分覆盖中间部分:

1
s = append(s[:2], s[5:]...)

语法复杂且容易出错,涉及子切片和可变参数。我们添加了slice.Delete来使删除元素变得更容易:

1
2
3
func Delete[S ~[]E, E any](s S, i, j int) S {
return append(s[:i], s[j:]...)
}

一行函数Delete更清晰地表达了程序员的意图。让我们考虑一个长度为6、容量为8的切片s,包含指针:

1
s = slices.Delete(s, 2, 5)

这个调用从切片s中删除了元素s[2]s[3]s[4]

删除在索引2、3、4的间隙通过将元素s[5]向左移动来填补,并将新长度设置为3。

Delete不需要分配一个新的数组,因为它是就地移动元素。像append一样,它返回一个新的切片。切片包中的许多其他函数遵循这一模式,包括CompactCompactFuncDeleteFuncGrowInsertReplace

调用这些函数时,我们必须认为原始切片无效,因为底层数组已经被修改。如果调用函数但忽略返回值,将是一个错误:

1
2
slices.Delete(s, 2, 5) // 错误!
// s仍然具有相同的长度,但内容已被修改

A problem of unwanted liveness

在Go 1.22之前,slices.Delete没有修改切片的新旧长度之间的元素。虽然返回的切片不包括这些元素,但在原始的、现在无效的切片末端创建的“间隙”仍然保留了它们。这些元素可能包含指向大对象(一个20MB的图像)的指针,垃圾回收器不会释放与这些对象关联的内存。这导致了一个内存泄漏,可能会导致严重的性能问题。

在这个例子中,我们成功地通过将一个元素向左移动来删除指针p2p3p4s[2:5]。但是p3p4仍然存在于底层数组中,在s的新长度之外。垃圾回收器不会回收它们。不太明显的是,p5不是被删除的元素之一,但是由于数组灰色部分中保留的p5指针,它的内存可能仍然会泄漏。

如果开发者没有意识到“看不见”的元素仍在使用内存,这可能会令人困惑。

所以我们有两个选择:

要么保留Delete的高效实现。如果用户想确保所指向的值可以被释放,他们可以自己将过时的指针设置为nil。
或者更改Delete以始终将过时的元素设置为零。这是额外的工作,使Delete稍微低效一些。将指针(将它们设置为nil)归零可以启用垃圾回收,当它们变得无法访问时。
不明显哪个选项是最好的。第一个默认提供性能,第二个默认提供内存节俭。

修复

一个关键的观察是“将过时的指针设置为nil”并不像看起来那么容易。实际上,这个任务非常容易出错,我们不应该让用户自己来写。出于实用主义,我们选择修改五个函数CompactCompactFuncDeleteDeleteFuncReplace的实现,以“清除尾部”。作为一个不错的副作用,认知负荷减少了,用户现在不需要担心这些内存泄漏。

在Go 1.22中,调用Delete后的内存是这样的:

修改后的五个函数中的代码使用新的内置函数clear(Go 1.21)将过时的元素设置为s元素类型的零值:

1
The zero value of E is nil when E is a type of pointer, slice, map, chan, or interface.

某些测试失败

这一变化导致了一些在Go 1.21中通过的测试在Go 1.22中失败。

如果你忽略了Delete的返回值:

1
slices.Delete(s, 2, 3)  // !! 错误 !!

然后你可能会错误地假设s不包含任何nil指针。在Go Playground 中的示例

如果你忽略了Compact的返回值:

1
2
slices.Sort(s) // 正确
slices.Compact(s) // !! 错误 !!

然后你可能会错误地假设s已经正确排序和压缩。示例

如果你将Delete的返回值分配给另一个变量,并继续使用原始切片:

1
u := slices.Delete(s, 2, 3)  // !! 错误,如果你继续使用 s !!

然后你可能会错误地假设s不包含任何nil指针。示例

如果你不小心遮挡了切片变量,并继续使用原始切片:

1
s := slices.Delete(s, 2, 3)  // !! 错误,使用 := 而不是 = !!

然后你可能会错误地假设s不包含任何nil指针。示例。

结论

切片包的 API 是传统非泛型语法删除或插入元素的改进。

我们鼓励开发者使用新函数,同时避免上述列出的“陷阱”。

由于最近的实现变化,一类内存泄漏被自动避免了,无需对API进行任何更改,开发者也不需要做任何额外的工作。


-------------The End-------------

本文标题:Robust generic functions on slices

文章作者:cloud sjhan

发布时间:2024年06月19日 - 17:06

最后更新:2024年06月19日 - 17:06

原始链接:https://cloudsjhan.github.io/2024/06/19/Robust-generic-functions-on-slices/

许可协议: 署名-非商业性使用-禁止演绎 4.0 国际 转载请保留原文链接及作者。

cloud sjhan wechat
subscribe to my blog by scanning my public wechat account
坚持原创技术分享,您的支持将鼓励我继续创作!
0%
;