[OrderedDictionary] forward ordered dictionary values equality to values property

vanvoorden commented 5 months ago

Background

https://github.com/apple/swift-collections/issues/334

The current implementation of OrderedDictionary.Values.== forwards to Sequence.elementsEqual, which needs to perform a linear-time (O[N]) comparison over both collections.[1]

Since the "backing store" of our OrderedDictionary.Values is a ContiguousArray, we can forward that equality check through to ContiguousArray. If both Values instances point to the same identity, the ContiguousArray implementation will return early from the comparison.[2]

We perform a similar check (against the ContiguousArray) in our implementation of OrderedDictionary.==.[3]

[1] https://github.com/apple/swift/blob/main/stdlib/public/core/SequenceAlgorithms.swift#L319-L336 [2] https://github.com/apple/swift/blob/main/stdlib/public/core/ContiguousArray.swift#L1318-L1321 [3] https://github.com/apple/swift-collections/blob/main/Sources/OrderedCollections/OrderedDictionary/OrderedDictionary%2BEquatable.swift#L20-L22

Changes

We migrate from:

public static func ==(left: Self, right: Self) -> Bool {
  left.elementsEqual(right)
}

We migrate to:

public static func ==(left: Self, right: Self) -> Bool {
  left._base._values == right._base._values
}

Test Plan

Two new tests are added:

OrderedDictionaryValueTests.test_values_getter_equal
OrderedDictionaryValueTests.test_values_getter_not_equal

Checklist

[x] I've read the Contribution Guidelines
[x] My contributions are licensed under the Swift license.
[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 (if appropriate).
[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 unexplained benchmark regressions.
[ ] I've updated the documentation if necessary.

vanvoorden commented 5 months ago

@swift-ci test

vanvoorden commented 5 months ago

@ingoem thanks for suggesting the reference equality check!

lorentey commented 5 months ago

@vanvoorden Can you please rebase this PR on top of the release/1.0 branch, rather than main?

I think it would make sense to ship this in the next patch release, rather than having it linger on main indefinitely.

vanvoorden commented 5 months ago

I think it would make sense to ship this in the next patch release, rather than having it linger on main indefinitely.

@lorentey Sounds good. Thanks!

vanvoorden commented 5 months ago

@lorentey Is there a CI job that can run Benchmarks on a diff to detect for regressions or improvements against base?

vanvoorden commented 5 months ago

Here are benchmarks running locally. The reason that OrderedDictionary.== is scaling linearly is because we are waiting on https://github.com/apple/swift-collections/pull/340. Optimizing the OrderedSet equality will optimize this one.

vanvoorden commented 5 months ago

@lorentey Thanks for reviewing!

lorentey commented 5 months ago

@swift-ci test

lorentey commented 5 months ago

(AFAIK, CI runs are still expected to fail on macOS. This is "fine", and it won't block us from landing this.)

apple / swift-collections