tertiary results of compiler-generated comparison operators

60 views
Skip to first unread message

Arno Schoedl

unread,
May 19, 2015, 3:00:05 AM5/19/15
to

Hello,

there as been some discussion recently about default compiler-generated
comparison operators, for example automatically generating operator< for
structs.

For total orders, often (hierarchical comparisons, strings, etc.) a
tertiary result (< or > or ==) can be generated for only a little more
runtime effort than a binary result (< or >=).

It would be a shame if any compiler generated comparisons would not expose
such tertiary result, because one would need to either manually implement
them or resort to the inefficiency of two calls to <.

For efficiency, any compiler-generated function should also be able to
internally use custom tertiary comparisons.

Arno


--
[ comp.std.c++ is moderated. To submit articles, try posting with your ]
[ newsreader. If that fails, use mailto:std-cpp...@vandevoorde.com ]
[ --- Please see the FAQ before posting. --- ]
[ FAQ: http://www.comeaucomputing.com/csc/faq.html ]

Öö Tiib

unread,
May 21, 2015, 10:30:05 PM5/21/15
to

On Tuesday, 19 May 2015 10:00:05 UTC+3, Arno Schoedl wrote:
> there as been some discussion recently about default compiler-generated
> comparison operators, for example automatically generating operator< for
> structs.

I feel it is an attractively sounding idea that unfortunately fits
only for too rare corner cases when:
1) all the data members of class are regular and totally ordered
2) all the data members matter for ordering of whole object
3) the data members matter exactly in their order in class

Most limiting constraint is 3) since order of members has already
several (not too well known) effects and it may make the class
that uses default 'operator<' fragile to maintain. 3 scenarios:

Testing shows that a state of a member depends (somewhat) on
state of other member but is constructed before (or destroyed
after). That causes some issue in some corner case and maintainer
moves it after to fix it and behavior of 'operator<' silently
changes.

Stress tests show that the objects take lot of memory. Maintainer
rearranges some members to reduce alignment-induced caps between
those and behavior of 'operator<' silently changes.

Performance measurements show that there are cache misses because
two members that are often used together are located far from each
other in object. Maintainer moves them closer and behavior of
'operator<' silently changes.

> For total orders, often (hierarchical comparisons, strings, etc.) a
> tertiary result (< or > or ==) can be generated for only a little more
> runtime effort than a binary result (< or >=).

For that we should first standardize some spaceship operator '<=>'
in C++ (like in Groovy, Ruby, PHP, Perl) or some member 'compare'.
It has been likely proposed before. How it went?

For me most puzzling is ... where to use it? The infrastructure for
three way comparison (besides 'qsort' of C) seems to be is missing
in C++. C++ does not have three way 'if's or the like; all sorted
containers use predicate; all ordering or searching algorithms
use predicate. So it would be something that does not fit with rest
of the language.

What little there is in C++ I have only observed it confusing novices
with things like:

if ( str1.compare("confusion") )
{
// ... no confusion?
}

> It would be a shame if any compiler generated comparisons would not expose
> such tertiary result, because one would need to either manually implement
> them or resort to the inefficiency of two calls to <.

You must elaborate where and how the inefficiency is measured. 'std::sort'
that uses predicate is in average about 25% quicker than 'qsort' that
uses three-way comparators. You need motivating examples otherwise it
is hard to understand.

The only simplification AFAIK that three-way comparison brings is
easiness of building further three-way comparisons for composites
whose order depends on components that have three way comparisons.
However you suggest that compiler should anyway make those so where
to use them?

> For efficiency, any compiler-generated function should also be able to
> internally use custom tertiary comparisons.

That is already jumping into technical details of implementation.
Reply all
Reply to author
Forward
0 new messages