[Pitch #2] Add `isKnownIdentical` Method for Quick Comparisons to `Equatable`

[vanvoorden (Rick van Voorden)]

@tera

I'd like to see a convincing example where one would like to use a custom isKnownIdentical hence the question should it be a customisation point to begin with instead of a non-customisable, freestanding, written once and set in stone, memcmp based func isIdentical<T>(_ lhs: T, _ rhs: T) -> Bool.

Hmm… I would maybe start with a comment from the previous pitch:

@lorentey

First, the bitwise equality of two objects does not necessarily imply that they are identical. An object's identity sometimes includes the location of its bits in addition to their value. For example, this is the case for noncopyable synchronization constructs like struct Atomic and struct Mutex -- two distinct atomic integers are never identical, even if at some point they both happen to have the same integer value, i.e., their storage consists of the same bits. Some Swift types are not bitwise comparable.

(This can also go in the other way. Two semantically identical Swift values can sometimes differ in their bit patterns due to padding bytes whose values are unspecified and can vary. In general, raw bitwise equality can be used neither to deny nor confirm that two Swift objects are identical.)

I do want to mostly keep this pitch review "out of the weeds" on tactical discussion over implementation details… but it could also be relevant to consider a "case study" specifically as an example of when a library maintainer might want or need a custom isKnownIdentical that is not memcmp.

One place we could start is our "prior art": the _isIdentical method on String:

stdlib/public/core/String.swift

AFAIK the only stored instance property on String is _guts:

stdlib/public/core/String.swift

But our _isIdentical is not memcmp over _guts… it's actually comparing value equality over _StringGuts.rawBits:

stdlib/public/core/StringGuts.swift

Which is itself the value of _StringObject.rawBits:

stdlib/public/core/StringObject.swift

But wait… that's the 64-bit version of rawBits. We have a different version of rawBits for 32-bit:

stdlib/public/core/StringObject.swift

Why is all that conditional logic and custom code needed? I have no idea… but I know I don't want to break it.

To go back to our String._isIdentical method… an approach on memcmp would compare the bytes of _StringObject directly without respecting all the work we built on rawBits.

If memcmp on String ever returned a "false positive" — returning true for identity equality when == value equality returns false — that would be considered a bug. If memcmp on String never returned a false positive but did return false negatives — returning false when the existing production logic on _isIdentical returns true — that would not exactly be a "bug"… but it would indicate that our library maintainer does know how to override isKnownIdentical as an impactful and non-trivial improvement over a default implementation on memcmp.

@tera

The above "struct Element" is not quite convincing for me: that in some cases equatable would be as quick as isKnownIdentical is not a show stopper.

I'm not sure what to say… an important opinion of this pitch is that isKnownIdentical must return in constant time and meaningfully faster than value equality. It's trending to a "circular" argument in the sense that I am saying "this is the way" it should be "because the pitch says so"… but that's a strong opinion we are making for now. If a type does not have any ability to answer isKnownIdentical without a comparison equal in effort to normal value equality, then that type should return nil.