Swift - Array

[TOC]

Array是我们日常打交道非常多的一个集合，下面我们就来研究一下它。

1. Array 的创建

1.1 初始化一个数组

Swift 中有很多创建Array的方式：

// 通过字面量初始化一个Int类型的Array
var numbers = [1, 2, 3, 4, 5]
// 通过字面量初始化一个String类型的Array
var strArray = ["element1", "element2", "element3", "element4",]

// 初始化一个Any类型的空Array，此处必须指定类型，否则会报编译错误
var emptyArray = Array<Any>()
var emptyArray1: [Any] = Array()
var emptyArray2: Array<Any> = Array()
var emptyArray3 = [Any]()

// 当然为了防止访问越界我们也可以这样初始化指定长度和初始值的数组
var array = Array(repeating: 0, count: 10)
print(array[0])

以上代码提供了数组的基本初始化方法。

• 可以通过字面量初始化
• 可以初始化空数组
• 可以初始化指定大小和初始值的数组

1.2 初始化数组的底层实现（SIL）

那么数组在底层是如何创建的呢？下面我们通过sil代码进行查看：

var numbers = [1, 2, 3, 4, 5]

-w999

在sil代码中可以看到：

• 调用了_allocateUninitializedArray函数初始了长度为5，类型为Int的数组
• 然后为初始的数据，也就是个元组，取出里面的两个指针赋值到%7和%8
• 根据%8的地址依次偏移，存储数组中的元素
• 最后将%7的指针存储到%3，也就是numbers

其实这段代码很好理解，但是有一个疑问，大家都说Array是一个值类型，那么我们刚才其实看到了alloc的调用，那么这是为什么呢？我们一步Swift源码Swift 5.3.1中一探究竟。

1.3 源码探索

1.3.1 _allocateUninitializedArray

首先我们搜索一下_allocateUninitializedArray方法，可以在ArrayShared.swift文件中找到。

-w623

在源码中我们可以看到：

• 根据count的不同做了不同的初始化
• 如果大于0会调用allocWithTailElems_1初始化一个bufferObject
• 然后调用_adoptStorage初始一个元组
• 如果不大于0则调用_allocateUninitialized初始化一个元组
• 最后返回这个元组

为了更好的跟代码，我们在Debug调试一下：

-w768 -w901

继续跟下去就到了这里：

-w1229

很熟悉的创建HeapObject的代码，接下来调用的是一个Array的函数，我我们跟一下：

1.3.2 _adoptStorage

-w604

在这个方法中我们可以看到：

• 首先创建了一个_ContiguousArrayBuffer类型的变量
• 然后返回了一个元组
  • 元组的第一个元素是一个Array的实例对象
  • 第二个元素是第一个元素的地址

所以在sil代码中，%7和%8对应的就是元组中的两个值。%7是Array的地址，%8是原生首地址的地址。

-w679

1.3.3 _ContiguousArrayBuffer

-w589

_ContiguousArrayBuffer也是个结构体。

1.4 Array 的内存布局

下面我们来看看Array的内存布局，从_adoptStorage方法继续向上翻就可以看到Array这个结构体中只有一个_buffer的成员变量。

-w641

下面我回到_ContiguousArrayBuffer中继续探索，在该结构体的最后，我们可以看到_storage属性的定义。

image

在其初始化的时候也都能看到对_storage的初始化：

image

_storage的类型是__ContiguousArrayStorageBase，下面我们就研究一下__ContiguousArrayStorageBase

1.4.1 __ContiguousArrayStorageBase

__ContiguousArrayStorageBase是一个类，定义在SwiftNativeNSArray.swift文件中：

-w876

这里面有一个成员属性，回到_ContiguousArrayBuffer中可以看到如下代码：

-w678

这里面初始化了countAndCapacity。

1.4.2 _ArrayBody

下面我们来看看_ArrayBody是什么，在ArrayBody.swift文件中我们可以看到如下代码：

-w753

我们可以看到_ArrayBody是一个结构体，里面有一个_SwiftArrayBodyStorage类型的属性。

