一：Array 的內(nèi)存布局

在 Swift 中 Array 其實(shí)是用結(jié)構(gòu)體實(shí)現(xiàn)的，所以 Array 是值類型。

Array.png

let array = [1, 2, 3, 4, 5]
print(MemoryLayout.stride(ofValue: array))

let array2 = [1, 2, 3, 4, 5, 6]
print(MemoryLayout.stride(ofValue: array2))

struct Person {
    var age = 18
    var height = 180
}

let p = Person()
print(MemoryLayout.stride(ofValue: p))

// 打印結(jié)果 
8
8
16

我們知道結(jié)構(gòu)體的大小取決于結(jié)構(gòu)體成員變量的大小。但是這里的 array 和 array1 的大小都是 8，這是為什么呢？這里只能說明一個問題，那就是數(shù)組的元素不是存儲在 array 變量上的，那數(shù)組在中數(shù)據(jù)存儲在什么地方？我們通過匯編代碼來看 array 的初始化。

array 的初始化匯編代碼.png

@inlinable // FIXME(inline-always)
@inline(__always)
@_semantics("array.uninitialized_intrinsic")
public // COMPILER_INTRINSIC
func _allocateUninitializedArray<Element>(_  builtinCount: Builtin.Word)
    -> (Array<Element>, Builtin.RawPointer) {
  let count = Int(builtinCount)
  if count > 0 {
    // Doing the actual buffer allocation outside of the array.uninitialized
    // semantics function enables stack propagation of the buffer.
    let bufferObject = Builtin.allocWithTailElems_1(
      _ContiguousArrayStorage<Element>.self, builtinCount, Element.self)

    let (array, ptr) = Array<Element>._adoptStorage(bufferObject, count: count)
    return (array, ptr._rawValue)
  }
  // For an empty array no buffer allocation is needed.
  let (array, ptr) = Array<Element>._allocateUninitialized(count)
  return (array, ptr._rawValue)
}

這里可以看到傳入的參數(shù)是 Builtin.Word 類型的 builtinCount 通過語義可以得到這個參數(shù)應(yīng)該就是數(shù)組元素的個數(shù)。

• 這個方法返回一個元組 第一個參數(shù)是數(shù)組 Array< Element > ， 第二次參數(shù)是一個指針。
• 通過 count 判斷當(dāng)前初始化的數(shù)組是否需要分配緩沖區(qū)。
• 當(dāng)大于 0 的時候，會調(diào)用一個 allocWithTailElems_1 方法，分配堆空間來存儲數(shù)組當(dāng)中的元素。接著通過 _adoptStorage 來創(chuàng)建數(shù)組。
• 當(dāng)小于 0 的時候，會調(diào)用 _allocateUninitialized 來創(chuàng)建一個空數(shù)組。

在 Array.Swift 文件中知道了 _adoptStorage 方法的實(shí)現(xiàn)

/// Returns an Array of `count` uninitialized elements using the
  /// given `storage`, and a pointer to uninitialized memory for the
  /// first element.
  ///
  /// - Precondition: `storage is _ContiguousArrayStorage`.
  @inlinable
  @_semantics("array.uninitialized")
  internal static func _adoptStorage(
    _ storage: __owned _ContiguousArrayStorage<Element>, count: Int
  ) -> (Array, UnsafeMutablePointer<Element>) {

    let innerBuffer = _ContiguousArrayBuffer<Element>(
      count: count,
      storage: storage)

    return (
      Array(
        _buffer: _Buffer(_buffer: innerBuffer, shiftedToStartIndex: 0)),
        innerBuffer.firstElementAddress)
  }

這里可以看到返回的是一個元祖

• 第一個元素是： Array(_buffer: _Buffer(_buffer: innerBuffer, shiftedToStartIndex: 0))
• 第二個元素是：數(shù)組第一個元素的地址。

這里為什么還要返回第一個元素首地址呢？難道 Array 的地址并不是指向存儲的第一個元素?
我們可以看到這里的 Array 調(diào)用的是 init(_buffer: _Buffer) 這個初始化方法傳入的是 _ContiguousArrayBuffer< Element > 類型的 innerBuffer

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

  /// Initialization from an existing buffer does not have "array.init"
  /// semantics because the caller may retain an alias to buffer.
  @inlinable
  internal init(_buffer: _Buffer) {
    self._buffer = _buffer
  }
}

可以看到這里的 _buffer 是作為 Array 的成員變量，那么 Array 的內(nèi)存地址肯定是有這個 _buffer 的空間的。

在 ContiguousArrayBuffer.swift 文件中找到 _ContiguousArrayBuffer 的聲明

