isEmpty vs count == 0

我们需要检查一个数组，集合, 字符串或者是其他的集合类型是空，这在日常开发中是常见的操作之一。之前在oc中会这么判断，我们先排除字符串为nil 或者 null的情况：

- (void)test6{
    NSString *text = @"hello world";
    NSLog(@"%ld",[text length]);

    NSArray *array = @[@"a",@"b",@"c"];
    NSLog(@"%ld",[array count]);
}

2020-06-20 16:32:49.657371+0800 objcTest[99024:8064113] 11
2020-06-20 16:32:49.657554+0800 objcTest[99024:8064113] 3

Swift中的运用

按照以往的习惯我们可能会这么使用

func test(){
        let text = "hello world"
        print("\(text.count)")
        let array = ["a","b","c"]
        print("\(array.count)")
 }
输出：11
输出：3

这么写也是没有一点毛病，但是我们会发现在String系列 以及Array系列都会有个isEmpty属性
在String.Swift中有isEmpty的描述

/// To check whether a string is empty, use its `isEmpty` property instead of
/// comparing the length of one of the views to `0`. Unlike with `isEmpty`,
/// calculating a view's `count` property requires iterating through the
/// elements of the string.

大意就是如果要判断string是否是空，请用isEmpty属性，而不要用count属性，因为这会迭代整个string的元素。
我们知道在Swift中面向协议的思想贯穿始终，我们在Collection协议中找到isEmpty的定义

public protocol Collection: Sequence {
/// A Boolean value indicating whether the collection is empty.
  ///
  /// When you need to check whether your collection is empty, use the
  /// `isEmpty` property instead of checking that the `count` property is
  /// equal to zero. For collections that don't conform to
  /// `RandomAccessCollection`, accessing the `count` property iterates
  /// through the elements of the collection.
  /// - Complexity: O(1)
  var isEmpty: Bool { get }
}

同样是判断空建议用isEmpty ，这里还补充了一下 对于不符合 RandomAccessCollection 协议的类型，count 属性会迭代遍历集合里面的全部元素。

public protocol RandomAccessCollection: BidirectionalCollection
where SubSequence: RandomAccessCollection, Indices: RandomAccessCollection
{
...
  override var startIndex: Index { get }
  override var endIndex: Index { get }
...
}

我们现在只讨论两个典型的类型String和 Array，它们都符合Collection协议。

String的isEmpty、count 比较

先上代码

func test(){
        
        let text = "hello world,coding is happy,so we will going all along"
        let time1 = CFAbsoluteTimeGetCurrent()
        for i in 0..<500000 {
            print("\(text.count == 0) index:\(i)")
        }
        let time2 = CFAbsoluteTimeGetCurrent()
        print("time:\(time2 - time1)")
    }
time:4.98923397064209

func test6(){
        let text = "hello world,coding is happy,so we will going all along"
        let time1 = CFAbsoluteTimeGetCurrent()
        for i in 0..<500000 {
            print("\(text.isEmpty) index:\(i)")
        }
        let time2 = CFAbsoluteTimeGetCurrent()
        print("time:\(time2 - time1)")
    }
time:5.166522026062012

这不对啊，这和Swift源码代码注释说的不大一样啊，两个几乎差不多，甚至isEmpty 比count更加耗时，另外Check if a Swift Array Is Empty: Best Practice Revisited 说的,也是String 建议用isEmpty 来判断是否为空，不然会迭代整个集合的元素来计算。见鬼了，还是去翻翻源码把。

public struct String {
  public // @SPI(Foundation)
  var _guts: _StringGuts

  @inlinable @inline(__always)
  internal init(_ _guts: _StringGuts) {
    self._guts = _guts
    _invariantCheck()
  }
...
}

在StringLegacy.swift 中

extension String {
...
  /// A Boolean value indicating whether a string has no characters.
  @inlinable
  public var isEmpty: Bool {
    @inline(__always) get { return _guts.isEmpty }
  }
}

从这些能知道String的本质是_StringGuts ，String的方法基本都是基于_StringGuts构建的，在_StringGuts中

xtension _StringGuts {
  // The number of code units
  @inlinable @inline(__always)
  internal var count: Int { return _object.count }

  @inlinable @inline(__always)
  internal var isEmpty: Bool { return count == 0 }
...
}

能看出来其实String 的isEmpty 和 count 其实还是一样的，isEmpty的具体实现还是拿count == 0来判断的

