Array.countはO(1)
Array.countはO(1)という話をTwitterで見かけました。
え？？？
— hori,masaki @ 南無自動最適化 (@masakihori) 2019年5月14日
もしかして SwiftのArrayのcountってO(1)なのでは？？？
O(n)だと思ってたんだけどhttps://t.co/rOcflehWR9
確かに、リンクにある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 だけで、あとはメソッドとかゲッターとかの定義です。
@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 の実装は以下のようになっています
public var count: Int {
return _getCount()
}
// https://github.com/apple/swift/blob/master/stdlib/public/core/Array.swift#L763-L767
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については次の章で書きます
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の定義は以下のようになっています。
internal var _storage: __ContiguousArrayStorageBase
// https://github.com/apple/swift/blob/e9d4687e31a3ae8e90604d3b15bf8b241479c211/stdlib/public/core/ContiguousArrayBuffer.swift#L507
__ContiguousArrayStorageBase
__ContiguousArrayStorageBase は以下のような実装です。
大事なポイントとして、countAndCapacityは _ArrayBody 型のプロパティとして保持されています。
ただこれはベースクラスで、実際に countAndCapacity に値を書き込む処理はありません。
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
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型です！
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) を使ったとしましょう。
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 をみていきます。
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の中身だけをみます。
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()です。
internal mutating func _makeUniqueAndReserveCapacityIfNotUnique() {
if _slowPath(!_buffer.isMutableAndUniquelyReferenced()) {
_copyToNewBuffer(oldCount: _buffer.count)
}
}
isMutableAndUniquelyReferenced() はCopyOnWrite(見た目は値渡しでも、実際のコピーは必要になるまで行わない)を実現するための機能だと思います。
必要なときは、 _copyToNewBuffer が呼ばれます。
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です。
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は今の値の方でしたね。
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 が呼ばれています。
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 との違いです。