[SR-14062] Array copy on write triggered unnecessarily

[swift-ci]

Previous ID	SR-14062
Radar	rdar://problem/73287154
Original Reporter	snicolai (JIRA User)
Type	Bug

Environment

MacOS: 10.15.7 (19H114)

Xcode: Version 12.3 (12C33)

Additional Detail from JIRA

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

md5: 63b050d6dfe63db61b5377327e1483ab

Issue Description:

From: https://forums.swift.org/t/why-is-array-copy-on-write-getting-triggered-in-this-code/43914

class Bug {
  var a = Array(repeating: -1, count: 1_000_000)
  func buggy()  {
    a[2] = a[1]
  }

  func workaround() {
    let t = a[1]
    a[2] = t
  }
}

public func triggerBug() {
  let c = Bug()
  for _ in 1...10_000  {
    c.buggy()
  }

  print("Buggy Done")
}

public func useWorkaround() {
  let c = Bug()
  for _ in 1...10_000 {
    c.workaround()
  }
  
  print("Workaround Done")  
}

triggerBug()  
useWorkaround()

Profiling this gives:

Weight Self Weight Symbol Name  
6.27 s 99.4% 0 s main  
6.27 s 99.4% 0 s triggerBug()  
6.21 s 98.5% 0 s Bug.buggy()  
6.21 s 98.5% 0 s specialized Array.subscript.modify  
6.21 s 98.5% 0 s specialized Array.\_makeMutableAndUnique()  
6.21 s 98.5% 1.00 ms specialized Array.\_createNewBuffer(bufferIsUnique:minimumCapacity:growForAppend🙂  
6.20 s 98.4% 0 s specialized \_ArrayBuffer.\_copyContents(subRange:initializing🙂  
6.20 s 98.4% 0 s specialized \_ContiguousArrayBuffer.\_copyContents(subRange:initializing🙂  
6.20 s 98.4% 0 s specialized UnsafeMutablePointer.initialize(from:count🙂  
6.20 s 98.4% 6.20 s \_platform_memmove$VARIANT$Haswell  
3.00 ms 0.0% 0 s specialized \_ContiguousArrayBuffer.init(\_uninitializedCount:minimumCapacity🙂  
3.00 ms 0.0% 0 s specialized \_ContiguousArrayBuffer.init(\_uninitializedCount:minimumCapacity🙂  
2.00 ms 0.0% 0 s swift_allocObject  
2.00 ms 0.0% 0 s swift_slowAlloc  
2.00 ms 0.0% 0 s malloc  
2.00 ms 0.0% 0 s malloc_zone_malloc  
2.00 ms 0.0% 2.00 ms default_zone_malloc  
1.00 ms 0.0% 0 s \_swift_stdlib_malloc_size  
1.00 ms 0.0% 0 s malloc_size  
1.00 ms 0.0% 1.00 ms szone_size_try_large  
1.00 ms 0.0% 1.00 ms swift_release  
1.00 ms 0.0% 1.00 ms swift_retain  
47.00 ms 0.7% 0 s \_swift_release_dealloc  
37.00 ms 0.5% 3.00 ms free_large  
34.00 ms 0.5% 34.00 ms madvise  
3.00 ms 0.0% 0 s swift_deallocClassInstance  
3.00 ms 0.0% 0 s objc_destructInstance  
2.00 ms 0.0% 2.00 ms objc_object::sidetable_clearDeallocating()  
1.00 ms 0.0% 1.00 ms \_object_remove_assocations  
3.00 ms 0.0% 3.00 ms *ContiguousArrayStorage.*\_deallocating_deinit  
2.00 ms 0.0% 1.00 ms free  
1.00 ms 0.0% 1.00 ms szone_size_try_large  
1.00 ms 0.0% 0 s \<Unknown Address\>  
1.00 ms 0.0% 1.00 ms szone_size_try_large  
1.00 ms 0.0% 1.00 ms large_entry_for_pointer_no_lock  
5.00 ms 0.0% 0 s Bug.\_\_allocating_init()  
5.00 ms 0.0% 0 s Bug.init()  
5.00 ms 0.0% 0 s specialized Array.init(repeating:count🙂  
5.00 ms 0.0% 0 s specialized UnsafeMutablePointer.initialize(to🙂  
5.00 ms 0.0% 5.00 ms \_platform_bzero$VARIANT$Haswell  
3.00 ms 0.0% 0 s Bug.buggy()  
3.00 ms 0.0% 2.00 ms swift_endAccess  
1.00 ms 0.0% 1.00 ms pthread_getspecific  
1.00 ms 0.0% 1.00 ms swift_release  
1.00 ms 0.0% 0 s Bug.buggy()  
1.00 ms 0.0% 1.00 ms swift_beginAccess  
1.00 ms 0.0% 1.00 ms swift_bridgeObjectRelease  
1.00 ms 0.0% 0 s useWorkaround()  
1.00 ms 0.0% 0 s Bug.\_\_allocating_init()  
1.00 ms 0.0% 0 s Bug.init()  
1.00 ms 0.0% 0 s specialized Array.init(repeating:count🙂  
1.00 ms 0.0% 0 s specialized UnsafeMutablePointer.initialize(to🙂  
1.00 ms 0.0% 1.00 ms \_platform_bzero$VARIANT$Haswell

Note that the buggy version takes 6.27 seconds on my machine, and the workaround takes 1 ms.

Filed with Feedback Assistant as: FB8972901

[swift-ci]

Comment by Michael D. Morris (JIRA)

Is this related to SR-11452?

[swift-ci]

Comment by Steve Nicolai (JIRA)

I think SR-11452 is different, this one seems to be related to having the same array on both sides of the equals sign, which is triggering the copy on write mechanism inside the array code unnecessarily. SR-11452 seems to involve an inout scalar integer.

[typesanitizer]

@swift-ci create

[boclair]

I hit this same issue when creating a min-heap class in swift. The implementation of which does several swaps in an array:

(arr[index1], arr[index2]) = (arr[index2], arr[index1])

or

let val1 = arr[index1]
arr[index1] = arr[index2]
arr[index2] = val1

both do way too many copy-on-writes, and actually makes the code 5000x slower :-\

let val1 = arr[index1]
let val2 = arr[index2]
arr[index1] = val2
arr[index2] = val1

fixes the problem. Or an UnsafeMutablePointer<> instead of an array, or passing the array by inout reference to a function that then does either of the above "swap" modifications. This was very unexpected and makes me sad.

[boclair]

And because maybe I'm a little too obsessed with this issue, here are some metrics on an array of size 10,000 doing repeats = 100,000 swaps. Some comparisons when run with swift -O:

• using arrRef and swapAt : [Int] - 0.8msec / [Obj] - 3.5msec
• using arrRef and 1 pair : [Int] - 0.4msec / [Obj] - 3.2msec
• using arrRef and 2 pairs: [Int] - 0.5msec / [Obj] - 5.6msec
• using arrRef and verbose: [Int] - 0.4msec / [Obj] - 5.6msec
• using self.arr and swapAt : [Int] - 1.6msec / [Obj] - 3.8msec
• using self.arr and 1 pair : [Int] - 159.0msec / [Obj] - 15600.0msec
• using self.arr and 2 pairs: [Int] - 1.5msec / [Obj] - 8.2msec
• using self.arr and verbose: [Int] - 1.4msec / [Obj] - 6.9msec

As you can see using self.arr hits the copy-on-write bug, and is especially bad when the array is of a simple object and not just an Int. (The simple object is just a class with an Int member.)

Sample code with arrRef:

   func swapsTestUsingReference(_ arrRef: inout [T], _ repeats: Int) {
    let size = arrRef.count
    for i in 0..<repeats {
      let index1 = i % size
      let index2 = (i + 1) % size
      
      // using swapAt
      //arrRef.swapAt(index1, index2)
      
      // using 1 pair
      //(arrRef[index1], arrRef[index2]) = (arrRef[index2], arrRef[index1])
      
      // using 2 pairs
      // let (v1, v2) = (arrRef[index1], arrRef[index2]);
      // (arrRef[index2], arrRef[index1]) = (v1, v2);

      // using verbose
      //let v1 = arrRef[index1]
      //let v2 = arrRef[index2]
      //arrRef[index2] = v1
      //arrRef[index1] = v2

    }
  }