Как Go выполняет встраивание06.09.2022 20:02

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

Что такое инлайнинг функций?  

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

Допустим, есть код, который мы хотим оптимизировать:  

func foo(a, b int) int {
  ret := 0;
  for i : = 0; i < 10; i++ {
    ret += a;
  }
  for j : = 0; j < 5; j++) {
    ret += b
  } 
  return ret
}

func bar() int{
  s = foo(4, 5);
}

func foobar() int{
  return bar()
}

Функции foo и bar вызывают друг друга, и это можно оптимизировать. После того как компилятор применяет оптимизацию, код может выглядеть так:

func foobar() int{
   ret := 0;
  for i := 0; i < 10; i++ {
    ret += 4
  }
  for j := 0; j < 5; j++ {
    ret += 5
  }
  return ret;
}

Теперь мы можем считать (с некоторой долей упрощения), что функций foo и bar нет в коде. Их инструкции и код физически скопированы в то место, где функции вызывались.

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

Мы, пока очень упрощённо, избавились от foo и bar: весь код вставили в месте вызова. Это и есть инлайнинг в общем виде.

Стратегии, главный плюс и пара минусов встраивания

Бывает две стратегии инлайнинга:

• на этапе компиляции — применяется в C, C++, Fortran, Rust, Zig, Go и других языках, которые используют LLVM-стек;

• в runtime — для платформ или движков JVM, V8, а теперь и Ruby с его JIT-компиляцией. Чтобы для них произвести инлайниг, сначала происходит JIT-компиляция, а вместо байт-кодов уже вставляется машинный код. Это тоже можно рассматривать как встраивание. 

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

Инлайнинг — это оптимизация. И как у любой оптимизации, у него есть обратная сторона. Посмотрим, какие плюсы и минусы есть у встраивания функций.

Главный плюс

На это и рассчитана оптимизация: чтобы программа работала быстрее. Но что это значит — быстрее?

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

// go:noinline
func foo (a, b int) int {
  ret := 0
  for i := 0; i < 10; i++ {
    ret += a
    ret *= b
  }
  return ret
}   

func bar(a, b int) int {
  ret := 0
  for i := 0; i < 10; i++ {
    ret += a
    ret *= b
  }
  return ret
}   

Есть две одинаковые функции foo и bar, но только одна из них помечена директивой go: noinline. Она говорит о том, что эта функция встроена не будет ни при каких обстоятельствах. 

Локальный бенчмарк для этого примера показал, что код с инлайнингом отработал в два раза быстрее, чем без.

goos: darwin
goarch: amb64
pkg: x
cpu: Intel(R) Core(TM) i5-1038NG7 CPU @ 2.00GHz

BenchmarkWithoutInlinig-8   215878278 55.426 ns/op
BenchmarkWithInlinig-8       551489780 2.274 ns/op

Уточним: пример синтетический, не всегда инлайнинг даёт ускорение в два раза.

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

А что значит «только её вызов»? Это несколько шагов — ведь чтобы вызвать функцию, нужно:

• выделить ей место на стеке;

• скопировать параметры;

• записать регистры;

• скопировать ответ;

• почистить за собой стек и регистры процессора.

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

Пара минусов

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

Возможно, для энтерпрайз-решений это не очень актуально. Подумаешь, бинарник будет весить на несколько килобайт больше. Его завернут в docker-контейнер, отправят в Kubernetes, в облако. 

Но вот во встраиваемых системах, IoT и мобильных приложениях размер исполняемого файла критически значим для системы. Если код должен исполняться на клиенте, то лишний вес файла может свести на нет профит от инлайнинга.

«Так, стоп», — скажете вы. Только что обсуждали, что встраивание ускоряет выполнение программы, и проверяли выигрыш на тесте. Откуда взялось замедление?

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

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

Только оперативная память медленная относительно скорости работы CPU.

L1 cache reference 			    0.5 ns
Branch mispredict				5   ns
L2 cache reference 			    7   ns
Mutex lock/unlock 				25  ns
Main memory reference 			100 ns

В таблице Latency numbers every programmer should know видим, что доступ к памяти занимает 100 ns. И при этом понимаем, что есть ближняя и дальняя память, так что до второй путь может быть ещё дольше. Поэтому и придумали всякие кеши (L1, L2, L3, даже L0), куда инструкции подгружаются пачками, чтобы быстрый CPU не ходил за ними в память.

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

Инлайнинг в Go: как реализуется 

В Go инлайнинг реализуется на этапе компиляции, и его идея максимально простая — основана на budget model, или cost-based model. Суть: у нас есть бюджет, равный 80, на встраивание одной функции. Считаем стоимость функции — если очень грубо, то это сумма всех инструкций, помноженных на какой-то вес. Если стоимость меньше или равна бюджету, мы можем встроить функцию. Если нет, то нет. 

