quasilyte 5 фев 2019 в 15:30

Дефективное встраивание функций в Go

7 мин

9.3K

Высокая производительность*Open source*Системное программирование*Компиляторы*Go*

Эквивалентен ли по производительности код, представленный ниже?

// (A). Вызов HasPrefix будет встроен.
return strings.HasPrefix(s, "#")
// (B). Ручное встраивание тела HasPrefix.
return len(s) >= len("#") && s[:len("#")] == "#"

Ответ: нет.

За подробностями и объяснениями прошу под кат.

Доброго времени суток, перед тем, как раскрыть тему, хотел бы представиться.
Меня зовут Искандер и я время от времени отправляю коммиты в репозиторий golang/go.

Раньше я делал это от лица команды Intel Go, но наши пути разошлись и теперь я независимый контрибьютор. С недавних пор работаю в vk в команде инфраструктуры.

В свободное время делаю разные инструменты для Go, типа go-critic и go-consistent. А ещё я рисую гоферов.

Measure it!

Сразу приступим к сравнению и набросаем бенчмарк:

package benchmark

import (
    "strings"
    "testing"
)

var s = "#string"

func BenchmarkHasPrefixCall(b *testing.B) {
    for i := 0; i < b.N; i++ {
        _ = strings.HasPrefix(s, "#")
        _ = strings.HasPrefix(s, "x")
    }
}

func BenchmarkHasPrefixInlined(b *testing.B) {
    for i := 0; i < b.N; i++ {
        _ = len(s) >= len("#") && s[:len("#")] == "#"
        _ = len(s) >= len("x") && s[:len("x")] == "x"
    }
}

Вместо того, чтобы рекомендовать вам benchstat, я покажу вам benchrun.

С помощью одной команды мы можем запустить оба бенчмарка и получить сравнение:

go-benchrun HasPrefixCall HasPrefixInlined -v -count=10 .
  Benchstat results:
name             old time/op  new time/op  delta
HasPrefixCall-8  9.15ns ± 1%  0.36ns ± 3%  -96.09%  (p=0.000 n=10+9)

Вариант с ручным встраиванием гораздо быстрее кода, который был получен при встраивании тела функции компилятором. Попробуем разобраться почему это происходит.

strings.HasPrefix

Вспомним реализацию strings.HasPrefix:

// HasPrefix tests whether the string s begins with prefix.
func HasPrefix(s, prefix string) bool {
    return len(s) >= len(prefix) && s[0:len(prefix)] == prefix
}

Функция HasPrefix встраивается компилятором.
Проверить это можно следующим образом:

go build -gcflags='-m=2' strings 2>&1 | grep 'can inline HasPrefix'

Для вызова strings.HasPrefix из варианта (A) мы получаем следующий машинный код:

    MOVQ    (TLS), CX
    CMPQ    SP, 16(CX)
    JLS more_stack
fn_body:
    SUBQ    $40, SP
    MOVQ    BP, 32(SP)
    LEAQ    32(SP), BP
    XCHGL   AX, AX
    MOVQ    s+56(SP), AX
    CMPQ    AX, $1
    JGE compare_strings
    XORL    AX, AX
    MOVB    AL, ~ret1+64(SP)
    MOVQ    32(SP), BP
    ADDQ    $40, SP
return:
    RET
compare_strings:
    MOVQ    s+48(SP), AX
    MOVQ    AX, (SP)
    LEAQ    go.string."#"(SB), AX
    MOVQ    AX, 8(SP)
    MOVQ    $1, 16(SP)
    CALL    runtime.memequal(SB)
    MOVBLZX 24(SP), AX
    JMP return
more_stack:
    CALL    runtime.morestack_noctxt(SB)
    JMP fn_body

Не обращайте внимания на то, что код выглядит как лапша.

На что стоит обратить внимание:

strings.HasPrefix действительно был вставлен, вызова нет.
Для сравнения строк вызывается runtime.memequal.

Но что же тогда генерируется для встроенного вручную варианта, кода из примера (B)?

    MOVQ    s+16(SP), AX
    CMPQ    AX, $1
    JLT different_length
    MOVQ    s+8(SP), AX
    CMPB    (AX), $35 // 35 - код символа "#"
    SETEQ   AL
return:
    MOVB    AL, "".~ret1+24(SP)
    RET
different_length:
    XORL    AX, AX
    JMP 22

