[Deque] check deque equality with buffer identity

[vanvoorden]

Background

https://github.com/apple/swift-collections/pull/335

Similar to what we added for OrderedDictionary, we can try and optimize our Deque equality checks for the case where two Deque instances point to the same identity.

Unlike OrderedDictionary, our Deque is not implemented on ContiguousArray. We can try and mimic the approach from ContiguousArray here in Deque by checking against the identity of the underlying ManagedBufferPointer instance.

---

Changes

From:

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

To:

let lhsCount = left.count
if lhsCount != right.count {
  return false
}

// Test referential equality.
if lhsCount == 0 || left._storage.isIdentical(to: right._storage) {
  return true
}

return left.elementsEqual(right)

---

Test Plan

We leverage the existing DequeTests.

---

Open Questions

Are there any additional edge-casey behaviors we should be testing for?

---

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]

Here are benchmarks from running locally.

[lorentey]

Note to self: letting Deque.SubSequence be the default Slice<Deque> means that it can't conform to Equatable/Hashable, and that is probably a defect in the Standard Library.

[lorentey]

@swift-ci test

[vanvoorden]

@lorentey Thanks for reviewing!