暂时结论:在String中，isEmpty 和 count 其实是相同的性能，都是通过迭代集合内元素来计算得出
为啥是暂时结论呢，因为我也不明白为啥文档说String的isEmpty 是O(1)操作 现在看来是O(n)操作。

Array的isEmpty、count 比较（也包含ContiguousArray）

在Collection协议中

public var isEmpty: Bool {
    return startIndex == endIndex
  }

Array.swift中

@inlinable
  public var startIndex: Int {
    return 0
  }
...
/// If the array is empty, `endIndex` is equal to `startIndex`.
  @inlinable
  public var endIndex: Int {
    @inlinable
    get {
      return _getCount()
    }
  }
...
@_semantics("array.get_count")
  internal func _getCount() -> Int {
    return _buffer.immutableCount
  }

immutableCount 是从_ArrayBody里面的count的值取出来的，既然Array 是符合 RandomAccessCollection协议的，count 和 isEmpty 的操作性能几乎一样都是O(1)操作，从哪里得出来的呢，得需要从array的扩容来研究，先从append方法来看

@inlinable
  @_semantics("array.append_element")
  public mutating func append(_ newElement: __owned Element) {
    // Separating uniqueness check and capacity check allows hoisting the
    // uniqueness check out of a loop.
    _makeUniqueAndReserveCapacityIfNotUnique()
    let oldCount = _buffer.mutableCount
    _reserveCapacityAssumingUniqueBuffer(oldCount: oldCount)
    _appendElementAssumeUniqueAndCapacity(oldCount, newElement: newElement)
    _endMutation()
  }

#源码分析
·第一行的函数，看名字表示，如果这个数组不是惟一的，就把它变成惟一的，而且保留数组容量。在Xcode里面搜索一下这个函数：

@inlinable
  @_semantics("array.make_mutable")
  internal mutating func _makeUniqueAndReserveCapacityIfNotUnique() {
    if _slowPath(!_buffer.beginCOWMutation()) {
      _createNewBuffer(bufferIsUnique: false,
                       minimumCapacity: count + 1,
                       growForAppend: true)
    }
  }

/// Returns `true` and puts the buffer in a mutable state iff the buffer's
  /// storage is uniquely-referenced.
  ///
  /// - Precondition: The buffer must be immutable.
  ///
  /// - Warning: It's a requirement to call `beginCOWMutation` before the buffer
  ///   is mutated.
  @_alwaysEmitIntoClient
  internal mutating func beginCOWMutation() -> Bool {
    let isUnique: Bool
    if !_isClassOrObjCExistential(Element.self) {
      isUnique = _storage.beginCOWMutationUnflaggedNative()
    } else if !_storage.beginCOWMutationNative() {
      return false
    } else {
      isUnique = _isNative
    }
#if INTERNAL_CHECKS_ENABLED
    if isUnique {
      _native.isImmutable = false
    }
#endif
    return isUnique
  }

如果数组不是唯一引用的，就会调用_createNewBuffer创建新的数组buffer，假设我们的数组是唯一引用的，这个方法就不会执行 ，咱们继续走
·第二行用一个变量oldCount保存数组当前长度。
·第三行表示：保存数组容量，假如是唯一引用的情况下。之所以做出这样的假设，是因为此前已经调用过_makeUniqueAndReserveCapacityIfNotUnique方法，即使这个数组不是唯一引用，也被复制了一份新的。我们来看看_reserveCapacityAssumingUniqueBuffer方法的实现：

@inlinable
  @_semantics("array.mutate_unknown")
  internal mutating func _reserveCapacityAssumingUniqueBuffer(oldCount: Int) {
    // Due to make_mutable hoisting the situation can arise where we hoist
    // _makeMutableAndUnique out of loop and use it to replace
    // _makeUniqueAndReserveCapacityIfNotUnique that preceeds this call. If the
    // array was empty _makeMutableAndUnique does not replace the empty array
    // buffer by a unique buffer (it just replaces it by the empty array
    // singleton).
    // This specific case is okay because we will make the buffer unique in this
    // function because we request a capacity > 0 and therefore _copyToNewBuffer
    // will be called creating a new buffer.
    let capacity = _buffer.mutableCapacity
    _internalInvariant(capacity == 0 || _buffer.isMutableAndUniquelyReferenced())

    if _slowPath(oldCount + 1 > capacity) {
      _createNewBuffer(bufferIsUnique: capacity > 0,
                       minimumCapacity: oldCount + 1,
                       growForAppend: true)
    }
  }