А вот тут компилятор не генерирует вызова runtime.memequal и производится сравнение единственного символа напрямую. В идеале, то же самое он должен был сделать и для первого варианта.

Мы наблюдаем слабую сторону оптимизатора Go, её и разберём.

Оптимизации константных выражений

Причина, по которой вызов strings.HasPrefix(s, "#") может быть оптимизирован в том, что аргумент-префикс является константой. Нам известна его длина и содержимое. Нет смысла вызывать runtime.memequal для коротких строк, быстрее сделать сравнение символов "на месте", избегая лишнего вызова.

Как вы знаете, в компиляторах обычно есть как минимум две части: compiler frontend и compiler backend. Первая работает с более высокоуровневым представлением, вторая уже ближе к машине и промежуточное представление будет похожим на поток инструкций. Уже несколько версий в Go используется SSA представление для оптимизаций в backend части компилятора.

Сворачивание констант, такое как {10*2 => 20}, реализовано в backend'е. Вообще большинство операций, связанных с понижением вычислительной стоимости выражений находятся именно в этой части компилятора. Но есть исключения.

Одним из исключений является оптимизация сравнений константных строк. Когда компилятор видит сравнение строк (или подстрок), в котором один или оба операнда являются константами, генерируется более эффективный код, нежели вызов runtime.memequal.

Посмотреть отвечающий за это исходный код можно в файле cmd/compile/internal/gc/walk.go:3362.

Встраивание функций происходит до запуска этих оптимизаций, но тоже во frontend части компилятора.

Казалось бы, что же всё-таки не даёт этой оптимизации сработать в нашем случае?

Как Go встраивает вызовы функций

Вот как будет происходить встраивание:

// Вот как выглядел вызов:
return strings.HasPrefix(s, "#")

// Вот сигнатура:
func HasPrefix(s, prefix string) bool

// А вот результат встраивания:
_s, _prefix := s, "#"
return len(s) >= len(prefix) && s[:len(prefix)] == prefix

При встраивании функций компилятор присваивает аргументы временным переменным, что ломает оптимизации, поскольку алгоритм в walk.go видит не константы, а аргументы с переменными. В этом проблема.

К слову, оптимизациям из backend'а, которые имеют в распоряжении SSA, это не мешает. Но там присутствуют другие проблемы, например, невозможность восстановить высокоуровневые конструкции языка для их эффективного сопоставления (работа по устранению этого недостатка "планируется" уже несколько лет).

Ещё один пример: escape analysis

Представим функцию, которой важно выделять временный буфер на стеке:

func businessLogic() error {
    buf := make([]byte, 0, 16)
    // buf используется только локально
    // для временного хранения результатов.
    return nil
}

Поскольку buf не "убегает", компилятор сможет выделить эти 16 байтов на стеке, без аллокации на куче. Опять же, всё благодаря константному значению при вызове make. Для выделения памяти на стеке нам важно знать требуемый размер, который будет входить в состав фрейма, отводимого под вызов функции.

Допустим, в будущем нам захотелось выделять временные буферы разных размеров и инкапсулировать некоторую логику в методах. Мы ввели новую абстракцию и решили везде использовать новый тип tmpBuf. Конструирующая функция предельно проста:

func newTmpBuf(sizeHint int) tmpBuf {
    return tmpBuf{buf: make([]byte, 0, sizeHint)}
}

Адаптируем исходный пример:

func businessLogic() error {
-   buf := make([]byte, 0, 16)
+   buf := newTmpBuf(16)
    // buf используется только локально
    // для временного хранения результатов.
    return nil
}

Конструктор будет встраиваться, но вот аллокация теперь всегда будет на куче, по той же причине передачи аргументов через временные переменные. Escape analysis будет видеть make([]byte, 0, _sizeHint), что не попадает под его паттерны распознавания оптимизируемых вызовов make.

Если бы у нас было "всё как у людей", проблемы бы не существовало, после встраивания конструктора newTmpBuf было бы ясно, что размер всё так же известен на этапе компиляции.

Это огорчает чуть ли не сильнее, чем ситуация со сравнением строк.

Горизонты Go 1.13

Ситуацию можно довольно легко поправить и я уже выслал первую часть решения.

Если вы считаете, что описанная в статье проблема действительно нуждается в решении, поставьте, пожалуйста, палец вверх в соответствующем issue.

