Дефективное встраивание функций в 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. А ещё я рисую гоферов.
Сразу приступим к сравнению и набросаем бенчмарк:
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:
// 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 части компилятора.
Казалось бы, что же всё-таки не даёт этой оптимизации сработать в нашем случае?
Вот как будет происходить встраивание:
// Вот как выглядел вызов:
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, это не мешает. Но там присутствуют другие проблемы, например, невозможность восстановить высокоуровневые конструкции языка для их эффективного сопоставления (работа по устранению этого недостатка «планируется» уже несколько лет).
Представим функцию, которой важно выделять временный буфер на стеке:
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 было бы ясно, что размер всё так же известен на этапе компиляции.
Это огорчает чуть ли не сильнее, чем ситуация со сравнением строк.
Ситуацию можно довольно легко поправить и я уже выслал первую часть решения.
Если вы считаете, что описанная в статье проблема действительно нуждается в решении, поставьте, пожалуйста, палец вверх в соответствующем issue.
Моя позиция состоит в том, что встраивать код руками только потому что он работает быстрее в текущей версии Go — это неправильно. Нужно исправить этот недочёт в оптимизаторе, хотя бы до того уровня, чтобы примеры, описанные выше, работали без неожиданных регрессий производительности.
Если всё пойдёт по плану, эта оптимизация войдёт в релиз Go 1.13.
Спасибо за внимание.