На примере:

func bar(a, b int) int {
  ret := 0

  for i := 0; i < 10; i++ {
    ret += a
    ret *= b
  }
    return ret
} 

Вот функция bar, и мы идём по каждому узлу в AST-дереве и складываем в наш формальный «контейнер». 

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

Всё так просто?

Почти. Когда дело касается нелистовых функций, стратегии инлайнинга становятся сложнее. Посмотрим на код:

func func1() {
/*
some code
*/
func2()
}

func func2() {
/*
some code 
*/
}

Есть func1 с некоторым кодом, который точно будет встроен, и есть вызов функции func2. Сумма бюджетов этих функций входит в допустимый размер. Вопрос: встроим ли мы func1 в место её вызова?

Ответ: можем встроить по-разному, в зависимости от версии языка Go. Переломным моментом стал выпуск Go 1.12: с ним пришёл mid-stack inlining. Он нацелен на то, чтобы решить проблему встраивания нелистовых функций.

Mid-stack inlining

Компилятор Go ранее встраивал только листовые функции — то есть те, которые не содержали в себе вызов других функций. Начало этой оптимизации было положено в версии 1.9, о ней рассказывается в презентации Mid-stack inlining in the Go compiler (David Lazar). До версии 1.12 она была доступна только через флаг -gcflags = -l = 4.

Как влиять на встраивание функций в Go

Кто работает с C/C++, знает, что компилятор можно попросить заинлайнить функцию. А как в Go?  

Во-первых, директивы // go: inline не существует! Нельзя сказать «Go, пожалуйста, встрой мне эту функцию», как бывает в C++. Зато есть директива // go: noinline. Она как раз говорит компилятору не встраивать функцию.

Второе, что можно использовать, это один из двух флагов компилятора:

— -gcflags=-l (или -gcflags=-l=1)—отключить встраивание;

— -gcflags=-l=4 — уменьшить стоимость встраивания метода нелистовых функций.

Ещё есть -gcflags=-l=2 и -gcflags=-l=3, но они сейчас не используются, поэтому никакого эффекта на компилятор не окажут.

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

Что Go может инлайнить, а что нет 

Посмотрим, что может и не может заинлайнить Go сейчас и как это происходило раньше. Для этого разберём несколько тестов.

Сразу оговоримся, что Go 1 никогда не сможет заинлайнить:

Это классы функций, которым нужен полноценный указатель на стек. 

Смотрим на примере:

func main() {
  foo()
}

func foo() {
  /*
    some code
  */
  bar()
}

func bar() {
  /*
    some code 
  */
  runtime.Caller(1)
  /*
    some code 
  */
}

Есть main, который вызывает foo; foo вызывает bar; bar вызывает runtime.Caller. С его помощью можем узнать, кто нас вызвал. При этом как аргумент эта функция принимает количество данных со стека. Так что можем узнать не только родителя, который нас вызывал, но и имя его предка. Функция bar в этом случае должна иметь полноценный указатель на стек функции foo, а та — на стек функции main. 

А что Go уже может заинлайнить?

• panic;

• goto;

• atomic-операции;

• append;

• map access;

• замыкания (почти);

• type switch (такая штука, когда вы по интерфейсу можете получить исходный тип) — эта оптимизация доступна с версии 1.16;

• for-loop;

• код с mutex начиная с Go 1.13;

• sync.Once.

Как узнать, встроится функция или нет? Посмотрим на примере с type switch:

