9983d38f3a644e39a75922c280dd25d1
Array 到底是什么 - Swift 标准库源码导读 (三)

Array 类型是我们在日常开发中最常用的类型之一了。我们都知道,Swift 的 Array 是 struct,它是一个带有写时复制特性的值类型。Swift 开源为我们提供了很好的条件来从源码层级探讨 Array 的实现。在这篇文章中,我们就以从上向下的方式来看看 Array 的构成和实现。

Array 定义

Array 类型是通过 gyb 模板实现的,我们在系列文章的第一篇和之前的一篇专栏文章中已经介绍了 gyb 的基本信息。在编译后,我们可以在 ${build_dir}/stdlib/public/core/8/ 下找到 Arrays.swift 文件。

在阅读这种大型文件时,为了避免阅读困难,最好是把注释和标注都先忽略掉。这样一来,我们就可以很清晰地看到实际的代码。在 Arrays.swift 中,主要定义了 ArrayContiguousArrayArraySlice 三种 public 类型,它们具有相同的接口,而且结构和行为也很类似。为了让事情稍微简单和直观一些,我们这里以 ContiguousArray 为例子挖掘。实际的 Array 大体与之相同,我想作为文末的练习部分留给读者会更好,我也会在最后进行一些提示。(毕竟这个系列的目的就是“导读”)

成员

为了方便阅读,我将 ContiguousArray 的源码进行了一些整理,去掉了妨碍阅读的部分 (包括注释,标注和一部分断言检查),你可以在这里找到这份源码片段。从编译后源码中截取的 ContiguousArray 定义如下

public struct ContiguousArray<Element>: _DestructorSafeContainer {
  internal typealias _Buffer = _ContiguousArrayBuffer<Element>
  internal var _buffer: _Buffer

  internal init(_buffer: _Buffer) {
    self._buffer = _buffer
  }
}

因为在 extension 中现在还不能包含存储变量,所以可以确定 ContiguousArray 仅仅就只是一个 类型为 _buffer 的封装,其类型为 _ContiguousArrayBuffer

ArrayContiguousArrayArraySlice 都遵守了 _DestructorSafeContainer 协议。这个协议在源码中是一个空协议,编译器会对满足了这个协议的类型进行检查,来确认其中的 Element 在数组被销毁时在内存中的行为。

ContiguousArray 的其他部分都定义在扩展中,基本是为了实现 RandomAccessCollectionMutableCollection,这两个协议为数组提供随机访问和内容可变的特性。对于随机访问,除了常规的索引计算以外,像是下标访问计数和计算可用空间复制内容等一操作,都是转发给 _buffer 进行处理的。

此时,ContiguousArray 对我们来说,更像是一个黑盒:

写时复制

ContiguousArray 的 extension 中,有几个值得关注的地方,首先是写时复制的内容。

一个 Swift 初学者在学习值类型和引用类型后,当看到 Array 是值类型时容易产生疑惑:是不是 Swift 的数组在赋值或者参数传递时,都必须进行拷贝?我们能不能让两个变量指向同一个 array,也就是说 array 能不能被共享?有这个疑惑是很正常的,而快速的数组操作显然是一门语言中最基础的问题之一。Swift 数组为此给出的答案也很直接和简单,那就是写时复制,也就是,只有在数组中的元素值发生改变 (比如增删或者对值类型的元素进行替换等) 时,才发生复制。这在保证了数组的值类型语义 (这有利于让程序员在操作数组这种大型结构时保持简单的心理模型,并可以清晰方便地对 array 进行思考) 的同时,也确保了操作数组类型的高效。

确保写时复制的关键代码是 _makeUniqueAndReserveCapacityIfNotUnique 方法。如果 _buffer 的持有者不唯一而且 _buffer 被声明为可变的话 (这是需要进行复制的前提,对于不可变数组由于内容是确定的,因此我们永远不需要复制),将 buffer 进行复制。

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 _makeUniqueAndReserveCapacityIfNotUnique() {
  if !_buffer.isMutableAndUniquelyReferenced() {
    _copyToNewBuffer(oldCount: _buffer.count)
  }
}

这个方法在 removeappendreplaceSubrange 的时候会被使用,当自身的 _buffer 也被其他对象引用时,则创建一个新的单一引用的 newBuffer

严格来说 replaceSubrange 并没有使用 _makeUniqueAndReserveCapacityIfNotUnique,而是直接通过 _buffer.requestUniqueMutableBackingBuffer 获取一个不超过目标大小的单一引用 buffer,如果非单一引用或者大小不合适的话,再进行创建。理论上我们也可以用 _makeUniqueAndReserveCapacityIfNotUnique 来完成同样的事情,但是这部分源码一直就处于分歧状态。

追加空间申请

另一个有趣的话题是关于可变数组的额外空间申请。在创建数组 (或者说 _ContiguousArrayBuffer) 时,我们需要指定一个 capacity 值,来指导需要为 buffer 分配多少内存空间。当我们之后在不断 append 后,之前申请的空间终将不足,在追加元素时,_reserveCapacityAssumingUniqueBuffer 将被调用以确保空间足够,这个方法最终将调用 _buffer_forceCreateUniqueMutableBuffer,最终在 Buffer 类型中走到以下代码:

internal func _forceCreateUniqueMutableBufferImpl(
    countForBuffer: Int, minNewCapacity: Int,
    requiredCapacity: Int
  ) -> _ContiguousArrayBuffer<Element> {

    let minimumCapacity = Swift.max(requiredCapacity,
      minNewCapacity > capacity
         ? _growArrayCapacity(capacity) : capacity)

    return _ContiguousArrayBuffer(
      _uninitializedCount: countForBuffer, minimumCapacity: minimumCapacity)
  }
}

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

可以看到,capacity 不足时,Swift 将会直接把现存的 capacity 翻倍,然后申请新的 buffer。这也就是在处理大容量数组时,我们有时候会看到明明只增加了很少量的元素,但是内存占用却增加很多的原因。如果存在这种内存压力的情况,知道数组内存申请的这个事实后,我们就可以考虑在临界值时将单一的数组分割为一个大数组和一个小数组,以进行优化,缓解内存压力。

_ContiguousArrayBuffer

讨论了顶层的一些接口后,我们现在来看看 _ContiguousArrayBuffer 这个黑盒里的内容。类似前面的做法,我把部分相关代码进行了整理,让它们可读性更好一些。

首先注意到,和 ContiguousArray 类似,_ContiguousArrayBuffer 中也只有一个唯一的成员变量:_storage,它的类型是 _ContiguousArrayStorageBase

struct _ContiguousArrayBuffer<Element> : _ArrayBufferProtocol {
  internal var _storage: _ContiguousArrayStorageBase
  //...
}

_ContiguousArrayBuffer 结构体中最关键的代码就是初始化方法中对 _storage 的赋值语句:

```swift
internal func _initStorageHeader(count: Int, capacity: Int) {

if _runtime(_ObjC)

let verbatim = _isBridgedVerbatimToObjectiveC(Element.self)

top Created with Sketch.