Unexpected swapAt free/malloc overhead

gnuoyd · October 11, 2020, 11:10pm

I have a program that performs many swapAt(::) calls on an
Array, where Memo is a class I define. In principle, it seems
that when swapAt returns, the Memos that change place should never have
a different number of references than when swapAt began. I had hoped
that the compiler would infer the constancy of the reference counts and
emit no retains or releases. However, my performance profile shows
swapAt calling retain and release, malloc and free.

I have a couple of questions about this:

Can I give a hint in my source code that will help the compiler to avoid
needless retains/releases in swapAt?

I am building my project with swift run -c release Records .... It is
my understanding that -c release will enable optimization. (I have
also tried -Xswiftc -O---no difference.) Can I use a higher level of
optimization that will eliminate unnecessary retains and releases?

Dave

Lantua · October 12, 2020, 12:55am

FWIW, it should be using this one–swift/MutableCollection.swift at 53bdffd120c41fa0a9810612d4df3ac6310fa911 · apple/swift · GitHub. I don't think array rolls its own implementation.

lukasa · October 13, 2020, 7:06am

I’m afraid this is a known limitation of swapAt. With that said I can’t find a bugs.swift.org covering this, so you should file it, but I definitely know that I know this problem and that the Swift performance team know about it.

Karl · October 13, 2020, 2:24pm

You may be able to avoid these by dropping down to UnsafeMutableBufferPointer.

You shouldn’t have to, of course, and I hope you file a bug report, but it may help you work-around the issue for now.

gnuoyd · October 13, 2020, 9:46pm

Thanks for the info. I will file a bug.

Should I expect similar code to be generated for a value type as for
a reference type? I ask because I have found a way to use a value
type instead of a reference type as my Array's Element, however, the
unexpected retain/release and malloc/free still appear in my profile.

Dave

lukasa · October 14, 2020, 6:46am

What does the value type contain? Some value types are class-backed, which means they still require retains/releases. This applies to any standard library type that is variable-size, e.g. String, Array, Dictionary, Set.

gnuoyd · October 21, 2020, 2:03am

The value type contains value types.

Last week I stepped through some of the assembly for swapAt and for
the subscript "get", and it looks like the compiler may have emitted
code that is applicable both to value types and to reference types.
Is that something the compiler will do? Can a value type have no-op
retain/release methods?

Details:

The value type is Proxy. Proxy and its dependencies:

struct Proxy : Comparable {
let idx: Int
let key: T.Key
static func <(_ l: Self, _ r: Self) -> Bool {
return l.key < r.key
}
static func ==(_ l: Self, _ r: Self) -> Bool {
return l.key == r.key
}
}

public protocol KeyComparable {
associatedtype Key : Comparable
var key : Key { get }
}

extension Memo : KeyComparable {
struct Key : Comparable {
let position: Position
let priority: Cost
static func <(_ l: Key, _ r: Key) -> Bool {
if l.priority == r.priority {
return l.position.l < r.position.l
}
return l.priority < r.priority
}
static func ==(_ l: Key, _ r: Key) -> Bool {
return l.priority == r.priority &&
l.position.l == r.position.l
}
}
final var key: Key {
return Key(position: position, priority: priority)
}
}

public typealias Cost = Int

struct Position {
let l, r: Int
init(_ l: Int, _ r: Int) {
self.l = l
self.r = r
}
init(_ p: (l: Int, r: Int)) {
self.l = p.l
self.r = p.r
}
static func +(_ p: Position, _ q: (Int, Int)) -> Position {
return Position(p.l + q.0, p.r + q.1)
}
}

BTW, Memo is a class. Maybe I am missing something, but I don't
think any references to a Memo should appear in Proxy.

Dave

lukasa · October 21, 2020, 5:35am

Is Proxy generic? Your code suggests it should be (there appears to be a generic type parameter T), but it doesn’t seem to actually be. I guess Memo is generic?

Is the swapAt code in the same module as the definition of these types?

gnuoyd · October 24, 2020, 1:50am

Is Proxy generic? Your code suggests it should be (there appears to be a generic type parameter T), but it doesn’t seem to actually be. I guess Memo is generic?

Proxy is generic: the key property has type T.Key. Memo is not generic.

Is the swapAt code in the same module as the definition of these types?

Memo is in a different module than the swapAt code.

As an experiment, I put most of the code into the same module. That
yields a >4x improvement on my main test case. Very good.

Maybe inter-modular optimization is not one of SPM's strong suits? Or
is there some option flag I can use that makes it try harder?

Dave

lukasa · October 24, 2020, 7:04am

Today Swift basically does no cross module optimisation. There are some ways to influence this, and some flags are coming to SwiftPM to do more, but they are limited in scope for now. This is why you still saw retains/releases: the compiler emitted unspecialised code, and that unspecialised code needs to handle arbitrary possibilities.

