[OrderedSet] forward ordered set equality to elements property by vanvoorden · Pull Request #340 · apple/swift-collections

vanvoorden · 2023-12-09T04:34:33Z

Background

Similar to OrderedDictionary, we can forward our OrderedSet equality checks down to the ContiguousArray instance to take advantage of early return when both arrays point to the same identity (no need to perform a linear comparison over all elements).

A side-effect of this optimization is we also optimize OrderedDictionary.==, which performs an equality check on the keys property (which is an OrderedSet).[1]

[1] https://github.com/apple/swift-collections/blob/main/Sources/OrderedCollections/OrderedDictionary/OrderedDictionary%2BEquatable.swift#L20-L22

Changes

From:

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

To:

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

We can also migrate OrderedSet.SubSequence. From:

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

To:

public static func ==(left: Self, right: Self) -> Bool {
  left._base._elements[left._bounds] == right._base._elements[right._bounds]
}

Test Plan

Five new tests are added:

OrderedSetTests.test_equal
OrderedSetTests.test_not_equal
OrderedSetTests.test_equal_elements
OrderedSetTests.test_subsequence_equality
OrderedSetTests.test_subsequence_not_equality

Checklist

I've read the Contribution Guidelines
My contributions are licensed under the Swift license.
I've followed the coding style of the rest of the project.
I've added tests covering all new code paths my change adds to the project (if appropriate).
I've added benchmarks covering new functionality (if appropriate).
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 · 2023-12-11T23:21:17Z

Here's what the benchmarks look like running locally.

vanvoorden · 2023-12-11T23:25:14Z

Here are more benchmarks running locally.

lorentey

Great catch again -- we'll definitely want to have this change. 👍

