Go: multiple len() calls vs performance?

At the moment I am implementing some sorting algorithms. As it's in the nature of algorithms, there are a lot of calls on the length of some arrays/slices using the len() method.

Now, given the following code for a (part of) the Mergesort algorithm:

  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)]
		}
	}

My question is: Do these multiple len() calls affect the performance of the algorithm negatively? Is it better to make a temporary variable for the length of the right and left slice? Or does the compiler does this itself?

There are two cases:

• Local slice: length will be cached and there is no overhead
• Global slice or passed (by reference): length cannot be cached and there is overhead

No overhead for local slices

For locally defined slices the length is cached, so there is no runtime overhead. You can see this in the assembly of the following program:

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

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

Compiled with go tool 6g -S test.go this yields, amongst other things, the following lines:

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

What happens here is that the first line retrieves the length of x by getting the value located 40 bytes from the beginning of x and most importantly caches this value in BX, which is then used for every occurrence of len(x). The reason for the offset is that an array has the following structure (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 is what is accessed by len(). You can see this in the code generation as well.

Global and referenced slices have overhead

For shared values caching of the length is not possible since the compiler has to assume that the slice changes between calls. Therefore the compiler has to write code that accesses the length attribute directly every time. Example:

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
}

Comparing the assembly of both functions yields the crucial difference that as soon as the variable is global the access to the nel attribute is not cached anymore and there will be a runtime overhead:

// 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)

Despite the good answers you are getting, I'm getting poorer performance if calling len(a) constantly, for example in this test 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
		}
	}
}

When run as go test -bench=. I get:

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

So there is clearly a penalty here, possibly because the compiler is making worse optimizations in compile-time.

Hope things got improved in the latest version of Go

go version 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