Post your code optimizations

[Simon F]

They are a ring IIRC, so why bother only with groups if you are talking about a more concise algebraic element...

Struth! I studied these things over 20 years ago! Cut me some slack

At least I think I'm 100% safe in saying it isn't a field (assuming N>1)!

 

[Xmas]

Yes, this makes sense in the case where the subexpressions are from other statements, grouped with parenthesis, or function calls, but the context of discussion was order of evaluation within an a statement (x = i++ * i++, f(a,b,c), etc)

But x = i++ * i++ is equivalent to (x = ((i++) * (i++))). It should not be evaluated from left to right, as in your example. So I'm not sure what your point is.

 

[DemoCoder]

As integers mod 2^N form a ring with operators + and *, you can do whatever you like with adds/subs/muls in any order. Divide, OTOH, is another matter.

That is precisely the case I had in mind (a+b)/x mod m != a/x + b/x mod m . A typical example of a bug I've seen is computing the midpoint between two points (a+b)/2 where a+b > m. Also, depending on what language and abstractions you're using, exceeding your modulus can generate the side effect of running code that traps overflows. (typically in security conscious code where integer overflow attacks are common)

So I'm not sure what your point is.

My point is, order of evaluation of floats is important and any language which doesn't have a order of evaluation for floats is broken. Side effects aren't the only bad thing about undefined evaluation order.

 

[KimB]

Well, evaluation order usually isn't important, so it can be nice to have some flexibility for compiler optimizations. And when it is important, you can always explicitly define what evaluation order you want.

 

[DemoCoder]

Well, evaluation order usually isn't important, so it can be nice to have some flexibility for compiler optimizations. And when it is important, you can always explicitly define what evaluation order you want.

Yes, that would be desirable, but the question is, does C++ yield both full compiler freedom and full author control? I don't think C++ permits equational reasoning, atleast, not to the degree that lazy pure functional languages do.

 

[Xmas]

My point is, order of evaluation of floats is important and any language which doesn't have a order of evaluation for floats is broken. Side effects aren't the only bad thing about undefined evaluation order.

Evaluation order is only undefined in C for independent (as in: on different branches of the expression tree) subexpressions.
"a+b+c+d" is evaluated from left to right, but in "a*b+c*d" c*d can be evaluated before a*b, and this only matters when there are side effects.

 

[DemoCoder]

Yes, I was never disputing the case where operator precedence provides a natural grouping of subexpressions. The point is, (a+b)+c != a+(b+c). Whether C's semantics are strict enough I don't recall. I think it is also a mistake to assume that "a + b" has no side effects. It certainly does have side effects, just not necessarily visible to the HLL, for example, setting a carry bit, or causing a trap or exception.

 

[KimB]

Yes, that would be desirable, but the question is, does C++ yield both full compiler freedom and full author control? I don't think C++ permits equational reasoning, atleast, not to the degree that lazy pure functional languages do.

Well, you may have to let your code be a bit less readable, but breaking things up into multiple statements will always work (if you're doing math, you'd probably also have to set the "volatile" keyword).

 

[DemoCoder]

Equational reasoning requires the compiler to prove that a expression can't have side effects. This is in general, very hard for non-pure languages. Traditional languages must be very very conservative, and frankly, any call that crosses a dynamic boundary is becomes a black hole you can't see through.

 

[RussSchultz]

(if you're doing math, you'd probably also have to set the "volatile" keyword).

Waaaa?

volatile is only useful when you've got a resource that can change without the compiler knowing. "Math" has nothing to do with it.

 

[KimB]

Waaaa?

volatile is only useful when you've got a resource that can change without the compiler knowing. "Math" has nothing to do with it.

Well, the volatile keyword is used to prevent the compiler from optimizing specific variables. So of course math can have something to do with it, as the compiler may attempt to reorder or evaluate differently your math instructions to improve performance. In this example that Nick posted on the second page of this thread, that optimization breaks the algorithm.

 

[OpenGL guy]

Well, the volatile keyword is used to prevent the compiler from optimizing specific variables. So of course math can have something to do with it, as the compiler may attempt to reorder or evaluate differently your math instructions to improve performance. In this example that Nick posted on the second page of this thread, that optimization breaks the algorithm.

Actually, it's the CPU keeping extra bits of precision that break the algorithm. Using "volatile" causes the compiler to write the value to memory each time it is changed, thus forcing the value to the desired precision.

Edit: Even if you disabled optimizations, it still wouldn't work properly on some CPUs.

A long time ago I had a customer say he'd found a compiler bug. Here's what he had written:

int i = 0;

void thread()
{
   while(ok_to_run) {  i++;}
}

int main(void)
{
   spawn_thread( thread);

   while (ok_to_run) { fprintf("%i\n",i); }
}

He complained that the thread was broken because the outputted value of i was always 0. I explained that he needed to declare i as "volatile" so the compiler would know that the value could change outside the scope, i.e. store the value in memory not in a register. His reply was that the compiler should do this for you!

 

[Simon F]

Actually, it's the CPU keeping extra bits of precision that break the algorithm.

Presumably it's the brain-dead x86 FPU architecture we're talking about? I had FP code that ran perfectly on Sun Sparcs and MIPs machines but just fell over in a heap on the x86 thanks to it sometimes doing 80 bit maths when the rest of the code was float

 

[Simon F]

That is precisely the case I had in mind (a+b)/x mod m != a/x + b/x mod m . A typical example of a bug I've seen is computing the midpoint between two points (a+b)/2 where a+b > m.

