Немного байт здесь, немного там — и вот вы уже говорите о том, как в действительности устроена память

Мой новый пост был навеян последним квизом по го. Обратите внимание на бенчмарк [1]:

func BenchmarkSortStrings(b *testing.B) {
        s := []string{"heart", "lungs", "brain", "kidneys", "pancreas"}
        b.ReportAllocs()
        for i := 0; i < b.N; i++ {
                sort.Strings(s)
        }
}

Будучи удобной обёрткой вокруг sort.Sort(sort.StringSlice(s)), sort.Strings изменяет переданные ей данные, сортируя их, так что далеко не каждый (по-крайней мере, как минимум, 43% подписчиков из twitter) мог бы предположить, что это приведёт к аллокациям [выделениям памяти на куче]. Однако, по-крайней мере в последних версиях Go это так и каждая итерация этого бенчмарка вызовет одну аллокацию. Но почему?

Как многие разработчики на Go должны знать, интерфейсы реализованы в виде структуры из двух (машинных) слов. Каждое значение интерфейса содержит два поля: одно содержит тип хранимого интерфейсом значения, а второе — указатель на это значение. [2]

В псевдокоде это бы выглядело вот так:

type interface struct {
        // порядковый номер типа значения, присвоенного интерфейсу
        type uintptr

        // (обычно) указатель на значение, присвоенное интерфейсу
        data uintptr
}

Поле interface.data может содержать одно машинное слово, чаще всего оно занимает 8 байт. Но, к примеру, слайс []string займёт уже 24 байта: одно слово на указатель на массив, лежащий внутри слайса; одно слово на длину; и одно слово на оставшуюся вместимость массива (capacity). Но как Go должен втиснуть эти 24 байта в необходимые 8? Используя очень старый трюк, а именно косвенную адресацию. Да, слайс []string занимает 24 байта, но вот указатель на слайс *[]string — уже опять 8.

Выделение [Escaping] на куче

Чтобы сделать пример чуть более явным, давайте перепишем его без хелпера sort.Strings:

func BenchmarkSortStrings(b *testing.B) {
        s := []string{"heart", "lungs", "brain", "kidneys", "pancreas"}
        b.ReportAllocs()
        for i := 0; i < b.N; i++ {
                var ss sort.StringSlice = s
                var si sort.Interface = ss // allocation
                sort.Sort(si)
        }
}

Чтобы заставить магию интерфейсов работать, компилятор перепишет присваивание var si sort.Interface = ss, как var si sort.Interface = &ss, используя адрес переменной ss [3]. Теперь Мы оказались в ситуации, когда интерфейс содержит указатель на ss, но куда он будет указывать? В каком участке памяти будет расположена ss?

Похоже, что ss будет перемещена в кучу [heap], что и отображается как аллокация при бенчмарке.

  Total:    296.01MB   296.01MB (flat, cum) 99.66%
      8            .          .           func BenchmarkSortStrings(b *testing.B) { 
      9            .          .             s := []string{"heart", "lungs", "brain", "kidneys", "pancreas"} 
     10            .          .             b.ReportAllocs() 
     11            .          .             for i := 0; i < b.N; i++ { 
     12            .          .                 var ss sort.StringSlice = s 
     13     296.01MB   296.01MB                 var si sort.Interface = ss // allocation 
     14            .          .                 sort.Sort(si) 
     15            .          .             } 
     16            .          .           } 

Аллокация происходит потому, что компилятор не может быть уверен, что что ss переживет si (кстати, есть мнение, что компилятор можно было бы и улучшить, но об этом мы поговорим как-нибудь в другой раз). Так, ss будет выделена в куче. Таким образом, возникает вопрос: сколько байтов будет выделяться на итерацию? Что же, давайте проверим.

% go test -bench=. sort_test.go
goos: darwin
goarch: amd64
cpu: Intel(R) Core(TM) i7-5650U CPU @ 2.20GHz
BenchmarkSortStrings-4          12591951                91.36 ns/op           24 B/op          1 allocs/op
PASS
ok      command-line-arguments  1.260s

При использовании Go 1.16beta1, на amd64, при каждой операции будет выделяться 24 байта[4].

Но при этом на прошлой версии Go при каждой операции будет выделяться уже 32 байта.

% go1.15 test -bench=. sort_test.go
goos: darwin
goarch: amd64
BenchmarkSortStrings-4          11453016                96.4 ns/op            32 B/op          1 allocs/op
PASS
ok      command-line-arguments  1.225s

И это приводит нас к основной теме текущей статьи поста: улучшениям в новой версии Go. Но перед тем, как обсудить это, давайте поговорим о классах размеров [size classes].

Классы размеров

Чтобы объяснить, что это такое, рассмотрим, как теоретическая среда выполнения [рантайм] Go могла бы выделить 24 байта в своей куче. Самый простой способ так сделать — это отслеживать всю выделенную на данный момент память, используя указатель на последний выделенный байт в куче. К примеру, чтобы выделить 24 байта, мы бы увеличили указатель кучи на 24, а предыдущее значение вернули вызывающей стороне. Пока код, запросивший эти 24 байта, не выйдет за пределы указателя, этот механизм не имеет накладных расходов. К сожалению, в реальной жизни аллокаторы не только выделяют память, иногда им нужно ее освобождать.

