Мифы Go, в которые мы верим: емкость



Книга Мифы Go, в которые мы верим: емкость

Развеем популярный миф о языке 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
", 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;

  • количества добавляемых элементов.



44   0  

Comments

    Ничего не найдено.