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

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

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症昏，這是為什么呢蛙粘？這里只能說(shuō)明一個(gè)問(wèn)題，那就是數(shù)組的元素不是存儲(chǔ)在 array 變量上的威彰，那數(shù)組在中數(shù)據(jù)存儲(chǔ)在什么地方出牧？我們通過(guò)匯編代碼來(lái)看 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 類(lèi)型的 builtinCount 通過(guò)語(yǔ)義可以得到這個(gè)參數(shù)應(yīng)該就是數(shù)組元素的個(gè)數(shù)。

• 這個(gè)方法返回一個(gè)元組 第一個(gè)參數(shù)是數(shù)組 Array< Element > 耿眉， 第二次參數(shù)是一個(gè)指針边翼。
• 通過(guò) count 判斷當(dāng)前初始化的數(shù)組是否需要分配緩沖區(qū)。
• 當(dāng)大于 0 的時(shí)候鸣剪，會(huì)調(diào)用一個(gè) allocWithTailElems_1 方法组底，分配堆空間來(lái)存儲(chǔ)數(shù)組當(dāng)中的元素。接著通過(guò) _adoptStorage 來(lái)創(chuàng)建數(shù)組筐骇。
• 當(dāng)小于 0 的時(shí)候债鸡，會(huì)調(diào)用 _allocateUninitialized 來(lái)創(chuàng)建一個(gè)空數(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)
  }

這里可以看到返回的是一個(gè)元祖

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

這里為什么還要返回第一個(gè)元素首地址呢厌均？難道 Array 的地址并不是指向存儲(chǔ)的第一個(gè)元素?
我們可以看到這里的 Array 調(diào)用的是 init(_buffer: _Buffer) 這個(gè)初始化方法傳入的是 _ContiguousArrayBuffer< Element > 類(lèi)型的 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)存地址肯定是有這個(gè) _buffer 的空間的告唆。

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

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

發(fā)現(xiàn) _ContiguousArrayBuffer 有一個(gè) __ContiguousArrayStorageBase 類(lèi)型的成員變量 _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 是一個(gè)繼承自 __SwiftNativeNSArrayWithContiguousStorage 的類(lèi)棺弊，并且有一個(gè) _ArrayBody 類(lèi)型的成員變量 countAndCapacity。

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

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

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

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

struct _SwiftArrayBodyStorage {
  __swift_intptr_t count;
  __swift_uintptr_t _capacityAndFlags;
};

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

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

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

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

二：Array 擴(kuò)容

對(duì)于 Array 來(lái)說(shuō)是可以實(shí)時(shí)的通過(guò) append() 方法添加元素

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

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

capacity.png

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

接下來(lái)看看 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)
    }
  }

可以看見(jiàn)這里有一個(gè)判斷條件 !_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ū)的存儲(chǔ)是否是被唯一引用的骑晶。如果是緩沖區(qū)的存儲(chǔ)是被多個(gè)引用的痛垛，則將緩沖區(qū)置為可變狀態(tài)；如果是被唯一引用桶蛔，則返回 false 匙头，這會(huì)去創(chuàng)建新的 buffer ，通過(guò)判斷條件進(jìn)入 if 的執(zhí)行語(yǔ)句仔雷，也就是去執(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)用了一個(gè)方法 _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 的最大值。
所以碟婆，一般情況下电抚，一個(gè)數(shù)組在進(jìn)行擴(kuò)容的時(shí)候，本質(zhì)上是在舊的 capacity 上進(jìn)行 2 倍擴(kuò)容竖共。