Go:多个len()调用vs性能？

Question

目前我正在实施一些排序算法.由于它属于算法的本质,因此使用该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分得一杯羹？或者编译器本身会这样做吗？

Answer 1

有两种情况:

• 本地切片:长度将被缓存,并且没有开销
• 全局切片或传递(通过引用):长度不能缓存并且有开销

本地切片没有开销

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

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().您也可以在代码生成中看到这一点.

全局和引用的片有开销

对于共享值,不可能缓存长度,因为编译器必须假设切片在调用之间发生变化.因此,编译器必须编写每次都直接访问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)

Answer 2

尽管你得到了很好的答案,但如果不断地调用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

所以这里显然有一个惩罚,可能是因为编译器在编译时进行了更糟糕的优化.