Выжимаем из Go максимум производительности

Разработчики, которые используют Go, сталкиваются с задачей выжать максимальную производительность из каждой строки кода. Но что делать, если оптимизировать уже нечего, а увеличивать скорость всё равно надо?

Меня зовут Никита Галушко. Я старший программист-разработчик в отделе высоконагруженных систем и оптимизации ВКонтакте. В статье поделюсь, какие хитрости помогут использовать Go на полную мощность.

О чём будет речь в статье

• Расскажу про память, а именно про small-size объекты и интерфейс, покажу пару трюков со стеком.

• Поделюсь, как сильно может влиять на производительность BCE (Bounds Check Elimination) и почему не все циклы for-loop одинаково полезны. 

• Раскрою особенности, которые текущий компилятор Go накладывает на наш код.

• Затрону такие темы, как оптимальная конвертация string -> []byte и []byte -> string, конкатенация и связанные с ней оптимизация, сортировка []string — это важно, так как в наших повседневных программах часто используются строки, и с типом string связано много мифов.

В первую очередь мы пишем код для человека. Но если нужно выжимать максимум производительности, то от такого подхода придётся отказаться и начать писать код для компилятора. Я не встречал высокопроизводительного кода, который был бы лёгок в чтении, тестировании и модификации.

Всё сказанное будет важно, только если вы уже подумали над теми структурами данных и алгоритмами, которые используются в вашем приложении. Нет смысла пытаться выигрывать наносекунды или единицы мегабайт, если используется неподходящая структура данных.

Что такое small-size объекты в Go?

Это объекты размером не более четырёх машинных слов. Для 64-битных систем — это 32 байта. Чтобы понять, как сильно они могут влиять на производительность, напишем пару бенчмарков.

Представьте, что у вас есть small-size объект, который состоит из четырёх int. Рядом с ним объект, отличающийся всего на один int. Функции простые — это сумма двух полей объекта.

type SmallObject struct {
	a, b, c, d int
}
type PlainObject struct {
	a, b, c, d int
	e          int
}

func sum1(obj SmallObject) int {
	return obj.a + obj.d
}
func sum2(obj PlainObject) int {
	return obj.a + obj.d
}

Бенчмарк к этому коду тоже максимально прост.

func BenchmarkSmall(b *testing.B) {
	var ret int
	for i := i; i < b.N; i++ {
		obj := SmallObject{a: i, d: i}
		ret = sum1(obj)
	}
	_ = ret
}

func BenchmarkPlain(b *testing.B) {
	var ret int
	for i := 0; i < b.N; i++ {
		obj := PlainObject{a: i, d: i, e: i}
		ret = sum2(obj)
	}
	_ = ret
}

Конструируем объект на месте и вызываем функцию в зависимости от типа. Если мы его запустим, то увидим, что функция, которая работает со small-size объектом, выполняется в 2–2,5 раза быстрее. 

BenchmarkSmallObject-8 1000000000 1.037 ns/op 0 B/op 0 allocs/op

BenchmarkPlainObject-8 423361981 2.571 ns/op 0 B/op 0 allocs/op

Это очень странно: у нас два почти одинаковых объекта, которые отличаются лишь на один int. Я напомню, что наша цель — экономия наносекунд, так как функция может вызываться тысячи и миллионы раз. Чтобы разобраться в этом, используем ассемблер. Мы будем к нему обращаться на протяжении всей статьи. Поделюсь, как вы можете это делать сами.

Есть ресурс Compiler Explorer (godbolt.org). Мне нравится пользоваться им больше, чем собственноручно компилировать через go tool, потому что можно поэкспериментировать с версиями Go, с архитектурой, под которую будет компиляция. Но если вы хотите экспериментировать на своей локальной машине или нет доступа к godbolt, то можно воспользоваться следующей командой:

go tool compile -S main.go > main.s

Давайте скомпилируем и посмотрим на ассемблер.

Из ассемблера видно, что функция, которая работает со small-size объектом, — это пара инструкций. Отмечу, что здесь мы взаимодействуем с регистрами напрямую. Если работаем с объектом, где лишь на один int больше, мы тратим время на заполнение стека, а затем по ходу выполнения функции на его чтение.

