Swift标准库源码阅读笔记 - Array和ContiguousArray-白红宇

关于 ContiguousArray ，这边有介绍的很详细了，可以先看看这个文章。

Array

接着喵神的思路，看一下 Array 以下是从源码中截取的代码片段。

public struct Array
    
     : _DestructorSafeContainer {  #if _runtime(_ObjC)    internal typealias _Buffer = _ArrayBuffer
     
        #else    internal typealias _Buffer = _ContiguousArrayBuffer
      
         #endif  internal var _buffer: _Buffer    internal init(_buffer: _Buffer) {    self._buffer = _buffer  }}复制代码

if _runtime(_ObjC) 等价于 #if os(iOS) || os(macOS) || os(tvOS) || os(watchOS)，从这个操作也可以看出 Swift 的野心不仅仅只是替换 Objective-C那么简单，而是往更加宽泛的方向发展。由于本次主要是研究在 iOS下的开发，所以主要看一下 _ArrayBuffer。

_ArrayBuffer

去掉了注释和与类型检查相关的属性和方法。

internal typealias _ArrayBridgeStorage  = _BridgeStorage<_ContiguousArrayStorageBase, _NSArrayCore>internal struct _ArrayBuffer
    
      : _ArrayBufferProtocol {  internal init() {    _storage = _ArrayBridgeStorage(native: _emptyArrayStorage)  }    internal var _storage: _ArrayBridgeStorage}复制代码

可见 _ArrayBuffer 仅有一个存储属性 _storage ，它的类型 _ArrayBridgeStorage，本质上是 _BridgeStorage。

_NSArrayCore 其实是一个协议，定义了一些 NSArray 的方法，主要是为了桥接 Objective-C 的 NSArray。

最主要的初始化函数，是通过 _emptyArrayStorage 来初始化 _storage。

实际上 _emptyArrayStorage 是 _EmptyArrayStorage 的实例，主要作用是初始化一个空的数组，并且将内存指定在堆上。

internal var _emptyArrayStorage : _EmptyArrayStorage {  return Builtin.bridgeFromRawPointer(    Builtin.addressof(&_swiftEmptyArrayStorage))}复制代码

_BridgeStorage

struct _BridgeStorage
    
      {    typealias Native = NativeClass  typealias ObjC = ObjCClass    init(native: Native, bits: Int) {    rawValue = _makeNativeBridgeObject(      native, UInt(bits) << _objectPointerLowSpareBitShift)  }    init(objC: ObjC) {    rawValue = _makeObjCBridgeObject(objC)  }    init(native: Native) {    rawValue = Builtin.reinterpretCast(native)  }    internal var rawValue: Builtin.BridgeObject复制代码

_BridgeStorage 实际上区分是否是 class、@objc ，进而提供不同的存储策略，为上层调用提供了不同的接口，以及类型判断，通过 Builtin.BridgeObject 这个中间参数，实现不同的储存策略。

The ContiguousArray type is a specialized array that always stores its elements in a contiguous region of memory. This contrasts with Array, which can store its elements in either a contiguous region of memory or an NSArray instance if its Element type is a class or @objc protocol.
If your array’s Element type is a class or @objc protocol and you do not need to bridge the array to NSArray or pass the array to Objective-C APIs, using ContiguousArray may be more efficient and have more predictable performance than Array. If the array’s Element type is a struct or enumeration, Array and ContiguousArray should have similar efficiency.

正因为储存策略的不同，特别是在class 或者 @objc，如果不考虑桥接到 NSArray 或者调用 Objective-C，苹果建议我们使用 ContiguousArray，会更有效率。

Array 和 ContiguousArray 区别

通过一些常用的数组操作，来看看两者之间的区别。

append

ContiguousArray

public mutating func append(_ newElement: Element) {    _makeUniqueAndReserveCapacityIfNotUnique()    let oldCount = _getCount()    _reserveCapacityAssumingUniqueBuffer(oldCount: oldCount)    _appendElementAssumeUniqueAndCapacity(oldCount, newElement: newElement)  }  internal mutating func _makeUniqueAndReserveCapacityIfNotUnique() {    if _slowPath(!_buffer.isMutableAndUniquelyReferenced()) {      _copyToNewBuffer(oldCount: _buffer.count)    }  }    internal mutating func _reserveCapacityAssumingUniqueBuffer(oldCount: Int) {    let capacity = _buffer.capacity == 0    if _slowPath(oldCount + 1 > _buffer.capacity) {      _copyToNewBuffer(oldCount: oldCount)    }  }    internal mutating func _copyToNewBuffer(oldCount: Int) {    let newCount = oldCount + 1    var newBuffer = _buffer._forceCreateUniqueMutableBuffer(      countForNewBuffer: oldCount, minNewCapacity: newCount)    _buffer._arrayOutOfPlaceUpdate(      &newBuffer, oldCount, 0, _IgnorePointer())  }    internal mutating func _appendElementAssumeUniqueAndCapacity(    _ oldCount: Int,    newElement: Element  ) {    _buffer.count = oldCount + 1    (_buffer.firstElementAddress + oldCount).initialize(to: newElement)  }复制代码

_makeUniqueAndReserveCapacityIfNotUnique() 检查数组是否是唯一持有者，以及是否是可变数组。

_reserveCapacityAssumingUniqueBuffer(oldCount: oldCount)检查数组内的元素个数加一后，是否超出超过所分配的空间。

前两个方法在检查之后都调用了 _copyToNewBuffer ，主要操作是如果当前数组需要申请空间，则申请空间，然后再复制 buffer 。

_appendElementAssumeUniqueAndCapacity(oldCount, newElement: newElement) 从首地址后的第 oldCount 个存储空间内，初始化 newElement 。

Array

Array 实现的过程与 ContiguousArray 差不多，但是还是有一些区别，具体看看，主要的区别存在于_ContiguousArrayBuffer 和 _ArrayBuffer

_ContiguousArrayBuffer

internal var firstElementAddress: UnsafeMutablePointer
    
      {  return UnsafeMutablePointer(Builtin.projectTailElems(_storage,                                                       Element.self))}复制代码

直接返回了内存地址。

_ArrayBuffer

internal var firstElementAddress: UnsafeMutablePointer
    
      {   _sanityCheck(_isNative, "must be a native buffer")   return _native.firstElementAddress } internal var _native: NativeBuffer {   return NativeBuffer(     _isClassOrObjCExistential(Element.self)     ? _storage.nativeInstance : _storage.nativeInstance_noSpareBits) } internal typealias NativeBuffer = _ContiguousArrayBuffer
     
      复制代码

从调用的情况来看，本质上还是调用了 _ContiguousArrayBuffer的firstElementAddress

但是在创建时，会有类型检查。

_isClassOrObjCExistential(Element.self)检查是否是类或者@objc修饰的。

在上述中检查持有者是否唯一和数组是否可变的函数中，其实是调用了 _buffer内部的 isMutableAndUniquelyReferenced()。

_ContiguousArrayBuffer

@inlinable  internal mutating func isUniquelyReferenced() -> Bool {    return _isUnique(&_storage)  }复制代码

internal func _isUnique
    
     (_ object: inout T) -> Bool {  return Bool(Builtin.isUnique(&object))}复制代码

最后调用的 Builtin 中的 isUnique。

_ArrayBuffer

internal mutating func isUniquelyReferenced() -> Bool {   if !_isClassOrObjCExistential(Element.self) {     return _storage.isUniquelyReferenced_native_noSpareBits()   }      if !_storage.isUniquelyReferencedNative() {     return false   }   return _isNative }  mutating func isUniquelyReferencedNative() -> Bool {   return _isUnique(&rawValue) } mutating func isUniquelyReferenced_native_noSpareBits() -> Bool {   _sanityCheck(isNative)   return _isUnique_native(&rawValue) }func _isUnique_native
    
     (_ object: inout T) -> Bool {  _sanityCheck(    (_bitPattern(Builtin.reinterpretCast(object)) &  _objectPointerSpareBits)    == 0)  _sanityCheck(_usesNativeSwiftReferenceCounting(      type(of: Builtin.reinterpretCast(object) as AnyObject))) return Bool(Builtin.isUnique_native(&object))}复制代码

如果是 class 或者 @objc 和 _ContiguousBuffer 一样。如果不是则需要调用 Builtin 中的 _isUnique_native，即要检查是否唯一，还要检查是否是 Swift 原生而不是 NSArray。相对于 _ContiguousArrayBuffer 由于 _ArrayBuffer 承载了需要桥接到 NSArray 的功能，所以多了一些类型检查的操作。

insert

ContiguousArray

//ContiguousArray public mutating func insert(_ newElement: Element, at i: Int) {   _checkIndex(i)   self.replaceSubrange(i..
    
     (    _ subrange: Range
     
      ,    with newElements: C  ) where C : Collection, C.Element == Element {    let oldCount = _buffer.count    let eraseCount = subrange.count    let insertCount = newElements.count    let growth = insertCount - eraseCount    if _buffer.requestUniqueMutableBackingBuffer(      minimumCapacity: oldCount + growth) != nil {      _buffer.replaceSubrange(        subrange, with: insertCount, elementsOf: newElements)    } else {      _buffer._arrayOutOfPlaceReplace(subrange, with: newElements, count: insertCount)    }  }    internal mutating func requestUniqueMutableBackingBuffer(    minimumCapacity: Int  ) -> _ContiguousArrayBuffer
      
       ? {    if _fastPath(isUniquelyReferenced() && capacity >= minimumCapacity) {      return self    }    return nil  }    //extension ArrayProtocol  internal mutating func replaceSubrange
       
        (    _ subrange: Range
        
         ,    with newCount: Int,    elementsOf newValues: C  ) where C : Collection, C.Element == Element {    _sanityCheck(startIndex == 0, "_SliceBuffer should override this function.")    let oldCount = self.count //现有数组大小    let eraseCount = subrange.count //需要替换大小    let growth = newCount - eraseCount //目标大小 和 需要替换大小 的差值    self.count = oldCount + growth  //替换后的数组大小    let elements = self.subscriptBaseAddress //数组首地址。    let oldTailIndex = subrange.upperBound     let oldTailStart = elements + oldTailIndex //需要替换的尾地址。    let newTailIndex = oldTailIndex + growth //需要增加的空间的尾下标    let newTailStart = oldTailStart + growth //需要增加的空间的尾地址    let tailCount = oldCount - subrange.upperBound //需要移动的内存空间大小    if growth > 0 {      var i = newValues.startIndex      for j in subrange {        elements[j] = newValues[i]        newValues.formIndex(after: &i)      }      for j in oldTailIndex..
         
           shrinkage { newTailStart.moveAssign(from: oldTailStart, count: shrinkage) oldTailStart.moveInitialize( from: oldTailStart + shrinkage, count: tailCount - shrinkage) } else { newTailStart.moveAssign(from: oldTailStart, count: tailCount) (newTailStart + tailCount).deinitialize( count: shrinkage - tailCount) } } }复制代码

insert 内部实际是调用了 replaceSubrange。而在 replaceSubrange 的操作是，判断内存空间是否够用，和持有者是否唯一，如果有一个不满足条件则复制 buffer 到新的内存空间，并且根据需求分配好内存空间大小。

而 _buffer 内部的 replaceSubrange：

计算 growth 值看所替换的大小和目标大小差值是多少。

如果 growth > 0 ，则需要将现有的内存空间向后移动 growth 位。

替换所需要替换的值。

超出的部分重新分配内存并初始化值。

如果 growth <= 0，则将现有的值替换成新的值即可。

如果 growth < 0，则将不需要的内存空间回收即可。（ps：删除多个元素或者需要替换的大小大于目标大小）。

Array insert 两者基本一致，唯一的区别和 append 一样在在buffer的内部方法，isUniquelyReferenced() 中，多了一些类型检查。

remove

ContiguousArray

public mutating func remove(at index: Int) -> Element {    _makeUniqueAndReserveCapacityIfNotUnique()    let newCount = _getCount() - 1    let pointer = (_buffer.firstElementAddress + index)    let result = pointer.move()    pointer.moveInitialize(from: pointer + 1, count: newCount - index)    _buffer.count = newCount    return result  }复制代码

检查数组持有者是否唯一，取出所要删除的内存地址，通过将当前的内存区域覆盖为一个未初始化的内存空间，以达到回收内存空间的作用，进而达到删除数组元素的作用。

Array

与 ContiguousArray 的区别就在于 _makeUniqueAndReserveCapacityIfNotUnique() 前面已经提到过，仍然是多了一些类型检查。

subscript

ContiguousArray

//ContiguousArraypublic subscript(index: Int) -> Element {    get {      let wasNativeTypeChecked = _hoistableIsNativeTypeChecked()      let token = _checkSubscript(        index, wasNativeTypeChecked: wasNativeTypeChecked)      return _getElement(        index, wasNativeTypeChecked: wasNativeTypeChecked,        matchingSubscriptCheck: token)    }  }    public  func _getElement(    _ index: Int,    wasNativeTypeChecked : Bool,    matchingSubscriptCheck: _DependenceToken  ) -> Element {  #if false    return _buffer.getElement(index, wasNativeTypeChecked: wasNativeTypeChecked)  #else    return _buffer.getElement(index)  #endif  }  //ContiguousArrayBuffer  internal func getElement(_ i: Int) -> Element {    return firstElementAddress[i]  }复制代码

_hoistableIsNativeTypeChecked() 不做任何检查，直接返回 true。 _checkSubscript(index, wasNativeTypeChecked: wasNativeTypeChecked) 检查 index 是否越界。 _getElement 最终还是操作内存，通过 firstElementAddress 偏移量取出值。

Array

//Array  public  func _checkSubscript(    _ index: Int, wasNativeTypeChecked: Bool  ) -> _DependenceToken {#if _runtime(_ObjC)    _buffer._checkInoutAndNativeTypeCheckedBounds(      index, wasNativeTypeChecked: wasNativeTypeChecked)#else    _buffer._checkValidSubscript(index)#endif    return _DependenceToken()  }    func _hoistableIsNativeTypeChecked() -> Bool {   return _buffer.arrayPropertyIsNativeTypeChecked  }    //ArrayBuffer  internal var arrayPropertyIsNativeTypeChecked: Bool {    return _hasNativeBuffer  }    internal var _isNativeTypeChecked: Bool {    if !_isClassOrObjCExistential(Element.self) {      return true    } else {      return _storage.isNativeWithClearedSpareBits(deferredTypeCheckMask)    }  }复制代码

在 ContiguousArray 中 _hoistableIsNativeTypeChecked() 直接返回 true, 而 Array 中如果不是 class 或者 @objc 会返回 ture，否则会检查是否可以桥接到 Swift。

而在 Array 中 _checkSubscript 调用的 _buffer 内部函数也不一样，下面来具体看一看内部实现。

//ArrayBuffer  internal func _checkInoutAndNativeTypeCheckedBounds(    _ index: Int, wasNativeTypeChecked: Bool  ) {    _precondition(      _isNativeTypeChecked == wasNativeTypeChecked,      "inout rules were violated: the array was overwritten")    if _fastPath(wasNativeTypeChecked) {      _native._checkValidSubscript(index)    }  }    //ContiguousArrayBuffer  internal func _checkValidSubscript(_ index : Int) {    _precondition(      (index >= 0) && (index < count),      "Index out of range"    )  }复制代码

本质上就是多了一些是否是类型检查。

//Arrayfunc _getElement(    _ index: Int,    wasNativeTypeChecked : Bool,    matchingSubscriptCheck: _DependenceToken  ) -> Element {#if _runtime(_ObjC)    return _buffer.getElement(index, wasNativeTypeChecked: wasNativeTypeChecked)#else    return _buffer.getElement(index)#endif  }//ArrayBufferinternal func getElement(_ i: Int, wasNativeTypeChecked: Bool) -> Element {    if _fastPath(wasNativeTypeChecked) {      return _nativeTypeChecked[i]    }    return unsafeBitCast(_getElementSlowPath(i), to: Element.self)  }  internal func _getElementSlowPath(_ i: Int) -> AnyObject {    let element: AnyObject    if _isNative {      _native._checkValidSubscript(i)            element = cast(toBufferOf: AnyObject.self)._native[i]    } else {      element = _nonNative.objectAt(i)    }    return element  }    //ContiguousArrayBuffer  internal subscript(i: Int) -> Element {    get {      return getElement(i)    }  }复制代码

在 _buffer 内部的 getElement , 与 ContiguousArray 不同的是需要适配桥接到 NSArray 的情况，如果是 非NSArray 的情况调用的是 ContiguousArrayBuffer 内部的 subscript ，和 ContiguousArray 相同。

总结

从增删改查来看，不管是 ContiguousArray 还是 Array 最终都是操作内存，稍显区别的就是 Array 需要更多的类型检查。所以当不需要 Objective-C，还是尽量使用 ContiguousArray 。下面是对数组中一些批量操作的总结：

removeAll 、insert<C>(contentsOf: C, at: Int) 、 removeSubrange：最终调用的是 replaceSubrange

append<S : Sequence>(contentsOf newElements: S) 和 init(repeating repeatedValue: Element, count: Int)：最终都是操作内存，循环初始化新的内存空间和值。

有什么不正确的地方，欢迎指出。