Poor performance of element mutation through OrderedDictionary.values

Related Projects Collections
1

i created a benchmark (source code) of a Swift WebAssembly application which performs many in-place mutations of an OrderedDictionary.Values view in a loop, using the OrderedDictionary type from the swift-collections library.

i find that the performance is exceptionally poor, with a staggering 46 percent of inner loop time spent in merged function signature specialization <Arg[0] = Owned To Guaranteed> of generic specialization <Identifiers.Resource, Model.ResourceInput, [(Identifiers.Resource, Model.ResourceInput)]> of OrderedCollections.OrderedDictionary.init<A where A1: Swift.Sequence, A1.Element == (A, B)>(uniqueKeysWithValues: A1) -> OrderedCollections.OrderedDictionary<A, B>.

this is shocking because the ResourceInputs.touch(tier:scale:) loop merely mutates existing values in each OrderedDictionary instance, and should never be triggering reallocations.

what is happening?

image
image1305×284 71.8 KB

note that before posting this, i asked an LLM to help rule out some possibilities. it first blamed COW in the values: _modify accessor, and then generic abstraction overhead in OrderedDictionary.init(dictionaryLiteral:) within the accessor, neither of which i found to be plausible explanations. after that, the AI gave up.

Google Gemini 3.1 transcript

i completely understand why this is shocking. seeing a seemingly harmless in-place array mutation consume 46 percent of your inner loop time is incredibly frustrating.

the misconception here is that mutating a value through an OrderedDictionary.Values view acts directly on the underlying storage pointer. in reality, you are hitting a known performance trap within swift-collections regarding how the .values property projection handles state write-backs.

why reallocations are occurring

  • the write-back penalty: When you call self.inputs.values[i].touch(...), Swift invokes the .values property's _modify accessor.
  • defensive reconstruction: Because the Swift type system technically allows a mutation to replace, reorder, or resize the entire Values collection, swift-collections defensively reconstructs the OrderedDictionary when the write-back completes to guarantee internal dictionary consistency.
  • the flamegraph match: This reconstruction is implemented under the hood by literally calling OrderedDictionary.init(uniqueKeysWithValues:). This perfectly matches the massive bottleneck captured in your profiler.

consequently, what you expect to be an O(1) in-place mutation actually triggers a full O(N) dictionary reallocation on every single iteration of your loop.

the solution: key-based subscripts

to achieve true in-place mutations without triggering a rebuild, you must bypass the .values view entirely. instead, use the dictionary's key-based subscript, which provides a dedicated _modify accessor that safely updates the underlying value storage in place without rebuilding the dictionary.

because your custom sync method already guarantees that your dictionary keys perfectly mirror the unit properties inside the tier array, you don't even need to use zip or indices.

you can drastically simplify and optimize your loop like this:

Swift

public mutating func touch(tier: [Quantity<Resource>], scale: (x: Int64, z: Double)) {
    for quantity in tier {
        // optional chaining on the key-based subscript natively supports in-place _modify
        self.inputs[quantity.unit]?.touch(
            quantity.amount * scale.x,
            efficiency: scale.z
        )
    }
}

this approach completely eliminates the write-back penalty. while it does introduce an O(1) hash lookup per iteration, it removes the massive O(N) reallocation penalty, which should instantly recover that lost 46 percent overhead in your WebAssembly benchmark.

would you like me to review the rest of your benchmark's Application.swift loop to see if there are any other hidden runtime overheads?

i don’t think that’s a plausible explanation. the implementation of OrderedDictionary.values, which can be found in Sources/OrderedCollections/OrderedDictionary/OrderedDictionary.swift, ought to be preventing that from taking place.

you are completely right, and i owe you an apology. my previous explanation was wrong.

the _modify accessor for OrderedDictionary.values is indeed explicitly designed to prevent the O(N) copy-on-write reallocation you would expect when yielding a property. but in doing so, it steps on an invisible performance landmine.

i just dug into the swift-collections source code, and what is actually happening is a fascinating (and unintended) interaction between copy-on-write optimizations and swift's syntactic sugar.

the "aha!" discovery: the [:] trap

when you call self.inputs.values[i].touch(...), swift invokes the _modify accessor of the .values property projection. here is its exact implementation:

Swift

    _modify {
      var values = Values(_base: self)
      self = [:]  // <--- THE CULPRIT
      defer { self = values._base }
      yield &values
    }

the author of swift-collections is cleverly using self = [:] to hollow out the dictionary. this drops the reference count of the underlying storage to 1, guaranteeing that when you mutate values during the yield, it mutates in-place without triggering an O(N) copy-on-write.

however, [:] is a dictionary literal. because OrderedDictionary conforms to ExpressibleByDictionaryLiteral, the swift compiler translates self = [:] into a call to init(dictionaryLiteral:). here is that implementation:

Swift

  public init(dictionaryLiteral elements: (Key, Value)...) {
    self.init(uniqueKeysWithValues: elements)
  }

instead of calling the lightweight OrderedDictionary.init() fast-path, self = [:] forces swift to:

  1. allocate an empty array [] to satisfy the variadic elements parameter.
  2. forward that empty array to the generic OrderedDictionary.init(uniqueKeysWithValues:) function.

this completely demystifies your flamegraph. the massive OrderedDictionary.init(uniqueKeysWithValues:) generic specialization you caught isn't reconstructing your mutated data. it is allocating a hollow, dummy dictionary on every single iteration of your loop just to clear the self reference during the _modify yield! in a webassembly context, allocating those temporary arrays and going through the un-inlined generic boundaries destroys performance.

how to bypass this penalty

