Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

[SR-14062] Array copy on write triggered unnecessarily #56451

Open
swift-ci opened this issue Jan 17, 2021 · 5 comments
Open

[SR-14062] Array copy on write triggered unnecessarily #56451

swift-ci opened this issue Jan 17, 2021 · 5 comments
Labels
Array Area → standard library: The `Array` type bug A deviation from expected or documented behavior. Also: expected but undesirable behavior. compiler The Swift compiler in itself COW Feature: Copy-On-Write support performance standard library Area: Standard library umbrella

Comments

@swift-ci
Copy link
Collaborator

swift-ci commented Jan 17, 2021

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
Copy link
Collaborator Author

Comment by Michael D. Morris (JIRA)

Is this related to SR-11452?

@swift-ci
Copy link
Collaborator Author

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
Copy link

@swift-ci create

@swift-ci swift-ci transferred this issue from apple/swift-issues Apr 25, 2022
@boclair
Copy link

boclair commented Mar 7, 2023

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
Copy link

boclair commented Mar 8, 2023

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

    }
  }

@AnthonyLatsis AnthonyLatsis added standard library Area: Standard library umbrella Array Area → standard library: The `Array` type COW Feature: Copy-On-Write support labels Mar 13, 2023
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Labels
Array Area → standard library: The `Array` type bug A deviation from expected or documented behavior. Also: expected but undesirable behavior. compiler The Swift compiler in itself COW Feature: Copy-On-Write support performance standard library Area: Standard library umbrella
Projects
None yet
Development

No branches or pull requests

4 participants