Привет, Хабр! В прошлой статье мы поговорили о строках в Swift - об их особенностях, внутреннем устройстве и подводных камнях. И я подумал: ведь строки это по сути - коллекции. А какая главная и самая популярная коллекция в Swift? Конечно же, массивы. Их используют повсюду. Но вы когда-нибудь задумывались, как они устроены внутри? Давайте погрузимся внутрь массивов и посмотрим, что они из себя представляют.

Базовые понятия

Итак, все мы знаем различные способы объявления массива:

let array = [1, 2, 3, 4]
let array2 = Array<Int>()
let array3 = Array(repeating: 5, count: 10)

Массив - это структура данных, которая хранит в себе коллекцию элементов одного типа. Это могут быть числа, строки, классы и т. д.

Массив поддерживает доступ по индексу, и этот доступ работает за O(1):

let array = [1, 2, 3, 4]
print(array[0]) // 1

Добавление в массив также работает за амортизированное константное время:

var array = [1, 2, 3, 4]
array.append(5)

Тут есть подводный камень: массив расширяется экспоненциально при заполнении буфера. Это значит, что при росте он будет увеличивать размер внутреннего хранилища и копировать все свои элементы в новое пространство. В такие моменты метод добавления будет работать дольше. Из-за этой особенности Apple рекомендует задавать изначальный размер массива через reserveCapacity(_:), если вам известно примерное количество элементов.

Метод insert работает за O(n), кроме случая, когда мы добавляем элемент в конец массива, тогда он работает также как метод append(_:):

var array = [1, 2, 3, 4]
array.insert(5, at: 2)

Удаление из массива работает за O(n):

var array = [1, 2, 3, 4]
array.remove(at: 2)
array.removeFirst()
array.removeLast()

Кроме метода removeLast() - он работает за O(1).

Почему так? Всё дело в том, что при удалении элемента из середины или из начала массива нужно сдвинуть все оставшиеся элементы на один индекс назад. А если удаляем элемент из конца, то делать этого не требуется.

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

Взаимодействие массива с value и reference типами

Массив - это тип значения, как и любая другая коллекция в Swift. Как уже было сказано выше, он хранит в себе коллекцию элементов. Эти элементы могут быть как ссылочного типа, так и типа значения.

С типами значения всё просто: меняем один массив - все его копии остаются нетронутыми:

var array1 = [1, 2, 3, 4]
let array2 = array1
array1[0] = 2

print(array1) // [2, 2, 3, 4]
print(array2) // [1, 2, 3, 4]

А вот с ссылочными типами всё чуть сложнее. Объекты классов лежат не в самом массиве, а в куче, а в массиве хранятся только ссылки на них. Если изменять сами ссылки, всё будет работать так же, как и со структурами. Но если менять свойства объектов по этим ссылкам, картина сильно меняется:

class Example {
    var a = 10
}

let array1 = [Example(), Example(), Example(), Example()]
let array2 = array1

array1[0].a = 20
// Ошибка: Cannot assign through subscript: 'array1' is a 'let' constant
//array1[0] = Example()

print(array1.map(\.a)) // [20, 10, 10, 10]
print(array2.map(\.a)) // [20, 10, 10, 10]

Поле поменялось в обоих массивах. Почему так происходит? Подробности можно почитать тут, но концептуально мы меняем объект по ссылке, поэтому все его копии также меняются, так как все копии ссылаются на один и тот же объект в куче.

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

Один из вариантов глубокого копирования:

protocol Copying {
    func copy() -> Self
}

class Person: Copying {
    var name: String
    var age: Int
    
    required init(name: String, age: Int) {
        self.name = name
        self.age = age
    }
    
    func copy() -> Self {
        return Self(name: name, age: age)
    }
}

extension Array where Element: Copying {
    func deepCopy() -> [Element] {
        return self.map { $0.copy() }
    }
}

let original: [Person] = [
    Person(name: "Sasha", age: 30),
    Person(name: "Masha", age: 25)
]

let copied = original.deepCopy()

copied[0].name = "Vanya"

print(original[0].name) // Sasha
print(copied[0].name)   // Vanya