检查如果oldCount + 1 > capacity 那就说明容量不够了，就需要扩容了，这时候调用_createNewBuffer 方法

@_alwaysEmitIntoClient
  internal mutating func _createNewBuffer(
    bufferIsUnique: Bool, minimumCapacity: Int, growForAppend: Bool
  ) {
    _internalInvariant(!bufferIsUnique || _buffer.isUniquelyReferenced())
    _buffer = _buffer._consumeAndCreateNew(bufferIsUnique: bufferIsUnique,
                                           minimumCapacity: minimumCapacity,
                                           growForAppend: growForAppend)
  }

internal __consuming func _consumeAndCreateNew(
    bufferIsUnique: Bool, minimumCapacity: Int, growForAppend: Bool
  ) -> _ArrayBuffer {
    let newCapacity = _growArrayCapacity(oldCapacity: capacity,
                                         minimumCapacity: minimumCapacity,
                                         growForAppend: growForAppend)
    let c = count
    _internalInvariant(newCapacity >= c)
    
    let newBuffer = _ContiguousArrayBuffer<Element>(
      _uninitializedCount: c, minimumCapacity: newCapacity)

    if bufferIsUnique {
      // As an optimization, if the original buffer is unique, we can just move
      // the elements instead of copying.
      let dest = newBuffer.firstElementAddress
      dest.moveInitialize(from: mutableFirstElementAddress,
                          count: c)
      _native.mutableCount = 0
    } else {
      _copyContents(
        subRange: 0..<c,
        initializing: newBuffer.mutableFirstElementAddress)
    }
    return _ArrayBuffer(_buffer: newBuffer, shiftedToStartIndex: 0)
  }

另外提下：在_consumeAndCreateNew方法中, _growArrayCapacity 方法里面做了对容量的处理

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

@_alwaysEmitIntoClient
internal func _growArrayCapacity(
  oldCapacity: Int, minimumCapacity: Int, growForAppend: Bool
) -> Int {
  if growForAppend {
    if oldCapacity < minimumCapacity {
      // When appending to an array, grow exponentially.
      return Swift.max(minimumCapacity, _growArrayCapacity(oldCapacity))
    }
    return oldCapacity
  }
  // If not for append, just use the specified capacity, ignoring oldCapacity.
  // This means that we "shrink" the buffer in case minimumCapacity is less
  // than oldCapacity.
  return minimumCapacity
}

当旧的数组容量小于minimumCapacity的时候，minimumCapacity就是oldCount + 1,这时候容量的扩容其实是呈指数增长，每次扩容，旧的容量就翻两倍。
同时也解释了append方法不是线程安全的，如果在某一个线程中插入新元素，导致了数组扩容，那么Swift会创建一个新的数组（意味着地址完全不同）。然后ARC会为我们自动释放旧的数组，但这时候可能另一个线程还在访问旧的数组对象。

初始化新的newBuffer 用_ContiguousArrayBuffer构造器 同时对数组storageHeader进行初始化

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

数组storage起始于_ArrayBody，结束于连续的数组元素 , _ArrayBody主要是描述当前array 的信息同理ContiguousArray也是，此时数组count ，capacity等都会到_ArrayBody 对象里；
取count最终我们会追踪到

internal var count: Int {
    get {
      return _storage.countAndCapacity.count
    }
    nonmutating set {
      _internalInvariant(newValue >= 0)

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

      mutableStorage.countAndCapacity.count = newValue
    }
  }

我们会直接从countAndCapacity(_ArrayBody类型）里面取出count，操作为O(1),另外array的isEmpty是根据startIndex endIndex是否相等来判断的，endIndex 取值就是取count，所以对于array 这些服从RandomAccessCollection协议的类型来说，isEmpty 和 count == 0 判断是一模一样的，都是O(1)操作。

总结：

1.String 的isEmpty 和 count==0判断效率是一样的，并不像想象中 count==0 会迭代集合里面的全部元素 O(n)。
2.Array这些符合RandomAccessCollection协议的类型同样，isEmpty 和 count==0判断效率是一样的 O(1)。
3.另外呢对于数据量大的数组，注意数据过大导致指数级增长的扩容带来的性能消耗。
4.数组的变更注意如果不是唯一引用的情况，要注意线程安全处理，因为会摧毁旧的数组，创建扩容两倍长度于旧数组的新数组，把旧数组的元素拷贝过来，再把元素插入到新数组中，会形成新的数组地址。

参考资料：
官方文档
Check if a Swift Array Is Empty: Best Practice Revisited
Swift数组扩容原理