May 16th, 2022

How can I synthesize a C++20 three-way comparison from two-way comparisons?

Raymond Chen

The C++20 three-way comparison operator <=> (commonly nicknamed the spaceship operator due to its appearance) compares two items and describes the result. It’s called the three-way comparison because there are five possible results: less, equal, equivalent, greater, and unordered.

Yeah, the name is kind of weird.

It’s called the three-way comparison because in other languages, the equivalent operator has three possible results: less, equal, and greater. C++20 expands the set of possible results but kept the old name. (Sound familiar?)

Ordering	Results
strong ordering	less	equal	equivalent	greater
weak ordering	less	equivalent		greater
partial ordering	less	equivalent		greater	unordered

Each of the orderings can convert to the one below it, using the conversions given by the chart.

The strong ordering distinguishes between items being equal (identical and interchangeable) and equivalent (not interchangeable but close enough for some purpose). For example, two instances of the same string "hello" are equal, in that they represent the same string and are fully interchangeable. On the other hand, two people with the same security clearance are equivalent from a security perspective (they have access to the same things), but they are not equal (they are nevertheless different people).

When sorting, you are usually interested in equivalence, but when searching you might be interested in equality. (I’m looking for Bob, not just anybody with the same security clearance as Bob.)

Suppose you have an object from a class library that predates C++20 and doesn’t support three-way comparison. You want your code to be able to take advantage of the three-way comparison should the library be updated but fall back to two-way comparison in the meantime. In other words, you want to take advantage of three-way comparison if available.

Fortunately, you don’t have to write all that SFINAE nonsense, because somebody else has done it for you: std::tuple.

Tuples have the bonus property of supporting the three-way comparison operator, even if the underlying types do not. In the case where they do not, they will synthesize a three-way comparison from the two-way comparisons.

if `a < b`	return `less`
else if `a > b`	return `greater`
otherwise	return `equivalent`

So we can just wrap the objects inside a std::tuple and compare the tuples. To avoid unnecessary copies, we can wrap them as references, or use forward_as_tuple which always uses references.

std::weak_ordering
compare_3way_via_tuple(T const& a, T const& b)
{
    return std::forward_as_tuple(a) <=>
           std::forward_as_tuple(b);
}

It turns out that there’s already a pre-made function that does something very similar: std::compare_weak_order_fallback also synthesize a missing three-way comparison, but it uses a different algorithm from tuples:

if `a == b`	return `equivalent`
else if `a < b`	return `less`
otherwise	return `greater`

Tuples use a different algorithm from std::compare_weak_order_fallback. Which one is better? Why are they different?

I suspect that tuples use a different algorithm because tuple ordering comes from C++11, which predates three-way comparison. Back in those days, the comparison operators was used mostly for sorting and other ordered-sequence type algorithms. And those algorithms require only that the objects support the < operator. Therefore, tuples have to make do with only the < operator.

On the other hand, std::compare_weak_order_fallback was born into the world of three-way comparisons, so it has more liberty to take dependencies on things beyond just the < operator.

If you know that the underlying object supports ==, then my guess is that std::compare_weak_order_fallback is better, because == testing tends to be faster than < testing. For example, comparing two strings for equality can short-circuit if the strings are different lengths. This shortcut is not available for less-than comparison.

Author

Raymond Chen

Raymond has been involved in the evolution of Windows for more than 30 years. In 2003, he began a Web site known as The Old New Thing which has grown in popularity far beyond his wildest imagination, a development which still gives him the heebie-jeebies. The Web site spawned a book, coincidentally also titled The Old New Thing (Addison Wesley 2007). He occasionally appears on the Windows Dev Docs Twitter account to tell stories which convey no useful information.

7 comments

Discussion is closed. Login to edit/delete existing comments.

Sort by :

Newest

Newest Popular Oldest

紅樓鍮 May 16, 2022 · Edited 0

Comparing two s for equality can also be a single SIMD operation if both strings are short, assuming that short string optimization applies mandatorily, that is sufficiently aligned, and that bytes that do not currently hold live s are kept 0 (or any other invariant value, maybe). Similarly, equality comparison for non-short strings can also be effectively SIMD-accelerated if heap allocation for is both sufficiently aligned and subject to the same zero-padding...
Read more
Comparing two std::strings for equality can also be a single SIMD operation if both strings are short, assuming that short string optimization applies mandatorily, that std::string is sufficiently aligned, and that bytes that do not currently hold live chars are kept 0 (or any other invariant value, maybe). Similarly, equality comparison for non-short strings can also be effectively SIMD-accelerated if heap allocation for std::string is both sufficiently aligned and subject to the same zero-padding invariant (at least in the last SIMD word that holds at least one live char).

