Эквивалентен ли по производительности код, представленный ниже?
// (A). Вызов HasPrefix будет встроен.
return strings.HasPrefix(s, "#")
// (B). Ручное встраивание тела HasPrefix.
return len(s) >= len("#") && s[:len("#")] == "#"
Ответ: нет.
За подробностями и объяснениями прошу под кат.
Доброго времени суток, перед тем, как раскрыть тему, хотел бы представиться.
Меня зовут Искандер и я время от времени отправляю коммиты в репозиторий golang/go.
С недавних пор работаю в vk в команде инфраструктуры. Раньше я делал это от лица команды Intel Go, но наши пути разошлись и теперь я независимый контрибьютор.
А ещё я рисую гоферов. В свободное время делаю разные инструменты для Go, типа go-critic и go-consistent.
Сразу приступим к сравнению и набросаем бенчмарк:
package benchmark import ( "strings" "testing"
) var s = "#string" func BenchmarkHasPrefixCall(b *testing.B)
} 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)
Попробуем разобраться почему это происходит. Вариант с ручным встраиванием гораздо быстрее кода, который был получен при встраивании тела функции компилятором.
HasPrefix: Вспомним реализацию strings.
// 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'
HasPrefix из варианта (A) мы получаем следующий машинный код: Для вызова strings.
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, её и разберём.
HasPrefix(s, "#") может быть оптимизирован в том, что аргумент-префикс является константой. Причина, по которой вызов strings. Нет смысла вызывать 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
}
Опять же, всё благодаря константному значению при вызове make. Поскольку buf не "убегает", компилятор сможет выделить эти 16 байтов на стеке, без аллокации на куче. Для выделения памяти на стеке нам важно знать требуемый размер, который будет входить в состав фрейма, отводимого под вызов функции.
Мы ввели новую абстракцию и решили везде использовать новый тип 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 — это неправильно.
13. Если всё пойдёт по плану, эта оптимизация войдёт в релиз Go 1.
Спасибо за внимание.