Small-size объекты не просто экономят память. Они позволяют компилятору генерировать более производительный код, работая напрямую с регистрами CPU. Есть одно но — это очень редкий случай, сложно спроектировать систему только на таких микрообъектах.

Почему интерфейсы — это зло, когда речь идёт о производительности в Go?

Я попытаюсь вас в этом убедить на нескольких иллюстрациях. Представьте, что у вас есть интерфейс, где всего лишь два метода. 

type Summer interface {
	SumValue(Object) int
	SumPointer(*Object) int
}

Один метод принимает аргумент по значению, а второй — по указателю. Предположим, что объект максимально простой — всего лишь два int.

type Object struct {
	A, B int
}

А ещё допустим, что все оптимизации, которые работают для small-size объектов, будут действовать и здесь. Код тоже простой — сумма этих двух полей.

type Sum struct{}

func (v Sum) SumValue(obj Object) int {
	return obj.A + obj.B
}
func (p Sum) SumPointer(obj *Object) int {
	return obj.A + obj.B
}

Запустим простой бенчмарк.

BenchmarkSumPointer-8    101133675    11.59 ns/op    16 B/op    1 allocs/op

BenchmarkSumValue-8      609446936    1.855 ns/op     0 B/op    0 allocs/op

В результате увидим, что метод, который принимает объект по указателю, работает медленнее, а ещё аллоцирует что-то в heap. Причина в escape analysis, так как он руководствуется в этом месте достаточно простым правилом: если доступ к переменной есть у более чем одной горутины, то переменную нужно отправить в heap.

Вы возразите, что там не было никаких горутин. И я вас сильнее запутаю: если мы будем работать с типом напрямую, без интерфейса, то аллокации не будет.

Проблема в том, что escape analysis не заходит в нашу реализацию интерфейса. Он видит, что у нас есть интерфейс и вызов. Необходимо решить, отправлять переменную на heap или нет. В случае с указателем переменная может измениться дальше при вызове других функций. А если мы передаём аргумент по значению, то каждый раз происходит поверхностное копирование, и фактически мы можем просто отсрочить принятие этого решения.

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

• указатели к интерфейсу;

• int, int32, int6, uint, uint32, uint64 — приведение int до 65 тысяч;

• очень простые типы (пустой struct или struct с полем, размер которого не превышает одно машинное слово).

Поэтому по возможности не используйте интерфейсы. Забудьте, что они есть в Go, если вы хотите выжать максимум.

Есть ещё один пример, достаточно частый паттерн, который я вижу в разных Go-приложениях: есть интерфейс и несколько его реализаций в одном пакете. В нашем случае — это fileDumper и dbDumper. Код лёгкий, хорошо тестируется и расширяется. Но есть ряд проблем.

 

Если мы скомпилируем этот код в ассемблер, то увидим такую историю, как go:itab.

Напомню, что интерфейс — это тип, состоящий из двух слов, где есть указатель на данные и указатель на тип. Проблема go:itab в том, что виртуальный вызов — всегда поиск по таблице. А пока мы ищем, полезная работа не выполняется.

Я предлагаю сделать enum из тех реализаций, которые нам нужны, и оставить всего лишь один тип.

type dumpKind int8

const (
	_ dumpKind = iota
	toFile
	toDB
)

type Dumper struct {
	kind dumpKind
}

func (d Dumper) Dump(s string) {
	switch d.kind {
	case toFile:
	// ...
	case toDB:
		// ...
	}
}

У нас не будет интерфейсов, а в реализации мы по свитчу выберем ту или иную имплементацию.

При этом этот код не даёт ещё аллокаций, как предыдущий.

BenchmarkInterfaceDumper-8 28651759  41.81 ns/op 48 B/op 2 allocs/op 

BenchmarkStructDumper-8    164893970 7.111 ns/op 0 B/op 0 allocs/op

Но есть цена за производительность:

• некрасиво и трудно расширять, если вы не знаете, для чего это было сделано;

• сложно тестировать.

Несколько трюков со стеком

