Go：multiple len() calls vs performance

发布于10月29日

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

现在，给出Mergesort算法(部分)的以下代码:

  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切片的长度设置一个临时变量是否更好？还是编译器自己做的？

推荐答案

有两种情况:

将缓存Local slice:个长度，并且没有任何开销
Global slice或(通过引用传递):Length不能缓存，存在开销

本地切片没有开销

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

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)的每次出现.偏移的原因是数组具有以下 struct (source):

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()访问的内容.你也可以在code generation米比赛中看到这一点.

全局切片和引用切片都有开销

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

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)