内容字号:默认大号超大号

段落设置:段首缩进取消段首缩进

字体设置:切换到微软雅黑切换到宋体

回答<Array到底是什么 - Swift标准库源码导读 (三)>之练习

2018-06-08 18:44 出处:清屏网 人气: 评论(0

喵神在这篇文章中对于Array进行了导读,并且留下了一些关于Array的练习,因为本人对于swift的source code也颇感兴趣,所以试着回答一下这些练习,以及我对于Array的补充。

Array

先模仿喵神的风格,分析一下 Array 的结构。

Array 也有一个 _buffer 成员,不过和 ContiguousArray 不同的是,它的类型是 _ArrayBuffer

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) 成立的情况,因为我想大多数还是在mac或者ios下做开发的。

Array 的大部分操作也是委托给 _buffer ,所以让我们看看 _ArrayBuffer 到底是什么东东。

_ArrayBuffer

_ArrayBuffer 也只有一个成员: _storage ,类型是 _ArrayBridgeStorage ,这个 _ArrayBridgeStorage 其实是一个typealias:

internal typealias _ArrayBridgeStorage = _BridgeStorage<_ContiguousArrayStorageBase, _NSArrayCore>

_ArrayBridgeStorage 的作用是保存当前Array的存储策略, Array有两种存储策略可以选择:ContiguousArray和NSArray。那让我们继续深入到 _BridgeStorage

_BridgeStorage

不管你是用哪个存储方式,在_BridgeStorage中都会转换成 Builtin.BridgeObject 来保存:

var rawValue: Builtin.BridgeObject

它还提供了一些方法,例如,判断当前是用哪种存储策略等。这个对象的作用就是提供一个统一的接口给上层对象来使用,用来屏蔽这种不同存储策略的差异。

那么整个Array的结构图大致如下:

Copy-On-Write

这里只分析和ContiguousArray的不同之处。

检查引用是否唯一的时候,ArrayBuffer要比ContiguousArrayBuffer复杂一点:

ContiguousArrayBuffer

internal mutating func isUniquelyReferenced() -> Bool {
    return _isUnique(&_storage)
}

ArrayBuffer

internal mutating func isUniquelyReferenced() -> Bool {
    if !_isClassOrObjCExistential(Element.self) {
      return _storage.isUniquelyReferenced_native_noSpareBits()
    }

    if !_storage.isUniquelyReferencedNative() {
      return false
    }

    return _isNative
}

这里要注意的是,因为 isUniquelyReferencedNative 背后和 isKnownUniquelyReferenced 一样都是调用Builtin的 isUnique 方法,所以如果当前保存的buffer是NSArray的话,永远返回的是false。也就是说,第一次的append,remove等操作,会生成一个新的ContiguousArrayBuffer,并把内容copy过去。

开始回答喵神的问题~

性能

在和喵神交流了之后,这是喵神的观点:

嘛…这个主要是 struct 的话很多东西就可以 inline..比如属性访问什么的。reference 的话就还要去 heap 上找…

我完全同意喵大的观点。。。,不过我还发现了另外一个原因,如果你调用比如说Array的Count方法,然后生成相应的sil后,你会发现当Array保存的类型不同,生成的sil是不同的。

Count方法的代码:

return _fastPath(_isNative) ? _native.count : _nonNative.count

如果保存类型是value type的话,sil的代码会直接忽略对于buffer类型的判断,直接执行_native.count部分的代码,但是如果类型是refrence type的话,就完全对应整个代码,会多出很多代码用来判断buffer的类型。

我想原因有可能是因为如果类型是value type的话,生成sil的时候,编译器可以肯定buffer类型是contiguousArrayBuffer。

不过就像喵神说的,这些细枝末节没必要弄的这么清楚,平时工作用不到的,这也只是我个人的爱好,大家不要像我一样,2333

Array的sort

简单来说swift用的是introSort,论文在 这里 ,先上代码:

if elements.distance(from: range.lowerBound, to: range.upperBound) < 20 {
    _insertionSort(&elements, subRange: range)
    return
}

if depthLimit == 0 {
    _heapSort(&elements, subRange: range)
    return
}