Ironically, if you'd wanted the average of 3 points, i.e. (a+b+c)/3, you'd be ok since gcd(3,2^N)=1

Also, depending on what language and abstractions you're using, exceeding your modulus can generate the side effect of running code that traps overflows. (typically in security conscious code where integer overflow attacks are common)

Real men use C ... or have to

My point is, order of evaluation of floats is important and any language which doesn't have a order of evaluation for floats is broken. Side effects aren't the only bad thing about undefined evaluation order.

Agreed.

 

[Mate Kovacs]

See the expression as a tree. It's defined where the branches are located, but it's not defined in which order they are evaluated. (Other than, of course, that the subexpressions into an operator must be evaluated before that operator is. )

(A) + (B) + (C) where A, B and C are subexpressions must be calculated as
((A) + (B)) + (C), but A, B and C can be calculated in any order.

Yes, this makes sense in the case where the subexpressions are from other statements, grouped with parenthesis, or function calls, but the context of discussion was order of evaluation within an a statement (x = i++ * i++, f(a,b,c), etc)

if I have the following:

a op b op c op d op e op f op g op h

It makes sense all the time. Any operator with its two operand(-subexpression)s forms a subexpression.
Just draw the corresponding tree for your expression, and apply the rules Basic has given.
E.g. If "op" means the same operator in every place, then the (left/right) grouping of that operator alone will dictate the shape of the tree.
For left grouping it will look like this:

              op
             /  \
            op   h
           /  \
          op   g
         /  \
        op   f
       /  \
      op   e
     /  \
    op   d
   /  \
  op   c
 /  \
a    b

As you can see, this is a rather degenerate tree. According to Basic's rules, there's only one way of evaluating this particular expression tree.

Now take "x = i++ * i++":

  =
 / \
x   *
   / \
 i++ i++

Here the problem is side effects. We don't know when the ++'s will happen, since there are no sequence-point operators in the tree.

Take "f(a,b,c)", and the tree will look like this:

  f()
 / | \
a  b  c

We know the order in which a, b and c are pushed on the stack, but if they're expressions themselves, we don't know the order in which they're evaluated.

 

[DemoCoder]

              op
             /  \
            op   h
           /  \
          op   g
         /  \
        op   f
       /  \
      op   e
     /  \
    op   d
   /  \
  op   c
 /  \
a    b

As you can see, this is a rather degenerate tree. According to Basic's rules, there's only one way of evaluating this particular expression tree.

I disagree. There are many ways of evaluating expression trees, and I didn't find his explanation particularly clarifying as to which part of the C standard spec mandates expression tree evaluation semantics. But in general for any programming language compiler,

#1 not every compiler will use binary trees
#2 even under binary tree, there are many ways to traverse a tree
#3 even if you dictate one traversal, there are many variations for turning an AST or Tree-IR into code. One of the common ones is maximal munch or dynamic programming variations for tiling trees, which does not necessary produce the "obvious" almost stack-like evaluation your calling for here and can definately produce an evaluation that breaks the associative rule.

You don't need to explain how your tree of subexpression argument works, I am well familiar with it, and I have written several compilers myself. I just disagree with it. Recognize that I am arguing from the abstract, not the specific. I am not familar enough with the C specification to know whether it mandates a particular expression tree evaluation strategy, I am just commenting that in general, the "correct" evaluation order does not "naturally fall out" just because one parses an expression into an AST. (it may for simplistic interpreters, but more complicated instruction selection mechanisms which operate by tree pattern matching and rewriting are not so simple)

 

[DemoCoder]

Ironically, if you'd wanted the average of 3 points, i.e. (a+b+c)/3, you'd be ok since gcd(3,2^N)=1

Yep, or you could do your arithmetic in a Galois Field of order 2^N. Addition = XOR, multiplication can be done via lookup table (obviously not good for n= 32 ) This is commonly used for error correcting codes like Reed-Solomon or for cryptography algorithms like Shamir Sharing where every element must have a multiplicative inverse.

 

[Mate Kovacs]

I disagree. There are many ways of evaluating expression trees, and I didn't find his explanation particularly clarifying as to which part of the C standard spec mandates expression tree evaluation semantics.

Forget those trees for a second, just take a look at your expression (and remember, I made the assumption that "op" means the same operator everywhere, and a..h are atoms (not expressions)):

a op b op c op d op e op f op g op h

According to the (C/C++) standard, if the operator "op" has left grouping/associativity (e.g. "+"), then that expression above means:

((((((a op b) op c) op d) op e) op f) op g) op h

If it has right grouping (e.g. "=") then it means:

a op (b op (c op (d op (e op (f op (g op h))))))

Again:

the subexpressions into an operator must be evaluated before that operator is

So there's only one way to evaluate such expressions, which was my point.

 

[Simon F]

Yep, or you could do your arithmetic in a Galois Field of order 2^N. Addition = XOR, multiplication can be done via lookup table (obviously not good for n= 32 )

That won't produce a useful result when, say, computing coordinates for 3D graphics!

This is commonly used for error correcting codes like Reed-Solomon ...

I'm quite familiar with the joys of Reed-Solomon codes, especially with regard to DVB television.

 

[Mate Kovacs]

I am just commenting that in general, the "correct" evaluation order does not "naturally fall out" just because one parses an expression into an AST.

Basic's original post used the "tree argument" to show how the run-time order of evaluation can be mostly unaffected (and undefined) by precedence and grouping. Now I don't quite understand what you have against that.