Golang"复制"时间复杂度

Question

我想知道go的copy函数的时间复杂度？

直觉上，我会假设线性时间的最坏情况。 但我想知道是否有任何魔法能够批量分配，或者有什么东西可以让它表现得更好？

https://golang.org/ref/spec#Appending_and_copying_slices

---

我想大会会解释一些事情，但我不确定我在读什么:p

$ GOOS=linux GOARCH=amd64 go tool compile -S main.go

---

func main() {
src := []int{1, 2, 3, 4, 5, 6, 7, 8, 9, 10}
dst := make([]int, len(src))
numCopied := copy(dst, src)
if numCopied != 10 {
panic(fmt.Sprintf("expected 5 copied received: %d", numCopied))
}
}

使用copy行的以下输出：

0x007a 00122 (main.go:23)       CMPQ    AX, $10
0x007e 00126 (main.go:23)       JLE     133
0x0080 00128 (main.go:23)       MOVL    $10, AX
0x0085 00133 (main.go:23)       MOVQ    AX, "".numCopied+56(SP)
0x008a 00138 (main.go:23)       MOVQ    CX, (SP)
0x008e 00142 (main.go:23)       LEAQ    ""..autotmp_8+72(SP), CX
0x0093 00147 (main.go:23)       MOVQ    CX, 8(SP)
0x0098 00152 (main.go:23)       SHLQ    $3, AX
0x009c 00156 (main.go:23)       MOVQ    AX, 16(SP)
0x00a1 00161 (main.go:23)       PCDATA  $0, $0
0x00a1 00161 (main.go:23)       CALL    runtime.memmove(SB)
0x00a6 00166 (main.go:23)       MOVQ    "".numCopied+56(SP), AX

---

然后我也尝试了 5 个元素：

func main() {
src := []int{1, 2, 3, 4, 5}
dst := make([]int, len(src))
numCopied := copy(dst, src)
if numCopied != 5 {
panic(fmt.Sprintf("expected 5 copied received: %d", numCopied))
}
}

使用copy行的以下输出：

0x0086 00134 (main.go:9)        CMPQ    AX, $5
0x008a 00138 (main.go:9)        JLE     145
0x008c 00140 (main.go:9)        MOVL    $5, AX
0x0091 00145 (main.go:9)        MOVQ    AX, "".numCopied+56(SP)
0x0096 00150 (main.go:9)        MOVQ    CX, (SP)
0x009a 00154 (main.go:9)        LEAQ    ""..autotmp_8+72(SP), CX
0x009f 00159 (main.go:9)        MOVQ    CX, 8(SP)
0x00a4 00164 (main.go:9)        SHLQ    $3, AX
0x00a8 00168 (main.go:9)        MOVQ    AX, 16(SP)
0x00ad 00173 (main.go:9)        PCDATA  $0, $0
0x00ad 00173 (main.go:9)        CALL    runtime.memmove(SB)
0x00b2 00178 (main.go:9)        MOVQ    "".numCopied+56(SP), AX

Answer 1

我建议对复制不同大小的数组/切片所需的时间进行基准测试。这里有一些东西可以让球滚动：

package main
import (
"fmt"
"math"
"testing"
)
func main() {
for i := 0; i < 16; i++ {
size := powerOfTwo(i)
runBench(size)
}
}
func runBench(size int) {
bench := func(b *testing.B) {
src := make([]int, size, size)
dst := make([]int, size, size)
// we don't want to measure the time
// it takes to make the arrays, so reset timer
b.ResetTimer() 
for i := 0; i < b.N; i++ {
copy(dst, src)
}
}
fmt.Printf("size = %d, %s", size, testing.Benchmark(bench))
}
func powerOfTwo(i int) int {
return int(math.Pow(float64(2), float64(i)))
}