Skip to content

Latest commit

 

History

History
219 lines (149 loc) · 11.1 KB

swift-array-append.md

File metadata and controls

219 lines (149 loc) · 11.1 KB
Raw

结论

首先把结论写在文章开头，因为接下来的分析会有些啰嗦、复杂，如果不愿意深究的话只要记住Swift中数组扩容的原理是：

Swift2中创建一个空数组，默认容量为2，当长度和容量相等，且还需要再添加元素时，创建一个

两倍长度于旧数组的新数组，把旧数组的元素拷贝过来，再把元素插入到新数组中。

引子

下面这段代码希望通过多线程技术，加速向数组中添加数字这个过程，我们来看看它有什么问题：

var array: [Int] = []
let concurrentQueue = dispatch_queue_create("com.gcd.kt", DISPATCH_QUEUE_CONCURRENT)

for i in 1...10000 {
  dispatch_async(concurrentQueue, { () -> Void in
    array.append(i)
  })
}

代码很简短，看上去问题不大。不过如果你运行完这段代码而且程序没有崩溃，我强烈建议买一份彩票，因为你的运气已经好到逆天了。

通常情况下，你会遇到这样的报错

fatal error: UnsafeMutablePointer.destroy with negative count

Append方法实现

程序会断在array.append(i)这一行。也就是append 方法出了问题。我们知道Swift里的数组不像C语言，不需要提前定义好长度，更像是C++的vector和OC的NSMutableArray。

所以，会不会是数组的可变性，导致了append方法是线程不安全的呢，带着这样的猜想，我们来研究一下Swift是如何实现Append方法的。

Swift已经开源了，github上相关源码已经可以下载。

虽然明知道有些文件夹不会包含append方法的实现源码，但真想找到也不容易。如果你试着搜索"append"的话，相关文件非常多，因为"append"本身就是一个非常常用的单词。我采取的办法是搜索完整的函数定义，而函数定义是我们很容易看到的。

当我们搜索"mutating func append(newElement: Element)"后，就只有六个相关文件了。如图所示:

搜索结果

前三个文件无法直接打开，暂时先不管。其实第三个一看也知道是单元测试文件。第六个是字符串，也不是我们感兴趣的。所以我们依次打开"ArrayType.swift"和"RangeReplaceableCollectionType.swift"这两个文件。

提示：这两个文件的目录都是"/swift/stdlib/public/core"

遗憾的是，ArrayType.swift文件中没有找到相关函数，RangeReplaceableCollectionType.swift文件倒是有一个append方法，不过参数类型对不上。于是我想到第一个文件——"Arrays.swift.gyb"，去掉gyb后缀后果然可以打开了。并且成功的找到了我们感兴趣的append方法：

public mutating func append(newElement: Element) {
  _makeUniqueAndReserveCapacityIfNotUnique()
  let oldCount = _getCount()
  _reserveCapacityAssumingUniqueBuffer(oldCount)
  _appendElementAssumeUniqueAndCapacity(oldCount, newElement: newElement)
}

源码分析

代码不长，我们逐行看一下

  • 第一行的函数，看名字表示，如果这个数组不是惟一的，就把它变成惟一的，而且保留数组容量。在 Xcode 里面搜索一下这个函数：
internal mutating func _makeUniqueAndReserveCapacityIfNotUnique() {
  if _slowPath(!_buffer.isMutableAndUniquelyReferenced()) {
    copyToNewBuffer(_buffer.count)
  }
}

这个函数会进行一个判断判断——如果数组不是被唯一引用的，就会复制一份新的。这其实就是“写时赋值(copy-on-write)”技术。如果你想了解它的具体使用，可以参考我的这篇文章——《�第二章——集合（数组与可变性）》

不过对于文章开头那个例子的数组来说，它肯定是唯一引用的。所以_copyToNewBuffer 函数不会调用，我们先记下这个方法。然后回到append 方法继续研究。

  • 第二行用一个变量oldCount保存数组当前长度。

  • 第三行的函数表示，在假设当前数组是唯一引用的前提下，保留数组容量。之所以做出这样的假设，是因为此前已经调用过_makeUniqueAndReserveCapacityIfNotUnique 方法，即使这个数组不是唯一引用，也被复制了一份新的。我们来看看_reserveCapacityAssumingUniqueBuffer 方法的实现：

internal mutating func _reserveCapacityAssumingUniqueBuffer(oldCount : Int) {
  _sanityCheck(_buffer.isMutableAndUniquelyReferenced())

  if _slowPath(oldCount + 1 > _buffer.capacity) {
    _copyToNewBuffer(oldCount)
  }
}

第一行有一个_sanityCheck 来判断数组是否可变且唯一引用。"sanity"说明这个判断是符合常理的，虽然它很有可能并没有效果，但也是为了确保万无一失。

下面还有一个判断，检查当前数组长度加一后是否大于数组容量。如果判断成立，说明oldCount == _buffer.capacity，在实际编程中，就意味着数组需要扩容了。可以看到又会执行刚刚提到过的_copyToNewBuffer 函数。我们还是先把这个函数放一放，接着往后看。

  • 最后一行的函数表示，假设数组是唯一引用的，且数组容量也设置正确，把新的元素添加到数组中。这其实是真正执行了“append”操作的地方。它的实现如下：
internal mutating func _appendElementAssumeUniqueAndCapacity(oldCount : Int, newElement : Element) {
  _sanityCheck(_buffer.isMutableAndUniquelyReferenced())
  _sanityCheck(_buffer.capacity >= _buffer.count + 1)

  _buffer.count = oldCount + 1
  (_buffer.firstElementAddress + oldCount).initialize(newElement)
}