Так, в конце концов среда выполнения Go должна будет освободить эти 24 байта, но с точки зрения среды выполнения единственное, что она знает — это начальный адрес, который она дала вызывающей стороне. Она не знает, сколько байтов было выделено после этого адреса. Чтобы сделать возможным освобождение памяти, наш гипотетический аллокатор должен будет записывать для каждой аллокации в куче её размер. Где же будут располагаться эти размеры? Конечно, на куче.

В нашем случае, когда среда выполнения хочет выделить память, она может запросить чуть больше, чем необходимо и использовать этот "излишек", чтобы записать туда размер выделенной памяти. Для нашего слайса, когда мы захотели выделить 24 байта, реально выделилось бы несколько больше. Но насколько больше? Оказывается, как минимум — одно машинное слово [5].

Для выделения 24 байт, мы бы реально выделили на 8 байт больше, чем хотели. 25% "излишней" памяти — не очень здорово, но и не очень плохо и чем больше памяти мы будем выделять, тем меньше нас будут волновать эти излишки. Но что есть мы захотим выделить в куче все лишь один байт? Получается, что мы выделим под хранение в 9 раз больше памяти, чем нужно! Можно ли это как-то оптимизировать?

Как вариант, вместо хранения длины каждой аллокации, мы могли бы хранить вместе объекты одного размера. Если все 24-байтовые объекты будут храниться вместе, то рантайм мог бы автоматически знать, какой размер занимает каждый из них, где он начинается и где заканчивается. Всё, что понадобилось бы такому рантайму — это один бит для того, чтобы разметить, занята ли кем-то конкретная 24-байтовая область или ещё нет. В Go такие области называются классами размеров, потому что все объекты одного размера хранятся вместе (класс здесь значит, что как в школе, все ученики одного возраста учатся в одном классе, не путайте с классами из C++). Когда же рантайм будет должен выделить память под объект меньшего размера, он будет использовать самый меньший класс размера из подходящих.

Классы размеров для всех, даром и без ограничений

Теперь мы знаем, как такие классы работают и можно дать ответ на очевидный вопрос: где будет выделяться память под них? Ответ вас не удивит: на куче. Для минимизации расходов, рантайм будет сначала выделяет побольше памяти (обычно, несколько страниц памяти из системы), а потом использует её для размещения на ней множества объектов одного размера. Но здесь есть проблема.

Такой способ выделения памяти работал бы хорошо [6], если бы количество видов объектов (а точнее их размеров) было сильно ограничено. Конечно, как правило это не так и программы используют объекты всевозможных размеров[7].

К примеру, представьте, что вы хотите выделить 9 байт. Это нетипичный размер, значит, вероятно, потребуется дополнительный класс размера для 9-байтовых объектов. Так как такие объекты будут использоваться (вероятно) не особо часто, скорее всего большая часть выделенной под этот класс размера области так и не будет использована, а это как минимум 4Кб. Поэтому, набор классов размеров граничен и если не существует идеально подходящего класса под наш объект — мы округлим необходимую память вверх до ближайшего возможного класса. В нашем случае 9 байт были бы выделены в 12 байтовом классе. Пожалуй, 3 неиспользуемых байта на объект — это лучше, чем целый класс размера, оставшийся практически не востребованным.

А теперь все вместе

Вот и финальный кусочек пазла. Go 1.15 не имеет 24 байтовых классов размеров, так что для переменной ss будет выделено 32 байта от минимально возможного класса размеров. Но благодаря Martin Möhrmann в Go 1.16 теперь есть 24 байтовый класс размера, так что память под использованием слайсов в интерфейсах будет выделяться эффективнее.

[1] Это неправильный способ тестирования функции сортировки, потому что после первой итерации входные данные уже будут отсортированы. Но в данном контексте это не важно.
[2] Точность этого утверждения зависит от используемой версии Go. Например, в Go 1.15 была добавлена возможность хранить некоторые целые числа непосредственно в значении интерфейса. Однако для большинства не-указателей, в качестве значения будет использован адрес переменной.
[3] Компилятор запомнит, что тип значения интерфейса здесь sort.StringSlice, а не *sort.StringSlice.
[4] На 32битных платформах оно займёт в два раза меньше памяти, но не будем оглядываться на прошлое.
[5] Если бы вы были готовы не выделять больше 4G (или, может быть, 64 Кб), вы могли бы использовать меньший объем памяти для хранения размера выделяемой памяти, но это означало бы проблемы с выравниванием [aligment] и необходимостью сдвига [padding] (почитать об этом можно, например, здесь — прим. переводчика).
[6] Хранение объектов одного размера рядом — это ещё и эффективный способ борьбы с фрагментацией памяти.
[7] Это не надуманный сценарий, те же строки бывают разных форм и размеров, и создать строку нового уникального размера можно просто добавив пробел в любую из них.