一：Array 的内存布局
在 Swift 中 Array 其实是用结构体实现的，所以 Array 是值类型。
通过直接打印
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 初始化的时候调用了 _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 )，以及元素的内存地址，大致结构如下。
通过 LLDB 的打印查看 Array 的内存结构
本质上
Array 是一个引用类型，只是在 struct 上嵌套了一个 class。
二：Array 扩容
对于 Array 来说是可以实时的通过 append() 方法添加元素
var array = [1, 2, 3, 4, 5]
array.append(6)
那么 append() 方法实际上干了些什么操作呢?
在源码中有下面一段注释
每个数组都保留特定数量的内存来保存其内容。 当向数组中添加元素时，如果数组开始超过其预留容量，则数组分配更大的内存区域，并将其元素 复制 到新的存储中。 新存储空间是旧存储空间的数倍。 这种指数增长策略意味着追加一个元素的时间是恒定的，可以平均许多追加操作的性能。 触发重新分配的附加操作会造成性能损失，但随着数组的增长，它们出现的频率越来越低。
接下来看看 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 倍扩容。