func foo(i interface{}) {
  switch i.(type) {
    case int64:
      print("float32”)
    case string:
      print("string”)
    default:
      print("unknown”)
  }
}

Есть флаг компилятора, который покажет, какие оптимизации были и как они отработали. 

Видим, что в версии 1.15 код, который производит инлайнинг, даже не знает узел type switch в AST-дереве. А в 1.16 уже знает и функция будет встроена: её стоимость равна 18 и 18 меньше, чем 80.

Go 1.16 может встраивать for. Но не любой. Например:

func foo() {
  for i := 0; i <= 10; i++ {
    print(i)
  }
}

func foo(arr []int) {
  for i := 0; i < len(arr); i++ {
    print(arr[i])
  }
}

func foo(arr []int) {
  for i := range arr {
    print(i)
  }
}

Go 1.13 и выше может встроить код с mutex. Это всё благодаря mid-stack inlining.

Если посмотрим на код из стандартной библиотеки, то увидим, что есть Fast path и Slow path. Причём быстрый путь состоит из вызова одной инструкции к процессору.

    // Lock locks m.
    // If the lock is already in use, the calling goroutine
    // blocks until the mutex is available.
    func (m *Mutex) Lock() {
    // Fast path: grab unlocked mutex.
     	if atomic.CompareAndSwapInt32(&m.state, 0, mutexLocked) {
     		if race.Enabled {
     			race.Acquire(unsafe.Pointer(m))
     		}
     		return
     	}
     	// Slow path (outlined so that the fast path can be inlined)
      	m.lockSlow()
     }

По такому же сценарию работает sync.Once. Там тоже есть быстрый путь, который представляет собой atomic-операцию (помним, что Go может встраивать atomic). И есть медленный.

      func (o *Once) Do(f func()) {
     	// Note: Here is an incorrect implementation of Do:
     	//
      	//	if atomic.CompareAndSwapUint32(&o.done, 0, 1) {
      	//		f()
      	//	}
      	//
      	// Do guarantees that when it returns, f has finished.
      	// This implementation would not implement that guarantee:
      	// given two simultaneous calls, the winner of the cas would
      	// call f, and the second would return immediately, without
      	// waiting for the first's call to f to complete.
      	// This is why the slow path falls back to a mutex, and why
      	// the atomic.StoreUint32 must be delayed until after f returns.
      
      	if atomic.LoadUint32(&o.done) == 0 {
      		// Outlined slow-path to allow inlining of the fast-path.
      		o.doSlow(f)

Общая идея оптимизации — разделять быстрые и медленные участки кода на разные функции. Это называется Function outlining и используется в мьютексах, в sync.Once, криптографии и ещё много где. Такой оптимизацией можем обмануть Go и заставить его инлайнить там, где формально он бы этого не делал. Можно использовать для оптимизаций не только встраивания, но и работы с памятью. 

При написании кода надо подумать, какая часть функции будет вызываться чаще, какая быстрее или медленнее. Отталкиваясь от этого, решить, использовать ли Function outlining.

Как это всё применять на практике

Так что, нужно иметь под рукой табличку «Что Go может встроить, а что нет» и постоянно с ней сверяться? Нет, есть способы поудобнее. 

1. Флаги к компилятору — уже упоминали их выше. Работает, но не совсем удобно, если у вас большой код или функция.

По Command+Shift+P или Ctrl+Shift+P в VSCode можно вызвать контекстное меню и выбрать action Go: Toggle gc details. Он при наведении на функцию покажет, будет ли она встроена, а если нет, то почему.

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

Бонус: несколько находок про инлайнинг

• В Go функции при инлайнинге не совсем равноправны. Компилятор разделяет функции на большие и маленькие. Большие — это те, в которых больше 5 000 узлов (узел — это часть AST-дерева). Инлайнинг в большую функцию стоит намного дороже, и бюджет на встраивание уменьшается с 80 до 20. Это категорическое снижение бюджета напоминает о том, что в Go хорошо писать небольшие функции. Не только чтобы было проще покрывать их тестами, делать код читаемым и поддерживаемым, но и чтобы Go мог эффективнее производить оптимизации. 

• Go может встроить замыкание, которое вы вернули из функции. На встраивание функции с замыканием влияет и сам факт замыкания, и то, насколько «дорогой» код внутри него. Стоимость одной функции, которую возвращает другая, влияет на общую стоимость.

• Константы не влияют на инлайнинг и на бюджет встраивания. На то они и константы.

• Любой вызов метода, который не может быть встроен, сжирает больше половины бюджета на инлайнинг. Обойти это можно флагом -gcflags=»-l=4». Но надеюсь, что это будет влито в upstream и станет работать под флагом по умолчанию.

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

В Go инлайнинг стремительно эволюционировал. Раньше мы даже не ожидали, что нелистовые функции могут быть встроены. А сейчас видим, что Go сможет встроить и циклы, и type switch, и atomic. 

Вместо вывода — три простых совета для работы с инлайнингом:

• Обновляйтесь до последней версии Go и не бойтесь проблем с совместимостью. Конечно, если вы пишете на этом языке давно, то помните, что в версии 1.14 сломалась работа с шаблонами. Но в целом сейчас можно ожидать, что ничего не повредится. Обновление будет простым и поможет программам работать быстрее — за счёт того, что Go заинлайнит новые фишки.

• Помните про Fast path и Slow path в Function outlining — потому что он влияет не только на инлайнинг, но и на то, чтобы обходить escape-анализ.

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

Эта статья написана по мотивам моего выступления на GolangConf в рамках HighLoad++ Foundation. Можно посмотреть видео, если это удобнее, или послушать Q&A сессией после доклада.

© Habrahabr.ru