在Go语言中是否有类似于memset的函数？

Question

在C++中，我可以使用memset来初始化一个数组的某些值：

const int MAX = 1000000;
int is_prime[MAX]

memset(is_prime, 1, sizeof(is_prime))

简单地说，memset的作用是将数组填充为某个值，而且速度非常快。

在Go语言中，我可以使用is_prime := make([]int, 1000000)来创建一个切片，但这会创建一个所有元素都为0的切片。同样的方式，我可以使用new([1000000]int)，但没有任何方法可以创建一个所有元素都为1或任何其他非零元素的数组/切片。

当然，我可以使用循环以后来填充它们，但memset的主要目的在于它比循环快得多。

那么，Go程序员是否有类似于memset的模拟（一种快速初始化数组为某些非零值的方式）？

- Salvador Dali

---

你可以使用runtime.duffzero，并在AX中使用一些其他值而不是0。另请参见mkduff.go。 - thwd

使用任何好的编译器，循环速度与memset一样快。 - edc65

дЅ зљ„memset同样没有将所有元素初始化为1гЂ‚ - milleniumbug

只是出于好奇，你有关于 memset 和循环性能的时间数据吗？ - Akavall

@edc65，有一个普遍的谬论认为循环速度与memset一样快。在一个拥有特殊缓存控制和SIMD指令的现代世界中，对于大缓冲区，memset可以比标量寄存器的简单循环运行得更快。这种情况最初是从20世纪90年代的PowerPC开始出现的，然后传到了Pentium III上的英特尔，并且在具有NEON指令的ARM上也是如此。 话虽如此：Go编译器明确地不花费太多时间进行优化，因为它应该优先考虑快速编译时间。 - Jon Watte

Answer 1

使用循环的最简单解决方案如下：

func memsetLoop(a []int, v int) {
    for i := range a {
        a[i] = v
    }
}

标准库中没有支持memset，但我们可以利用内置的copy()函数进行高度优化。

使用多次copy()

我们可以手动设置第一个元素，并使用copy()将已设置部分复制到未设置部分，其中已设置部分每次都会变得越来越大（翻倍），所以迭代次数为log(n)：

func memsetRepeat(a []int, v int) {
    if len(a) == 0 {
        return
    }
    a[0] = v
    for bp := 1; bp < len(a); bp *= 2 {
        copy(a[bp:], a[:bp])
    }
}

这个解决方案的灵感来自于bytes.Repeat()的实现。如果您只想创建一个填充有相同值的新[]byte，您可以使用bytes.Repeat()函数。但对于现有的切片或除[]byte以外的其他切片，您不能使用它，为此，您可以使用memsetRepeat()。

对于小的切片，memsetRepeat()可能比memsetLoop()慢（但对于小的切片并不重要，它会在瞬间运行）。

由于使用了快速的copy()，如果元素数量增加，memsetRepeat()将会更快。

对这两种解决方案进行基准测试：

var a = make([]int, 1000) // Size will vary

func BenchmarkLoop(b *testing.B) {
    for i := 0; i < b.N; i++ {
        memsetLoop(a, 10)
    }
}

func BenchmarkRepeat(b *testing.B) {
    for i := 0; i < b.N; i++ {
        memsetRepeat(a, 11)
    }
}

基准测试结果

100个元素： 比原来快了约1.15倍

BenchmarkLoop   20000000                81.6 ns/op
BenchmarkRepeat 20000000                71.0 ns/op

1,000 个元素： 速度提升 ~2.5 倍

BenchmarkLoop    2000000               706 ns/op
BenchmarkRepeat  5000000               279 ns/op

1万个元素：快大约2倍

BenchmarkLoop     200000              7029 ns/op
BenchmarkRepeat   500000              3544 ns/op

100,000个元素：快大约1.5倍

BenchmarkLoop      20000             70671 ns/op
BenchmarkRepeat    30000             45213 ns/op

性能提升最高的范围在3800-4000个元素左右，速度大约快了3.2倍。

- icza

---

感谢您的回答。从理论上讲，您可以获得“log(n)”的速度，但实际上只能快大约两倍，这看起来有些奇怪。 - Salvador Dali

@SalvadorDali 迭代次数为log(n)，但每次迭代中的copy()函数需要做两倍数量的工作（复制两倍数量的元素）。因此，重要的不仅是迭代次数。 - icza

这里有一小点说明，在Go编译器中存在这个优化。 - Awn

在 Linux 3.10.0 上运行，使用 amd64 go 1.14，结果如下：goarch: amd64 pkg: - BenchmarkLoop-4 1949619 573 ns/op BenchmarkRepeat-4 785382 1359 ns/op - Liqang Liu

Answer 2

根据标题为“优化memset习语”的此错误，在Go中除了循环外没有其他方法可以实现它。该问题于2013年1月9日关闭，并发表以下帖子：

我认为这个问题已解决。 优化非零情况并不是非常有趣。

如果人们感到强烈需要更多的优化，我们可以开一个新的bug。

因此，解决方案是像icza一样使用循环。

有bytes.Repeat，但也只使用循环。

func Repeat(b []byte, count int) []byte {
    nb := make([]byte, len(b)*count)
    bp := copy(nb, b)
    for bp < len(nb) {
        copy(nb[bp:], nb[:bp])
        bp *= 2
    }
    return nb
}

- IamNaN

---

请注意，C语言的实现也只是一个“循环”。它确保字对齐，并逐字写入，而不是按照所涉及数据类型的宽度。 - thwd

在C语言中，它可能会编译成x86架构上的特定指令，因此不算真正的循环 - 即memset的编译器内部函数。 - paulm