Array和ContiguousArray
栏目: Objective-C · 发布时间: 6年前
内容简介:关于接着喵神的思路,看一下
关于 ContiguousArray
,这边有喵神的文章介绍的很详细了,可以先看看这个文章。
Array
接着喵神的思路,看一下 Array
以下是从源码中截取的代码片段。
public struct Array<Element>: _DestructorSafeContainer { #if _runtime(_ObjC) internal typealias _Buffer = _ArrayBuffer<Element> #else internal typealias _Buffer = _ContiguousArrayBuffer<Element> #endif internal var _buffer: _Buffer internal init(_buffer: _Buffer) { self._buffer = _buffer } }
if _runtime(_ObjC)
等价于 #if os(iOS) || os(macOS) || os(tvOS) || os(watchOS)
,从这个操作也可以看出 Swift
的野心不仅仅只是替换 Objective-C
那么简单,而是往更加宽泛的方向发展。由于本次主要是研究在 iOS
下的开发,所以主要看一下 _ArrayBuffer
。
_ArrayBuffer
去掉了注释和与类型检查相关的属性和方法。
internal typealias _ArrayBridgeStorage = _BridgeStorage<_ContiguousArrayStorageBase, _NSArrayCore> internal struct _ArrayBuffer<Element> : _ArrayBufferProtocol { internal init() { _storage = _ArrayBridgeStorage(native: _emptyArrayStorage) } internal var _storage: _ArrayBridgeStorage }
可见 _ArrayBuffer
仅有一个存储属性 _storage
,它的类型 _ArrayBridgeStorage
,本质上是 _BridgeStorage
。
_NSArrayCore
其实是一个协议,定义了一些 NSArray
的方法,主要是为了桥接 Objective-C
的 NSArray
。
最主要的初始化函数,是通过 _emptyArrayStorage
来初始化 _storage
。
实际上 _emptyArrayStorage
是 _EmptyArrayStorage
的实例,主要作用是初始化一个空的数组,并且将内存指定在堆上。
internal var _emptyArrayStorage : _EmptyArrayStorage { return Builtin.bridgeFromRawPointer( Builtin.addressof(&_swiftEmptyArrayStorage)) }
_BridgeStorage
struct _BridgeStorage<NativeClass: AnyObject, ObjCClass: AnyObject> { typealias Native = NativeClass typealias ObjC = ObjCClass init(native: Native, bits: Int) { rawValue = _makeNativeBridgeObject( native, UInt(bits) << _objectPointerLowSpareBitShift) } init(objC: ObjC) { rawValue = _makeObjCBridgeObject(objC) } init(native: Native) { rawValue = Builtin.reinterpretCast(native) } internal var rawValue: Builtin.BridgeObject
_BridgeStorage
实际上区分 是否是 class、@objc
,进而提供不同的存储策略,为上层调用提供了不同的接口,以及类型判断,通过 Builtin.BridgeObject
这个中间参数,实现不同的储存策略。
The ContiguousArray type is a specialized array that always stores its elements in a contiguous region of memory. This contrasts with Array, which can store its elements in either a contiguous region of memory or an NSArray instance if its Element type is a class or @objc protocol. If your array’s Element type is a class or @objc protocol and you do not need to bridge the array to NSArray or pass the array to Objective-C APIs, using ContiguousArray may be more efficient and have more predictable performance than Array. If the array’s Element type is a struct or enumeration, Array and ContiguousArray should have similar efficiency.
正因为储存策略的不同,特别是在 class
或者 @objc
,如果不考虑桥接到 NSArray
或者调用 Objective-C
,苹果建议我们使用 ContiguousArray
,会更有效率。
Array 和 ContiguousArray 区别
通过一些常用的数组操作,来看看两者之间的区别。
append
ContiguousArray
public mutating func append(_ newElement: Element) { _makeUniqueAndReserveCapacityIfNotUnique() let oldCount = _getCount() _reserveCapacityAssumingUniqueBuffer(oldCount: oldCount) _appendElementAssumeUniqueAndCapacity(oldCount, newElement: newElement) } internal mutating func _makeUniqueAndReserveCapacityIfNotUnique() { if _slowPath(!_buffer.isMutableAndUniquelyReferenced()) { _copyToNewBuffer(oldCount: _buffer.count) } } internal mutating func _reserveCapacityAssumingUniqueBuffer(oldCount: Int) { let capacity = _buffer.capacity == 0 if _slowPath(oldCount + 1 > _buffer.capacity) { _copyToNewBuffer(oldCount: oldCount) } } internal mutating func _copyToNewBuffer(oldCount: Int) { let newCount = oldCount + 1 var newBuffer = _buffer._forceCreateUniqueMutableBuffer( countForNewBuffer: oldCount, minNewCapacity: newCount) _buffer._arrayOutOfPlaceUpdate( &newBuffer, oldCount, 0, _IgnorePointer()) } internal mutating func _appendElementAssumeUniqueAndCapacity( _ oldCount: Int, newElement: Element ) { _buffer.count = oldCount + 1 (_buffer.firstElementAddress + oldCount).initialize(to: newElement) }
_makeUniqueAndReserveCapacityIfNotUnique()
检查数组是否是唯一持有者,以及是否是可变数组。
_reserveCapacityAssumingUniqueBuffer(oldCount: oldCount)
检查数组内的元素个数加一后,是否超出超过所分配的空间。
前两个方法在检查之后都调用了 _copyToNewBuffer
,主要操作是如果当前数组需要申请空间,则申请空间,然后再复制 buffer
。
_appendElementAssumeUniqueAndCapacity(oldCount, newElement: newElement)
从首地址后的第 oldCount
个存储空间内,初始化 newElement
。
Array
Array
实现的过程与 ContiguousArray
差不多,但是还是有一些区别,具体看看,主要的区别存在于 _ContiguousArrayBuffer
和 _ArrayBuffer
_ContiguousArrayBuffer
internal var firstElementAddress: UnsafeMutablePointer<Element> { return UnsafeMutablePointer(Builtin.projectTailElems(_storage, Element.self)) }
直接返回了内存地址。
_ArrayBuffer
internal var firstElementAddress: UnsafeMutablePointer<Element> { _sanityCheck(_isNative, "must be a native buffer") return _native.firstElementAddress } internal var _native: NativeBuffer { return NativeBuffer( _isClassOrObjCExistential(Element.self) ? _storage.nativeInstance : _storage.nativeInstance_noSpareBits) } internal typealias NativeBuffer = _ContiguousArrayBuffer<Element>
从调用的情况来看,本质上还是调用了 _ContiguousArrayBuffer
的 firstElementAddress
但是在创建时,会有类型检查。
_isClassOrObjCExistential(Element.self)
检查是否是类或者 @objc
修饰的。
在上述中检查持有者是否唯一和数组是否可变的函数中, 其实是调用了 _buffer
内部的 isMutableAndUniquelyReferenced()
。
_ContiguousArrayBuffer
@inlinable internal mutating func isUniquelyReferenced() -> Bool { return _isUnique(&_storage) }
internal func _isUnique<T>(_ object: inout T) -> Bool { return Bool(Builtin.isUnique(&object)) }
最后调用的 Builtin
中的 isUnique
。
_ArrayBuffer
internal mutating func isUniquelyReferenced() -> Bool { if !_isClassOrObjCExistential(Element.self) { return _storage.isUniquelyReferenced_native_noSpareBits() } if !_storage.isUniquelyReferencedNative() { return false } return _isNative } mutating func isUniquelyReferencedNative() -> Bool { return _isUnique(&rawValue) } mutating func isUniquelyReferenced_native_noSpareBits() -> Bool { _sanityCheck(isNative) return _isUnique_native(&rawValue) } func _isUnique_native<T>(_ object: inout T) -> Bool { _sanityCheck( (_bitPattern(Builtin.reinterpretCast(object)) & _objectPointerSpareBits) == 0) _sanityCheck(_usesNativeSwiftReferenceCounting( type(of: Builtin.reinterpretCast(object) as AnyObject))) return Bool(Builtin.isUnique_native(&object)) }
如果是 class 或者 @objc
和 _ContiguousBuffer
一样。如果不是则需要调用 Builtin
中的 _isUnique_native
,即要检查是否唯一,还要检查是否是 Swift
原生 而不是 NSArray
。
相对于 _ContiguousArrayBuffer
由于 _ArrayBuffer
承载了需要桥接到 NSArray
的功能,所以多了一些类型检查的操作。
insert
ContiguousArray
//ContiguousArray public mutating func insert(_ newElement: Element, at i: Int) { _checkIndex(i) self.replaceSubrange(i..<i, with: CollectionOfOne(newElement)) } public mutating func replaceSubrange<C>( _ subrange: Range<Int>, with newElements: C ) where C : Collection, C.Element == Element { let oldCount = _buffer.count let eraseCount = subrange.count let insertCount = newElements.count let growth = insertCount - eraseCount if _buffer.requestUniqueMutableBackingBuffer( minimumCapacity: oldCount + growth) != nil { _buffer.replaceSubrange( subrange, with: insertCount, elementsOf: newElements) } else { _buffer._arrayOutOfPlaceReplace(subrange, with: newElements, count: insertCount) } } internal mutating func requestUniqueMutableBackingBuffer( minimumCapacity: Int ) -> _ContiguousArrayBuffer<Element>? { if _fastPath(isUniquelyReferenced() && capacity >= minimumCapacity) { return self } return nil } //extension ArrayProtocol internal mutating func replaceSubrange<C>( _ subrange: Range<Int>, with newCount: Int, elementsOf newValues: C ) where C : Collection, C.Element == Element { _sanityCheck(startIndex == 0, "_SliceBuffer should override this function.") let oldCount = self.count //现有数组大小 let eraseCount = subrange.count //需要替换大小 let growth = newCount - eraseCount //目标大小 和 需要替换大小 的差值 self.count = oldCount + growth //替换后的数组大小 let elements = self.subscriptBaseAddress //数组首地址。 let oldTailIndex = subrange.upperBound let oldTailStart = elements + oldTailIndex //需要替换的尾地址。 let newTailIndex = oldTailIndex + growth //需要增加的空间的尾下标 let newTailStart = oldTailStart + growth //需要增加的空间的尾地址 let tailCount = oldCount - subrange.upperBound //需要移动的内存空间大小 if growth > 0 { var i = newValues.startIndex for j in subrange { elements[j] = newValues[i] newValues.formIndex(after: &i) } for j in oldTailIndex..<newTailIndex { (elements + j).initialize(to: newValues[i]) newValues.formIndex(after: &i) } _expectEnd(of: newValues, is: i) } else { var i = subrange.lowerBound var j = newValues.startIndex for _ in 0..<newCount { elements[i] = newValues[j] i += 1 newValues.formIndex(after: &j) } _expectEnd(of: newValues, is: j) if growth == 0 { return } let shrinkage = -growth if tailCount > shrinkage { newTailStart.moveAssign(from: oldTailStart, count: shrinkage) oldTailStart.moveInitialize( from: oldTailStart + shrinkage, count: tailCount - shrinkage) } else { newTailStart.moveAssign(from: oldTailStart, count: tailCount) (newTailStart + tailCount).deinitialize( count: shrinkage - tailCount) } } }
insert
内部实际是 调用了 replaceSubrange
。
而在 replaceSubrange
的操作是,判断内存空间是否够用,和持有者是否唯一,如果有一个不满足条件则复制 buffer
到新的内存空间,并且根据需求分配好内存空间大小。
而 _buffer
内部的 replaceSubrange
:
-
计算
growth
值看所替换的大小和目标大小差值是多少。 -
如果
growth > 0
,则需要将现有的内存空间向后移动growth
位。 - 替换所需要替换的值。
- 超出的部分重新分配内存并初始化值。
-
如果
growth <= 0
,则将现有的值替换成新的值即可。 -
如果
growth < 0
,则将不需要的内存空间回收即可。(ps:删除多个元素或者需要替换的大小大于目标大小)。
Array insert
两者基本一致,唯一的区别和 append
一样在 在 buffer
的内部方法, isUniquelyReferenced()
中,多了一些类型检查。
remove
ContiguousArray
public mutating func remove(at index: Int) -> Element { _makeUniqueAndReserveCapacityIfNotUnique() let newCount = _getCount() - 1 let pointer = (_buffer.firstElementAddress + index) let result = pointer.move() pointer.moveInitialize(from: pointer + 1, count: newCount - index) _buffer.count = newCount return result }
检查数组持有者是否唯一,取出所要删除的内存地址,通过将当前的内存区域覆盖为一个未初始化的内存空间,以达到回收内存空间的作用,进而达到删除数组元素的作用。
Array
与 ContiguousArray
的区别就在于 _makeUniqueAndReserveCapacityIfNotUnique()
前面已经提到过,仍然是多了一些类型检查。
subscript
ContiguousArray
//ContiguousArray public subscript(index: Int) -> Element { get { let wasNativeTypeChecked = _hoistableIsNativeTypeChecked() let token = _checkSubscript( index, wasNativeTypeChecked: wasNativeTypeChecked) return _getElement( index, wasNativeTypeChecked: wasNativeTypeChecked, matchingSubscriptCheck: token) } } public func _getElement( _ index: Int, wasNativeTypeChecked : Bool, matchingSubscriptCheck: _DependenceToken ) -> Element { #if false return _buffer.getElement(index, wasNativeTypeChecked: wasNativeTypeChecked) #else return _buffer.getElement(index) #endif } //ContiguousArrayBuffer internal func getElement(_ i: Int) -> Element { return firstElementAddress[i] }
_hoistableIsNativeTypeChecked()
不做任何检查,直接返回 true
。 _checkSubscript(index, wasNativeTypeChecked: wasNativeTypeChecked)
检查 index
是否越界。 _getElement
最终还是操作内存,通过 firstElementAddress
偏移量取出值。
Array
//Array public func _checkSubscript( _ index: Int, wasNativeTypeChecked: Bool ) -> _DependenceToken { #if _runtime(_ObjC) _buffer._checkInoutAndNativeTypeCheckedBounds( index, wasNativeTypeChecked: wasNativeTypeChecked) #else _buffer._checkValidSubscript(index) #endif return _DependenceToken() } func _hoistableIsNativeTypeChecked() -> Bool { return _buffer.arrayPropertyIsNativeTypeChecked } //ArrayBuffer internal var arrayPropertyIsNativeTypeChecked: Bool { return _hasNativeBuffer } internal var _isNativeTypeChecked: Bool { if !_isClassOrObjCExistential(Element.self) { return true } else { return _storage.isNativeWithClearedSpareBits(deferredTypeCheckMask) } }
在 ContiguousArray
中 _hoistableIsNativeTypeChecked()
直接返回 true
, 而 Array
中如果不是 class 或者 @objc
会返回 ture
,否则会检查是否可以桥接到 Swift
。
而在 Array
中 _checkSubscript
调用的 _buffer
内部函数也不一样,下面来具体看一看内部实现。
//ArrayBuffer internal func _checkInoutAndNativeTypeCheckedBounds( _ index: Int, wasNativeTypeChecked: Bool ) { _precondition( _isNativeTypeChecked == wasNativeTypeChecked, "inout rules were violated: the array was overwritten") if _fastPath(wasNativeTypeChecked) { _native._checkValidSubscript(index) } } //ContiguousArrayBuffer internal func _checkValidSubscript(_ index : Int) { _precondition( (index >= 0) && (index < count), "Index out of range" ) }
本质上就是多了一些是否是类型检查。
//Array func _getElement( _ index: Int, wasNativeTypeChecked : Bool, matchingSubscriptCheck: _DependenceToken ) -> Element { #if _runtime(_ObjC) return _buffer.getElement(index, wasNativeTypeChecked: wasNativeTypeChecked) #else return _buffer.getElement(index) #endif } //ArrayBuffer internal func getElement(_ i: Int, wasNativeTypeChecked: Bool) -> Element { if _fastPath(wasNativeTypeChecked) { return _nativeTypeChecked[i] } return unsafeBitCast(_getElementSlowPath(i), to: Element.self) } internal func _getElementSlowPath(_ i: Int) -> AnyObject { let element: AnyObject if _isNative { _native._checkValidSubscript(i) element = cast(toBufferOf: AnyObject.self)._native[i] } else { element = _nonNative.objectAt(i) } return element } //ContiguousArrayBuffer internal subscript(i: Int) -> Element { get { return getElement(i) } }
在 _buffer
内部的 getElement
, 与 ContiguousArray
不同的是需要适配桥接到 NSArray
的情况,如果是 非NSArray
的情况调用的是 ContiguousArrayBuffer
内部的 subscript
,和 ContiguousArray
相同。
总结
从增删改查来看,不管是 ContiguousArray
还是 Array
最终都是操作内存,稍显区别的就是 Array
需要更多的类型检查。所以当不需要 Objective-C
,还是尽量使用 ContiguousArray
。
下面是对数组中一些批量操作的总结:
-
removeAll
、insert<C>(contentsOf: C, at: Int)
、removeSubrange
:最终调用的是replaceSubrange
-
append<S : Sequence>(contentsOf newElements: S)
和init(repeating repeatedValue: Element, count: Int)
:最终都是操作内存,循环初始化新的内存空间和值。
有什么不正确的地方,欢迎指出。
以上就是本文的全部内容,希望对大家的学习有所帮助,也希望大家多多支持 码农网
猜你喜欢:本站部分资源来源于网络,本站转载出于传递更多信息之目的,版权归原作者或者来源机构所有,如转载稿涉及版权问题,请联系我们。