“This is my 27th day of participating in the First Challenge 2022. For more details: First Challenge 2022.”

  • This paper mainly introduces the exploration of Array in Swift

1. Array composition

We define an array of numbers and compile it into a SIL file

var number = [1.2.3.4.5.6]

print(number)
Copy the code

Compiling SIL files

The main is to focus on initialization array will call _allocateUninitializedArray method, storage after our values. We can search globally in the source code to get this method:

We’ll find an implementation of this function in arrayShared. swift

@inlinable // FIXME(inline-always)
@inline(__always)
@_semantics("array.uninitialized_intrinsic")
public // COMPILER_INTRINSIC
func _allocateUninitializedArray<Element>(_  builtinCount: Builtin.Word)
    -> (Array<Element>, Builtin.RawPointer) {
  let count = Int(builtinCount)
  if count > 0 {
    // Doing the actual buffer allocation outside of the array.uninitialized
    // semantics function enables stack propagation of the buffer.
    let bufferObject = Builtin.allocWithTailElems_1(
      _ContiguousArrayStorage<Element>.self, builtinCount, Element.self)

    let (array, ptr) = Array<Element>._adoptStorage(bufferObject, count: count)
    return (array, ptr._rawValue)
  }
  // For an empty array no buffer allocation is needed.
  let (array, ptr) = Array<Element>._allocateUninitialized(count)
  return (array, ptr._rawValue)
}
Copy the code

If the current array count is greater than 0, create an empty array. Greater than 0, allocWithTailElems_1 creates a memory space in the heap to hold the elements of the array. Then we create an Array using _adoptStorage. Let’s look at the internal implementation of the _adoptStorage method

 @inlinable
  @_semantics("array.uninitialized")
  internal static func _adoptStorage(
    _ storage: __owned _ContiguousArrayStorage<Element>, count: Int
  ) -> (Array, UnsafeMutablePointer<Element>) {

    let innerBuffer = _ContiguousArrayBuffer<Element>(
      count: count,
      storage: storage)

    return (
      Array(
        _buffer: _Buffer(_buffer: innerBuffer, shiftedToStartIndex: 0)),
        innerBuffer.firstElementAddress)
  }
Copy the code

Create a buffer to store the elements in our array. It then returns a tuple containing the buffer and the first address of the buffer. So we can see that this tuple will return the array we created and the address of the first element of the array. There should be more information before the address of the first element. Here is the conclusion, as shown in the figure:

Here is a brief introduction, the array stores the memory address of a class named _ContiguousArrayStorage, which stores the meta type, reference count, number of elements, capacity size and flag bit, as well as the memory address of the first element.

We use LLDB debugging:

The distribution of our conclusion is also verified through debugging.

2. Array stitching

We usually add to append, number.append(7). Then the array should be expanded, we look at the source code on the implementation of append.

@_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()
  }
Copy the code

We continue to look at the implementation of the _makeUniqueAndReserveCapacityIfNotUnique

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

If the buffer’s storage is uniquely referenced, place the buffer in a mutable state and create a new buffer. We continue to see this _createNewBuffer (bufferIsUnique: minimumCapacity: growForAppend) the implementation of the code is as follows:

/// Copy the contents of the current buffer to a new unique mutable buffer.
  /// The count of the new buffer is set to `oldCount`, the capacity of the
  /// new buffer is big enough to hold 'oldCount' + 1 elements.
  @inline(never)
  @inlinable // @specializable
  internal mutating func _copyToNewBuffer(oldCount: Int) {
    let newCount = oldCount &+ 1
    var newBuffer = _buffer._forceCreateUniqueMutableBuffer(
      countForNewBuffer: oldCount, minNewCapacity: newCount)
    _buffer._arrayOutOfPlaceUpdate(&newBuffer, oldCount, 0)}Copy the code

In this method, it calls the _growArrayCapacity method to expand capacity. Let’s move on to the implementation of _growArrayCapacity

Each expansion is twice the original base. For our array, when it needs to be expanded, we need to double the capacity instead of just expanding the memory we need. In order to prevent the next time to add, we can not expand the capacity, although it may waste some space, but improve the efficiency.