Swift探索（ 十二）: Array源码分析

一：Array 的内存布局

在 Swift 中 Array 其实是用结构体实现的，所以 Array 是值类型。

Array.png

通过直接打印 Array 可可以看出来 Array 是值类型

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))

// 打印结果 
8
8
16

我们知道结构体的大小取决于结构体成员变量的大小。但是这里的 array 和 array1 的大小都是 8，这是为什么呢？这里只能说明一个问题，那就是数组的元素不是存储在 array 变量上的，那数组在中数据存储在什么地方？我们通过汇编代码来看 array 的初始化。

array 的初始化汇编代码.png

这里可以看到 array 初始化的时候调用了 _allocateUninitializedArray 这个方法，并且传入了一个参数。那么，这个方法在内部都做了什么操作呢，我们来看一下源码中它是如何实现的。
在 ArrayShared.swift 文件中找到这个函数的具体实现：

@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)
}

这里可以看到传入的参数是 Builtin.Word 类型的 builtinCount 通过语义可以得到这个参数应该就是数组元素的个数。

  • 这个方法返回一个元组 第一个参数是数组 Array< Element > ， 第二次参数是一个指针。
  • 通过 count 判断当前初始化的数组是否需要分配缓冲区。
  • 当大于 0 的时候，会调用一个 allocWithTailElems_1 方法，分配堆空间来存储数组当中的元素。接着通过 _adoptStorage 来创建数组。
  • 当小于 0 的时候，会调用 _allocateUninitialized 来创建一个空数组。

在 Array.Swift 文件中知道了 _adoptStorage 方法的实现

/// 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))
  • 第二个元素是：数组第一个元素的地址。

这里为什么还要返回第一个元素首地址呢？难道 Array 的地址并不是指向存储的第一个元素?
我们可以看到这里的 Array 调用的是 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 的内存地址肯定是有这个 _buffer 的空间的。

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

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

发现 _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")
  }
...

发现 __ContiguousArrayStorageBase 是一个继承自 __SwiftNativeNSArrayWithContiguousStorage 的类，并且有一个 _ArrayBody 类型的成员变量 countAndCapacity。

在之前的 Swift探索（一）: 类与结构体（上） 的文章中我们就研究过类的内存结构是由 metadata 和 refCount 组成。

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

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

发现 _ArrayBody 有个 _SwiftArrayBodyStorage 类型的成员变量 _storage
在 GlobalObjects.h 找到 _SwiftArrayBodyStorage 的声明

struct _SwiftArrayBodyStorage {
  __swift_intptr_t count;
  __swift_uintptr_t _capacityAndFlags;
};

综上能够得出数组类型的变量里存储的其实是一个名为 __ContiguousArrayStorageBase 类的内存地址，而这个类存储着类的信息( metadata 和 refCount）和元素的个数( count)，容量的大小和标志位( _capacityAndFlags )，以及元素的内存地址，大致结构如下。

Array的内存结构.png

通过 LLDB 的打印查看 Array 的内存结构

Array的内存结构.png

本质上 Array 是一个引用类型，只是在 struct 上嵌套了一个 class。

二：Array 扩容

对于 Array 来说是可以实时的通过 append() 方法添加元素

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

那么 append() 方法实际上干了些什么操作呢?
在源码中有下面一段注释

capacity.png

每个数组都保留特定数量的内存来保存其内容。 当向数组中添加元素时，如果数组开始超过其预留容量，则数组分配更大的内存区域，并将其元素 复制 到新的存储中。 新存储空间是旧存储空间的数倍。 这种指数增长策略意味着追加一个元素的时间是恒定的，可以平均许多追加操作的性能。 触发重新分配的附加操作会造成性能损失，但随着数组的增长，它们出现的频率越来越低。

接下来看看 append() 具体是怎么实现的。在 Array.swift 文件中找到 append() 方法的实现

@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()
  }

首先调用了 _makeUniqueAndReserveCapacityIfNotUnique() 方法，定位到 _makeUniqueAndReserveCapacityIfNotUnique() 的实现

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

可以看见这里有一个判断条件 !_buffer.beginCOWMutation() 找到 beginCOWMutation() 的实现

@_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;
  }

其实就是去判断缓冲区的存储是否是被唯一引用的。如果是缓冲区的存储是被多个引用的，则将缓冲区置为可变状态；如果是被唯一引用，则返回 false ，这会去创建新的 buffer ，通过判断条件进入 if 的执行语句，也就是去执行 _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)
  }

这里面调用的是 _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)
  }

这里又调用了一个方法 _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 的最大值。
所以，一般情况下，一个数组在进行扩容的时候，本质上是在旧的 capacity 上进行 2 倍扩容。

©著作权归作者所有,转载或内容合作请联系作者
【社区内容提示】社区部分内容疑似由AI辅助生成，浏览时请结合常识与多方信息审慎甄别。
平台声明：文章内容（如有图片或视频亦包括在内）由作者上传并发布，文章内容仅代表作者本人观点，简书系信息发布平台，仅提供信息存储服务。

推荐阅读更多精彩内容