Важный тезис: в Go объекты до 64 Кб будут размещены на стеке. Помним про escape analysis, который может по своим правилам отправить переменную в heap, поэтому:

• не используем в другой горутине;

• не возвращаем из функции;

• не передаём в интерфейсы;

Представим, что есть код, где в функции foo выделяем два слайса по 64 Кб.

func foo() {
	a := make([]byte, 641024)
	b := make([]byte, 641024)
}

А в функции bar делаем то же самое, только на 2 байта больше.

func bar() {
	a := make([]byte, 641024+1)
	b := make([]byte, 641024+1)
}

Кажется, что может пойти не так? А пойти не так может всё.

BenchmarkFoo-8 1000000000 0.3189 ns/op 0 B/op 0 allocs/op

BenchmarkBar-8 73376 16924 ns/op 147456 B/op 2 allocs/op

Функция foo выполняется на порядок быстрее, чем bar, и делает 0 аллокаций.

Тут нужно сделать отдельную ремарку, что чем больше вы выделяете памяти на стеке, тем сильнее раздувается размер фрейма функции, а значит, переаллокация стека становится дороже.

Хорошо, 64 Кб выделяется на стеке, но что, если нам нужно выделить слайсы большего размера и строго на стеке? Придётся создавать их несколько по 64 Кб и жонглировать индексами? Нет. В Go есть интересный хак, который позволяет инстанцировать слайс на месте, задавая конкретному индексу какое-то значение, — и это не даст аллокаций.

func baz() {
	a := []byte{1_000_000: 0}
}

BenchmarkBaz-8 3636 302480 ns/op 0 B/op 0 allocs/op

Лично для меня это серая зона. Есть issue на эту тему. С одной стороны, тикету уже 3,5 года и ничего с ним не происходит, а с другой стороны, комментарии говорят о том, что есть вопросы.

Поговорим про CPU

BCE — Bounds Check Elimination 

Go позиционирует себя как безопасный язык, который пытается нас оградить от выходов за границу массива или слайса с помощью BCE — Bounds Check Elimination. Но насколько сильно эта безопасность влияет на производительность?

Представьте, что есть максимально простой код, который из []byte получает uint64 (взято из стандартной библиотеки).

func toUint64(b []byte) uint64 {
	return uint64(b[0]) |
		uint64(b[1])<<8 |
		uint64(b[2])<<16 |
		uint64(b[3])<<24 |
		uint64(b[4])<<32 |
		uint64(b[5])<<40 |
		uint64(b[6])<<48 |
		uint64(b[7])<<56
}

Код берёт элемент по индексу и делает две битовые операции. Кажется, что эта функция должна работать максимально быстро. Но если мы запустим бенчмарк, то увидим, что этот код выполняется целых 3 наносекунды.

func BenchmarkBCE(b *testing.B) {
	buf := make([]byte, 8)
	var ret uint64
	for i := 0; i < b.N; i++ {
		ret = toUint64(buf)
	}
	_ = ret
}

BenchmarkBCE-4 342406828 3.361 ns/op

Функция подобного рода может выполняться тысячи и миллионы раз, поэтому хочется сделать её максимально быстрой. 

Чтобы понять, почему уходит столько времени, нужно спуститься в ассемблер.

main_toUint64_pc91:
MOVL    $7, AX
MOVQ    AX, CX
PCDATA  $1, $1
CALL    runtime.panicIndex(SB)
main_toUint64_pc104:
MOVL    $6, AX
MOVQ    AX, CX
CALL    runtime.panicIndex(SB)
main_toUint64_pc117:
MOVL    $5, AX
MOVQ    AX, CX
NOP
CALL    runtime.panicIndex(SB)
main_toUint64_pc133:
MOVL    $4, AX
MOVQ    AX, CX
CALL    runtime.panicIndex(SB)
main_toUint64_pc146:
MOVL    $3, AX
MOVQ    AX, CX
CALL    runtime.panicIndex(SB)
main_toUint64_pc159:
MOVL    $2, AX
MOVQ    AX, CX
CALL    runtime.panicIndex(SB)
main_toUint64_pc172:
MOVL    $1, AX
MOVQ    AX, CX
CALL    runtime.panicIndex(SB)
main_toUint64_pc185:
XORL    AX, AX
MOVQ    AX, CX
NOP
CALL    runtime.panicIndex(SB)
XCHGL   AX, AX

