Привет, Хабр! Меня зовут Владислав Белогрудов, я работаю в команде разработки интерфейсов и сервисов управления в YADRO. Мой текущий проект — информационная система на Go. 

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

Под катом рассмотрим, что такое слайсы и string (строки) изнутри, как использовать их с sync.Pool для ускорения — без «внутренностей» последнего, но с точки зрения клиента. Расскажу о полезных трюках, приведу значения измерений производительности и познакомлю с альтернативными решениями. 

Что такое слайс

Слайс — динамический массив, состоящий из трех элементов:  указателя на память под элементы массива, длины, которая показывает, сколько ячеек массива заполнено и capacity. Capacity (вместимость) сообщает, сколько всего мы можем поместить элементов в этот слайс без выделения новой памяти.

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

type slice struct {
  array unsafe.Pointer 
  len	int
  cap	int
}

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

Посмотрим, как происходит наполнение слайса. 

// var myslice []int

array=nil

len=0

cap=0

Как только мы начнем добавлять туда числа, массив будет заполняться, аллоцируя новые и все большие участки памяти под элементы. Первая аллокация — под один элемент

myslice = append(myslice, 11)

array -> [11]

len=1

cap=1

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

myslice = append(myslice, 22)

array -> [11, 22]

len=2

cap=2

Добавляем третий элемент, происходит аллоцирование нового массива — и остается свободная ячейка.

myslice = append(myslice, 33)

array -> [11, 22, 33, _ ]

len=3

cap=4

Это наводит на мысль, что на малых количествах таких «добавок» слайсы работают не очень эффективно, потому что приходится постоянно выделять новые участки памяти и копировать в них элементы из старых участков. Но чем дальше двигаемся, тем меньше копирования и тем лучше работает структура. Далее я подробно расскажу, как растет вместимость массива. 

Как растет capacity

И во сколько раз Go увеличивает наш внутренний массив элементов? Чтобы это выяснить, я провел небольшой тест: добавлял один элемент к уже заполненным слайсам.

На графике видно, что в районе 200 элементов увеличенный слайс вмещает уже 400 элементов, а в районе 800 — 1200, то есть вместимость выросла сначала в два раза, потом — в полтора. 

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

 Существует забавная константа для вычисления вместимости: три четвертых от 256. Разработчики на Go посчитали, что так происходит более плавный переход от фактора 2x к фактору 1.25.

На самом деле на этом графике я ожидал увидеть красивую кривую, а получил какие-то странные ступеньки. Поэтому я провел еще один эксперимент и просто посмотрел, как как фактор зависит от capacity (максимальной длины старого массива). 

На этом графике видим что-то странное: в начале фактор был больше двойки и постоянно скакал. Это меня немножко удивило. Дальше фактор снижается в 1,5, и в теории он должен когда-то превратиться в 1.25. Но все равно что-то здесь не так.

Я продолжил эксперименты. Создал слайс, заполненный на 17 элементов, добавил один дополнительный. Я думал, что в конце получу слайс на 34 элемента, но вместимость показала 36. 

a := make([]int, 17) 
a = append(a, 1)
fmt.Println(len(a), cap(a))   // 18, 36

b := make([]int, 18)
b = append(b, 1)
fmt.Println(len(b), cap(b))  // 19, 36

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

Еще отмечу, что все объекты одного класса хранятся на одной странице памяти. Видимо, так сделано, чтобы уменьшить фрагментацию памяти и упростить менеджмент. Здесь Go оптимизирует по максимуму, даже если получается какое-то округление и неиспользуемые участки памяти внутри.

Давайте теперь рассмотрим конкатенацию слайсов:

a :=make([]int, 17)
b :=make([]int, 5)

// new len > 2 * old cap
c = append(b, a...)
fmt.Println(len(c), cap(c))   // 22, 22

// new len < 2 * old cap
c := append(a, b...)
fmt.Println(len(c), cap(c))   // 22, 36

