making comparison operators for pointers well-defined

[Brian Bi]

Forgive me, I'm sure this has been asked before.

A well-known fact is that the result of comparing pointers is unspecified unless they point into the same array or into the same complete object, but std::less<T*> is nonetheless guaranteed to provide a strict total order even if the built-in < operator for T* does not.

Why can't we just change the standard so that the built-in < operator for T* also provides a strict total order? It would take about 5 minutes to write up a paper, which is why I'm sure it would have been done by now if there wasn't a good reason not to.

--

Brian Bi

[Thiago Macieira]

On Monday, 18 June 2018 13:36:39 PDT Brian Bi wrote:
> Why can't we just change the standard so that the built-in < operator for
> T* also provides a strict total order? It would take about 5 minutes to
> write up a paper, which is why I'm sure it would have been done by now if
> there wasn't a good reason not to.

The reason is that you're not *supposed* to order pointers for different
arrays. And the reason for that is that on some systems only a portion of the
pointer representation needs to be compared to determine the ordering, if it
is in the same array.

Think of 16-bit segmented DOS builds, with 32-bit far pointers. Aside from the
Huge Memory Model, all objects (including arrays) are limited to 64kB in size,
so the segment portion of the pointer remains the same for any pointer.
Iteration only requires modifying the offset portion.

Ordering in that system requires only to compare the 16-bit offsets, not the
entire 32-bit representation. Considering it's a build for a 16-bit platform
with 16-bit CMP instructions, a 32-bit comparison would mean an extra jump,
something you don't want in the general case. That logic is only required in
std::less, so it's kept there.

--
Thiago Macieira - thiago (AT) macieira.info - thiago (AT) kde.org
Software Architect - Intel Open Source Technology Center

[Nevin Liber]

Please list the C++17 compilers and standard libraries which target such a system.  I'd love to see how std::less, especially std::less<void>, is implemented.  Actual implementations and not hypotheticals, please.

While I am strongly in favor of such a change, the shorter answer is that there are a number of committee members who are adamantly against such a change, and trying to do so is a battle not worth fighting.

-- 

 Nevin ":-)" Liber  <mailto:ne...@eviloverlord.com>  +1-847-691-1404

[Thiago Macieira]

On Monday, 18 June 2018 14:19:50 PDT Nevin Liber wrote:
> Please list the C++17 compilers and standard libraries which target such a
> system. I'd love to see how std::less, especially std::less<void>, is
> implemented. Actual implementations and not hypotheticals, please.

I can't. It's all in the past and I really don't expect anyone to think of
supporting 16-bit DOS in the future.

I could give hypotheticals of systems with persistent memory (see [1][2][3],
just the top three Google results). Since we've only just begun to have NVRAM
as useful storage, we don't know where the technology will lead and it's not
unthinkable to have a 128-bit-wide pointer to contain a control block. For
now, see [4] for what the team was thinking of in order to enable persistent
memory Standard Library containers.

See also [5], for a product that was reported to need pointers wider than 64-
bit. sorry, I can't find the slides that said that and that may not have
survived to the actual product.

[1] https://www.techrepublic.com/article/how-intel-optane-dc-persistent-memory-could-up-capacity-lower-cost-of-in-memory-databases/
[2] https://arstechnica.com/gadgets/2018/05/intel-finally-announces-ddr4-memory-made-from-persistent-3d-xpoint/
[3] https://www.forbes.com/sites/marcochiappetta/2018/05/30/intel-could-revolutionize-datacenters-with-optane-dc-persistent-memory/
[4] https://events.static.linuxfound.org/sites/events/files/slides/
NVML_Cpp_linuxcon_0.pdf
[5] https://www.labs.hpe.com/the-machine

> While I am strongly in favor of such a change, the shorter answer is that
> there are a number of committee members who are adamantly against such a
> change, and trying to do so is a battle not worth fighting.

--

[Alberto Barbati]

Il giorno lunedì 18 giugno 2018 22:36:42 UTC+2, Brian Bi ha scritto:

Why can't we just change the standard so that the built-in < operator for T* also provides a strict total order? It would take about 5 minutes to write up a paper, which is why I'm sure it would have been done by now if there wasn't a good reason not to.

By making it UB you allow an implementation to put diagnostic runtime traps on pointer misuse. If you would make such operations well formed the only effect would be to ban the only weapon against this kind of objectionable code. The good reason is that there is actually nothing to gain and much to lose.

[floria...@gmail.com]

Except it's not Undefined Behavior, but Unspecified Result. Which is completely different.

Unspecified result means: the language doesn't tell you anything about the result, but guarantee somehow that the result will be fully determined. So you cannot expect if the it will return true or false, but you can expect nothing more complicated than that will happen.

However, accessing a out-of-bound pointer is Undefined Behavior, and tools can be put here for misuse check.

[Thiago Macieira]

On Tuesday, 19 June 2018 00:45:13 PDT floria...@gmail.com wrote:
> Except it's not Undefined Behavior, but Unspecified Result. Which is
> completely different.
>
> Unspecified result means: the language doesn't tell you anything about the
> result, but guarantee somehow that the result will be fully determined. So
> you cannot expect if the it will return true or false, but you can expect
> nothing more complicated than that will happen.

The language does not ensure the three-way comparison (total ordering) that if
p1 < p2 and p2 < p3, that p1 will be less than p3. You need std::less for
total ordering.

[Arthur O'Dwyer]

On Tuesday, June 19, 2018 at 7:21:10 AM UTC-7, Thiago Macieira wrote:

On Tuesday, 19 June 2018 00:45:13 PDT floria...@gmail.com wrote:
> Except it's not Undefined Behavior, but Unspecified Result. Which is
> completely different.
>
> Unspecified result means: the language doesn't tell you anything about the
> result, but guarantee somehow that the result will be fully determined. So
> you cannot expect if the it will return true or false, but you can expect
> nothing more complicated than that will happen.

The language does not ensure the three-way comparison (total ordering) that if
p1 < p2 and p2 < p3, that p1 will be less than p3. You need std::less for
total ordering.

Yes. And even std::less will not tell you the actual ordering of pointers on your system. It is perfectly valid for the library implementor to implement an "interleaved" std::less such that

    int a[10], b[10];

    int *p = &a[5];

    auto Less = std::less<int*>();

    assert( Less(a, p) && Less(p, a+10) );  // this MUST be true, according to the standard's rules, because a < p && p < a+10

    assert( Less(b, p) && Less(p, b+10) );  // this ALSO COULD be true, according to the standard's rules

–Arthur