搜索一下_SwiftArrayBodyStorage可以在GlobalObjects.h文件中找到其定义：

struct _SwiftArrayBodyStorage {
  __swift_intptr_t count;
  __swift_uintptr_t _capacityAndFlags;
};

可以看到_SwiftArrayBodyStorage是一个结构体，里面定义了两个成员变量。

1.4.3 内存布局总结

经过上面的一番探索我们总结一下Array的内存布局：

struct Array----->struct _ContiguousArrayBuffer----->class __ContiguousArrayStorageBase----->包含一个属性类型是struct ArrayBody----->包含一个属性struct _SwiftArrayBodyStorage----->包含两个属性count和_capacityAndFlags

这里最主要的就是__ContigousArrayStorageBase，因为前面都是值类型。

image

1.4.4 通过lldb验证以上结论

下面我们通过lldb打印一下：

-w619

1.4.5 _capacityAndFlags

乍一看_capacityAndFlags的值好像是count的两倍，下面我们通过源码来看一看：

@inlinable
internal init(
    count: Int, capacity: Int, elementTypeIsBridgedVerbatim: Bool = false
  ) {
    _internalInvariant(count >= 0)
    _internalInvariant(capacity >= 0)
    
    _storage = _SwiftArrayBodyStorage(
      count: count,
      _capacityAndFlags:
        (UInt(truncatingIfNeeded: capacity) &<< 1) |
        (elementTypeIsBridgedVerbatim ? 1 : 0))
}

以上是_ArrayBody的初始化代码，我们可以看到对_capacityAndFlags赋值的时候是将capacity的值左移1位 在或（|）上(elementTypeIsBridgedVerbatim ? 1 : 0)。

  /// Is the Element type bitwise-compatible with some Objective-C
  /// class?  The answer is---in principle---statically-knowable, but
  /// I don't expect to be able to get this information to the
  /// optimizer before 1.0 ships, so we store it in a bit here to
  /// avoid the cost of calls into the runtime that compute the
  /// answer.
  @inlinable
  internal var elementTypeIsBridgedVerbatim: Bool {
    get {
      return (_capacityAndFlags & 0x1) != 0
    }
    set {
      _capacityAndFlags
        = newValue ? _capacityAndFlags | 1 : _capacityAndFlags & ~1
    }
  }

elementTypeIsBridgedVerbatim是一个计算属性，看看是否当兼容Objective-C的时候是1，否则是0，这里我们并没有兼容OC所以使用0。

那么调用的时候传值是怎么传的呢？这个属性是__ContiguousArrayStorageBase中的countAndCapacity，初始化是在_ContiguousArrayBuffer中初始化的：

    // We can initialize by assignment because _ArrayBody is a trivial type,
    // i.e. contains no references.
    _storage.countAndCapacity = _ArrayBody(
      count: count,
      capacity: capacity,
      elementTypeIsBridgedVerbatim: verbatim)
  }

这里的capacity也是调用处传过来的，调用点也在_ContiguousArrayBuffer中：

  @inlinable
  internal init(count: Int, storage: _ContiguousArrayStorage<Element>) {
    _storage = storage

    _initStorageHeader(count: count, capacity: count)
  }

可以看到这个capacity的值就是count，所以说_capacityAndFlags也是个按位存储的变量，通过计算得出capacity，并不是这存储capacity，根据变量的名称我们也可以知道该变量并不是只存储一个值的。

1.4.6 metadata

在lldb调试的时候，我们发现存储metadata的地址很大，那么怎么怎么回事呢？我们通过cat address命令查看一下（需要安装插件），Xcode默认不带这个命令：

image

那么这个InitialAllocationPool是什么呢？我们去源码中看看，可以在Metadata.cpp中找到：

image

下面我们测试一下，初始化一个数组：

image

可以看到调用堆栈确实调用了。但其实不同的创建方式，这个位置的内容是不一样的：

image image

