День 1-1 · Феликс Гайзендорфер
Опубликовано:
Настало время гиков, так что пришло время Адвента Кода 2021. Моей темой в прошлом году было изучение ржавчины, но в этом году я решил сосредоточиться на профилировании Go.
Идея состоит в том, чтобы закодировать простые решения и использовать инструменты профилирования Go для их оптимизации. Несколько человек в твиттере были заинтересованы в том, чтобы увидеть результаты в виде сообщений в блоге, поэтому я надеюсь написать несколько из них.
Весь код и профили вы можете найти в истории этого репозитория: github.com/felixge/advent-2021.
Отказ от ответственности: в настоящее время я работаю над непрерывным профилированием Go для Datadog, но я не лаю здесь от имени своего работодателя.
Задачу дня 1-1 решить довольно легко, поэтому я быстро нашел простое решение, см. ниже.
func Answer(input string) (int, error) {
var prev struct {
val int64
set bool
}
var increases int
for _, line := range strings.Split(input, "\n") {
val, err := strconv.ParseInt(line, 10, 64)
if err != nil {
return 0, err
}
if val > prev.val && prev.set {
increases++
}
prev.set = true
prev.val = val
}
return increases, nil
}
Это работает, но достаточно ли это быстро? Давайте проведем тест.
$ go test -count 5 -run '^$' -bench . -cpuprofile=v1.cpu.pprof > v1.txt
$ benchstat v1.txt
name time/op
Answer-6 325ns ± 1%
Хотя вам это может показаться не таким уж плохим, это определенно не Christmas Scale™️, поэтому давайте выясним, что мы можем оптимизировать, взглянув на профиль нашего процессора как на FlameGraph:
Похоже, 44% нашего времени мы проводим в strings.Split()давайте это оптимизируем.
v2: Оптимизировать strings.Split() (ссылка на код)
Глядя на FrameGraph выше, обратите внимание, что strings.Split() звонки strings.IndexByte() который реализован на ассемблере. Оказывается, мы можем вызвать это напрямую, чтобы выполнить собственное разделение новой строки:
func Answer(input string) (int, error) {
var prev struct {
val int64
set bool
}
var increases int
var line string
for len(input) > 0 {
i := strings.IndexByte(input, '\n')
if i == -1 {
line = input
input = ""
} else {
line = input(0:i)
input = input(i+1:)
}
val, err := strconv.ParseInt(line, 10, 64)
if err != nil {
return 0, err
}
if val > prev.val && prev.set {
increases++
}
prev.set = true
prev.val = val
}
return increases, nil
}
Это немного сложнее, но давайте посмотрим, что это нам дает:
$ benchstat v1.txt v2.txt
name old time/op new time/op delta
Answer-6 325ns ± 1% 168ns ± 2% -48.25% (p=0.008 n=5+5)
Сокращение времени выполнения на 48 % — похоже, у нас хорошее начало! Что дальше?
Похоже на strconv.ParseInt() стал нашим новым узким местом.
v3: Оптимизация strconv.ParseInt() (ссылка на код)
Хотя эльфы не заявляют об этом явно, они дают нам только положительные целые числа. Таким образом, мы могли бы применить тот же трюк, что и раньше, и вызвать strconv.ParseUint() напрямую, а не через strconv.ParseInt().
Однако, глядя на реализацию ParseUint, становится ясно, что он делает кучу вещей для поддержки разных баз и размеров бит. Нам ничего из этого не нужно, поэтому давайте просто реализуем то подмножество, которое нам действительно нужно:
func parseInt(val string) (int64, error) {
var intVal int64
factor := int64(1)
for i := len(val) - 1; i >= 0; i-- {
c := val(i)
if c >= '0' && c <= '9' {
intVal += int64(c-'0') * factor
} else {
return intVal, fmt.Errorf("bad int: %q", val)
}
factor *= 10
}
return intVal, nil
}
Посмотрим, стоило ли оно того:
$ benchstat v2.txt v3.txt
name old time/op new time/op delta
Answer-6 168ns ± 2% 92ns ± 3% -45.29% (p=0.016 n=5+4)
Еще 45% — возможно, здесь мы, в конце концов, достигнем Christmas Scale™️.
Можем ли мы добиться еще большего?
Приведенный выше FlameGraph не дает нам никаких очевидных подсказок о том, что делать дальше. Но мы можем копнуть глубже. Например, давайте посмотрим, посмотрим View -> Source:
Как вы можете видеть, мы тратим довольно много времени на операцию подсрезов в режиме онлайн. 41. Это наша следующая подсказка?
v4: Ботаник-бекас
Эльфы сообщили мне, что текущее решение более чем в 3 раза быстрее, чем версия 1, что на данный момент достаточно хорошо:
$ benchstat v1.txt v3.txt
name old time/op new time/op delta
Answer-6 325ns ± 1% 92ns ± 3% -71.68% (p=0.016 n=5+4)
Однако они готовы предложить специальное предложение. Перейти к профилированию звезды всем, кому удастся улучшить версию v3. Здесь вы можете войти. Просто пришлите мне ссылку на ваше решение v4 в эта ветка в твиттере включая твой benchstats v3.txt v4.txt вывод, и я дам ссылку на него отсюда.
- Валентин Делеплас‘s решение с
-87%дельта против v3 - Гарет Левин‘s решение с
-83%дельта против v3 - Понтус Лейтцлер‘s решение с
-74%дельта против v3 - @Фугиман‘s решение с
-50%дельта против v3
Примечание: Приведенные выше результаты по разнице производительности получены самостоятельно. В моем собственном тестировании решение Валентина показало впечатляющие результаты. 14 ns/op и имеет -52% дельта против решения Гарета.
Вот и все на сегодня. Я определенно найду время только для нескольких из этих постов, но постараюсь, чтобы они появлялись.
— Феликс Гейзендорфер
Подпишитесь на этот блог через RSS или по электронной почте или получайте от меня небольшие обновления через Твиттер.
