Как сделать программу на Go быстрее на 42%, изменив один символ

Если вы прочитали заголовок и подумали «ну, ты, наверно, сделал сначала что-то глупое», то вы правы! Но что такое программирование, как не упражнения в глупых ошибках? Поиск глупых ошибок — это и есть самое большое удовольствие!

Также стоит заранее сделать оговорку о бенчмаркинге: ускорение на 42% было замерено при выполнении программы с моими данными и на моём компьютере, поэтому относитесь к этому результату с долей скепсиса.

Что делает программа?

codeowners — это программа на Go, выводящая владельцев каждого из файлов в репозитории согласно набору правил, указанному в файле GitHub CODEOWNERS. Правило может гласить, что всеми файлами с расширением .go владеет команда @gophers, или что всеми файлами в папке docs/ владеет команда @docs.

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

type Ruleset []Rule

func (r Ruleset) Match(path string) (*Rule, error) {
  for i := len(r) - 1; i >= 0; i-- {
    rule := r[i]
    match, err := rule.Match(path)
    if match || err != nil {
      return &rule, err
    }
  }
  return nil, nil
}

Поиск медленных фрагментов при помощи pprof и flamegraph

При обработке умеренно крупного репозитория мой инструмент работал немного медленно:

$ hyperfine codeowners
Benchmark 1: codeowners
  Time (mean ± σ):      4.221 s ±  0.089 s    [User: 5.862 s, System: 0.248 s]
  Range (min … max):    4.141 s …  4.358 s    10 runs

Чтобы понять, на какие части программа тратит своё время, я записал профиль CPU при помощи pprof. Сгенерировать профиль CPU можно, добавив в начало функции main следующий фрагмент кода:

pprofFile, pprofErr := os.Create("cpu.pprof")
if pprofErr != nil {
  log.Fatal(pprofErr)
}
pprof.StartCPUProfile(pprofFile)
defer pprof.StopCPUProfile()

Примечание: я пользуюсь pprof довольно активно, поэтому сохранил этот код в виде сниппета vscode. Я просто ввожу pprof, жму tab, и появляется этот сниппет.

У Go есть удобный интерактивный инструмент для визуализации профилей. Я визуализировал профиль в виде flamegraph, запустив следующую команду, а затем перейдя в режим flamegraph из меню в верхней части страницы.

$ go tool pprof -http=":8000" ./codeowners ./cpu.pprof

Как я и ожидал, основную часть времени программа тратила на функцию Match. Паттерны CODEOWNERS компилируются в регулярные выражения, и бо́льшая часть времени функции Match тратилась на движок regex языка Go. Но также я заметил, что много времени тратилось на распределение и возвращение памяти. Сиреневые блоки в показанном ниже flamegraph соответствуют паттерну gc|malloc, и видно, что суммарно они составляют существенную часть времени выполнения программы.

Охота на распределения кучи при помощи трассировок escape-анализа

Давайте посмотрим, есть ли какие-то распределения, от которых можно избавиться, чтобы снизить давление GC и уменьшить время, занимаемое malloc.

Чтобы разобраться, когда какая-то память должна продолжать жить в куче, компилятор Go использует методику под названием «escape-анализ». Допустим, функция инициализирует struct, а затем возвращает указатель на неё. Если struct распределена в стеке, возвращённый указатель станет недействительным сразу после возврата функции и инвалидации соответствующего кадра стека. В этом случае компилятор Go определит, что указатель «сбежал» от функции и переместит struct в кучу.

Посматривать, как принимаются эти решения, можно, передавая -gcflags=-m команде go build:

$ go build -gcflags=-m *.go 2>&1 | grep codeowners.go
./codeowners.go:82:18: inlining call to os.IsNotExist
./codeowners.go:71:28: inlining call to filepath.Join
./codeowners.go:52:19: inlining call to os.Open
./codeowners.go:131:6: can inline Rule.Match
./codeowners.go:108:27: inlining call to Rule.Match
./codeowners.go:126:6: can inline Rule.RawPattern
./codeowners.go:155:6: can inline Owner.String
./codeowners.go:92:29: ... argument does not escape
./codeowners.go:96:33: string(output) escapes to heap
./codeowners.go:80:17: leaking param: path
./codeowners.go:70:31: []string{...} does not escape
./codeowners.go:71:28: ... argument does not escape
./codeowners.go:51:15: leaking param: path
./codeowners.go:105:7: leaking param content: r
./codeowners.go:105:24: leaking param: path
./codeowners.go:107:3: moved to heap: rule <<< --------- перемещение в кучу
./codeowners.go:126:7: leaking param: r to result ~r0 level=0
./codeowners.go:131:7: leaking param: r
./codeowners.go:131:21: leaking param: path
./codeowners.go:155:7: leaking param: o to result ~r0 level=0
./codeowners.go:159:13: "@" + o.Value escapes to heap

Вывод выглядит немного зашумлённым, однако бо́льшую его часть можно игнорировать. Так как мы ищем распределения, нас должна волновать фраза moved to heap. Если посмотреть на приведённый выше код Match, можно увидеть, что структуры Rule хранятся в слайсе Ruleset, насчёт которого мы можем уверены, что он уже находится в куче. И поскольку возвращается указатель на rule, не должны требоваться никакие дополнительные распределения.

И тут я понял: присваивая rule := r[i], мы копируем распределённое в куче Rule из слайса в стек, а возвращая &rule, мы создаём указатель («сбегающий») на копию struct. К счастью, исправить это легко. Нам нужно просто переместить амперсанд немного выше, чтобы мы получали ссылку на struct в слайсе, а не копировали её:

 func (r Ruleset) Match(path string) (*Rule, error) {
 	for i := len(r) - 1; i >= 0; i-- {
		rule := &r[i] // вместо rule := r[i]
 		match, err := rule.Match(path)
 		if match || err != nil {
			return rule, err // вместо return &rule, err
 		}
 	}
 	return nil, nil
 }

я рассмотрел и два других подхода:

1. Превращение Ruleset из []Rule в []*Rule, что означало бы, что нам больше не нужно явным образом получать ссылку на правило.
2. Возврат Rule вместо *Rule. Это всё равно скопирует Rule, но оно должно остаться в стеке, а не переместиться в кучу.

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

Как бы то ни было, после внесения этого изменения мы можем проверить, дало ли оно желаемый эффект, получив от компилятора новую трассировку и сравнив её со старой:

$ diff trace-a trace-b
14a15
> ./codeowners.go:105:7: leaking param: r to result ~r0 level=0
16d16
< ./codeowners.go:107:3: moved to heap: rule

Успех! Распределение пропало. Теперь посмотрим, как удаление этого одного распределения кучи повлияло на производительность:

$ hyperfine ./codeowners-a ./codeowners-b
Benchmark 1: ./codeowners-a
  Time (mean ± σ):      4.146 s ±  0.003 s    [User: 5.809 s, System: 0.249 s]
  Range (min … max):    4.139 s …  4.149 s    10 runs

Benchmark 2: ./codeowners-b
  Time (mean ± σ):      2.435 s ±  0.029 s    [User: 2.424 s, System: 0.026 s]
  Range (min … max):    2.413 s …  2.516 s    10 runs

Summary
  ./codeowners-b ran
    1.70 ± 0.02 times faster than ./codeowners-a

Так как это распределение происходило для каждого сопоставляемого пути, его удаление дало в моём случае увеличение скорости в 1,7 раза (то есть программа начала работать на 42% быстрее). Неплохой результат для изменения в один символ.