其实这么大的地址就是静态变量（这里也应该是Metadata），尝试了几次，如果初始化一个空数组就是_swiftEmptyArrayStorage，有值的时候就是InitialAllocationPool，并没有过多测试，不知道具体准不准确。

2. 数组的拼接

2.1 数组的扩容

一个数组初始完成后，我们会需要往里面添加数据，也就是append操作，涉及到append就存在扩容的问题，那么Swift中的Array是如何扩容的呢？

我们直接找到append方法：

-w684

我们可以看到，扩容时调用的_reserveCapacityAssumingUniqueBuffer方法，如果全局搜索会有好几个_reserveCapacityAssumingUniqueBuffer方法，经过测试实际是调用的Array.Swift文件中的。

-w699

这里也很简单，判断oldCount + 1 > _buffer.capacity就扩容。

接下来我们找到_createNewBuffer方法，也在Array.Swift文件中。

-w901

扩容的时候调用的是_growArrayCapacity(oldCapacity:minimumCapacity: growForAppend:)方法，在ArrayShared.swift文件中：

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

_growArrayCapacity(oldCapacity:minimumCapacity: growForAppend:)方法中：

• 首先会判断使其扩容的是不是append方法
• 如果是判断oldCapacity是否小于minimumCapacity
• 如果不是返回oldCapacity
• 如果是取出oldCapacity的两倍和minimumCapacity中的大值进行返回

这个minimumCapacity的值在这条调用堆栈上是oldCount + 1，growForAppend的值为true可以在_reserveCapacityAssumingUniqueBuffer方法中看到。

所以基本可以认为数组的扩容时之前的两倍。

扩容时对于就元素的的处理，如果原始缓冲区是唯一的，我们可以移动元素，而不是复制。如果不是就需要复制元素。

回到我们的代码中，通过lldb调试一下：

-w660

append后数组的地址就已经改变了。

读取两段地址：

image

_capacityAndFlags的值分别是0xa和0x14。

-w356

右移1位分别是5和10。

2.1 Array的拷贝

首先我们看看下面这段代码：

var numbers = [1, 2, 3, 4, 5]
var tmpArray = numbers

-w638

我们看到这里只调用了copy_addr，下面我们看看copy_addr的作用是什么：

-w567

可以看到这里面就是一个值的拷贝，在这里就是把numbers里面存储的内容（这里是一个指针）拷贝一份到tmpArray中。

那么这里就存在一个问题了，Array在底层是一个结构体，在Swift中结构体是一个值类型，那么也就意味着当前我们改变numbers或者tmpArray不会影响另外一个里面的值。

var numbers = [1, 2, 3, 4, 5]

var tmpArray = numbers
tmpArray[0] = 2

print(numbers)
print(tmpArray)

-w490

我们可以看到确实没有影响到另一个。但是numbers里面存储的是地址，当初我们在探索值类型和引用类型的时候，当值类型内嵌套引用类型的时候，改变值类型中的引用类型的值，会影响到拷贝的另一个值类型，这点就不一样了，还是上面的代码，我们通过lldb调试看一看：

-w678

我们可以看到给tmpArray修改值后，其存储的值已经改变了，那么修改的时候发生可什么呢？下面我们在看看Sil代码：

-w717

下面我们到源码中看看：

-w766

在Array.swift中我们可以看到subscript方法有get和_modify两个方法。在_modify里面会调用_makeMutableAndUnique方法，下面我们就看看这个方法：

-w720

这里会调用_createNewBuffer方法，这就是我们在数组拼接的时候介绍的这个方法：

-w903

这里会创建一个新的buffer赋值给_buffer

3. 总结

至此我们对 Swift 中数组的介绍就结束，下面总结一下：

• Swift中的数组本质是个结构体，里面的结构如下图：

image

• 因为是结构体，所以我们认为数组是值类型
• 数组空间的扩容时原来容量的两倍，目前没有发现有最大容量限制
• 数组的拷贝是写时复制机制，只有修改的时候才会修改
  • 首先拷贝的时候是拷贝数组的地址
  • 当需要修改任一指向同一空间的数组的时候创建一个新的buffer来存储里面的元素