Go: несколько вызовов len() против производительности?

В настоящий момент я реализую некоторые алгоритмы сортировки. Поскольку в природе алгоритмов существует много вызовов по длине некоторых массивов/срезов с использованием метода 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? Или компилятор делает это сам?

Ответ 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, которое затем используется для каждого случая of 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(). Вы можете увидеть это в генерации кода.

Глобальные и ссылочные фрагменты имеют служебные данные

Для общих значений кеширование длины невозможно, поскольку компилятор должен предположить, что срез изменяется между вызовами. Поэтому компилятор должен писать код, который обращается к атрибуту 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)

Ответ 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

Таким образом, здесь явно существует штраф, возможно, потому, что компилятор делает хуже оптимизацию во время компиляции.