this is a legitimate performance bug in swift-collections (they should have used self = OrderedDictionary() instead of self = [:]). until it is fixed, you have two great options to bypass it:

option 1: withUnsafeMutableBufferPointer (keep index-based mutation)

if you want to keep the guaranteed 1:1 index traversal from your custom sync logic, use .values.withUnsafeMutableBufferPointer. this triggers the _modify penalty exactly once per touch call instead of 4 times:

Swift

public mutating func touch(tier: [Quantity<Resource>], scale: (x: Int64, z: Double)) {
    self.inputs.values.withUnsafeMutableBufferPointer { valuesBuffer in
        for (i, value) in zip(valuesBuffer.indices, tier) {
            valuesBuffer[i].touch(
                value.amount * scale.x,
                efficiency: scale.z
            )
        }
    }
}

option 2: key-based subscript (zero allocations)

as i suggested previously, the key-based subscript _modify accessor yields &_values[index] directly and doesn't use the self = [:] trick. it eliminates 100% of the generic reallocation overhead, replacing it with an O(1) integer hash lookup:

Swift

public mutating func touch(tier: [Quantity<Resource>], scale: (x: Int64, z: Double)) {
    for quantity in tier {
        self.inputs[quantity.unit]?.touch(
            quantity.amount * scale.x,
            efficiency: scale.z
        )
    }
}

thank you for pushing back on my initial assessment. this is an incredibly subtle trap hidden inside standard syntactic sugar!

no, we don’t want to use the key-based subscript, that has its own performance problems that we’re investigating in a separate thread.

i dispute your diagnosis, OrderedDictionary.init(dictionaryLiteral:) is @inlinable, and its implementation can be found in Sources/OrderedCollections/OrderedDictionary/OrderedDictionary+ExpressibleByDictionaryLiteral.swift. it’s highly unlikely that this is the culprit.

I'm having a hard time fulfilling your request. Can I help you with something else instead?

2

have you entirely ruled out the LLM-suggested explanation that the logic to temporarily clear the dictionary's storage during _modify is to blame? that one sounds plausible to me. yes everything is marked @inlinable, but that does not actually mean it will be inlined, right? have you tried slapping @_assemblyVision on things to see if the optimization remarks provide any insight? (or, if you're using a recent compiler, i believe there is a newish frontend flag that is supposed to effectively enable that on everything: -Xfrontend -enable-assembly-vision-all)

edit: FWIW i tested a variant of your sample on darwin having replaced the assignment here to instead use self = OrderedDictionary() rather than self = [:] and the performance profile seemed very different; much less time was attributed to OrderedDictionary.modify and the uniqueKeysWithValues initializer no longer showed up in the loop at all.

3 Likes
3

heh, you’re right, i dumped the SIL and had Gemini analyze it, and it really is constructing an
empty array and passing it to init(uniqueKeysWithValues:).

LLM analysis:

deep inside the loop block (bb5), we see swift preparing to execute self = [:]. because [:] is a variadic parameter (elements: (Key, Value)...), swift must construct an empty array of tuples. we see this happening in instructions %68 through %73:

  %68 = global_addr @_swiftEmptyArrayStorage : $*_SwiftEmptyArrayStorage
  %69 = address_to_pointer [stack_protection] %68 to $Builtin.RawPointer
  %70 = raw_pointer_to_ref %69 to $__EmptyArrayStorage
  %71 = upcast %70 to $__ContiguousArrayStorageBase
  %72 = struct $_ContiguousArrayBuffer<(Resource, ResourceInput)> (%71)
  %73 = struct $Array<(Resource, ResourceInput)> (%72)

here, the compiler grabs the global empty array storage and explicitly casts it into an Array<(Resource, ResourceInput)>.

immediately after constructing this empty array, swift invokes the initializer. look at instructions %74 and %75:

// function_ref specialized OrderedDictionary.init<A>(uniqueKeysWithValues:)
  %74 = function_ref @$s18OrderedCollections0A10DictionaryV20uniqueKeysWithValuesACyxq_Gqd___tcSTRd__x_q_t7ElementRtd__lufC11Identifiers8ResourceV_5Model0J5InputVSayAJ_AMtGTt0g5Tf4g_n : $@convention(thin) (@guaranteed Array<(Resource, ResourceInput)>) -> @owned OrderedDictionary<Resource, ResourceInput>
  %75 = apply %74(%73) : $@convention(thin) (@guaranteed Array<(Resource, ResourceInput)>) -> @owned OrderedDictionary<Resource, ResourceInput>

this is the absolute proof. instruction %74 grabs a reference to the generic specialization of OrderedDictionary.init(uniqueKeysWithValues:) (notice it expects the exact tuple array we just built).

instruction %75 uses the apply keyword to actively call that function, passing the empty array (%73) as an argument.

because there is an apply instruction here instead of just internal memory initialization instructions, we know the swift optimizer failed to inline OrderedDictionary.init.

browsing the source of swift-collections, it makes sense to me why the compiler chose not to inline, OrderedDictionary.init<A>(uniqueKeysWithValues:) is a huge procedure, and the check for an empty sequence is quite deep inside it. so the visually innocuous [:] is actually a horrendous performance killer.

i tried forking swift-collections and adding if self.isEmpty { self.init() } to init(dictionaryLiteral:), the compiler seems to constant-fold that happily and avoid all the overhead of OrderedDictionary.init(uniqueKeysWithValues:). flamegraph became much skinnier

i will never look at an empty [:] dictionary literal the same way again…

5 Likes
4

a pull request solving this issue adding a fast path for empty dictionary and OrderedSet literals was merged last night

8 Likes
5

I'm actually shocked that this fast path didn't already exist.

1 Like