Мы видим, что каждое обращение к индексу по факту оборачивается в if, который проверяет выход за границу массива. И если условие истинно, кидаем панику, если нет, то делаем джамп и продолжаем выполнение.

Как нам избавиться от ненужных проверок? Что, если мы знаем, что в нашем слайсе уже есть нужное количество элементов? Всё просто — достаточно потрогать самый дальний элемент.

Очевидно (как для человека, так и для Go), что если есть самый дальний элемент (в данном случае под индексом 7), то есть и все остальные. Добавим всего одну строчку в нашу исходную функцию.

func toUint64(b []byte) uint64 {
	_ = b[7]
	// ...
}

Затем запустим тот же самый бенчмарк ещё раз и увидим ускорение в 2 раза.

BenchmarkBCE-4    715002706    1.657 ns/op

Циклы

В Go у нас есть два вида циклов: for-loop и for-range. Я покажу, сколько приходится платить каждый раз, когда мы используем for-range, поскольку этот цикл основан на копировании. Всякий раз, когда вы получаете следующий элемент слайса при итерации, происходит его поверхностное копирование.

Тест будет простой. Объект с одним полем int и две функции, которые пробегают по слайсу из объектов, суммируя значение единственного поля.

type Obj struct {
	index int
}

func sumRange(objects []Obj) int {
	ret := 0
	for _, v := range objects {
		ret += v.index
	}
	return ret
}

func sumLoop(objects []Obj) int {
	ret := 0
	for i := 0; i < len(objects); i++ {
		ret += objects[i].index
	}
	return ret
}

Если мы запустим бенчмарк (он тривиальный, поэтому код не привожу), то увидим, что функция, которая использует обычный, стандартный for-loop по индексу, работает в 4 раза быстрее, чем for-range. Чем жирнее объект внутри слайса, тем эта разница будет больше.

BenchmarkForRange-4   443161 2371 ns/op

BenchmarkForLoop-4   1863501   641.7 ns/op

Про что ещё важно не забывать?

• Компилятор не векторизует операции (приходится писать на ассемблере). Код из примера про циклы по факту должен хорошо поддаваться векторизации, но увы, Go сейчас это не умеет. Поэтому если вы хотите использовать векторные инструкции, то придётся писать самому на ассемблере 🙁

• Кеш линии процессора. Не нужно забывать про кеш линии. Виртуальный вызов в интерфейсах — это ещё и проблема для кеша, потому что мы каждый раз вымываем инструкции, которые CPU уже взял себе на исполнение. При этом особенность Go в том, что у нас не треды, а горутины, и некоторые фишки, такие как, например, прикрепление конкретной горутины к конкретному ядру CPU, не пройдут (хоть это и частый паттерн в сетевых приложениях).

Строки

Когда мы говорим про производительность и всплывает тема строк, то тут же появляется и Unsafe.

Unsafe

У Unsafe в Go есть ряд проблем. Первая — это то, что перевод из строки в []byte и обратно даёт Unsafe-строчку, то есть любое изменение исходного []byte отразится на получаемой вами строке.

Но начиная с Go 1.20 вам не надо писать свои функции, которые переводят из []byte в строчку и из строчки в []byte, потому что это уже есть в стандартной библиотеке. В ней появились unsafe.StringData и unsafe.String. Это важно знать, потому что очень часто на Stack Overflow и подобных площадках можно наткнуться на ответы, где такие функции реализованы ошибочно.

Какие есть оптимизации над строками в Go 

• Конвертация в цикле for-range не вызывает аллокаций.

  s := "GolangConf"
  for _, b := range []byte{s} { // 0 аллокаций
  	// ...
  } 

  Когда вы итерируетесь через for-range по строке, приводя её в []byte или в []rune, это не даёт аллокаций.

