为什么访问变量比访问 len() 慢得多？

Question

我编写了这个函数uniq，它接受 s 的排序切片int并返回删除了重复项的切片：func uniq(x []int) []int {    i := 0    for i < len(x)-1 {        if x[i] == x[i+1] {            copy(x[i:], x[i+1:])            x = x[:len(x)-1]        } else {            i++        }    }    return x}和uniq2，重写uniq具有相同的结果：func uniq2(x []int) []int {    i := 0    l := len(x)    for i < l-1 {        if x[i] == x[i+1] {            copy(x[i:], x[i+1:])            l--        } else {            i++        }    }    return x[:l]}这两个函数之间的唯一区别是，在 中，我不是每次都uniq2切片x 和直接访问，而是保存到一个变量 并在每次移动切片时递减它。len(x)len(x)l我认为这uniq2会比uniq 因为len(x)不再称为迭代要快一点，但实际上，它慢得莫名其妙。通过这个生成随机排序切片并调用uniq/ uniq21000 次的测试，我在 Linux 上运行它：func main() {    rand.Seed(time.Now().Unix())    for i := 0; i < 1000; i++ {        _ = uniq(genSlice())        //_ = uniq2(genSlice())    }}func genSlice() []int {    x := make([]int, 0, 1000)    for num := 1; num <= 10; num++ {        amount := rand.Intn(1000)        for i := 0; i < amount; i++ {            x = append(x, num)        }    }    return x}$ go build uniq.go$ time ./uniquniq通常需要5--6秒才能完成。whileuniq2慢两倍多，需要 12--15 秒。为什么我将切片长度保存到变量的地方比我直接调用的地方uniq2慢得多？uniqlen不应该稍微快点吗？

Answer 1

您期望大致相同的执行时间，因为您认为它们做大致相同的事情。

这两个函数之间的唯一区别是，在 中，我不是每次都uniq2切片x和直接访问，而是保存到一个变量并在每次移动切片时递减它。len(x)len(x)l

这是错误的。

第一个版本：

        copy(x[i:], x[i+1:])
        x = x[:len(x)-1]

第二个是：

        copy(x[i:], x[i+1:])
        l--

第一个区别是第一个分配（复制）一个切片头，它是一个reflect.SliceHeader值，是 3 个整数（在 64 位架构上为 24 字节），同时l--进行简单的递减，速度要快得多。

但主要区别并非源于此。主要区别在于，由于第一个版本更改了x切片（标头、包括的长度），您最终复制的元素越来越少，而第二个版本没有更改x，并且总是复制到切片的末尾。x[i+1:]相当于x[x+1:len(x)].

为了演示，假设您传递了一个长度为 10 且所有元素都相等的切片。第一个版本将首先复制 9 个元素，然后是 8 个，然后是 7 个等。第二个版本将首先复制 9 个元素，然后再复制 9 个，然后再复制 9 个，依此类推。

让我们修改您的函数以计算复制元素的数量：

func uniq(x []int) []int {

    count := 0

    i := 0

    for i < len(x)-1 {

        if x[i] == x[i+1] {

            count += copy(x[i:], x[i+1:])

            x = x[:len(x)-1]

        } else {

            i++

        }

    }

    fmt.Println("uniq copied", count, "elements")

    return x

}

func uniq2(x []int) []int {

    count := 0

    i := 0

    l := len(x)

    for i < l-1 {

        if x[i] == x[i+1] {

            count += copy(x[i:], x[i+1:])

            l--

        } else {

            i++

        }

    }

    fmt.Println("uniq2 copied", count, "elements")

    return x[:l]

}

测试它：

uniq(make([]int, 1000))

uniq2(make([]int, 1000))

输出是：

uniq copied 499500 elements

uniq2 copied 998001 elements

uniq2()复制两倍的元素！

如果我们用随机切片测试它：

uniq(genSlice())

uniq2(genSlice())

输出是：

uniq copied 7956671 elements

uniq2 copied 11900262 elements

同样，uniq2()复制大约 1.5 倍的元素！（但这在很大程度上取决于随机数。）

尝试Go Playground上的示例。

“修复”是修改uniq2()复制直到l：

        copy(x[i:], x[i+1:l])

        l--

通过这种“适当”的改变，性能大致相同。