algorithm - Go:多个 len() 调用与性能？

Question

目前我正在实现一些排序算法。由于它是算法的本质，使用 len() 方法对某些数组/slice 的长度进行了很多调用。

现在，给定合并排序算法(部分)的以下代码:

  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 slice 的长度创建一个临时变量会更好吗？还是编译器自己做的？

Answer 1

有两种情况:

• 本地 slice :长度会被缓存，没有开销
• 全局 slice 或传递(通过引用):长度无法缓存，有开销

本地 slice 没有开销

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

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 的长度通过获取距离 x 开头 40 个字节的值最重要的是将此值缓存在 BX 中, 然后用于每次出现 len(x) .偏移的原因是数组具有以下结构(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 中看到这一点也是。

全局 slice 和引用 slice 有开销

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

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)