C++ Logo

sg12

Advanced search

Re: [ub] Justification for < not being a total order on pointers?

From: Chandler Carruth <chandlerc_at_[hidden]>
Date: Mon, 26 Aug 2013 09:57:48 -0700
On Mon, Aug 26, 2013 at 9:27 AM, Gabriel Dos Reis <gdr_at_[hidden]>wrote:

> Nevin Liber <nevin_at_[hidden]> writes:
>
> | On 26 August 2013 11:00, Jeffrey Yasskin <jyasskin_at_[hidden]> wrote:
> |
> |
> | Could someone explain why we need to allow operator<(T*) to be a
> non-order?
> |
> |
> | It comes from C. I believe it comes from the days of segmented
> architectures.
>
> You're right. Historically, it came from segmented architectures.
>
> However, because it has been in the standard for that long, some
> implementations may have taken advantage of that semantics restriction
> even if they are not targeting segmented architecture.


Also, there are now uses of segmented addressing outside of segmented
architectures.

The interesting thing is that it remains possible (and unsurprisingly
possible) to implement a total ordering for all addresses. It just means
that this ordering may be marginally more complex than a single integer
comparison on some architectures. I think this is a fine requirement to
place on them. In all cases where the segment is known to be the same (the
overwhelming majority), any reasonable implementation will produce the same
code as today.


> So, it is not
> the case that because we don't have wide spread architecture anymore
> means that removing that restriction is a breeze. It will invalidate
> implementations that use compilation and program transformations based
> on that.
>

I actually do not believe there is any such optimization or implementation
today. I'm not aware of even theoretical optimizations that really benefit
from this.

The freedom that optimizing compilers very deeply need is that the ordering
be totally unspecified. Preserving the relative order of two object's
addresses is a very high bar (much higher than *providing* some relative
order) and would impede many real world optimizations.

So long as we keep this, I have no knowledge of significant negative
impacts on optimizing compilers. If you have other specific optimizations,
please bring them up (clearly, I'm not familiar with all optimizing
compilers! ;])


> If you make operator< a total order for all valid pointers (and
> including the usual one-past-the-end pointers), I suspect you might also
> as a by-product impose a stronger requirement on operator== on pointers.
>

This is actually my only real concern, and could well be addressed by a
careful and thorough paper on the subject.

Received on 2013-08-26 18:57:50