SwiftのArray.countはO(1)なのか？を実装で確認してみた。

# Array.countはO(1)

Array.countはO(1)という話をTwitterで見かけました。

<blockquote class="twitter-tweet" data-lang="ja"><p lang="ja" dir="ltr">え？？？<br>もしかして SwiftのArrayのcountってO(1)なのでは？？？<br>O(n)だと思ってたんだけど<a href="https://t.co/rOcflehWR9">https://t.co/rOcflehWR9</a></p>&mdash; hori,masaki @ 南無自動最適化 (@masakihori) <a href="https://twitter.com/masakihori/status/1128228401502777347?ref_src=twsrc%5Etfw">2019年5月14日</a></blockquote>

確かに、リンクにあるCollection.countのドキュメントを読むとこうあります

> To check whether a collection is empty, use its isEmpty property instead of comparing count to zero. Unless the collection guarantees random-access performance, calculating count can be an O(n) operation.
Complexity: O(1) if the collection conforms to RandomAccessCollection; otherwise, O(n), where n is the length of the collection.

すなわち、(そのCollectionが)`RandomAccessCollection` に適合している場合はO(1)、そうでない場合はO(n)と書かれています。

また、Arrayは `RandomAccessCollection` に適合しているので、O(1)ということになります。

結論としては、プロパティを参照して、appendなどの場合は適切に更新することでO(1)が実現されていました。
これを実装から実際に確認してみます。

