Анализируем bound checks в Go по CPU профилю
Сегодня мы будем анализировать бинарники на пару с CPU профилями, чтобы создать на их основе расширенные профили исполнения. Эти дополненные профили мы сможем использовать для оценки времени, которое программа тратит на проверки выхода за границу массивов и слайсов.
Введение в проблему
Профилирование в Go собирает стеки вызовов вместе с позицией текущей исполняемой инструкции. И хотя такая гранулярность очень полезна при просмотре в disasm режиме, она мало чего говорит нам о том, какова семантика исполняемых инструкций.
Проще всего работать с уровнем функций. По функциям мы можем агрегировать семплы, строить деревья вызовов и флеймграфы.
Некоторые встроенные в язык операции генерируют какой-то понятный вызов. Например, операторы для работы с каналами (runtime.chanrecv, runtime.chansend).
Другие могут превращаться в несколько вызовов: append(b1, b2...) создаст вызовы runtime.growslice и runtime.memmove. Это уже усложняет анализ профилей, но у нас хотя бы есть, за что зацепиться.
Самое сложное — это операции, которые встраивают свой код прямо в место использования, без какого-либо вызова. Это эффективно в плане скорости исполнения, но профилирование таких конструкций штатными средствами становится невозможным. Машинный код этих операций смешивается с использующей их функцией, а в профиле эти значения будут увеличивать личное (flat/self) время этой функции.
Цена bound check’ов
Будем бенчмаркать довольно простую функцию получения последнего элемента слайса:
package bcbench
import "testing"
//go:noinline
func getlast(xs []int) int {
return xs[len(xs)-1]
}
func BenchmarkGetLast(b *testing.B) {
xs := []int{0, 2, 3, 5}
for i := 0; i < b.N; i++ {
getlast(xs)
getlast(xs)
getlast(xs)
getlast(xs)
}
}Чтобы бинарник с тестом был доступен после бенчмарков, соберём его явно через -c. Нам потребуется много запусков (count), так как сами тестируемые операции очень быстрые — семплирующая природа профилирования требует более длинных интервалов, чтобы у нас был шанс снять стеки в нужные моменты.
$ go test -c
$ ./bcbench.test -test.count=60 -test.cpuprofile=cpu.out -test.bench=. .Теперь откроем профиль в браузере:
$ go tool pprof -http=:8080
Я отметил строки, которые напрямую относятся к проверкам выхода за пределы слайса. Мы ещё вернёмся к этой структуре, но сначала я хочу обратить ваше внимание на то, что большая часть семплов вообще не покрыла связанные инструкции. Это не значит, что bound check в данном случае бесплатен. Это скорее признак того, что записывая семплы 100 раз в секунду нам очень сложно поймать некоторые участки машинного кода.
Перепишем функцию getlast так, чтобы там не было проверок, вставленных компилятором:
//go:noinline
func getlast(xs []int) int {
if len(xs) != 0 {
return xs[len(xs)-1]
}
return 0
}Запустим аналогичные бенчмарки, соберём профиль, сравним быстродействие.
Можем видеть, что вставленных компилятором проверок нет. Вместо CMPQ у нас в коде TESTQ и, может показаться, что это работает медленнее, ведь целых 4 секунды мы провели на этой инструкции. Но это не так, нам просто «повезло».
При сравнении быстродействия видно, что вторая версия функции быстрее, хоть её исходники и более многословные:
$ benchstat old.txt new.txt
name old time/op new time/op delta
GetLast-8 12.5ns ± 2% 9.3ns ± 1% -25.93% (p=0.000 n=10+10)И, снова, это скорее побочный эффект: версия без вызова panicindex не имеет фрейма, поэтому сама по себе функция более легковесная. Наша проблема в том, что даже имея всю информацию, замерять время, потраченное на bound check — не очень просто.
Сам бенчмарк можно переписать, убрав go:noinline, но тогда нужно сделать так, чтобы компилятор не догадался, что наш слайс — неизменяемый и проверять его длину внутри цикла нет смысла. Писать корректные бенчмарки — это нетривиально.
Откуда появляется bound check
Проверки выхода за пределы массива бывают разные. Давайте попробуем узнать, что вообще в нашем коде может требовать этих проверок.
Для массивов, частью типа которых является их длина, проверки вставляются только в случае неконстантных индексов.
func f(i int) {
var a [8]int
println(a[0]) // не требует проверок
println(a[i]) // проверка i < len(a)
}Для слайсов эти проверки вставляются почти по любому поводу. На практике, часть из этих проверок удаляется как избыточные, когда компилятор может доказать, что индекс точно лежит в допустимом интервале.
При слайсинге (взятии «срезов») массивов происходят те же самые проверки, поэтому для a[i:] компилятор будет вставлять проверку на i <= len(a).
func f(b []byte, i, j int) {
println(b[i]) // проверка i < len(b)
println(b[i:]) // проверка i <= len(b)
println(b[:j]) // проверка j <= cap(b)
println(b[i:j]) // проверка i <= len(b) && j <= cap(b)
}Здесь важно отметить, что разные операции могут генерировать немного отличающиеся фрагменты. Результаты так же зависят от версии Go компилятора. Данная статья написана опираясь на go 1.17 и 1.18.
Смотрим на дизассемблер bound check’ов
Все примеры кода актуальны для x86–64 (GOARCH=amd64).
Начнём с самого простого случая:
func indexing(i int, xs []int) int {
return xs[i]
}Посмотрим на сгенерированный код:
SUBQ $24, SP
MOVQ BP, 16(SP)
LEAQ 16(SP), BP
MOVQ BX, xs+40(FP)
CMPQ CX, AX
JLS bc_fail
MOVQ (BX)(AX*8), AX
MOVQ 16(SP), BP
ADDQ $24, SP
RET
bc_fail:
CALL runtime.panicIndex(SB)Это и есть довольно общая схема для bound check’а:
- Инструкция сравнения (CMPQ или TEST в случае сравнения с 0)
- Условный прыжок (JLS выше — это JBE)
- В месте прыжка идёт вызов одной из паникующих функций
До инструкции CALL могут быть несколько инструкций типа MOV или LEA для передачи нужных аргументов.
Возьмём ещё несколько функций для экспериментов:
func slicingFrom(i int, xs []int) []int {
return xs[i:]
}
func slicingTo(i int, xs []int) []int {
return xs[:i]
}
func slicingFromTo(i, j int, xs []int) []int {
return xs[i:j]
}Если посмотреть через дизассемблер на получившийся код, мы заметим, что для этих случаев генерируется во многом похожий код, но функции «паники» отличаются.
indexing—runtime.panicIndex()slicingFrom—runtime.panicSliceB()slicingTo—runtime.panicSliceAcap()slicintFromTo—runtime.panicSliceB()иruntime.panicSliceAcap()
На самом деле, даже это не полный набор. Весь список функций можно подсмотреть в исходниках компилятора.
Это означает, что есть более одной функции, которая может вызываться в случае неуспешной проверки. Нам нужно знать адреса всех этих функций.
Если же машинный код матчится по алгоритму выше и завершается вызовом специальной функции-паники, типа panicSliceAcap, то мы можем быть уверенными, что перед нами bound check.
При этом считать семплы мы будем только для двух инструкций из всей распознанной последовательности: CMPQ и JLS.
Собираем адреса функций-паник
Я буду рассматривать пример с ELF бинарником.
В стандартной библиотеке Go есть пакет debug/elf. Им мы и воспользуемся.
var bcFuncNames = map[string]struct{}{
"runtime.panicIndex": {},
"runtime.panicIndexU": {},
"runtime.panicSliceAlen": {},
"runtime.panicSliceAlenU": {},
"runtime.panicSliceAcap": {},
"runtime.panicSliceAcapU": {},
"runtime.panicSliceB": {},
"runtime.panicSliceBU": {},
"runtime.panicSlice3Alen": {},
"runtime.panicSlice3AlenU": {},
"runtime.panicSlice3Acap": {},
"runtime.panicSlice3AcapU": {},
"runtime.panicSlice3B": {},
"runtime.panicSlice3BU": {},
"runtime.panicSlice3C": {},
"runtime.panicSlice3CU": {},
"runtime.panicSliceConvert": {},
}
bcFuncAddresses := make(map[int64]struct{})
// exeBytes - []byte из нашего бинарника
f, err := elf.NewFile(bytes.NewReader(exeBytes))
if err != nil {
return fmt.Errorf("parse ELF: %v", err)
}
symbols, err := f.Symbols()
if err != nil {
return fmt.Errorf("fetch ELF symbols: %v", err)
}
for _, sym := range symbols {
if _, ok := bcFuncNames[sym.Name]; !ok {
continue
}
addr := sym.Value // !!! <----------------------------
bcFuncAddresses[int64(addr)] = struct{}{}
}К сожалению, этот код не совсем корректен. Обратите внимание на строку с отметкой.
Чтобы адреса успешно отображались на то, что будет внутри CPU профиля, нам нужно выполнить некоторые преобразования. Пришло время парсить CPU профиль.
Пакет github.com/google/pprof/profile идеально подходит для нашей задачи.
// Использую ReadFile, а не os.Open, чтобы не возиться с файлом,
// который потом нужно будет закрывать
data, err := os.ReadFile("cpu.out")
if err != nil {
return fmt.Errorf("read profile: %v", err)
}
p, err := profile.Parse(bytes.NewReader(data))
if err != nil {
return fmt.Errorf("parse profile: %v", err)
}Теперь поменяем вычисления адреса:
- addr := sym.Value
+ addr := sym.Value + p.Mapping[0].Offset - p.Mapping[0].StartУра! Теперь мы можем определять CALL по таблице адресов.
Разбираем машинный код
Обходя семплы, мы используем loc.Address, чтобы получить адрес текущей исполняемой инструкции. Затем мы проверяем, можно ли с этой позиции распознать bound check в функции markBoundCheck.
for _, sample := range p.Sample {
if len(sample.Location) == 0 {
continue
}
for _, loc := range sample.Location {
if len(loc.Line) == 0 {
continue
}
m := loc.Mapping
addr := int64(loc.Address + m.Offset - m.Start)
// ctx содержит подготовленный ранее bcFuncAddresses
markBoundCheck(ctx, exeBytes, addr)
}
}Картинка ниже призвана помочь понять высокоуровневую структуру профилей. Семплы располагаются примерно так:
Остаётся реализовать markBoundCheck. Для декодирования инструкций будем использовать golang.org/x/arch/x86/x86asm.
func markBoundCheck(ctx *context, code []byte, addr int64) bool {
// 1. Инструкция сравнения
cmp, err := x86asm.Decode(code[addr:], 64)
if err != nil {
return false
}
if cmp.Op != x86asm.CMP && cmp.Op != x86asm.TEST {
return false
}
// 2. Условный прыжок
jmp, err := x86asm.Decode(code[addr+int64(cmp.Len):], 64)
if err != nil {
return false
}
jumpFrom := int64(addr) + int64(cmp.Len)
var jumpTo int64
switch jmp.Op {
case x86asm.JBE, x86asm.JB, x86asm.JA:
rel, ok := jmp.Args[0].(x86asm.Rel)
if !ok {
return false
}
jumpTo = jumpFrom + int64(rel) + int64(jmp.Len)
default:
return false
}
// 3. Вызов паникующей функции
call, err := x86asm.Decode(code[jumpTo:], 64)
if err != nil {
return false
}
if inst.Op != x86asm.CALL {
return false
}
funcRel, ok := call.Args[0].(x86asm.Rel)
if !ok {
return false
}
funcAddr := jumpTo + int64(funcRel) + int64(call.Len)
if _, ok := ctx.bcFuncAddresses[funcAddr]; !ok {
return false
}
// Записываем, что CMPQ (addr) и прыжок (addr+cmp.Len) относятся
// к bound check операциям
ctx.bcAddresses[addr] = struct{}{}
ctx.bcAddresses[addr+int64(cmp.Len)] = struct{}{}
return true
}Этот код немного упрощён. Ссылка на полную реализацию я привожу в конце статьи.
Теперь можем по любому адресу инструкции из CPU профиля сказать, относится ли она к bound check или нет.
Добавляем runtime.boundcheck в профиль
Самый простой способ — это добавить новые inline фреймы в уже существующие profile.Location объекты.
Но сначала нам нужно добавить в профиль информацию о новой функции. Назовём её runtime.boundcheck:
// ID начинаются с 1, то есть p.Function[i].ID == i+1
id := len(p.Function) + 1
boundcheckFunc := &profile.Function{
ID: uint64(id),
Name: "runtime.boundcheck",
SystemName: "runtime.boundcheck",
Filename: "builtins.go", // Не имеет значения
StartLine: 1, // Не имеет значения
}
p.Function = append(p.Function, boundcheckFunc)Теперь пройдёмся по всем семплам ещё раз и будем вставлять runtime.boundcheck для всех семплов, которые сейчас исполняют связанный с этим код.
for _, sample := range p.Sample {
if len(sample.Location) == 0 {
continue
}
loc := sample.Location[0]
if len(loc.Line) == 0 {
continue
}
m := loc.Mapping
addr := int64(loc.Address + m.Offset - m.Start)
if _, ok := ctx.bcAddresses[addr]; ok {
insertLine(loc, boundcheckFunc)
}
}Функцию insertLine можно реализовать так:
func insertLine(loc *profile.Location, fn *profile.Function) {
if loc.Line[0].Function == fn {
return // Видимо, мы уже вставляли сюда новый вызов
}
newLine := profile.Line{
Function: fn,
Line: lines[1].Line,
}
loc.Line = append([]profile.Line{newLine}, loc.Line...)
}После работы с объектов профиля нам остаётся вызвать метод Write и сохранить его в новый файл:
f, err := os.Create("cpu2.out")
if err != nil {
return err
}
defer f.Close()
if err := p.Write(f); err != nil {
return err
}Работаем с новым, дополненным профилем
Попробуем открыть новый профиль в pprof:
$ go tool pprof cpu2.out
Всё работает. GUI режим тоже работает, вы уже могли видеть скриншот выше (КДПВ).
На скриншоте можно так же видеть runtime.nilcheck. Добавить эту информацию в профиль не сложно, а алгоритм будет абсолютно идентичен. Отличается только mark фаза, где мы пытаемся матчить машинный код. Чаще всего nil check в Go выглядит так: TESTB AX, (reg).
Заключение
Добавление в профиль псевдо-функций runtime.nilcheck и runtime.boundcheck реализовано в qpprof. Полные версии исходников из примеров можно найти там же.
На данном этапе я не могу сказать, что мы получаем релевантные значения, но, по крайней мере, мы научились дополнять профили чем-то новым. Если использовать альтернативный профилировщик для Go, который имеет более высокий hz для профилирования, либо вообще является не семплирующим, то наши шансы получить более точные метрики возрастают. Если эти другие профилировщики умеют экспортировать данные в формате pprof (profile.proto), то все приёмчики из этой статьи будут актуальны. В противном случае мы можем попробовать конвертировать профиль в родной для Go формат.
У меня есть ещё одно секретное применения для таких расширенных профилей, но об этом мы поговорим в другой раз.
