Как работает под капотом Capacity Array?

Как работает Capacity (ёмкость) массива в Swift

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

Основной принцип работы

Когда вы создаёте массив, система выделяет определённый объём памяти под его элементы. Ёмкость (capacity) — это количество элементов, которое массив может хранить без перераспределения памяти. Количество элементов (count) — это фактическое число элементов в массиве на данный момент.

var numbers = [1, 2, 3, 4]
print(numbers.count)      // 4 (фактические элементы)
print(numbers.capacity)   // Например, 4 или больше (зависит от реализации)

Стратегия роста (Geometric Growth)

Когда вы добавляете элементы (append) и count достигает capacity, массив должен увеличить свой размер. Вместо увеличения ровно на один элемент (что привело бы к реаллокации при каждом добавлении), Swift применяет стратегию геометрического роста (умножения):

1. Выделяется новый, больший блок памяти (обычно в 2 раза больше текущей capacity, хотя точный множитель — деталь реализации).
2. Существующие элементы копируются в новый блок.
3. Старый блок памяти освобождается.
4. Новый элемент добавляется в конец.
5. Значение capacity обновляется.

var arr = [Int]()
for i in 1...10 {
    arr.append(i)
    print("Count: \(arr.count), Capacity: \(arr.capacity)")
}
// Пример вывода (может варьироваться):
// Count: 1, Capacity: 1
// Count: 2, Capacity: 2
// Count: 3, Capacity: 4  <- Произошла реаллокация, capacity удвоилась
// Count: 4, Capacity: 4
// Count: 5, Capacity: 8  <- Снова реаллокация и удвоение
// ... и так далее

Эта стратегия амортизирует стоимость операций добавления. Хотя отдельные операции append могут быть дорогими (O(n) из-за копирования), в среднем, для длинной серии добавлений, амортизированная сложность становится O(1).

Управление ёмкостью

Разработчик может влиять на поведение массива для оптимизации:

• reserveCapacity(_:): Метод для явного запроса минимальной ёмкости. Если вы заранее знаете количество элементов, это позволяет избежать множественных реаллокаций.

  var largeArray = [Int]()
  largeArray.reserveCapacity(1000) // Одна реаллокация
  for i in 0..<1000 {
      largeArray.append(i)          // 1000 добавлений без реаллокаций
  }
  

• shrinkToFit() (через trimToCapacity в некоторых контекстах): Метод для уменьшения capacity до текущего count, экономя память, если массив больше не будет расти.

Как это реализовано "под капотом"

Массив в Swift — это структура (value type), но она использует механизм Copy-on-Write (CoW) с внутренним буфером в куче (heap):

1. Внутри структуры массива хранится указатель на буфер в куче, содержащий элементы.
2. При копировании массива (при присваивании, передаче в функцию) копируется только этот указатель, а не сами данные. Фактическое копирование буфера происходит только при попытке изменить один из массивов, когда на буфер есть более одной ссылки (это и есть CoW).
3. Понятие capacity относится именно к размеру этого внутреннего буфера в куче.
4. Реаллокация — это создание нового, большего буфера, копирование в него старых элементов и замена указателя на новый буфер.

Ключевые преимущества и выводы

• Производительность: Стратегия геометрического роста минимизирует количество операций полного копирования данных.
• Предсказуемость: Использование reserveCapacity позволяет сделать производительность предсказуемой в критических участках кода.
• Память: Существует компромисс между count и capacity. Большая capacity уменьшает частоту реаллокаций, но может вести к избыточному потреблению памяти. Методы управления помогают это балансировать.

Таким образом, capacity — это не просто техническая деталь, а важный инструмент для написания эффективного Swift-кода, особенно при работе с большими или часто изменяемыми коллекциями. Понимание этого механизма позволяет сознательно управлять производительностью и памятью.