4

There is a great question about the "as-if" rule in general, but I wonder if there are any exceptions when it comes to measuring time.

Consider this (taken from here slightly modified):

using std::chrono;
auto begin = steady_clock::now();

auto result = some_lengthy_calculation(some_params);

auto end = std::chrono::steady_clock::now();

std::cout << "Time diff = " << duration_cast<microseconds>(end - begin).count() <<std::endl;
std::cout << "Result = " << result;

The compiler is allowed to apply any optimization that results in the same result. The point here is that the "as-if" rule does not apply to the measured time directly. Of course the measured time is not something that should be constant when optimizations are applied.

So my question is: How is it possible that I can reliably measure time with the above code when, according to the "as-if" rule, the compiler is allowed to rearrange it to one of the following?

auto temp = some_lengthy_calculation(some_params); // clever "optimization", precompute some stuff

auto begin = steady_clock::now();
auto result = temp;               // yay, I can use it here to pretend to be faster
auto end = steady_clock::now();

std::cout << "Time diff = " << duration_cast<microseconds>(end - begin).count() <<std::endl;
std::cout << "Result = " << result;

or even "more optimized":

std::cout << "Time diff = " << 42 <<std::endl;
std::cout << "Result = " << some_lengthy_calculation(some_params);

I assume no sane compiler would do that, but what exactly prevents a compiler from doing such "optimization"?

TL;DR...

  • One can observe the runtime difference between optimized and non-optimized code
  • If compiler optimizations are allowed to effect measured times, what prevents the compiler from not creating any code for the timing at all?
Jarod42
  • 203,559
  • 14
  • 181
  • 302
463035818_is_not_an_ai
  • 109,796
  • 11
  • 89
  • 185
  • That changes the observable behaviour and so doesn't look like a valid optimization in either case. The issue here isn't time, it's that the compiler has to be able to determine that a change won't affect observable behaviour. – pvg Oct 04 '17 at 19:40
  • @pvg well I am almost certain that I am wrong with my assumptions somewhere, but what exactly can be observed here that wouldnt be ok with the as if rule? – 463035818_is_not_an_ai Oct 04 '17 at 19:41
  • 1
    *"what prevents the compiler from not creating any code for the timing at all?"* -- Compiler authors are bound by more standards than just the language standard. The standards of common decency, for one. Assuming the compiler is actually made for professional programmers to use, and not just a toy, of course. – Benjamin Lindley Oct 04 '17 at 20:07
  • @BenjaminLindley of course I dont expect any compiler to do anything like that, but the c++ standard is usually quite pedantic on everything, so I would be surprised if it was allowed – 463035818_is_not_an_ai Oct 05 '17 at 08:01
  • "_what prevents the compiler from not creating any code for the timing at all_" Because reading the clock is an output-input operation. It's the same as outputting "what is the current time" on `cout` and then reading the time on `cin` (provided by the user). You cannot define "time" in any other way. – curiousguy May 28 '19 at 13:09

2 Answers2

2

The compiler won't do that, you can be sure about that.

While in pure theory, it would be allowed to, getting the system time involves system calls, which are a complete black box for the compiler.

The compiler can't reorder around black box function calls, as it can't assume that this won't have any side effects or contains any barriers.

Ext3h
  • 5,713
  • 17
  • 43
  • The compiler can't change the order of two "black box function calls"; what it can do is perform optimization on objects not reachable outside the function call, or the function, or the current TU. F.ex. it might notice that a static object is only given positive values, and optimize accordingly, across black box calls, as black box doesn't mean "can do anything on any object". – curiousguy May 28 '19 at 13:20
  • "_While in pure theory, it would be allowed to_" What "pure theory" allows that? – curiousguy May 28 '19 at 13:43
2

For the As-If rule to apply, the compiler must prove that the proposed change has no impact on the observable behavior. You are correct that the passage of time is not an observable behavior. However, in the case of reordering functions, it must prove that the order the functions are called in doesn't impact the observable behavior.

Using timing features will invariably involve some mechanism for measuring time which the compiler will not be able to prove is safe to reorder. For example, it might involve a call to an opaque system API function or driver function that it can't inspect. If we take the most transparent example, a monotonic software clock that simply advances by 1 unit of time every time it's state is taken, there's no way to prove that the call order doesn't matter because it does matter.

François Andrieux
  • 28,148
  • 6
  • 56
  • 87
  • 1
    Just accessing a volatile won't stop the compiler from reordering yet. Only the order of operations on volatile variables are left untouched, all code in between can be shifter to hearts content. Only the system calls stop the compiler, as no proof can be provided for unknown code. Well, at least if the API or the C++ implementation doesn't make any additional guarantees by pragma. – Ext3h Oct 04 '17 at 19:54
  • so the point is that the compiler cannot prove that `some_lengthy_calculation(some_params)` always yields the same result in the presence of a system call (even if in reality it does), right? – 463035818_is_not_an_ai Oct 05 '17 at 08:07
  • @tobi303 Rather, the more relevant question is rather or not the compiler can prove that it is allowed to reorder `auto begin = steady_clock::now();`. To reorder A and B implies that both A and B will change order, to move A ahead of B would not only change the order of A in relation to B, but it would change B's order in relation to A. The compiler still have to know that it can reorder it vis-à-vis the timing function call. – François Andrieux Oct 05 '17 at 13:35
  • Measuring time is in essence an I/O operation. – curiousguy May 28 '19 at 13:13