Моя позиция состоит в том, что встраивать код руками только потому что он работает быстрее в текущей версии Go — это неправильно. Нужно исправить этот недочёт в оптимизаторе, хотя бы до того уровня, чтобы примеры, описанные выше, работали без неожиданных регрессий производительности.

Если всё пойдёт по плану, эта оптимизация войдёт в релиз Go 1.13.

Спасибо за внимание.

Дополнение: предложенное решение

Эта секция для самых храбрых, тех, кто ещё не устал читать.

Итак, у нас несколько мест, которые работают хуже при использовании переменных вместо их значений напрямую. Предложенное решение состоит в том, чтобы ввести во frontend части компилятора новую функцию, которая позволяет по имени получить последнее привязанное значение. После этого в каждой оптимизации, которая ожидает константное значение, не сдаваться при обнаружении переменной, а получать это ранее сохранённое состояние.

Сигнатура нашей новой функции может выглядеть так:

func getConstValue(n *Node) *Node

Определение Node можно посмотреть в файле syntax.go.

Каждому определению переменной соответствует Node с тегом ONAME. Внутри Node.Name.Defn для большинства таких переменных имеется инициализирующее значение.

Если Node уже литерал, ничего делать не нужно и мы просто возвращаем n. Если же это ONAME (переменная), то можно попробовать извлечь из n.Name.Defn то самое инициализирующее значение.

Но как быть с модификациями между объявлением и чтением переменной, для которой мы вызываем getConstValue? Если мы ограничимся только read-only переменными, то никакой проблемы не существует. В frontend'е Go уже есть специальные флаги ноды, которые отмечают подобные имена. Если переменная модифицировалась, getConstValue не будет возвращать инициализирующее значение.

Программисты, обычно, не модифицируют входные аргументы числовых и строковых типов и это позволяет покрыть довольно большое число случаев этим примитивным алгоритмом.

Теперь мы готовы рассмотреть реализацию:

func getConstValue(n *Node) *Node {
    // Мы раскрываем только ONAME у которых доступен definition.
    if n.Op != ONAME || n.Name.Defn == nil {
        return n
    }

    // Проверка на то, что инициализирующее значение не изменялось.
    // Заметим, что это очень консервативно, но нашу задачу по
    // исправлению проблемы встраивания функций и escape analysis'а решает.
    maybeModified := n.Assigned() || n.Name.Defn.Assigned() || n.Addrtaken()
    if maybeModified {
        return n
    }

    // OAS - Node типа присваивания.
    // n.Name.Defn.Left - это LHS.
    // n.Name.Defn.Right - это RHS.
    // consttype(v) возвращает константный тип инициализирующего выражения.
    // Если это CTxxx, то переданное выражение не является константным.
    if n.Name.Defn.Op == OAS {
        v := n.Name.Defn.Right
        if v != nil && consttype(v) != CTxxx {
            return v
        }
    }
    return n    
}

Примерно вот так меняется код, который зависит от констант:

- i := indexconst(r)
+ i := indexconst(getConstValue(r))

Отлично, и оно даже работает:

n := 10
xs := make([]int, n) // Теперь не убегает в кучу!

До этого изменения escape analysis не мог получить через n значение 10, из-за чего делал предположение о необходимости разместить xs в куче.

Код выше синтаксически похож на ситуацию, наблюдаемую при встраивании. n может быть временной переменной, которая добавляется при передаче аргумента.

К сожалению, есть нюансы.

Мы решили проблему для локальных переменных, вводимых через OAS, но Go инициализирует переменные для встроенных функций через OAS2. Из-за этого нам понадобится второе изменение, расширяющее функцию getConstValue и немного модифицирующее код самого inliner'а, ведь, помимо прочего, OAS2 не имеет подходящего поля Defn.

Это были плохие новости. Хорошие новости: в русскоязычном слаке появился канал #gocontributing, где можно делиться своими идеями и планами, задавать вопросы, а также обсуждать всё, что связано с участием в разработке Go.

Теги:

Хабы:

Дефективное встраивание функций в Go

Measure it!

strings.HasPrefix

Оптимизации константных выражений

Как Go встраивает вызовы функций

Ещё один пример: escape analysis

Горизонты Go 1.13

Дополнение: предложенное решение

Публикации

Истории

Работа

Ближайшие события