You can arrange for the compiler to specialise the swapAt code using @inlinable, or pass the -cross-module-optimisation flag which may help (it only enables optimisation in limited scenarios).

Jens · October 25, 2020, 4:25am

In general, whenever I have to try and see if some performance critical piece of Swift code can be optimized, I'll find that the profile is dominated by ARC-related stuff that the optimizer hasn't been able to eliminate. Getting rid of it, by rewriting the code in various non-pretty ways, often makes the code run tens or even hundreds of times faster, which makes you wonder:

What % of an average app's energy consumption is due to needless retain/release/free/malloc?
How much energy (every day around the world) is spent on this?

(These questions are of course equally or more relevant when replacing "ARC-related stuff" with "not completely/ideally optimized code in general resulting from any programming language", but anyway.)

hassila · June 14, 2021, 5:19pm

@gnuoyd did you file a bug? I encountered a similar issue and would like to append to the same issue in that case (just the Malloc/free, as it was a value type):

github.com/apple/swift-collections

Add a priority queue implementation built on top of `Heap`

apple:main ← AquaGeek:priority-queue

opened 09:38PM - 28 May 21 UTC

AquaGeek

+724 -20

### Description This introduces a double-ended `PriorityQueue` as discussed i…n #3. ### Detailed Design `Heap` (a min-max heap) is used as the storage. One of the big advantages of using a min-max heap is that we don't need to bifurcate into a min heap or max heap and keep track of which kind is used — you can pop min or max, as needed. The main difference between `Heap` and `PriorityQueue` is that the latter separates the value from the comparable priority of it. This is useful in cases where a type doesn't conform to `Comparable` directly but it may have a property that does — e.g. `Task.priority`. It also keeps track of insertion order, so dequeueing of elements with the same priority should happen in FIFO order. ```swift public struct PriorityQueue<Value, Priority: Comparable> { public typealias Element = (value: Value, priority: Priority) public var isEmpty: Bool public var count: Int // Initializers public init() public init<S: Sequence>(_ elements: S) where S.Element == Element public init(arrayLiteral elements: Element...) public init(dictionaryLiteral elements: (Value, Priority)...) // Mutations/querying public mutating func insert(_ value: Value, priority: Priority) public func min() -> Value? public func max() -> Value? public mutating func popMin() -> Value? public mutating func popMax() -> Value? public mutating func removeMin() -> Value public mutating func removeMax() -> Value } ``` ### To-Do - [x] Merge @AmanuelEphrem's `Sequence` conformance - [x] Reformat the code to match the 2 space indent/80 char width style - [x] Optimize `_indexOfChildOrGrandchild(of:sortedUsing:)` (probably by splitting it back out into 2 separate functions) - [x] Chase down [suggestion from @timvermeulen](https://github.com/apple/swift-collections/pull/51#discussion_r651145630) about skipping nodes that have children - [x] Figure out if `@inlinable` is required - [x] Add checks for heap invariants - [x] Make a call on whether or not we want to [add `removeMin/Max`](https://github.com/apple/swift-collections/pull/51#discussion_r651089847) - [x] Make `_minMaxHeapIsMinLevel` an instance method - [x] Merge @hassila's changes to make `_bubbleUpMin(startingAt:)` and `_trickleDown(startingAt:)` iterative instead of recursive - [X] Add implementation of `insert(contentsOf:)` - [X] Rebase this on top of the `Heap` implementation merged into `main` ### Future Directions - Add support for merging two priority queues - Add `replaceMin` and `replaceMax` ### Documentation The public APIs have largely been documented. An overview document has been added to the Documentation directory. ### Testing There are unit tests for the added `PriorityQueue` type. ### Performance Performance tests have been added. @lorentey has a PR up (#76) which adds a `std::priority_queue` benchmark — it would be interesting to compare against that with more complex types. We may want to revisit the library JSON to ensure we have the desired comparisons defined. ### Source Impact This is purely additive. No existing APIs were changed, deprecated, or removed. ### Checklist - [X] I've read the [Contribution Guidelines](/README.md#contributing-to-swift-collections) - [X] My contributions are licensed under the [Swift license](https://swift.org/LICENSE.txt). - [X] I've followed the coding style of the rest of the project. - [X] I've added tests covering all new code paths my change adds to the project (to the extent possible). - [X] I've added benchmarks covering new functionality (if appropriate). - [X] I've verified that my change does not break any existing tests or introduce unexpected benchmark regressions. - [X] I've updated the documentation (if appropriate).

gnuoyd · June 14, 2021, 5:23pm

No, I don't think I filed a bug.

Dave

hassila · June 14, 2021, 6:40pm

Thanks, then I’ll try to whittle down a case for it.

hassila · June 15, 2021, 8:44am

I created [SR-14778] Standard Library swapAt: creates transient memory allocations for small value types · Issue #57128 · apple/swift · GitHub for the swapAt: issue.