首先是两个基本判断，然后把count 属性加一，最后获取到将要添加的位置的地址，用一个新的值初始化它。

OK，append方法的结构基本上了解了，首先会保证数组是唯一引用的，然后处理数组的容量问题，最后把待插入的元素放到指定位置上。其中最关键，也是目前还没有彻底明白的一步，就是之前所说的_copyToNewBuffer 函数了

copyToNewBuffer

先来看看copyToNewBuffer函数的实现：

internal mutating func _copyToNewBuffer(oldCount: Int) {
  let newCount = oldCount + 1
  var newBuffer = Optional(
  _forceCreateUniqueMutableBuffer(&_buffer, countForNewBuffer: oldCount, minNewCapacity: newCount))
  _arrayOutOfPlaceUpdate(&_buffer, &newBuffer, oldCount, 0, _IgnorePointer())
}

这个方法又分为两步，_forceCreateUniqueMutableBuffer 和_arrayOutOfPlaceUpdate 。前者实现了新存储区域的创建，而后者完成了数据的复制工作。

为了简单起见，我们先看看_arrayOutOfPlaceUpdate 函数,这个函数的实现太长了，不过好在有注释：

/// Initialize the elements of dest by copying the first headCount
/// items from source, calling initializeNewElements on the next
/// uninitialized element, and finally by copying the last N items
/// from source into the N remaining uninitialized elements of dest.
///
/// As an optimization, may move elements out of source rather than
/// copying when it isUniquelyReferenced.

大意是说，源数组中已存在的元素会被复制到目标数组中，如果新数组比较长，空缺部分会调用initializeNewElements 方法来初始化。为了优化性能，被唯一引用的元素可能会直接从源数组移到新数组而不是复制。其实就是换了一个指针指向那个元素，从而避免了复制。

接下来我们再研究一下比较关键的_forceCreateUniqueMutableBuffer 部分，也就是数组是怎样扩容的：

@inline(never)
func _forceCreateUniqueMutableBuffer<_Buffer : _ArrayBufferType>(inout source: _Buffer,  countForNewBuffer: Int,  minNewCapacity: Int) -> _ContiguousArrayBuffer<_Buffer.Element> {

  //其实什么也没干，多加了一个参数就转发给_forceCreateUniqueMutableBufferImpl 了
  return _forceCreateUniqueMutableBufferImpl(&source, countForBuffer: countForNewBuffer, minNewCapacity: minNewCapacity, requiredCapacity: minNewCapacity)
}

internal func _forceCreateUniqueMutableBufferImpl<_Buffer : _ArrayBufferType>(inout source: _Buffer,  countForBuffer: Int, minNewCapacity: Int, requiredCapacity: Int) -> _ContiguousArrayBuffer<_Buffer.Element> {
  _sanityCheck(countForBuffer >= 0)
  _sanityCheck(requiredCapacity >= countForBuffer)
  _sanityCheck(minNewCapacity >= countForBuffer)

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

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

_forceCreateUniqueMutableBufferImpl 函数刚开始的三个检查读者可以自行理解，关键部分在于minimumCapacity 的计算。因为它会作为容量参数被传到用于创建新的Buffer的函数中。

这个函数有四个参数，第一个参数buffer可以理解为数组中真正用于数据存放的那个部分。对于最后两个参数，意思有点像，我们不妨考虑一个实际的、需要进行数组扩容的情况，向一个容量为3，长度为3的数组新增一个元素1，此时函数的调用顺序如下：

  1. append(1)
  2. _reserveCapacityAssumingUniqueBuffer(3)
  3. _copyToNewBuffer(3)
  4. _forceCreateUniqueMutableBuffer(&_buffer, countForNewBuffer: 3, minNewCapacity: 4)
  5. _forceCreateUniqueMutableBufferImpl(&_buffer, countForBuffer: 3, minNewCapacity: 4, requiredCapacity: 4)

还记得_copyToNewBuffer()方法里的let newCount = oldCount + 1么，所以oldCount(=3)作为minNewCapacity ，而newCount(=4)作为requiredCapacity 参数被传入_forceCreateUniqueMutableBufferImpl 方法。

此时，minimumCapacity的计算，其实就是以下表达式的值：

max(4, 4 > 3 ? _growArrayCapacity(3) : 3)

我们知道，如果数组需要扩容，source.capacity总是等于minNewCapacity 的。也就是说上式可以写为：

max(length+1, length+1 > length ? _growArrayCapacity(length) : length)

//等价于
max(length+1, _growArrayCapacity(length))

可以看到_growArrayCapacity 返回值是传入参数的两倍：

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

所以minimumCapacity = max(length+1, 2 * length) = 2 * length。也就是新扩容的数组长度其实翻倍了。

线程安全

现在我们可以理解为什么append方法不是线程安全的了。如果在某一个线程中插入新元素，导致了数组扩容，那么Swift会创建一个新的数组（意味着地址完全不同）。然后ARC会为我们自动释放旧的数组，但这时候可能另一个线程还在访问旧的数组对象。

验证

说了这么多，我们来证明一下Swift数组扩容的工作原理：

let semaphore = dispatch_semaphore_create(1)
var array: [Int] = []
for i in 1...100000 {
  array.append(i)
  let arrayPtr = UnsafeMutableBufferPointer<Int>(start: &array, count: array.count)
  print(arrayPtr)
}

运行结果如下，可以验证文章开头的结论：“初始容量为2，扩容时容量翻倍”

容量翻倍