Fork me on GitHub

Swift 中的 值类型 写时复制

发表于 | 更新于 | 分类于 | 评论数： | 阅读次数：

　　如果想用 Swift 练习一下排序算法，就会碰到这么一个需求：创建几个完全一样的数组，来对比不同排序算法间的性能差异。

　　在 OC 时代，我们可以使用工具类创建一个可变数组，向数组中填充我们生成的随机数，然后对这个数组做可变拷贝，再定义几个新的变量进行赋值，最终每个算法使用新的数组进行排序，这样能保证每个排序算法分配到的随机数组是完全一致的，并且排序的时候互不干扰。

1
2
3
// 为数组创建可变拷贝(深拷贝)
NSMutableArray *arr = [NSMutableArray arrayWithObjects:@10, @8, @55, nil];
NSMutableArray *array1 = [arr mutableCopy];

　　但是，在 Swift4.2 中，我们发现 Array 这个结构体并没有任何 copy 相关的方法，那我们如何做到生成多个完全一致却又互不干扰的随机数组呢？

　　查了资料发现，Swift 中 值类型 有“写时复制（Copy-On-Write）”的特性。

什么是COW（Copy-On-Write）

　　我们都知道 Swift 有值类型和引用类型，而值类型在被赋值或被传递给函数时是会被拷贝的。在 Swift 中，所有的基本类型，包括整数、浮点数、字符串、数组和字典等都是值类型，并且都以结构体的形式实现。那么，我们在写代码时，这些值类型每次赋值传递都是会重新在内存里拷贝一份吗？

　　答案是否定的，想象一下，假如有个包含上千个元素的数组，然后你把它 copy 一份给另一个变量，那么 Swift 就要拷贝所有的元素，即使这两个变量的数组内容完全一样，这对它性能来说是多么糟糕。

　　在 The Swift Programming Language (Swift 4.1) Classes and Structures 章节中有如下一段话，也明确地提到了 Swift 对其实现做了优化，可避免不必要的复制：

1
Collections defined by the standard library like arrays, dictionaries, and strings use an optimization to reduce the performance cost of copying. Instead of making a copy immediately, these collections share the memory where the elements are stored between the original instance and any copies. If one of the copies of the collection is modified, the elements are copied just before the modification. The behavior you see in your code is always as if a copy took place immediately.

　　而这个优化方式就是 Copy-On-Write（写时复制），即只有当这个值需要改变时才进行复制行为。

例子：
　　首先，让我们看下面的例子我们更容易理解，我们创建了数组 array1，然后将 array1 赋值给 array2，再给 array2 数组添加多一个元素，我们通过查看其地址变化来确定是否进行了拷贝行为。

1
2
3
4
5
6
let array1 = [1, 2, 3, 4]
var array2 = array1
// 断点1
array2.append(2) 
// 断点2
print("hello world")

　　断点1位置，使用 lldb 命令 fr v -R [object] 来查看对象内存结构。打印出 array1，array2 内存结构如下，我们可以看到 array1 和 array2 内存地址都是 0x0000000101a1a590，说明 array1 和 array2 此时是共享同一个实例

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
(lldb) fr v -R array1
(Swift.Array<Swift.Int>) array1 = {
  _buffer = {
    _storage = {
      rawValue = 0x0000000101a1a590 {
        Swift._ContiguousArrayStorageBase = {
          Swift._SwiftNativeNSArrayWithContiguousStorage = {
            Swift._SwiftNativeNSArray = {}
          }
          countAndCapacity = {
            _storage = {
              count = {
                _value = 4
              }
              _capacityAndFlags = {
                _value = 8
              }
            }
          }
        }
      }
    }
  }
}
(lldb) fr v -R array2
(Swift.Array<Swift.Int>) array2 = {
  _buffer = {
    _storage = {
      rawValue = 0x0000000101a1a590 {
        Swift._ContiguousArrayStorageBase = {
          Swift._SwiftNativeNSArrayWithContiguousStorage = {
            Swift._SwiftNativeNSArray = {}
          }
          countAndCapacity = {
            _storage = {
              count = {
                _value = 4
              }
              _capacityAndFlags = {
                _value = 8
              }
            }
          }
        }
      }
    }
  }
}

　　断点2位置，此时 array2 添加了新元素，打印 array2，内存结构如下，我们可以看到 array2 内存地址已经变成了0x0000000101a1a5d0，说明此时它们不再共享同一个实例，array2 对应的值进行了拷贝行为

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
(lldb) fr v -R array2
(Swift.Array<Swift.Int>) array2 = {
  _buffer = {
    _storage = {
      rawValue = 0x0000000101a1a5d0 {
        Swift._ContiguousArrayStorageBase = {
          Swift._SwiftNativeNSArrayWithContiguousStorage = {
            Swift._SwiftNativeNSArray = {}
          }
          countAndCapacity = {
            _storage = {
              count = {
                _value = 5
              }
              _capacityAndFlags = {
                _value = 16
              }
            }
          }
        }
      }
    }
  }
}

　　由此可见，array2 未做修改时，array1 和 array2 是共享同一个实例。

具体实现

　　在结构体内部存储了一个指向实际数据的引用 reference，在不进行修改操作的普通传递过程中，都是将内部的reference 的应用计数 +1，在进行修改时，对内部的 reference 做一次 copy 操作，再在这个复制出来的数据进行真正的修改，防止和之前的 reference 产生意外的数据共享。

结论

　　至此，我们已经能够轻松的解决刚开始的时候提出的问题：Swift 中 Array 是结构体，那么我们可以利用”写时复制“的特性，直接按照一定规则生成一个数组，然后定义新的变量，并用初始数组赋值，每个排序算法中使用一个数组变量，示例代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
// Swift 中 Struct 具有“写时复制”的特性
let arr = SortHelper.generateRandomArray(count: 100000, maxValue: 10)

var arr1 = arr
var arr2 = arr
var arr3 = arr

SortHelper.testSort(sortName: "快速排序") {
    arr1.quickSort()
    assert(arr1.isSorted)
}

SortHelper.testSort(sortName: "双路快排") {
    arr2.quickSort2Way()
    assert(arr2.isSorted)
}

SortHelper.testSort(sortName: "三路快排") {
    arr3.quickSort3Way()
    assert(arr3.isSorted)
}

　　得到元素一致且互不干扰的数组之后，就可以安心的练习排序算法啦 :-D。

写在最后

　　有一点需要留意的是， “写时复制” 这个特性在 Swift 中是属于 值类型 的，而不是 Struct 独有的特性，在 Swift 中，典型的有 struct，enum，以及 tuple 都是值类型。而平时使用的 Int， Double，Float，String，Array，Dictionary，Set 其实都是用结构体实现的，也是值类型。

　　写时复制 允许复制数组和原数组共享同一个内存地址，直到其中之一发生改变。这样的设计使得值类型可以被多次复制而无需耗费多余的内存，只有在变化的时候才会增加开销。因此内存的使用更加高效。

------------- 本文结束感谢您的阅读 -------------