Бонусом приведу один интересный кейс при работе с массивами, которые являются частью структуры. Итак, что будет, если сделать так?

struct A {
    let a: A
}

Мы получим ошибку компиляции:

Value type 'A' cannot have a stored property that recursively contains it

Что она означает? Размер структуры рассчитывается на этапе компиляции, но в данном случае это невозможно, так как структура содержит саму себя.

Но если сделать так:

struct A {
    let a: [A]
}

то всё будет нормально, и ошибка компиляции нас больше не побеспокоит. Это связано с особенностями устройства массива, о которых мы поговорим далее.

Устройство массива

Массив, несмотря то, что он является value типом, не хранит элементы внутри себя на стеке. Он представляет собой обёртку над буфером. Конкретный тип буфера определяется на этапе компиляции: если включён objc runtime, используется _ArrayBuffer, в противном случае - _ContiguousArrayBuffer.

Напоминание: Objective-C runtime включен всегда, когда мы разрабатываем под iOS, MacOS, tvOS и watchOS

@frozen
@_eagerMove
public struct Array<Element>: _DestructorSafeContainer {
  #if _runtime(_ObjC)
  @usableFromInline
  internal typealias _Buffer = _ArrayBuffer<Element>
  #else
  @usableFromInline
  internal typealias _Buffer = _ContiguousArrayBuffer<Element>
  #endif

  @usableFromInline
  internal var _buffer: _Buffer

  @inlinable
  internal init(_buffer: _Buffer) {
    self._buffer = _buffer
  }
}

Array выступает как внешний интерфейс: методы вроде count, capacity или доступ по индексу передаются буферу.

_ContiguousArrayBuffer

_ContiguousArrayBuffer используется, если массив и его элементы представлены только в Swift. Он хранит _ContiguousArrayStorage, которое работает с данными как с непрерывным блоком памяти в куче.

Буфер хранит _ContiguousArrayStorage не напрямую, а через абстрактный класс __ContiguousArrayStorageBase. Это сделано для совместимости с Objective-C, так как __ContiguousArrayStorageBase наследует обёртку __SwiftNativeNSArrayWithContiguousStorage, которая добавляет Swift'овую поддержку подсчёта ссылок к NSArray.

Назревает логичный вопрос: зачем нам __ContiguousArrayStorageBase для поддержки работы с Objective-C, если _ContiguousArrayBuffer работает только со Swift-типами? Дело в том, что есть несколько типов хранилищ, например __EmptyArrayStorage или __StaticArrayStorage (о них расскажу чуть ниже). В таком случае __ContiguousArrayStorageBase нужен, чтобы избежать жёсткой привязки к конкретному типу. При этом, если Objective-C рантайм выключен, у нас нет оверхеда с __SwiftNativeNSArrayWithContiguousStorage, так как без objc это просто класс-заглушка.

@usableFromInline
@_fixed_layout
internal class __SwiftNativeNSArrayWithContiguousStorage {
  @inlinable
  internal init() {}

  @inlinable
  deinit {}
}

_ArrayBuffer и _BridgeStorage

Если включён Objective-C runtime, используется _ArrayBuffer. Он хранит __ContiguousArrayStorageBase через вспомогательную обёртку _BridgeStorage, которая определяет, нативные ли элементы хранятся в массиве, или они связаны с Objective-C.

internal typealias _ArrayBridgeStorage
  = _BridgeStorage<__ContiguousArrayStorageBase>

@usableFromInline
@frozen
internal struct _ArrayBuffer<Element>: _ArrayBufferProtocol {
  @usableFromInline
  internal var _storage: _ArrayBridgeStorage
  // ...
}

_BridgeStorage абстрагирует работу с нативными и Objective-C типами, обеспечивая корректное хранение и доступ в зависимости от происхождения элементов массива.

