• February 25, 2021, 04:38:28 PM

Login with username, password and session length

Author Topic:  CPU: order of evaluation of an arithmetic expression  (Read 290 times)

0 Members and 1 Guest are viewing this topic.

Offline marcm200

  • 3c
  • ***
  • Posts: 925
CPU: order of evaluation of an arithmetic expression
« on: February 11, 2020, 10:36:52 AM »
Expressions like a=b+c-d can be evaluated in any order provided sufficient precision.

But using values like a=2+2^100-2^100 changes that for C++ double. a=(b+c)-d gives 0, a=b+(c-d) gives the correct answer 2.

I am concerned (i.e. I don't know how it's handled): If I were a CPU scheduler to assign work to FPUs and b and c were in cache while d has to be fetched from memory, I would compute b+c and then -d. But it might very well happen that 5 minutes later d is in cache while b is no longer.

Does the order of evaluation change then?  Or does the CPU not do such look-ahead optimizations as it also knows the limited precision?

I can force the compiler to produce specific code using parentheses or sequential expressions like a=c-d; a += b. But does the CPU adhere to that?

Background: I'm optimizing my TSA software and if I could beforehand make sure of a deterministic order of evaluation, I could often use the fastest datatype when a certain test is passed instead of using a slow datatype that provides enough precision.


Linkback: https://fractalforums.org/programming/11/cpu-order-of-evaluation-of-an-arithmetic-expression/3314/

Offline claude

  • 3f
  • ******
  • Posts: 1781
    • mathr.co.uk
Re: CPU: order of evaluation of an arithmetic expression
« Reply #1 on: February 11, 2020, 02:48:22 PM »
I've never heard of a CPU rearranging expressions. Assembly language has no notion of them. It is the job of the compiler, and it should do what you say unless you enable unsafe math optimizations explicitly.

Offline marcm200

  • 3c
  • ***
  • Posts: 925
Re: CPU: order of evaluation of an arithmetic expression
« Reply #2 on: February 11, 2020, 11:15:14 PM »
That's good to know, thanks. I will then use sequential binary expressions to enforce a deterministic evaluation order on the compiler to optimize my algorithm.

Offline hobold

  • Fractal Fluff
  • *****
  • Posts: 396
Re: CPU: order of evaluation of an arithmetic expression
« Reply #3 on: February 11, 2020, 11:34:01 PM »
There are two different things at play here that might have been mixed up.

Hardware:
Modern processors do something called "dynamic out of order execution", where they do in fact try to re-arrange the sequence of machine instructions to best utilize the available circuits. However, special care is taken that this trickery remains hidden; i.e. that it doesn't change the produced results. (Messing this up was one of the causes for Intel's security flaws "Meltdown" and "Spectre" and the stream of subsequent flaws uncovered since.)

Software:
The compiler will also do its best to re-arrange the given program statements to better match what the hardware can do. However, the compiler's changes can and do change the results (after all the compiler's output is the sequence of instructions that the machine is supposed to follow to the letter). However, the default of all sane compilers is to not change the order of floating point operations as specified by the programmer. Even at high optimization levels, for example, GCC will not re-arrange floating point arithmetic unless you explicitly allow "-funsafe-math-optimization" (or imply it with "-ffast-math") on invocation of the compiler.

The latter compiler guarantees are not generally true for GPGPU programming. There, the default tends to be utmost performance.

Conclusion:
When you write sequential code in C/C++, you can control the order of floating point arithmetic with parenthesis, and the compiler will generally stick to that. Unless you specifically instruct it to compromise exact correctness for more performance. (Special caveats apply to multithreaded programming, where concurrency means that there is no guaranteed global order between different parallel threads.)

Offline marcm200

  • 3c
  • ***
  • Posts: 925
Re: CPU: order of evaluation of an arithmetic expression
« Reply #4 on: February 12, 2020, 09:06:21 AM »
I recently read about "look-ahead-optimization" and "branch-prediction" on CPU level, and that's why I was concerned about a deterministic outcome.

Usually I compute my data with a number type providing enough precision, but being slow. But using C++ double, I need to make sure that the results are deterministic in the sense that calculations where rounding will occur yield the same result no matter what part of the hardware is currently idle.

So I will control the flow of evaluation, not use fast-math and as the processors adhere to the deterministic principle, I can now implement my test routine (I will come back to that later in the appropriate thread).

Thanks again to both!


Offline hobold

  • Fractal Fluff
  • *****
  • Posts: 396
Re: CPU: order of evaluation of an arithmetic expression
« Reply #5 on: February 12, 2020, 09:35:38 AM »
I recently read about "look-ahead-optimization" and "branch-prediction" on CPU level, and that's why I was concerned about a deterministic outcome.
The results are supposed to be deterministic, the timing is not supposed to be deterministic (but as fast as possible). That is the general contract that hardware designers have to fulfil.

(Modern microprocessor architecture is quite an awesome engineering feat. But on the surface, everything is still appearing as if it were a simple one-after-the-other matter.)


xx
Round-off errors in polynomial evaluation

Started by marcm200 on Programming

25 Replies
766 Views
Last post July 04, 2020, 11:22:42 PM
by 3DickUlus
question
Higher order M sets

Started by mcneils on Fractal Mathematics And New Theories

6 Replies
114 Views
Last post February 23, 2021, 06:10:03 AM
by gerrit
xx
3rd Order Evolution Of Tilings

Started by Dinkydau on Fractal Image Gallery

2 Replies
385 Views
Last post September 09, 2017, 04:46:37 PM
by Dinkydau
xx
Re: 3rd order Metaphase evolution

Started by gerrit on Fractal Image of the Month

0 Replies
55 Views
Last post January 12, 2021, 12:18:26 AM
by gerrit
xx
order 2 noodle sphere mapping

Started by hobold on Fractal Image Gallery

0 Replies
340 Views
Last post November 27, 2017, 07:19:48 PM
by hobold