При добавлении одного слайса в другой может оказаться, что в первом слайсе нет места для добавления — соответственно, его нужно увеличивать. Обычно рантайм Go увеличивает слайс в два раза. Как увеличиваем слайс:

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

• Если слайс был больше, чем тот, который добавляем, то увеличиваем первый в два раза и добавляем второй.

Способы создания слайса

Слайс можно создавать несколькими способами:

1. Объявляем слайс как переменную (var slice []int) или при объявлении присваиваем переменной пустой слайс (slice := []int{}).

2. Выделяем нужное количество ячеек для слайса и обнуляем их (slice := make([]int, 8).

3. Выделяем количество ячеек, но не инициализируем их. При этом длина слайса нулевая, в то же время нужное количество ячеек зарезервировано (slice := make([]int, 0, 8).

Если добавлять к слайсу элементы, то в первом случае придется часто увеличивать слайс, потому что начинаем мы с нулевого размера, а затем будут размеры 1, 2, 4 и так далее. Во втором и третьем случаях есть подготовленные ячейки для заполнения.

Какой способ быстрее? Не будем долго думать — просто измерим. Первый — самый тормозной, там куча аллокаций и копирования. А через make (второй и третий способы) все работает неоднозначно: зависит от того, какой у вас слайс — большой или маленький. Ориентируемся на контекст и на то, как сделать код более читаемым.

Как передавать слайсы в функции

Еще один важный аспект в работе со слайсами — это передача их в функции. Это можно сделать двумя способами: 

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

2. По указателю — передается адрес оригинального слайса. 

   

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

Если мы попытаемся добавить новые элементы внутри функции, то мы не увидим эти изменения снаружи, так как не изменится length и capacity снаружи. 

Передача по указателю на микросекунды быстрее, потому что передается 8 байт вместо 24. Вот еще несколько способов ускорить слайсы:

• Добавить каписити, если знаем порядок слайсов.

• Использовать функцию container/list для быстрых вставок и удалений.

• Использовать *element, если элементы большие и вам требуется много манипуляций со структурой: вставок, удалений, добавлений.

• Подключить sync.Pool — о нем мы еще поговорим.

• Удалить лишний код.

В следующем блоке расскажу о строках и о том, как с ними работать.

String

String — структура, похожая на слайс. Главное отличие string от слайса — структура работает только для чтения: когда создаем string, не можем ничего изменить внутри. Функции len() и cap() означают одно и то же.

В структуре string внутренний массив байтов является utf8-последовательностью. И для нее функция len() возвращает количество байт, а не символов. Соответственно, чтобы найти количество символов, нужно декодировать строку с помощью библиотеки unicode/utf8. 

Конвертация в байты и обратно

Самая частая операция со string — конвертация в слайс байтов и обратно. Даже если мы напрямую не делаем это в коде, этим занимается одна из наших библиотек. Надо сказать, что мы не можем взять память под байты из слайса и сказать стрингу: «Используй эту память». Нужно делать копию, потому что мы хотим обезопасить себя от модификации нашей строчки.

Но некоторые все равно не хотят так делать и занимаются хакерством. Через unsafe.Pointer все-таки подсовывают память из слайса в стринг. В Kubernetes даже есть такой код, но лучше им не пользоваться. Если компилятор видит, что можно такие преобразования делать с экономией памяти, он сделает это за нас.

str := "hello"
...
key = []byte{0x41, 0x42}
if str < string(key) {
...
}

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

Стандартная конкатенация 

Давайте посмотрим, как складываются строчки. 

  var words = []string{
    "hello", "double", "bye", "triple"}

  var sum string
  for i := range words {
    sum += words[i]
  }
  
  sum = words[0] + words[1] + words[2] + words[3]

  sum = strings.Join(words, "") // clever?!

• Первый способ, который приходит в голову — через for loop. Но, к сожалению, самый медленный, потому что здесь каждый раз создается новая строка, чтобы вместить предыдущие две.

• Второй способ — это просто написать все через плюсики (строка + строка). Кажется, самый банальный путь, которому не стоит следовать, потому что мы все-таки программисты.

• Третий путь — тоже простенький. Кто-то вспомнит библиотеку strings. Там есть хорошая функция Join(), которой можно задать сепаратор, и тоже сконцентрировать все в суммарную строчку.

Если заглянем в код парсера компилятора Go, то увидим, что парсер на лету заменяет код. Если он видит меньше 5 строчек, он заменяет на соответствующую функцию concatstring2, 3, 4, 5, если больше — превращает все складываемые строчки в слайс строк. Подытожу: с плюсиком складывать строки в Go просто очень-очень эффективно, даже если у вас 100 или 1000 строк. Но есть ли другие рабочие способы? Давайте поищем.

func concatstrings(buf *tmpBuf, a []string) string ..

func concatstring2(buf *tmpBuf, a0, a1 string) string { return concatstrings(buf, []string{a0, a1})
}
func concatstring3(... func concatstring4(... func concatstring5(...

Конкатенация через bytes.Buffer

Bytes.Buffer — структура для работы со слайсами и строчками, в нее можно добавлять многократно и то и другое, а также можно считывать обратно в виде слайса байтов или строки. Внутри здесь есть слайс байт, который мы наполняем или, наоборот, опустошаем. Буфер растет динамически, когда мы туда что-то добавляем. Есть и аллокации, и копирование, как у обычных слайсов. А еще — оптимизация. Например, пустой слайс сразу стартует с 64 байт, а буфер сам следит за своим ростом. Рост составляет ровно 2х — нет такого, что мы внезапно переходим к фактору 1.25. 

Как им пользоваться? Достаточно просто. 

func ConcatBuffer(words []string) string {

  b := bytes.Buffer{}

  for i := range words {
    b.WriteString(words[i])
  }
  return b.String()
}

Мы создаем пустой буфер. Через WriteString() складываем строчки в этот буфер, а через метод String() возвращаем уже итоговую строку. И здесь, в методе String(), у нас как раз происходит копирование байтов, накопленных в буфере, — в string. Помним, что string — неизменяемая вещь, и нам нужна копия, потому что буфер может меняться внутри как угодно.

Конкатенация через strings.Builder

Очень похожее решение — это структура strings.Builder. Даже внутри одной программы, в разных модулях, инженеры используют и strings.Builder, и bytes.Buffer.  

Тем не менее, в документации говорится, что strings.Builder более эффективен для складывания строчек. Сигнатуры те же самые, те же методы. Используются те же методы: аккумулируем с помощью WriteString() и достаем результат с помощью String().

bytes.Buffer при получении из него строчки копирует содержимое внутреннего слайса байт в строку, а strings.Builder просто и безопасно возвращает нам в качестве строки накопленные байты. При этом используется преобразование с unsafe.Ptr,  записанные в strings.Builder байты никто не поменяет и наша строчка в безопасности.

Сравнение решений

• И в bytes.Buffer, и в strings.Builder под капотом лежат слайсы байт.

• Bytes.Buffer растет быстрее, потому что делает меньше аллокаций, фактор всегда 2х.

• Bytes.Buffer работает быстрее на небольших строчках (до 64 байт).

• Strings.Builder эффективнее дает результирующую строчку, потому что нет лишнего копирования байт в конце.

Добавлю, что еще есть builder.Reset() и buffer.Reset(). Оба обнуляют внутренние слайсы, но builder.Reset() не сохраняет внутренний слайс, а устанавливает его в nil. А bytes.Buffer говорит, что у нас теперь нулевая длина, но выделенный буфер остается.

Strings.Builder никогда не используют с sync.Pool, потому что он не дает никаких преимуществ, когда его ресетишь.

sync.Pool

Чтобы ускорить операции, о которых мы говорим в этой статье, предлагаю использовать sync.Pool, который хранит участки памяти и оптимизирует работу с ней. Мы можем «попросить» у sync.Pool новый объект из хипа и без проблем его получить. После завершения работы с объектом вернем его в sync.Pool, и программа обозначит его как «грязный» или выделенный. Выделенные объекты можно переиспользовать, пока их не утилизирует Garbage Collector. 

Хотите узнать, как уменьшить влияние GC на выполнение программы? Прочитайте статью Александра Иванова, Go-разработчика в YADRO. Александр протестировал три реализации memory pool и решил проблему с пиковыми нагрузками.

Что можно ускорить? 

• Первым делом мы создаем pool и обозначаем, какие объекты он будет отдавать. В данном случае мы говорим о bytes.Buffer, потому что он может вырасти, выделится память из кучи. Если мы объект возвратим в pool и заберем снова, в нем все еще будет выделенная память, в данном случае слайс байт с хорошим capacity.

var pool = sync.Pool{
  New: func() any {
    return &bytes.Buffer{}
  },
}

• Через метод Get() получаем этот буфер. Так как он возвращает any, мы его преобразуем уже в нужный тип.

func ConcatPool(words []string) string {

// достаем объект, новый или переиспользуемый b := pool.Get().(*bytes.Buffer)

// не забываем положить обратно после defer pool.Put(b)

// на всякий случай чистим (если переиспользуемый) b.Reset()
...

Важно сделать defer pool.Put(b), чтобы отдать этот буфер. Иначе получится, что мы из pool забираем какие-то объекты, никуда не кладем после использования — будет утечка памяти.

• Если нам попадется заполненный буфер, то нужно сделать его Reset(), чтобы почистить. Понятное дело, здесь как раз Builder не годится — только буфер, потому что у него сохраняется внутренний слайс байт. И, как обычно, просто добавляем слова в этот объект через WriteString().

func ConcatPool(words []string) string {
  ...

  // кладем слова в буфер
  for i := range words {
    b.WriteString(words[i])
  }
  //создаем результирующую строчку return b.String()
}

Правила хорошего тона для пользователей sync.Pool:

• Очищайте объект из пула.

• Не забывайте отдавать память в пул.

• Не используйте память после отдачи.

Давайте теперь померяем производительность всех рассмотренных решений, насколько все это быстрее или нет. 

В данном случае (результат 1) я взял 8 слов, сделал так, чтобы в сумме они давали 65 байт, и попробовал прогнать тесты. Самый плохой способ был через for loop. Builder сработал быстрее, потому что было меньше аллокаций.

Почему в bytes.Buffer всего три аллокации?

Во-первых, потому что сразу выделилось 64 байта в новом объекте. Потом выросли до 65 байт для суммы байт слов. И потом мы выделили такую же память под новую строчку. Получилось три аллокации. Тем не менее, все равно работает гораздо медленнее, чем sync.Pool или bytes.Buffer с изначально выделенным большим внутренним слайсом (последний позволяет это делать через свой «конструктор»).  strings.Join() тоже быстрее. И самое быстрое – это обычное сложение строк.

Если немного увеличим (результат 2) наши строчки, получатся целые файлики, которые мы конкатенируем. Buffer и Builder работают достаточно медлено потому что все-таки они начинают с нулевого или 64-байтного внутреннего слайса. Даже если начнем с 64 байт, все равно получаются реаллокации, копирования из меньшего в большее. И поэтому здесь, конечно, sync.Pool, strings.Join() и сложение строк в большом выигрыше.  В данном случае большие строчки лучше не соединять через Builder или Buffer.

Но если взять много маленьких слов (Результат 3), в данном случае 800, то мы увидим, что любой динамический массив начинает хорошо работать. Все меньше и меньше аллокаций и копирования. Поэтому три верхних строчки бенчмарка мало чем друг от друга отличаются. strings.Join() и sync.Pool не стали работать быстрее. Но если экстремально поднять количестко слов, с 800 до 8000, то мы увидим, что практически все решения находятся в одном диапазоне.

Если заинтересовала тема слайсов и стрингов, советую почитать и посмотреть это:

• Запись выступления о слайсах на конференции GoFunc.

• Статья про слайсы в официальном блоге Go.

• Книга «Язык программирования Go», Алан А. А. Донован, Брайан У. Керниган.

• Видео Николая Тузова