[SR-13923] Array.removeAll(keepingCapacity: true) wastes time copying memory around when Array is not uniquely referenced

[Lukasa]

Previous ID	SR-13923
Radar	rdar://problem/71809690
Original Reporter	@Lukasa
Type	Bug

Environment

Apple Swift version 5.3.1 (swiftlang-1200.0.43 clang-1200.0.32.8)

Additional Detail from JIRA

Votes	0
Component/s	Standard Library
Labels	Bug, Performance
Assignee	None
Priority	Medium

md5: 724c0c846234a1ede0885d027c480e99

Issue Description:

Here's a simple (and stupid) Swift program:

@inline(never)
func workIt(_ array: [Int]) -> Int {
    var elements = array
    elements.removeAll(keepingCapacity: true)
    var count = 0
    for element in elements {
        count += element
    }

    return count
}

func main() {
    let base = Array(repeating: 1, count: 100_000)
    var superCount = 0
    for _ in 0..<100_000 {
        superCount += workIt(base)
    }
    if superCount != 0 {
        fatalError()
    }
}

main()

This program is mostly noise to prevent the optimiser from killing the program, but at its root it allocates a big Array and then calls workIt in a loop. workIt makes a copy of the array, removes all the elements from it (keeping capacity), and then iterates the (now empty) array and does some math.

When run under time profiler in Instruments this program spends all of its time (and it is a noticeable amount of time) in memmove. This is because the implementation of Array.removeAll(keepingCapacity🙂 is pessimistic for keepingCapacity=true:

  @inlinable
  public mutating func removeAll(keepingCapacity keepCapacity: Bool = false) {
    if !keepCapacity {
      _buffer = _Buffer()
    }
    else {
      self.replaceSubrange(indices, with: EmptyCollection())
    }
  }

replaceSubrange is extremely general, and so it keeps the contents of the Array as it is. This means, if the Array is not uniquely referenced, it wastes its time copying over the entire contents of the buffer, which it then promptly throws away.

[Lukasa]

@swift-ci create

[lorentey]

The same optimization opportunity also applies on most other Array mutations – AFAIR currently they all guarantee uniqueness as a standalone step before performing the mutation. In most cases it would make much more sense to fall back to generating a new Array instance directly, rather than copying the existing one then mutating the copy.

The tradeoff here is that adding a new code path roughly doubles the code size of these operations, which may have unintended consequences. Still, this is definitely something we should try fixing.