[SR-12524] Straightforward mutating divide-and-conquer algorithms cause COW

[dabrahams]

Previous ID	SR-12524
Radar	rdar://problem/62201732
Original Reporter	@dabrahams
Type	Bug

Additional Detail from JIRA

| | | |------------------|-----------------| |Votes | 1 | |Component/s | Compiler, Standard Library | |Labels | Bug | |Assignee | None | |Priority | Medium | md5: 09efd968f958e93863a1491ba05236db

Issue Description:

The appended program should print "0". Instead it prints "242".

The library was designed so we didn’t have to do the STL thing and pass pairs of iterators (Indexes) around to demarcate subranges we want to operate on. Instead you’re supposed to be able to say:

c[..<i].recursiveMutation()

c[i...].recursiveMutation()

The problem is that this causes COW. It shouldn’t as long as the mutation is only using MutableCollection operations, but it does. ARC needs to borrow ownership for the slicing operation and the mutation, but it does not.

The result is that if you want to write any of these algorithms efficiently, you need to implement algorithms taking pairs of indices, and if you want to build a composable family of generic algorithms, you have to expose these APIs publicly.

extension ArraySlice {
  /// Scramble `self`, returning the number of reallocations due to COW, given
  /// that the storage of `self` was expected to match `expectedFootprint`.
  mutating func scramble(in expectedFootprint: ClosedRange<UnsafePointer<Element>>) -> Int {
    let base = withUnsafeBufferPointer { $0.baseAddress! }
    var reallocations = expectedFootprint.contains(base) ? 0 : 1
    if count < 1 { return reallocations }
    if count < 4 {
      swapAt(startIndex, endIndex - 1)
    }
    else {
      let footprint = base...(base+count)
      let m = (startIndex + endIndex) / 2
      reallocations += self[startIndex..<m].scramble(in: footprint)
      reallocations += self[m..<endIndex].scramble(in: footprint)
    }
    return reallocations
  }

  /// Scramble `self`, returning the number of reallocations due to COW.
  mutating func scramble() -> Int {
    if count < 1 { return 0 }
    let base = withUnsafeBufferPointer { $0.baseAddress! }
    let footprint = base...base + count
    if count < 4 {
      swapAt(startIndex, endIndex - 1)
      return 0
    }
    else {
      let m = (startIndex + endIndex) / 2
      let r0 = self[startIndex..<m].scramble(in: footprint)
      let r1 = self[m..<endIndex].scramble(in: footprint)
      return r0 + r1
    }
  }
}

extension ContiguousArray {
  /// Scramble `self`, returning the number of reallocations due to COW.
  mutating func scramble() -> Int {
    if count < 1 { return 0 }
    let base = withUnsafeBufferPointer { $0.baseAddress! }
    let footprint = base...base + count
    if count < 4 {
      swapAt(startIndex, endIndex - 1)
      return 0
    }
    else {
      let m = (startIndex + endIndex) / 2
      let r0 = self[startIndex..<m].scramble(in: footprint)
      let r1 = self[m..<endIndex].scramble(in: footprint)
      return r0 + r1
    }
  }
}

func test() {
  var a = ContiguousArray(0..<500)
  let reallocs = a.scramble()
  print(reallocs)
}

test()

[dabrahams]

https://github.com/dabrahams/DivideAndConquer demonstrates the bones of a solution. It's not refined, but it appears to work. Probably if we brought back the "pinned" bit it could be better used for this purpose.

[dabrahams]

See also https://forums.swift.org/t/solving-the-mutating-slice-cow-problem/35297

[beccadax]

@swift-ci create