Bonus chatter: Consequently, comparing std::string_views has the potential to be vastly more inefficient than comparing std::strings, because std::string_view loses both alignment and padding information completely.

Bonus bonus chatter: On a second thought, apparently comparison for less-than can also be SIMD-accelerated, subject to the same memory alignment and zero-padding requirements, if the processor supports comparison of unsigned integers in big endian.

Read less
- Adam Rosenfield May 18, 2022 · Edited 0
  
  The assumption that non-live chars are kept at 0 is not going to be valid. That would require e.g. the `resize()` and `erase()` methods to zero out data past the end-of-string when shrinking a string. Even without that assumption, though, it'd still be possible to have a SIMD-accelerated implementation, but you'd just need a bit of extra logic to handle that edge case, which would reduce the performance a bit.
  
  Microoptimizing string comparison is...
  Read more
  The assumption that non-live chars are kept at 0 is not going to be valid. That would require e.g. the `resize()` and `erase()` methods to zero out data past the end-of-string when shrinking a string. Even without that assumption, though, it’d still be possible to have a SIMD-accelerated implementation, but you’d just need a bit of extra logic to handle that edge case, which would reduce the performance a bit.
  
  Microoptimizing string comparison is a complex task. If you look at the glibc implementation of strcmp(), it’s over 2000 lines of optimized assembly to handle all of the different edge cases, using SIMD when possible.
  
  Read less
- Sukru Tikves May 16, 2022 0
  
  You’d need to compare a lot of strings to need these kinds of micro optimizations.
  
  By then, you would probably use some sort of indexing, and hashing mechanism to avoid string comparisons anyway.
Stuart Ballard May 16, 2022 · Edited 0
There's clearly a tradeoff of performance vs accuracy here, but wouldn't the most you really want would be

<code>

From my limited understanding of C++ which mainly comes from following Raymond's blog and being fascinated by programming language design, I would guess you could use templates to automatically add a spaceship operator to any type that has == and > operators. Is that possible, or is there a language rule that prevents it?

Read more
There’s clearly a tradeoff of performance vs accuracy here, but wouldn’t the most you really want would be
```
bool is_partial = false; // Indicates whether to return equivalent or unordered if no comparison operator returns true

if (a == b) {
  return equal;
} else if (a > b) {
  return greater;
} else if (b > a) { // Account for the possibility of no operator <
  return less;
} else {
  return is_partial ? unordered : equivalent;
}
```
From my limited understanding of C++ which mainly comes from following Raymond’s blog and being fascinated by programming language design, I would guess you could use templates to automatically add a spaceship operator to any type that has == and > operators. Is that possible, or is there a language rule that prevents it?
Read less
- 紅樓鍮 May 16, 2022 0
  
  …you could use templates to automatically add a spaceship operator to any type that has == and > operators.
  
  My understanding is that Raymond wants to use an existing operator<=> if it’s available, or live with the old comparison operators otherwise. If an operator<=> already exists, redefining it would be an error.
  - Stuart Ballard May 17, 2022 0
    
    Ahh, I was imagining it like C#, where it's often possible for multiple implementations of the same thing to exist and the compiler will choose the most specific match. I thought it would be perfectly allowable for a definition from a template to co-exist with one on the type itself, and that the compiler would prefer the latter when it exists.
    
    Could SFINAE be used to make the template only valid on types that don't already...
    Read more
    Ahh, I was imagining it like C#, where it’s often possible for multiple implementations of the same thing to exist and the compiler will choose the most specific match. I thought it would be perfectly allowable for a definition from a template to co-exist with one on the type itself, and that the compiler would prefer the latter when it exists.
    
    Could SFINAE be used to make the template only valid on types that don’t already have a spaceship operator?
    
    Read less
  - 紅樓鍮 May 17, 2022 0
    Ah, if you mean a blanket definition of
    
    template <typename T> std::weak_ordering operator<=>(const T &, const T &) requires { /* ... */ };
    
    then I guess yeah, it is possible.