Uploaded image for project: 'Swift'
  1. Swift
  2. SR-12524

Straightforward mutating divide-and-conquer algorithms cause COW

    XMLWordPrintable

    Details

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

        Attachments

          Activity

            People

            Assignee:
            Unassigned
            Reporter:
            dabrahams Dave Abrahams
            Votes:
            1 Vote for this issue
            Watchers:
            8 Start watching this issue

              Dates

              Created:
              Updated: