Go语言：多次调用len()会影响性能吗？

Question

Go语言：多次调用len()会影响性能吗？

46

目前我正在实现一些排序算法。由于算法的本质，使用 len() 方法对一些数组/切片的长度进行了大量调用。

现在，考虑下面这段代码，它是归并排序算法的一部分：

  for len(left) > 0 || len(right) > 0 {
        if len(left) > 0 && len(right) > 0 {
            if left[0] <= right[0] {
                result = append(result, left[0])
                left = left[1:len(left)]
            } else {
                result = append(result, right[0])
                right = right[1:len(right)]
            }
        } else if len(left) > 0 {
            result = append(result, left[0])
            left = left[1:len(left)]
        } else if len(right) > 0 {
            result = append(result, right[0])
            right = right[1:len(right)]
        }
    }

我的问题是：这些多次调用 len() 方法会对算法的性能产生负面影响吗？是否最好为 right 和 left 切片的长度创建一个临时变量？或者编译器会自行处理这个问题？

- Andreas Fröwis

9

当有疑虑时，进行基准测试和/或性能分析。 - JimB

1

这对于进行内存分配的代码来说是一个奇怪的问题。如果有人问你：“在航空母舰上供应咸黄油会增加任务成本吗？”你会回答什么？是的，会增加成本，但这并不重要（假设咸黄油更昂贵）。 - Volker

3个回答

11

尽管您得到了很好的答案，但是如果频繁地调用len(a)，例如在此测试中，我的性能会变差。http://play.golang.org/p/fiP1Sy2Hfk

package main

import "testing"

func BenchmarkTest1(b *testing.B) {
    a := make([]int, 1000)
    for i := 0; i < b.N; i++ {
        count := 0
        for i := 0; i < len(a); i++ {
            count += len(a)
        }
    }
}

func BenchmarkTest2(b *testing.B) {
    a := make([]int, 1000)
    for i := 0; i < b.N; i++ {
        count := 0
        lena := len(a)
        for i := 0; i < lena; i++ {
            count += lena
        }
    }
}

当以go test -bench=.运行时，我得到：

BenchmarkTest1   5000000               668 ns/op
BenchmarkTest2   5000000               402 ns/op

所以这里显然存在一个惩罚，可能是因为编译器在编译时做出了更糟糕的优化。

- siritinga

3

为了公平比较，该“slice”也应为局部变量。 - user4122236

尝试使用本地变量，结果相同。如果计数在本地声明，则差异很重要，但我不知道为什么。 - siritinga

1

@siritinga分享的切片（如全局变量）会被特殊处理，并且具有运行时开销。我已经更新了我的答案来涵盖这种情况。 - nemo

@siritinga 在切片创建后使用 b.ResetTimer()。您正在测量切片创建时间。第二个测试可能正在重复使用第一个切片的空间。 - nemo

@nemo 使用 ResetTimer() 并不会改变时间。这是可以预料的，因为它只被分配一次用于测试，所以可以忽略不计。如果我改变顺序，得到的结果相同。因此，还有其他问题发生了。 - siritinga

显示剩余2条评论

1

希望Go的最新版本有所改进。

go版本为go1.16.7 linux/amd64。

goos: linux
goarch: amd64
pkg: 001_test
cpu: 11th Gen Intel(R) Core(TM) i7-1165G7 @ 2.80GHz
BenchmarkTest1-8     4903609           228.8 ns/op
BenchmarkTest2-8     5280086           229.9 ns/op

- M. Gopal

1

你想用那个基准测试结果表达什么意思？在1.17.1和1.15之间，上述基准测试的速度提高了两倍。 - user4466350

1

go version go1.17.5 linux/amd64BenchmarkTest1-8 4665556 253.3 ns/opBenchmarkTest2-8 4493875 254.4 ns/op不知道在1.17.1版本中为什么会更快，在1.17.5版本中并没有更快的情况，而且使用len函数也不会有明显的惩罚。 - M. Gopal

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- nemo · Accepted Answer

有两种情况：

局部切片: 长度将被缓存，没有额外开销
全局切片 或者（按引用）传递的切片：长度无法被缓存，存在开销

局部切片无开销

对于在本地定义的切片，长度将被缓存，因此没有运行时开销。您可以在以下程序的汇编中看到这一点：

func generateSlice(x int) []int {
    return make([]int, x)
}

func main() {
    x := generateSlice(10)
    println(len(x))
}

使用 go tool 6g -S test.go 编译后，其中包含如下代码：

MOVQ    "".x+40(SP),BX
MOVQ    BX,(SP)
// ...
CALL    ,runtime.printint(SB)

这里发生的情况是，第一行通过获取位于x开头40个字节处的值来检索x的长度，并且将此值缓存在 BX中，然后在每次出现len(x)时都使用它。偏移量的原因在于数组具有以下结构（来源）：

typedef struct
{               // must not move anything
    uchar   array[8];   // pointer to data
    uchar   nel[4];     // number of elements
    uchar   cap[4];     // allocated number of elements
} Array;

nel 是被 len() 访问的。你可以在代码生成中看到这一点。

全局和引用切片有开销

对于共享值，长度缓存是不可能的，因为编译器必须假设切片在调用之间发生了变化。因此，编译器必须编写直接访问长度属性的代码。例如：

func accessLocal() int {
    a := make([]int, 1000) // local
    count := 0
    for i := 0; i < len(a); i++ {
        count += len(a)
    }
    return count
}

var ag = make([]int, 1000) // pseudo-code

func accessGlobal() int {
    count := 0
    for i := 0; i < len(ag); i++ {
        count += len(ag)
    }
    return count
}

比较两个函数的汇编代码可以发现一个关键的差异：一旦变量是全局的，访问nel属性就不再被缓存，这会导致运行时开销:

// accessLocal
MOVQ    "".a+8048(SP),SI // cache length in SI
// ...
CMPQ    SI,AX            // i < len(a)
// ...
MOVQ    SI,BX
ADDQ    CX,BX
MOVQ    BX,CX            // count += len(a)

// accessGlobal
MOVQ    "".ag+8(SB),BX
CMPQ    BX,AX            // i < len(ag)
// ...
MOVQ    "".ag+8(SB),BX
ADDQ    CX,BX
MOVQ    BX,CX            // count += len(ag)