I think I found a correctness issue, though; it also indicates that we should do another pass on the test additions, to improve coverage. 🤔 I commented some suggested changes. (Beware that I haven't tried them, though. 😛)

Sources/OrderedCollections/OrderedSet/OrderedSet+SubSequence.swift

Tests/OrderedCollectionsTests/OrderedSet/OrderedSetTests.swift

Co-authored-by: Karoy Lorentey <klorentey@apple.com>

vanvoorden · 2023-12-12T22:01:01Z

Tests/OrderedCollectionsTests/OrderedSet/OrderedSetTests.swift

+  func test_subsequence_not_equality() {
+    let c = 5
+    let items1 = OrderedSet(0 ..< c)
+    let items2 = OrderedSet(0 ..< c)
+    withEvery("i", in: 0 ..< c) { i in
+      let leftSlice = items1[0 ..< i]
+      expectNotEqual(items1[0 ..< c], leftSlice)  //  same identity
+      expectNotEqual(items2[0 ..< c], leftSlice)  //  different identity
+
+      let rightSlice = items1[i + 1 ..< c]
+      expectNotEqual(items1[0 ..< c], rightSlice) //  same identity
+      expectNotEqual(items2[0 ..< c], rightSlice) //  different identity
+    }
+  }


@lorentey I confirmed that this test "broke" on the previous equality check with the bug.

lorentey

This looks ready! 👍

lorentey · 2023-12-13T00:18:11Z

@swift-ci test

…v1.0.6 (#822) This PR contains the following updates: | Package | Type | Update | Change | |---|---|---|---| | [com_github_apple_swift_collections](https://togithub.com/apple/swift-collections) | http_archive | patch | `1.0.5` -> `1.0.6` | --- ### Release Notes <details> <summary>apple/swift-collections (com_github_apple_swift_collections)</summary> ### [`v1.0.6`](https://togithub.com/apple/swift-collections/releases/tag/1.0.6): Swift Collections 1.0.6 [Compare Source](https://togithub.com/apple/swift-collections/compare/1.0.5...1.0.6) This bugfix release adds `Sendable` conformances to all public types (fixing compatibility with Swift's strict concurrency checking), and speeds up equality checks (`==`) of identical collection values. ##### What's Changed - Fix typos: OrderedSet Documentation by [@kati-kms](https://togithub.com/kati-kms) in [https://github.com/apple/swift-collections/pull/322](https://togithub.com/apple/swift-collections/pull/322) - \[1.0] build: support building in Debug mode on Windows by [@compnerd](https://togithub.com/compnerd) in [https://github.com/apple/swift-collections/pull/337](https://togithub.com/apple/swift-collections/pull/337) - build: tweak search path for embedding by [@compnerd](https://togithub.com/compnerd) in [https://github.com/apple/swift-collections/pull/338](https://togithub.com/apple/swift-collections/pull/338) - \[OrderedDictionary] forward ordered dictionary values equality to values property by [@vanvoorden](https://togithub.com/vanvoorden) in [https://github.com/apple/swift-collections/pull/335](https://togithub.com/apple/swift-collections/pull/335) - \[OrderedSet] forward ordered set equality to elements property by [@vanvoorden](https://togithub.com/vanvoorden) in [https://github.com/apple/swift-collections/pull/340](https://togithub.com/apple/swift-collections/pull/340) - \[Deque] check deque equality with buffer identity by [@vanvoorden](https://togithub.com/vanvoorden) in [https://github.com/apple/swift-collections/pull/341](https://togithub.com/apple/swift-collections/pull/341) - \[OrderedDictionary] Fix usage of deprecated API in index(forKey:) docs by [@lorentey](https://togithub.com/lorentey) in [https://github.com/apple/swift-collections/pull/342](https://togithub.com/apple/swift-collections/pull/342) - \[1.0] Backport Sendable conformances on all public types by [@lorentey](https://togithub.com/lorentey) in [https://github.com/apple/swift-collections/pull/343](https://togithub.com/apple/swift-collections/pull/343) - OrderedSet: Fix sendable conformance on old swifts by [@lorentey](https://togithub.com/lorentey) in [https://github.com/apple/swift-collections/pull/346](https://togithub.com/apple/swift-collections/pull/346) - Update CMake configuration by [@lorentey](https://togithub.com/lorentey) in [https://github.com/apple/swift-collections/pull/347](https://togithub.com/apple/swift-collections/pull/347) ##### New Contributors - [@kati-kms](https://togithub.com/kati-kms) made their first contribution in [https://github.com/apple/swift-collections/pull/322](https://togithub.com/apple/swift-collections/pull/322) - [@vanvoorden](https://togithub.com/vanvoorden) made their first contribution in [https://github.com/apple/swift-collections/pull/335](https://togithub.com/apple/swift-collections/pull/335) **Full Changelog**: apple/swift-collections@1.0.5...1.0.6 Thank you to everyone who contributed to this release! </details> --- ### Configuration 📅 **Schedule**: Branch creation - At any time (no schedule defined), Automerge - At any time (no schedule defined). 🚦 **Automerge**: Enabled. ♻ **Rebasing**: Whenever PR is behind base branch, or you tick the rebase/retry checkbox. 👻 **Immortal**: This PR will be recreated if closed unmerged. Get [config help](https://togithub.com/renovatebot/renovate/discussions) if that's undesired. --- - [ ] If you want to rebase/retry this PR, check this box --- This PR has been generated by [Renovate Bot](https://togithub.com/renovatebot/renovate).  Co-authored-by: Self-hosted Renovate Bot <361546+cgrindel-self-hosted-renovate[bot]@users.noreply.github.enterprise.com>

forward ordered set equality to elements property

3caf13b

vanvoorden requested a review from lorentey as a code owner December 9, 2023 04:34

ordered set equality benchmarks

90d31f5

forward ordered set subsequence equality to elements property

e2b033c

add set equality tests

edb431e

vanvoorden mentioned this pull request Dec 12, 2023

[OrderedDictionary] forward ordered dictionary values equality to values property #335

Merged

7 tasks

updated set equality tests

ba88bca

lorentey requested changes Dec 12, 2023

View reviewed changes

Sources/OrderedCollections/OrderedSet/OrderedSet+SubSequence.swift Outdated Show resolved Hide resolved

Tests/OrderedCollectionsTests/OrderedSet/OrderedSetTests.swift Outdated Show resolved Hide resolved

lorentey added this to the 1.0.6 milestone Dec 12, 2023

lorentey added the OrderedCollections OrderedSet and OrderedDictionary label Dec 12, 2023

vanvoorden and others added 4 commits December 12, 2023 11:38

test through ordered set subsequences

88404c3

Co-authored-by: Karoy Lorentey <klorentey@apple.com>

ordered set bounds equality check

9430147

Co-authored-by: Karoy Lorentey <klorentey@apple.com>

update ordered set subsequence tests

0031fc7

remove ordered set print statements

00ccf9a

vanvoorden requested a review from lorentey December 12, 2023 20:31

vanvoorden added 2 commits December 12, 2023 12:33

ordered set fix compiler error

e37e505

clean up ordered set equality test

525bb54

vanvoorden commented Dec 12, 2023

View reviewed changes

lorentey approved these changes Dec 13, 2023

View reviewed changes

lorentey merged commit 8b8a14f into apple:release/1.0 Dec 13, 2023

Provide feedback

Saved searches

Use saved searches to filter your results more quickly

[OrderedSet] forward ordered set equality to elements property#340

[OrderedSet] forward ordered set equality to elements property#340
lorentey merged 11 commits intoapple:release/1.0from
vanvoorden:vanvoorden/ordered-set-equality

vanvoorden commented Dec 9, 2023 •

edited

Loading

Uh oh!

vanvoorden commented Dec 11, 2023

Uh oh!

vanvoorden commented Dec 11, 2023

Uh oh!

lorentey left a comment

Uh oh!

Uh oh!

Uh oh!

vanvoorden Dec 12, 2023

Uh oh!

lorentey left a comment

Uh oh!

lorentey commented Dec 13, 2023

Uh oh!

Reviewers

Assignees

Labels

Projects

Milestone

Development

Uh oh!

2 participants

Conversation

vanvoorden commented Dec 9, 2023 • edited Loading Uh oh! There was an error while loading. Please reload this page.

Uh oh!

Background

Changes

Test Plan

Checklist

Uh oh!

vanvoorden commented Dec 11, 2023

Uh oh!

vanvoorden commented Dec 11, 2023

Uh oh!

lorentey left a comment

Choose a reason for hiding this comment

Uh oh!

Uh oh!

Uh oh!

vanvoorden Dec 12, 2023

Choose a reason for hiding this comment

Uh oh!

lorentey left a comment

Choose a reason for hiding this comment

Uh oh!

lorentey commented Dec 13, 2023

Uh oh!

Reviewers

Assignees

Labels

Projects

Milestone

Development

Uh oh!

2 participants

vanvoorden commented Dec 9, 2023 •

edited

Loading