What does "current time" mean?

[Manu Raju]

Some of you might be interested in this paper by Amazon Engineer:

<https://www.open-std.org/jtc1/sc22/wg21/docs/papers/2023/p0342r1.pdf>

[Scott Lurndal]

Manu Raju <M...@invalid.invalid> writes:
>Some of you might be interested in this paper by Amazon Engineer:
>
><https://www.open-std.org/jtc1/sc22/wg21/docs/papers/2023/p0342r1.pdf>

Removing sequence points from the C++11 and following standards was sure to bite.

[Keith Thompson]

Manu Raju <M...@invalid.invalid> writes:
> Some of you might be interested in this paper by Amazon Engineer:
>
> <https://www.open-std.org/jtc1/sc22/wg21/docs/papers/2023/p0342r1.pdf>

From the paper:

auto start = chrono::high_resolution_clock::now();
auto result = fib(which);
auto end = chrono::high_resolution_clock::now();
...

I was surprised to discover that the program printed an elapsed time
of zero milliseconds on at least one compiler. Looking at the
generated code at https://godbolt.org/z/vY5d9bref revealed that the
compiler had reordered the code to get the end time prior to running
the calculation.

I'm surprised such a transformation would be legal.

--
Keith Thompson (The_Other_Keith) Keith.S.T...@gmail.com
Working, but not speaking, for XCOM Labs
void Void(void) { Void(); } /* The recursive call of the void */

[Keith Thompson]

But C++11 still has this in [intro.execution]:

Every value computation and side effect associated with a
full-expression is sequenced before every value computation and side
effect associated with the next full-expression to be evaluated.

I would think that would make it illegal to reorder these statements
(quoted from the paper); the calls to now(), fib(), and now() are full
expressions.

auto start = chrono::high_resolution_clock::now();
auto result = fib(which);
auto end = chrono::high_resolution_clock::now();

It seems to me the author encountered a compiler bug, not a flaw in the
language.

[David Brown]

On 07/02/2023 20:51, Keith Thompson wrote:
> Manu Raju <M...@invalid.invalid> writes:
>> Some of you might be interested in this paper by Amazon Engineer:
>>
>> <https://www.open-std.org/jtc1/sc22/wg21/docs/papers/2023/p0342r1.pdf>
>
> From the paper:
>
> auto start = chrono::high_resolution_clock::now();
> auto result = fib(which);
> auto end = chrono::high_resolution_clock::now();
> ...
>
> I was surprised to discover that the program printed an elapsed time
> of zero milliseconds on at least one compiler. Looking at the
> generated code at https://godbolt.org/z/vY5d9bref revealed that the
> compiler had reordered the code to get the end time prior to running
> the calculation.
>
> I'm surprised such a transformation would be legal.
>

(Note - I haven't read the paper yet, just this post.)

It seems perfectly reasonable to me. Neither C nor C++ care about
timing, nor the ordering of anything except observable behaviour. The
compiler can see that "fib" does not have any observable behaviour - it
is a "pure" function. It doesn't matter when the calculation is done,
as far as the observable behaviour is concerned, so it is fine to move
it before or after the calls to now() if that gives more efficient code.

It would also be fine for the compiler to pre-calculate fib(42) at
compile time and skip the run-time calculation entirely.

I see this kind of misunderstanding regularly when people try to make
benchmarks. Usually the solution is to put "volatile" in the right
place - force observable behaviour to force the ordering by making
"which" and "result" volatile.

[Vir Campestris]

On 07/02/2023 20:00, Keith Thompson wrote:
> It seems to me the author encountered a compiler bug, not a flaw in the
> language.

That was my first thought. but then I read on...

On 07/02/2023 22:16, David Brown wrote:
> It would also be fine for the compiler to pre-calculate fib(42) at
> compile time and skip the run-time calculation entirely.

And that also seemed quite possible. So I looked at his stuff on
Godbolt. It's clearly making two calls to now(), passing an address on
the stack in eax to both calls.

Only then does it call fib(). The odd thing is that the parameter to
fib() is on the stack - and it calls fib() twice with values 41 and 40,
then adds the two results together.

It then does something with cout I can't be bothered to decode.

I don't understand why it adds fib for 40 and 41 together either,
instead of just calling it with 42.

I'll go with compiler bug.

Andy

[Chris M. Thomasson]

On 2/7/2023 11:00 AM, Manu Raju wrote:
> Some of you might be interested in this paper by Amazon Engineer:
>
> <https://www.open-std.org/jtc1/sc22/wg21/docs/papers/2023/p0342r1.pdf>
>
>
>

[OT], drift, Sorry. Some comic relief... It's the now, now:

https://youtu.be/nRGCZh5A8T4?t=78

;^)

[David Brown]

On 09/02/2023 13:11, Vir Campestris wrote:
> On 07/02/2023 20:00, Keith Thompson wrote:
>> It seems to me the author encountered a compiler bug, not a flaw in the
>> language.
>
> That was my first thought. but then I read on...
>
> On 07/02/2023 22:16, David Brown wrote:
> > It would also be fine for the compiler to pre-calculate fib(42) at
> > compile time and skip the run-time calculation entirely.
>
> And that also seemed quite possible. So I looked at his stuff on
> Godbolt. It's clearly making two calls to now(), passing an address on
> the stack in eax to both calls.
>
> Only then does it call fib(). The odd thing is that the parameter to
> fib() is on the stack - and it calls fib() twice with values 41 and 40,
> then adds the two results together.
>
> It then does something with cout I can't be bothered to decode.

(When looking at this kind of stuff, I usually remove any main, cout or
printf nonsense and replace them with calls to a simple extern function
that is never defined. Then the generated assembly code is vastly
easier to understand.)

>
> I don't understand why it adds fib for 40 and 41 together either,
> instead of just calling it with 42.
>

It is inlining the first call to fib(42), to get fib(41) + fib(40).
That too is a perfectly valid optimisation (and the two fib's can be
called in either order). It is not necessarily a particularly helpful
optimisation, but it is valid.

> I'll go with compiler bug.
>

I disagree.

Again, you can happily argue that the transformations made here are not
helpful, but I cannot see that any are invalid.


It all comes down to observable behaviour. The calls to "now()" are
observable, and must be done in the order specified in the code. The
outputs to cout is also observable, and must be ordered correctly with
respect to the calls to "now()". The call(s) to "fib" are not
observable, and can be moved around freely or eliminated entirely as
long as the result is known before it is used in the "cout" output.

[Chris M. Thomasson]

On 2/7/2023 11:00 AM, Manu Raju wrote:

> Some of you might be interested in this paper by Amazon Engineer:
>
> <https://www.open-std.org/jtc1/sc22/wg21/docs/papers/2023/p0342r1.pdf>
>
>
>

Always remember to keep a delta from the last time and the current time...

[Andrey Tarasevich]

On 02/07/23 11:00 AM, Manu Raju wrote:
> Some of you might be interested in this paper by Amazon Engineer:
>
> <https://www.open-std.org/jtc1/sc22/wg21/docs/papers/2023/p0342r1.pdf>

We have already seen issues of that same general nature previously with
thread synchronization primitives. Before the proper memory fencing was
introduced into the language there was no guarantee that

mutex.lock();
<access to the resource>
mutex.unlock();

would not get reordered into

<access to the resource>
mutex.lock();
mutex.unlock();

thus defeating the synchronization. Back in C++98 times volatile access
was used as a workaround to introduce observable behavior and force the
desired sequencing.

Apparently, a more general mechanism is needed for sequence fencing not
tied to memory access.

--
Best regards,
Andrey