Развеем популярный миф о языке Go: после добавления емкость среза удваивается.
Проведя более 500 собеседований, я теперь часто шучу: «Джуны утверждают, что емкость срезов просто удваивается, мидлы — что удваивается, но по достижении некоторой длины поведение меняется…, сеньоры — что удваивается, но по достижении некоторой длины…, но после того как изменилась специальная формула высвобождения… Все эти объяснения допустимы как ответы, только все это ложь».
Рассмотрим код:
func main() {
slice := make([]int, 17, 17)
slice = append(slice, 0)
fmt.Printf("len=%d, cap=%d", len(slice), cap(slice))
}
Вывод: длина len = 18, емкость cap = 36.
Если создать срез длиной и емкостью 17, а затем добавить к нему, получится срез емкостью 36. Но 17 * 2 = 34. И 17 меньше, чем 256 — пороговое значение функции growslice в версии 1.21.
Копнем глубже и создадим функцию, которою указывается, сколько раз емкость удваивается, а сколько раз нет:
func main() {
x2Counter := 0
for i := 0; i < 1000; i++ {
slice := make([]int, i, i)
slice = append(slice, 0)
if cap(slice) == i*2 {
x2Counter++
}
}
fmt.Println(x2Counter)
}
Вывод: 44.
Емкость среза удваивается только в 44 случаях из 1000. Интересно, что мифический «порог» не всегда функционирует так, как от него ожидается:
func main() {
slice := make([]int, 336, 336)
slice = append(slice, 0)
fmt.Printf("len=%d, cap=%d", len(slice), cap(slice))
}
Вывод: длина len = 337, емкость cap = 672.
Действительно, 336 * 2 = 672. Однако пороговое значение 256 превышено, результат «должен быть» ниже. Приведем еще несколько интересных примеров, а затем разберемся в базовой механике.
Почему она кажется такой запутанной и недоступной для понимания и почему всегда по умолчанию используется int64?
Поэкспериментируем с чем-нибудь другим:
func main() {
x2Counter := 0
for i := 0; i < 1000; i++ {
slice := make([]int8, i, i)
slice = append(slice, 0)
if cap(slice) == i*2 {
x2Counter++
}
}
fmt.Println(x2Counter)
}
Вывод: 28.
Все дело в типе данных. Изучим подробнее вот что:
func main() {
x2Counter := 0
for i := 0; i < 1000; i++ {
slice := make([]struct{}, i, i)
slice = append(slice, struct{}{})
if cap(slice) == i*2 {
x2Counter++
}
}
fmt.Println(x2Counter)
}
Вывод: 1.
На какой итерации получен этот результат, спросите вы? На второй, где емкость и длина равны 1:
func main() {
for i := 0; i < 10; i++ {
slice := make([]struct{}, i, i)
slice = append(slice, struct{}{})
fmt.Printf("slice: len=%d, cap=%d\n", len(slice), cap(slice))
}
}
Вывод:
slice: len=1, cap=1
slice: len=2, cap=2
slice: len=3, cap=3
…
Каждый раз емкости добавляется единица.
Емкость удваивается не всегда, а только в определенных случаях. Теперь доказательств этого достаточно. Каков же принцип работы?
Присмотримся к функции growslice. Ею вычисляется новая емкость среза.
В первой части функции наблюдается поведение увеличения емкости «по умолчанию»: если емкость ниже порогового значения, текущая емкость удвоится.
В противном случае имеется формула плавного роста:
newcap += (newcap + 3*threshold) / 4
Но самый интересный — исходя из размеров элементов среза — сегмент находится ниже, в операторе switch. Здесь переменной capmem показывается объем памяти, необходимый для размещения новой емкости элементов в срезе.
Тут-то и начинается сложность. Нельзя просто выделить произвольный объем памяти — malloc так не работает. Память выделяется исходя из конкретных классов размеров. Кстати, этот код генерируется отсюда.
В команде Go, чтобы оптимизировать использование памяти, выделенный для новой емкости объем памяти привели в соответствие с этими классами размеров.
Если попросить malloc выделить память для 34 элементов по 8 байт каждый, будет выделено 288 байт. То есть 36 * 8, так как вычисляемый результат зависит от конкретного класса размеров. Вот базовая логика.
В зависимости от необходимого для выделения объема памяти, объем сопоставляется с одним из классов размеров, а затем класс размеров сопоставляется с фактическим объемом памяти.
В этом конкретном случае выделенной памяти достаточно для хранения двух дополнительных элементов. Зачем же их терять? Просто добавим их в срез. Эти вычисления направлены на приведение емкости в соответствие с объемом памяти, выделяемым в malloc.
Формулы и методы вычислений для разных типов различаются: имеются равные размеру указателя — в зависимости от архитектуры, имеются размером 1 байт, имеются размером степени двух и другие. Но концепция во всех этих случаях остается той же: вычисляется минимальный объем требуемой памяти и приводится в ближайшее соответствие с результатами работы malloc.
А как насчет пустых структур? Размер пустой структуры равен 0, для нее имеется особый случай.
Срезы для пустых структур, которые в них содержатся, служат счетчиками. Для «данных» в таких срезах выделять память нет необходимости. Следовательно, концепция емкости неприменима: эта емкость всегда равна текущей длине среза.
И в завершение упомянем о работе функции append при добавлении нескольких элементов:
doublecap := newcap + newcap
if newLen > doublecap {
newcap = newLen
}
Рассмотренные выше правила применимы и для этого случая:
func main() {
slice := make([]int, 3, 3)
slice = append(slice, 1, 2, 3, 4, 5)
fmt.Println(cap(slice))
}
Вывод: 8.
Заключение
Теперь мы знаем правильный ответ на вопрос: «Как растет емкость среза?» Осуществляется лишь попытка удвоить емкость среза, но реальность сложнее.
Расчет основан на множестве факторов, не только на достижении порогового значения. Он зависит от:
- типа элемента и размера;
- архитектуры, разрядности, то есть размера указателя;
- текущих длины и емкости среза;
- размера среза, части roundupsize;
- текущей реализации malloc;
- количества добавляемых элементов.
Читайте также:
- Производительность Redis и атомарность в Golang. Возможности конвейеров, транзакций и Lua-скриптов
- Самые полезные библиотеки Go
- Простое объяснение интерфейсов на Golang
Читайте нас в Telegram, VK и Дзен
Перевод статьи Herman Samolazov: GO Myths we believe: Capacity