※以下の実装は2019/7/3時点のmasterの実装から抽出しています。また、アノテーションやコメントを割愛したり、改行位置を変えたりしています。最新の実際の実装は[apple/swift](https://github.com/apple/swift)から確認をお願いします。

# Arrayの実装

stdlibはOSSなので、ここから見ることができます → [Array.swift](https://github.com/apple/swift/blob/master/stdlib/public/core/Array.swift)

Arrayはstructで、中身は `_buffer` だけで、あとはメソッドとかゲッターとかの定義です。

```swift:Array.swift
@frozen
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
  }
}

// https://github.com/apple/swift/blob/master/stdlib/public/core/Array.swift#L299-L318
```

# `Array.count` を根っこまで辿る

`.count` の実装は以下のようになっています

```swift:Array.swift
public var count: Int {
  return _getCount()
}

// https://github.com/apple/swift/blob/master/stdlib/public/core/Array.swift#L763-L767
```


```swift:Array.swift
internal func _getCount() -> Int {
  return _buffer.count
}
```

つまり、`_buffer.count`を返しているだけになります。 `_buffer` は先程も示したとおり、以下のような定義です。

```swift
#if _runtime(_ObjC)
internal typealias _Buffer = _ArrayBuffer<Element>
#else
internal typealias _Buffer = _ContiguousArrayBuffer<Element>
#endif

internal var _buffer: _Buffer
// https://github.com/apple/swift/blob/master/stdlib/public/core/Array.swift#L301-L310
```

知識不足でどういう状況でどちらが選択されるのかわからないですが、他の実装を見る限りおそらく通常は `_ContiguousArrayBuffer` が使用されると思われるので、
こちらについてみていきます。

**7/4追記：Mac版では`_ArrayBuffer`の方らしい！！！ので以下はLinux版の実装ということになります（コメント参照）**

~~※ [reserveCapacity](https://github.com/apple/swift/blob/e9d4687e31a3ae8e90604d3b15bf8b241479c211/stdlib/public/core/Array.swift#L1019-L1024)の実装を見ると、newBufferとして `_ContiguousArrayBuffer` が生成されていますので、このときには必ず `_ContiguousArrayBuffer` が使用されることになります。また、`init(repeatedValue:count)` を用いた場合も必ず `_ContiguousArrayBuffer` が使われているのも確認しました。 ので、そう判断しました。~~
~~おそらく `_ArrayBuffer` はObjCとのブリッジ用で、 [こんなコメント](https://github.com/apple/swift/blob/e9d4687e31a3ae8e90604d3b15bf8b241479c211/stdlib/public/core/Array.swift#L1786-L1790)とかあるので、Swiftだけを意識するなら無視して良いかなと。~~

## _ContiguousArrayBuffer

`_buffer.count` をgetしたときに実際に返される値は以下です。つまり、`_storage.countAndCapacity.count`ですね。

※ countにsetが存在するということはつまり、、、？という感じもしますね。setについては次の章で書きます

```swift:ContiguousArrayBuffer.swift
internal var count: Int {
  get {
    return _storage.countAndCapacity.count
  }
  nonmutating set {
...
}

// https://github.com/apple/swift/blob/e9d4687e31a3ae8e90604d3b15bf8b241479c211/stdlib/public/core/ContiguousArrayBuffer.swift#L347-L353
```

_storageの定義は以下のようになっています。

```swift:ContiguousArrayBuffer.swift
internal var _storage: __ContiguousArrayStorageBase

// https://github.com/apple/swift/blob/e9d4687e31a3ae8e90604d3b15bf8b241479c211/stdlib/public/core/ContiguousArrayBuffer.swift#L507
```

### __ContiguousArrayStorageBase

`__ContiguousArrayStorageBase` は以下のような実装です。
大事なポイントとして、`countAndCapacity`は `_ArrayBody` 型のプロパティとして保持されています。

ただこれはベースクラスで、実際に `countAndCapacity` に値を書き込む処理はありません。

```swift:SwiftNativeNSArray.swift
internal class __ContiguousArrayStorageBase: __SwiftNativeNSArrayWithContiguousStorage {
  final var countAndCapacity: _ArrayBody

...
}

// https://github.com/apple/swift/blob/e9d4687e31a3ae8e90604d3b15bf8b241479c211/stdlib/public/core/SwiftNativeNSArray.swift#L268
```

実際に実装されているクラスは、以下の２つです。

```swift
internal final class _ContiguousArrayStorage<Element> : __ContiguousArrayStorageBase {

internal final class __EmptyArrayStorage: __ContiguousArrayStorageBase {
```

今はとにかく実際の値を辿るため、 `_ArrayBody`　の中身を見に行きます。

### _ArrayBody

```swift:ArrayBody.swift
internal struct _ArrayBody {
   internal var _storage: _SwiftArrayBodyStorage
...
  internal var count: Int {
    get {
      return _assumeNonNegative(_storage.count)
    }
    set(newCount) {
...
}

// https://github.com/apple/swift/blob/e9d4687e31a3ae8e90604d3b15bf8b241479c211/stdlib/public/core/ArrayBody.swift#L22
```

`.count`をgetしたときは、 `_storage.count` が返されます。
(_assumeNonNegativeは最後にちょっと説明しますが、値をそのまま返す関数です)

### _SwiftArrayBodyStorage

`_SwiftArrayBodyStorage.count`　をみにいくと、やっとこさ実際の値に行き着きます。
つまり、countはprimitive型です！

```cpp:GlobalObjects.h
struct _SwiftArrayBodyStorage {
  __swift_intptr_t count;
  __swift_uintptr_t _capacityAndFlags;
};

// https://github.com/apple/swift/blob/48d8ebd1b051fba09d09e3322afc9c48fabe0921/stdlib/public/SwiftShims/GlobalObjects.h#L30-L33
```

※ `__swift_intptr_t` は `Int`です（[MappedTypes.def](https://github.com/apple/swift/blob/e9d4687e31a3ae8e90604d3b15bf8b241479c211/lib/ClangImporter/MappedTypes.def#L101)）

よって、結論として、`.count`として値を取得した場合、

`Array._buffer._storage.countAndCapacity._storage.count`

というプリミティブな値が返される事がわかりましたね！
ということで `O(1)` ぽいですね！

ここからは、どういう仕組でこうなっているのかを辿りたいと思います。

# `.count` の初期値を辿る

Arrayの生成時に `init(repeating repeatedValue: Element, count: Int)` を使ったとしましょう。

```swift:Array.swift
public init(repeating repeatedValue: Element, count: Int) {
  var p: UnsafeMutablePointer<Element>
  (self, p) = Array._allocateUninitialized(count)
  for _ in 0..<count {
    p.initialize(to: repeatedValue)
    p += 1
  }
}

// https://github.com/apple/swift/blob/e9d4687e31a3ae8e90604d3b15bf8b241479c211/stdlib/public/core/Array.swift#L866-L875
```

まずはここが呼ばれます。
まずメモリをallocateして、for以下の処理はポインタを走査して値を書き込んでいるだけですね。
selfは`Array._allocateUninitialized`の返り値の１つ目の値みたいです。
`Array._allocateUninitialized` をみていきます。

```swift:Array.swift
internal static func _allocateUninitialized(_ count: Int) -> (Array, UnsafeMutablePointer<Element>) {
  let result = Array(_uninitializedCount: count)
  return (result, result._buffer.firstElementAddress)
}

// https://github.com/apple/swift/blob/e9d4687e31a3ae8e90604d3b15bf8b241479c211/stdlib/public/core/Array.swift#L905-L914
```

ここではイニシャライザが呼ばれています。
返り値の２つ目の値はただの先頭アドレスみたい。
次は `init(_uninitializedCount:)`　をみます。

```swift
@inlinable
internal init(_uninitializedCount count: Int) {
  _precondition(count >= 0, "Can't construct Array with count < 0")
  // Note: Sinking this constructor into an else branch below causes an extra
  // Retain/Release.
  _buffer = _Buffer()
  if count > 0 {
    // Creating a buffer instead of calling reserveCapacity saves doing an
    // unnecessary uniqueness check. We disable inlining here to curb code
    // growth.
    _buffer = Array._allocateBufferUninitialized(minimumCapacity: count)
    _buffer.count = count
  }
  // Can't store count here because the buffer might be pointing to the
  // shared empty array.
}

// https://github.com/apple/swift/blob/e9d4687e31a3ae8e90604d3b15bf8b241479c211/stdlib/public/core/Array.swift#L887-L903
```

`_precondition` はただのアサーションなので無視して良きです。

`_buffer = _Buffer()` で作っているに見えますが、count > 0のときは `_buffer = Array._allocateBufferUninitialized(minimumCapacity: count)` として上書きしています。
コメントを見る限り最適化のためっぽいですね。
というわけでifの中身だけをみます。

```swift:Array.swift
internal static func _allocateBufferUninitialized(
  minimumCapacity: Int
) -> _Buffer {
  let newBuffer = _ContiguousArrayBuffer<Element>(
  _uninitializedCount: 0, minimumCapacity: minimumCapacity)
  return _Buffer(_buffer: newBuffer, shiftedToStartIndex: 0)
}

// https://github.com/apple/swift/blob/e9d4687e31a3ae8e90604d3b15bf8b241479c211/stdlib/public/core/Array.swift#L877-L885
```

きました。`_buffer.count`に書き込んでいます。
ここで冒頭でちらっと紹介したsetterが呼ばれます。

```swift
nonmutating set {
  _internalInvariant(newValue >= 0)

  _internalInvariant(
    newValue <= capacity,
    "Can't grow an array buffer past its capacity")

  _storage.countAndCapacity.count = newValue
}

// https://github.com/apple/swift/blob/e9d4687e31a3ae8e90604d3b15bf8b241479c211/stdlib/public/core/ContiguousArrayBuffer.swift#L353-L361
```

ここで、 `_internalInvariant` もただのアサーションなので、無視してよきです（あとで書きます）
実際の中身は、 `_storage.countAndCapacity.count` に値を書き込んでいるだけです。

ここで `countAndCapacity`　は `_ArrayBody` 型なので、また `_ArrayBody` のセッターに戻ります。

```swift
set(newCount) {
  _storage.count = newCount
}

// https://github.com/apple/swift/blob/e9d4687e31a3ae8e90604d3b15bf8b241479c211/stdlib/public/core/ArrayBody.swift#L55-L57
```

と、やっぱり_storage.countに値を書き込んでいて、これが先程のプリミティブ値になります。

よって、最終的に正しくcountが格納されています。

# `.count` の変化を辿る

appendの場合どう変化しているのでしょうか。

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

// https://github.com/apple/swift/blob/e9d4687e31a3ae8e90604d3b15bf8b241479c211/stdlib/public/core/Array.swift#L1120-L1125
```

### _makeUniqueAndReserveCapacityIfNotUnique()
まず一行目、`_makeUniqueAndReserveCapacityIfNotUnique()`です。

```swift:Array.swift
internal mutating func _makeUniqueAndReserveCapacityIfNotUnique() {
  if _slowPath(!_buffer.isMutableAndUniquelyReferenced()) {
    _copyToNewBuffer(oldCount: _buffer.count)
  }
}
```

`isMutableAndUniquelyReferenced()` はCopyOnWrite(見た目は値渡しでも、実際のコピーは必要になるまで行わない)を実現するための機能だと思います。
必要なときは、 `_copyToNewBuffer`　が呼ばれます。

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

newCountとして今の長さに一つ増やした長さが与えられえていますね。
それが`_forceCreateUniqueMutableBuffer`の`minNewCapacity` として与えられています。
countForBufferは現在のcountです。

```swift:ArrayShared.swift
internal func _forceCreateUniqueMutableBuffer(
  countForNewBuffer: Int, minNewCapacity: Int
) -> _ContiguousArrayBuffer<Element> {
  return _forceCreateUniqueMutableBufferImpl(
    countForBuffer: countForNewBuffer, minNewCapacity: minNewCapacity,
    requiredCapacity: minNewCapacity)
}

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

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

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

// https://github.com/apple/swift/blob/e9d4687e31a3ae8e90604d3b15bf8b241479c211/stdlib/public/core/ArrayShared.swift#L154-L193
```

`let minimumCapacity` の計算はcapacityが足りないときに、二倍にする処理です。
これはSwiftに限らず、一般的なArrayのcapacity確保の仕組みです。またいつかArrayのメモリ連続が担保されている話をしたいと思います。

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

そのcapacityを用いて、新しいbufferが作られています。
このとき、`count` と `capacity` を渡しています。
countは今の値の方でしたね。

```swift:ContiguousArrayBuffer.swift
internal init(
  _uninitializedCount uninitializedCount: Int,
  minimumCapacity: Int
) {
  let realMinimumCapacity = Swift.max(uninitializedCount, minimumCapacity)
  if realMinimumCapacity == 0 {
    self = _ContiguousArrayBuffer<Element>()
  }
  else {
    _storage = Builtin.allocWithTailElems_1(
    _ContiguousArrayStorage<Element>.self,
    realMinimumCapacity._builtinWordValue, Element.self)

    let storageAddr = UnsafeMutableRawPointer(Builtin.bridgeToRawPointer(_storage))
    let endAddr = storageAddr + _swift_stdlib_malloc_size(storageAddr)
    let realCapacity = endAddr.assumingMemoryBound(to: Element.self) - firstElementAddress

    _initStorageHeader(
      count: uninitializedCount, capacity: realCapacity)
  }
}

// https://github.com/apple/swift/blob/e9d4687e31a3ae8e90604d3b15bf8b241479c211/stdlib/public/core/ContiguousArrayBuffer.swift#L177-L202
```

minimumCapacityは必ず0より大きいので、elseブロックをみると、
一番下で `_initStorageHeader` が呼ばれています。

```swift:ContiguousArrayBuffer.swift
internal func _initStorageHeader(count: Int, capacity: Int) {
#if _runtime(_ObjC)
  let verbatim = _isBridgedVerbatimToObjectiveC(Element.self)
#else
  let verbatim = false
#endif

  // 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)
}
```

というわけで、今の値がそのままcountとして渡されて、capacityが（必要に応じて）広がった `_ArrayBody` が作られます。

で、`_copyToNewBuffer` のところに戻って、 `_buffer._arrayOutOfPlaceUpdate(&newBuffer, oldCount, 0)` が実行されます。
(newBufferにはさきほど作られた新しい`_ContiguousArrayBuffer`が入っています。)

[_arrayOutOfPlaceUpdate](https://github.com/apple/swift/blob/e9d4687e31a3ae8e90604d3b15bf8b241479c211/stdlib/public/core/ArrayShared.swift#L205) は長いので細かい実装は省略しますが、最後以下のようになっています。

```swift
...
self = Self(_buffer: dest, shiftedToStartIndex: startIndex)
```

destは上で作られた新しい `_ContiguousArrayBuffer` です。
selfをdestを使って置き換えているのがわかります。
それ以外は主に中身のcopyの処理です（そもそも `_copyToNewBuffer` から呼ばれているので）

よって、appendを実行可能な箱ができましたが、まだcountはそのままです。

### _reserveCapacityAssumingUniqueBuffer(oldCount: oldCount)

append自体の実装に戻ります。

二行目でoldCountには現在のcountの値が代入され、 `_reserveCapacityAssumingUniqueBuffer(oldCount: oldCount)` に進みます。

```swift
internal mutating func _reserveCapacityAssumingUniqueBuffer(oldCount: Int) {
  let capacity = _buffer.capacity == 0
  _internalInvariant(capacity || _buffer.isMutableAndUniquelyReferenced())
  if _slowPath(oldCount + 1 > _buffer.capacity) {
    _copyToNewBuffer(oldCount: oldCount)
  }
}

// https://github.com/apple/swift/blob/e9d4687e31a3ae8e90604d3b15bf8b241479c211/stdlib/public/core/Array.swift#L1055-L1082
```

一行目のcapacityは `_internalInvariant` にしか使われていませんが、これはコメントを見る限り最適化のためらしいです。
よって、if以下だけを見ますと、capacityが`(oldCount + 1)`に足りないなら `_copyToNewBuffer` ということになります。
さっきと同じですね。copyOnWriteのための複製の必要がなくても、capacityが足りなければ確保する必要があります。

### _appendElementAssumeUniqueAndCapacity(oldCount, newElement: newElement)

append関数の最後の行、やっとappendを実行しそうな感じの名前です。

```swift
internal mutating func _appendElementAssumeUniqueAndCapacity(
  _ oldCount: Int,
  newElement: __owned Element
) {
  _internalInvariant(_buffer.isMutableAndUniquelyReferenced())
  _internalInvariant(_buffer.capacity >= _buffer.count + 1)

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

// https://github.com/apple/swift/blob/e9d4687e31a3ae8e90604d3b15bf8b241479c211/stdlib/public/core/Array.swift#L1086-L1095
```

やったー！てかココだけ見ればよかった〜！
buffer.countに1を足して、値を書き込んでいます。

というわけで、append時にもこうやってcountが値として更新されていることがわかりました。

# まとめ

Array.countは通常はO(1)なことが確認できました。

removeとか、他のイニシャライザ使った時とかまで追ってないですが、
とにかく `.count` はたどればprimitive値なので、O(1)になるはずです。

# おまけ:Assertion

上でたまにでてきてた `_assumeNonNegative`, `_internalInvariant` などはアサーション用の関数です。

主に[Assert.swift](https://github.com/apple/swift/blob/e9d4687e31a3ae8e90604d3b15bf8b241479c211/stdlib/public/core/Assert.swift)に定義されています。

`_assumeNonNegative` は0以上であることを確認して、値をそのまま返すメソッドです。

```swift
@_transparent
public func _assumeNonNegative(_ x: ${Self}) -> ${Self} {
  _internalInvariant(x >= (0 as ${Self}))
  return ${Self}(Builtin.assumeNonNegative_${BuiltinName}(x._value))
}

// https://github.com/apple/swift/blob/e9d4687e31a3ae8e90604d3b15bf8b241479c211/stdlib/public/core/IntegerTypes.swift.gyb#L1701-L1710
```

gyb(Pythonを混ぜてSwiftのコードを生成する仕組み)で書かれているのでちょっと読みづらいかもしれませんが、だいたいSwiftだと思って読んでください。

integer_typesのうち、signedのものにこの実装が生成されています。
https://github.com/apple/swift/blob/e9d4687e31a3ae8e90604d3b15bf8b241479c211/stdlib/public/core/IntegerTypes.swift.gyb#L1067-L1071

中で使われている `_internalInvariant` は、`INTERNAL_CHECKS_ENABLED` のときだけconditionをチェックして、落とすものみたいです。

```swift
internal func _internalInvariant(
  _ condition: @autoclosure () -> Bool, _ message: StaticString = StaticString(),
  file: StaticString = #file, line: UInt = #line
) {
#if INTERNAL_CHECKS_ENABLED
  if !_fastPath(condition()) {
    _fatalErrorMessage("Fatal error", message, file: file, line: line,
      flags: _fatalErrorFlags())
  }
#endif
}

// https://github.com/apple/swift/blob/ba750305905e94173fbb6b6494477e7298fe0ba3/stdlib/public/core/Assert.swift#L287-L298
```

`_fastPath`の説明はmarkdownに見つかりました→[Standard Library Programmers Manual](https://github.com/apple/swift/blob/ba750305905e94173fbb6b6494477e7298fe0ba3/docs/StandardLibraryProgrammersManual.md#_fastpath-and-_slowpath)

> _fastPath returns its argument, wrapped in a Builtin.expect

中身をそのまま返すだけで、最適化のためのものらしいです。

[_precondition](https://github.com/apple/swift/blob/e9d4687e31a3ae8e90604d3b15bf8b241479c211/stdlib/public/core/Assert.swift#L196-L217) もconditionをチェックして落とすものですが、リリース時にも実行される点が `_internalInvariant` との違いです。