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-13923] Array.removeAll(keepingCapacity: true) wastes time copying memory around when Array is not uniquely referenced #56321

Open
Lukasa opened this issue Nov 30, 2020 · 2 comments

Comments

@Lukasa
Copy link
Contributor

@Lukasa Lukasa commented Nov 30, 2020

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

@Lukasa Lukasa commented Nov 30, 2020

@swift-ci create

@lorentey
Copy link
Member

@lorentey lorentey commented Dec 19, 2020

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.

@swift-ci swift-ci transferred this issue from apple/swift-issues Apr 25, 2022
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Projects
None yet
Development

No branches or pull requests

2 participants