@usableFromInline
@frozen
internal struct _ContiguousArrayBuffer<Element>: _ArrayBufferProtocol {
  @usableFromInline
  internal var _storage: __ContiguousArrayStorageBase
...

發(fā)現(xiàn) _ContiguousArrayBuffer 有一個 __ContiguousArrayStorageBase 類型的成員變量 _storage

在 SwiftNativeNSArray.swift 文件中找到 __ContiguousArrayStorageBase 的聲明

internal class __ContiguousArrayStorageBase
  : __SwiftNativeNSArrayWithContiguousStorage {

  @usableFromInline
  final var countAndCapacity: _ArrayBody

  @inlinable
  @nonobjc
  internal init(_doNotCallMeBase: ()) {
    _internalInvariantFailure("creating instance of __ContiguousArrayStorageBase")
  }
...

發(fā)現(xiàn) __ContiguousArrayStorageBase 是一個繼承自 __SwiftNativeNSArrayWithContiguousStorage 的類，并且有一個 _ArrayBody 類型的成員變量 countAndCapacity。

在之前的 Swift探索（一）: 類與結(jié)構(gòu)體（上） 的文章中我們就研究過類的內(nèi)存結(jié)構(gòu)是由 metadata 和 refCount 組成。

在 ArrayBody.swift 文件中 定位到 _ArrayBody 的聲明

internal struct _ArrayBody {
  @usableFromInline
  internal var _storage: _SwiftArrayBodyStorage
...

發(fā)現(xiàn) _ArrayBody 有個 _SwiftArrayBodyStorage 類型的成員變量 _storage
在 GlobalObjects.h 找到 _SwiftArrayBodyStorage 的聲明

struct _SwiftArrayBodyStorage {
  __swift_intptr_t count;
  __swift_uintptr_t _capacityAndFlags;
};

綜上能夠得出數(shù)組類型的變量里存儲的其實(shí)是一個名為 __ContiguousArrayStorageBase 類的內(nèi)存地址，而這個類存儲著類的信息( metadata 和 refCount）和元素的個數(shù)( count)，容量的大小和標(biāo)志位( _capacityAndFlags )，以及元素的內(nèi)存地址，大致結(jié)構(gòu)如下。

Array的內(nèi)存結(jié)構(gòu).png

通過 LLDB 的打印查看 Array 的內(nèi)存結(jié)構(gòu)

Array的內(nèi)存結(jié)構(gòu).png

二：Array 擴(kuò)容

對于 Array 來說是可以實(shí)時的通過 append() 方法添加元素

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

那么 append() 方法實(shí)際上干了些什么操作呢?
在源碼中有下面一段注釋

capacity.png

每個數(shù)組都保留特定數(shù)量的內(nèi)存來保存其內(nèi)容。 當(dāng)向數(shù)組中添加元素時，如果數(shù)組開始超過其預(yù)留容量，則數(shù)組分配更大的內(nèi)存區(qū)域，并將其元素 復(fù)制 到新的存儲中。 新存儲空間是舊存儲空間的數(shù)倍。 這種指數(shù)增長策略意味著追加一個元素的時間是恒定的，可以平均許多追加操作的性能。 觸發(fā)重新分配的附加操作會造成性能損失，但隨著數(shù)組的增長，它們出現(xiàn)的頻率越來越低。

接下來看看 append() 具體是怎么實(shí)現(xiàn)的。在 Array.swift 文件中找到 append() 方法的實(shí)現(xiàn)

@inlinable
  @_semantics("array.append_element")
  public mutating func append(_ newElement: __owned Element) {
    // Separating uniqueness check and capacity check allows hoisting the
    // uniqueness check out of a loop.
    _makeUniqueAndReserveCapacityIfNotUnique()
    let oldCount = _buffer.mutableCount
    _reserveCapacityAssumingUniqueBuffer(oldCount: oldCount)
    _appendElementAssumeUniqueAndCapacity(oldCount, newElement: newElement)
    _endMutation()
  }

首先調(diào)用了 _makeUniqueAndReserveCapacityIfNotUnique() 方法，定位到 _makeUniqueAndReserveCapacityIfNotUnique() 的實(shí)現(xiàn)

@inlinable
  @_semantics("array.make_mutable")
  internal mutating func _makeUniqueAndReserveCapacityIfNotUnique() {
    if _slowPath(!_buffer.beginCOWMutation()) {
      _createNewBuffer(bufferIsUnique: false,
                       minimumCapacity: count &+ 1,
                       growForAppend: true)
    }
  }

可以看見這里有一個判斷條件 !_buffer.beginCOWMutation() 找到 beginCOWMutation() 的實(shí)現(xiàn)

@_alwaysEmitIntoClient
  internal mutating func beginCOWMutation() -> Bool {
    if !_hasNativeBuffer {
      return false
    }
    if Bool(Builtin.beginCOWMutation(&owner)) {
#if INTERNAL_CHECKS_ENABLED && COW_CHECKS_ENABLED
      nativeBuffer.isImmutable = false
#endif
      return true
    }
    return false;
  }

其實(shí)就是去判斷緩沖區(qū)的存儲是否是被唯一引用的。如果是緩沖區(qū)的存儲是被多個引用的，則將緩沖區(qū)置為可變狀態(tài)；如果是被唯一引用，則返回 false ，這會去創(chuàng)建新的 buffer ，通過判斷條件進(jìn)入 if 的執(zhí)行語句，也就是去執(zhí)行 _createNewBuffer(bufferIsUnique: false, minimumCapacity: count &+ 1, growForAppend: true)
定位到 _createNewBuffer(bufferIsUnique: minimumCapacity: growForAppend:)

 /// Creates a new buffer, replacing the current buffer.
  ///
  /// If `bufferIsUnique` is true, the buffer is assumed to be uniquely
  /// referenced by this array and the elements are moved - instead of copied -
  /// to the new buffer.
  /// The `minimumCapacity` is the lower bound for the new capacity.
  /// If `growForAppend` is true, the new capacity is calculated using
  /// `_growArrayCapacity`, but at least kept at `minimumCapacity`.
  @_alwaysEmitIntoClient
  internal mutating func _createNewBuffer(
    bufferIsUnique: Bool, minimumCapacity: Int, growForAppend: Bool
  ) {
    _internalInvariant(!bufferIsUnique || _buffer.isUniquelyReferenced())
    _buffer = _buffer._consumeAndCreateNew(bufferIsUnique: bufferIsUnique,
                                           minimumCapacity: minimumCapacity,
                                           growForAppend: growForAppend)
  }

這里面調(diào)用的是 _consumeAndCreateNew() 方法，定位到 _consumeAndCreateNew()

/// Creates and returns a new uniquely referenced buffer which is a copy of
  /// this buffer.
  ///
  /// If `bufferIsUnique` is true, the buffer is assumed to be uniquely
  /// referenced and the elements are moved - instead of copied - to the new
  /// buffer.
  /// The `minimumCapacity` is the lower bound for the new capacity.
  /// If `growForAppend` is true, the new capacity is calculated using
  /// `_growArrayCapacity`, but at least kept at `minimumCapacity`.
  ///
  /// This buffer is consumed, i.e. it's released.
  @_alwaysEmitIntoClient
  @inline(never)
  @_semantics("optimize.sil.specialize.owned2guarantee.never")
  internal __consuming func _consumeAndCreateNew(
    bufferIsUnique: Bool, minimumCapacity: Int, growForAppend: Bool
  ) -> _ArrayBuffer {
    let newCapacity = _growArrayCapacity(oldCapacity: capacity,
                                         minimumCapacity: minimumCapacity,
                                         growForAppend: growForAppend)
    let c = count
    _internalInvariant(newCapacity >= c)
    
    let newBuffer = _ContiguousArrayBuffer<Element>(
      _uninitializedCount: c, minimumCapacity: newCapacity)

    if bufferIsUnique {
      // As an optimization, if the original buffer is unique, we can just move
      // the elements instead of copying.
      let dest = newBuffer.firstElementAddress
      dest.moveInitialize(from: mutableFirstElementAddress,
                          count: c)
      _native.mutableCount = 0
    } else {
      _copyContents(
        subRange: 0..<c,
        initializing: newBuffer.mutableFirstElementAddress)
    }
    return _ArrayBuffer(_buffer: newBuffer, shiftedToStartIndex: 0)
  }

這里又調(diào)用了一個方法 _growArrayCapacity() 接著定位到 _growArrayCapacity()

@inlinable
internal func _growArrayCapacity(_ capacity: Int) -> Int {
  return capacity * 2
}

@_alwaysEmitIntoClient
internal func _growArrayCapacity(
  oldCapacity: Int, minimumCapacity: Int, growForAppend: Bool
) -> Int {
  if growForAppend {
    if oldCapacity < minimumCapacity {
      // When appending to an array, grow exponentially.
      return Swift.max(minimumCapacity, _growArrayCapacity(oldCapacity))
    }
    return oldCapacity
  }
  // If not for append, just use the specified capacity, ignoring oldCapacity.
  // This means that we "shrink" the buffer in case minimumCapacity is less
  // than oldCapacity.
  return minimumCapacity
}

這里可以看到 這里返回的是 minimumCapacity 和 oldCapacity * 2 的最大值。
所以，一般情況下，一個數(shù)組在進(jìn)行擴(kuò)容的時候，本質(zhì)上是在舊的 capacity 上進(jìn)行 2 倍擴(kuò)容。