LoginSignup
22
6

Delete article

Deleted articles cannot be recovered.

Draft of this article would be also deleted.

Are you sure you want to delete this article?

More than 5 years have passed since last update.

@_ha1f(はるふ)

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

Last updated at Posted at 2019-07-04

Array.countはO(1)

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

確かに、リンクにある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から確認をお願いします。

Arrayの実装

stdlibはOSSなので、ここから見ることができます → Array.swift

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

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 の実装は以下のようになっています

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

// https://github.com/apple/swift/blob/master/stdlib/public/core/Array.swift#L763-L767
Array.swift
internal func _getCount() -> Int {
  return _buffer.count
}

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

#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の実装を見ると、newBufferとして _ContiguousArrayBuffer が生成されていますので、このときには必ず _ContiguousArrayBuffer が使用されることになります。また、init(repeatedValue:count) を用いた場合も必ず _ContiguousArrayBuffer が使われているのも確認しました。 ので、そう判断しました。
おそらく _ArrayBuffer はObjCとのブリッジ用で、 こんなコメントとかあるので、Swiftだけを意識するなら無視して良いかなと。

_ContiguousArrayBuffer

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

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

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の定義は以下のようになっています。

ContiguousArrayBuffer.swift
internal var _storage: __ContiguousArrayStorageBase

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

__ContiguousArrayStorageBase

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

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

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

...
}

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

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

internal final class _ContiguousArrayStorage<Element> : __ContiguousArrayStorageBase {

internal final class __EmptyArrayStorage: __ContiguousArrayStorageBase {

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

_ArrayBody

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型です！

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）

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

Array._buffer._storage.countAndCapacity._storage.count

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

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

.count の初期値を辿る

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

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 をみていきます。

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:)　をみます。

@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の中身だけをみます。

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が呼ばれます。

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 のセッターに戻ります。

set(newCount) {
  _storage.count = newCount
}

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

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

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

.count の変化を辿る

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

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()です。

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

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

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です。

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のメモリ連続が担保されている話をしたいと思います。

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

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

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 が呼ばれています。

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 は長いので細かい実装は省略しますが、最後以下のようになっています。

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

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

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

_reserveCapacityAssumingUniqueBuffer(oldCount: oldCount)

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

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

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を実行しそうな感じの名前です。

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に定義されています。

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

@_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をチェックして、落とすものみたいです。

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

_fastPath returns its argument, wrapped in a Builtin.expect

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

_precondition もconditionをチェックして落とすものですが、リリース時にも実行される点が _internalInvariant との違いです。

22
6
2

Register as a new user and use Qiita more conveniently

  1. You get articles that match your needs
  2. You can efficiently read back useful information
  3. You can use dark theme
What you can do with signing up
Sign upLogin
22
6

Delete article

Deleted articles cannot be recovered.

Draft of this article would be also deleted.

Are you sure you want to delete this article?