• При сравнении слайсов байтов, когда мы переводим их к строке.

  s1 := []byte{0: 65, 1024: 90}
  s2 := []byte{0: 65, 1024: 90}
  if string(s1) == string(s2) { // 0 аллокаций
  	// ...
  }

  Если вы хотите сравнить два []byte как строчки (напомню, что их нельзя сравнивать через == напрямую), то это тоже не даёт аллокаций. Вам в этом месте не нужен никакой Unsafe :)

• При поиске в map.

  var m map[string]any
  key := []byte{...}
  value := m[string(key)] // 0 аллокаций

  Интересно, что если ключом в map является строка, а на руках у нас []byte, то приведение слайса байт к строке при поиске ключа аллокаций не даст.

• При конкатенации.

  Есть огромный пласт оптимизаций при конкатенации. Например, у нас есть два слайса байт foo и bar. В строчке a мы их конкатенируем с непустой строкой, а в строчке b делаем то же самое, только строка пустая. 

  foo := []byte{100: 65}
  bar := []byte{100: 65}
  a := "_" + string(foo) + string(bar)
  b := "" + string(foo) + string(bar)

  Получается так, что при создании строки a будет всего одна аллокация, хотя для строки b — целых три.

  Чтобы понять, почему так, нужно снова посмотреть в ассемблер.

  

  Слева конкатенация с непустой строкой, справа с пустой. Конкатенация с непустой строкой — это по факту значит посчитать выровненный адрес всех наших аргументов и вызвать функцию из пакета в runtime. В случае конкатенации с пустой строкой нам нужно сначала foo и bar привести к строке, и уже потом вызвать ту же самую функцию.

  Суть в том, что Go, понимая, что у него уже есть какая-то исходная строка с ненулевой длиной, может на её основе сразу аллоцировать всю память, то есть ему не приходится аллоцировать сначала для foo, затем для bar и потом уже для всей строки.

  При этом, если мы зайдём в пакет, где реализована эта функция конкатенации, то нас встретит странная штука (на картинке ниже выделена красным блоком), которая означает, что всегда есть какой-то временный буфер размером 32 байта.

  

  Как мы можем это использовать? Конкатенируем строки чанками по 32 байта. Нам не надо экспериментировать с конкатенацией с пустой и непустой строкой. 

  

  Если мы запустим бенчмарк, то увидим, что конкатенация с помощью чанков по 32 байта также делает всего одну аллокацию для всей исходной строки.

  Если мы запустим бенчмарк, то увидим, что конкатенация с помощью чанков по 32 байта также делает всего одну аллокацию для всей исходной строки.

  BenchmarkSimpleConcat-8 14532418 72.20 ns/op 512 B/op 3 allocs/op

  BenchmarkChunkConcat-8 16568988 64.24 ns/op 256 B/op 1 allocs/op

  У этого знания есть ещё одно преимущество. Любые бенчмарки, которые вы пишете, обязаны использовать данные по объёму, приближённому к объёму данных, которые у вас будут на проде. Иначе вы можете не увидеть тех аллокаций, которые на самом деле есть.

  Единственная проблема этого хака в том, что применим он только в кодогенерации, потому что если вы напишете то же самое, но с циклом, это будет работать сильно хуже.

Сортировка слайса строк

Совсем недавно на GitHub появился тикет. Он говорит о том, что сейчас в Go sort.Strings, который напрямую работает со строками, действует на 30 % быстрее, чем дженерик-решение slices.Sort. Это вызвано тем, что sort.Strings делает всего одно сравнение вместо трёх. Сейчас в Go нельзя отсортировать оптимально список объектов по строковому полю.

Что получаем в сухом остатке

• Я рассказал, что такое small-size объекты и как они позволяют компилятору создавать более оптимальный код.

• Очень надеюсь, что убедил вас в том, что интерфейсы — зло. Если вы хотите выжать максимум, то про них нужно забыть.

• Я показал, насколько сильно простая проверка выхода за границы массива может влиять на производительность.

• Продемонстрировал, как сильно на производительность влияет тот или иной цикл и что работа со строками в Go хорошо оптимизирована.

Надеюсь, мой опыт поможет вам выжать из Go максимум — и сделать свой продукт ещё круче и быстрее.

В основе статьи — доклад на профессиональной конференции Saint HighLoad++. Здесь можно посмотреть запись выступления.