let partIdx: C.Index =  _partition(&elements, subRange: range)
_introSortImpl(&elements, subRange: range.lowerBound..<partIdx, depthLimit: depthLimit &- 1)
_introSortImpl(&elements, subRange: partIdx..<range.upperBound, depthLimit: depthLimit &- 1)

因为对于数量比较少的情况,插入排序性能会比较好,所以这里swift定了一个阀值:20,(如果我记的没错的话,java的阀值是47),元素数量低于这个阀值的时候就用插入排序。

根据论文,swift这里还限制了递归的层数,这就是depthLimit的作用,这个参数的值在代码中是:

2*floor(log(N))

如果到达了最大的层数,就用堆排序;否则就是标准的Middle-of-Three快速排序。

至于算法的细节,大家可以结合论文和代码,应该还是比较清晰的。

桥接的性能

就像喵神说的,如果当元素类型不是 class 或者 @ objc 协议时,桥接的性能是O(n),代码在ArrayBuffer中,如下:

/// Convert to an NSArray.
  ///
  /// O(1) if the element type is bridged verbatim, O(*n*) otherwise.
  
    // FIXME(abi): Used from tests
  internal func _asCocoaArray() -> _NSArrayCore {
    return _fastPath(_isNative) ? _native._asCocoaArray() : _nonNative
  }

可以从代码中看到,如果当前buffer是NSArray的话,那么直接返回就可以了。

反之的情况下,会调用ContiguousArrayBuffer的_asCocoaArray方法:

internal func _asCocoaArray() -> _NSArrayCore {
    if count == 0 {
      return _emptyArrayStorage
    }
    if _isBridgedVerbatimToObjectiveC(Element.self) {
      return _storage
    }
    return _SwiftDeferredNSArray(_nativeStorage: _storage)
}
这里先要提一下

NSArrayCore协议,swift为了能够桥接的同时又保持和Foundation module之间没有过多的依赖,所以创建了一个ShadowProtocols.swift文件,这个文件中定义了各种所谓的shadow protocol,比如说这个_NSArrayCore,它就是定义了一些和NSArray方法名相同的核心操作。

从代码中可以看到,如果类型是class或者@ objc的话,直接返回

storage,它也是符合_NSArrayCore的,如果不是,返回的是一个_SwiftDeferredNSArray类型,正如这个类型的名字所表明的,这里swift用了lazy loading的优化手段,当你访问这个数组中的元素的时候,它才会去做真正的桥接工作,例如:
(objectAtIndex:)
internal func objectAt(_ index: Int) -> AnyObject {
    return withUnsafeBufferOfObjects {
      objects in
      _precondition(
        _isValidArraySubscript(index, count: objects.count),
        "Array index out of range")
      return objects[index]
    }
}

所以关键的是这个withUnsafeBufferOfObjects方法,我精简了代码:

// If we've already got a buffer of bridged objects, just use it
if let bridgedStorage = _heapBufferBridged {
    // do something
}
// If elements are bridged verbatim, the native buffer is all we need, so return that.
else if let buf = _nativeStorage._withVerbatimBridgedUnsafeBuffer({ $0 }) {
    // do something
}
else {
    // Create buffer of bridged objects.
    let objects = _nativeStorage._getNonVerbatimBridgedHeapBuffer()
}

_getNonVerbatimBridgedHeapBuffer方法就是做了这么一个事:

for i in 0..<count {
      (resultPtr + i).initialize(to: _bridgeAnythingToObjectiveC(p[i]))
}

这就是为什么这类桥接需要O(n)的复杂度的原因。

还补充一点的就是,不管是从NSArray还是NSMutableArray转换到Array,swift都是copy一下,所以这也就是为什么我之前说的,在做一些操作前,先要生成一个ContiguousArrayBuffer,把copy得到的NSArray的内容,copy到新的buffer中。


分享给小伙伴们:
本文标签: ArraySwift

相关文章

发表评论愿您的每句评论,都能给大家的生活添色彩,带来共鸣,带来思索,带来快乐。

CopyRight © 2015-2016 QingPingShan.com , All Rights Reserved.

清屏网 版权所有 豫ICP备15026204号