Чтобы упростить взаимодействие с массивами Objective-C, используется _CocoaArrayWrapper. Если элементы связаны с Objective-C, _ArrayBuffer при обращении проверяет «нативность» массива: если элементы массива нативные — доступ идёт напрямую к хранилищу, если нет — то через wrapper.

  @inlinable
  internal var _isNative: Bool {
    if !_isClassOrObjCExistential(Element.self) {
      return true
    } else {
      return _storage.isNative
    }
  }
  // ...
 
  // пример обращения к сабскрипту для получения буфера среза (ArraySlice)
  @inlinable
  internal subscript(bounds: Range<Int>) -> _SliceBuffer<Element> {
    get {
      _typeCheck(bounds)
      if _fastPath(_isNative) {
        return _native[bounds]
      }
      return _nonNative[bounds].unsafeCastElements(to: Element.self)
    }
    set {
      fatalError("not implemented")
    }
  }

  // ...
  @inlinable
  internal var _native: NativeBuffer {
    return NativeBuffer(
      _isClassOrObjCExistential(Element.self)
      ? _storage.nativeInstance : _storage.unflaggedNativeInstance)
  }

  @inlinable
  internal var _nonNative: _CocoaArrayWrapper {
    get {
      _internalInvariant(_isClassOrObjCExistential(Element.self))
      return _CocoaArrayWrapper(_storage.objCInstance)
    }
  }

Хранилище массива может быть трёх типов:

_ContiguousArrayStorage - основное хранилище для данных.
__EmptyArrayStorage - хранилище для пустых массивов. Все пустые массивы в коде ссылаются на него, что избавляет от дополнительных аллокаций.
__StaticArrayStorage - для массивов-констант. Они неизменяемы в рантайме, поэтому методы модификации для этого типа завершаются ошибкой, возвращают false или nil

Возвращаясь к примеру из прошлого раздела:

struct A {
    let a: [A]
}

print(MemoryLayout<A>.size) // 8

Swift позволяет объявить такую структуру, так как массив не хранит сами элементы, а хранит ссылку на буфер, который содержит хранилище с данными в куче. Эта ссылка всегда имеет фиксированный размер (8 байт на 64-битных системах). Следовательно, компилятор может вычислить размер структуры A на этапе компиляции: он будет равен 8 байтам.

Copy-on-Write

Массивы в Swift реализуют механизм Copy-on-Write (COW). Это также достигается за счёт буферов:

@inlinable
@_semantics("array.make_mutable")
@_effects(notEscaping self.**)
internal mutating func _makeMutableAndUnique() {
  if _slowPath(!_buffer.beginCOWMutation()) {
    _buffer = _buffer._consumeAndCreateNew()
  }
}

Здесь метод проверяет, что у буфера есть только одна уникальная ссылка (вызов beginCOWMutation). Если это не так, то создаётся новый буфер с копией данных. Таким образом, все копии массива до его первого изменения ссылаются на одну область памяти.

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

ArraySlice

Рассмотрим задачку, которая иногда встречается на собеседованиях:

let numbers = [10, 20, 30, 40, 50]
let slice = numbers[1...3]
print(slice[0]) // Что будет выведено?

Кажется, что ответ - 10. Но на самом деле в рантайме произойдёт креш.

Почему? Особенность ArraySlice в том, что он не копирует массив, а является ограниченным видом на ту же область памяти. Для простоты это можно представить так: есть стена - это массив, когда мы светим на стену фонариком, то подсвечивается только определенное пространство на стене - это срез.

В примере выше slice покрывает индексы 1...3, поэтому индекса 0 у него попросту нет.

Схематично это можно представить так:

numbers: [10, 20, 30, 40, 50] (индексы 0...4)
slice: [20, 30, 40], но с индексами 1...3.

Код под капотом выглядит так:

public subscript(bounds: Range<Int>) -> ArraySlice<Element> {
  get {
    _checkIndex(bounds.lowerBound)
    _checkIndex(bounds.upperBound)
    return ArraySlice(_buffer: _buffer[bounds])
  }
  ...
}

Таким образом, в slice просто отсутствует индекс 0. Чтобы обратиться к первому элементу, нужно использовать его реальный индекс:

print(slice[1]) // 20

Выводы

Мы разобрали, как устроены массивы в Swift под капотом: от базовых операций добавления и удаления до тонкостей работы с value/reference типами. Посмотрели на Copy-on-Write и устройство буфера. Также узнали, почему массивы - это всего лишь обёртки над хранилищем в куче, и чем ArraySlice отличается от обычного массива.

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

Ссылки