Concerns on specifying evaluation order of function arguments (P0145R0)

[Kazutoshi Satoda]

P0145R0: Refining Expression Evaluation Order for Idiomatic C++ (Revision 1)
http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2015/p0145r0.pdf
> In summary, the following expressions are evaluated in the order
> a, then b, then c, then d:
...
> 3. a(b, c, d)

I have thought of a pattern where specifying evaluation order of
function arguments can result in general and noticeable prohibition
of some compiler optimizations.
(I'm afraid of that this is already discussed, or I'm just writing
something silly. I'm not a compiler writer, and the paper should
have been reviewed by some compiler writers...)

Consider the following transformation from g() to g_transformed():

int f(int a1, int a2, int a3);
int pure(int);
int non_local;

int g(int (*unknown)())
{
return f(pure(non_local), unknown(), pure(non_local));
}

int g_transformed(int (*unknown)())
{
int temp = pure(non_local);
return f(temp, unknown(), temp);
}

Assuming that the compiler can detect or be informed that pure() is a
pure function (it returns a value depending only on its arguments), this
transformation is valid as optimization because the compiler is allowed
to choose the evaluation order as (a1 -> a3 -> a2) so that it can be
proven that two evaluations of "pure(non_local)" produce a same value.

If evaluation order is specified as "left to right", this transformation
is no longer possible because unknown() can modify non_local and then
two evaluations of "pure(non_local)" can produce different values.

If the execution time of unknown() and f() are negligible compared to
the execution time of pure(), the total execution time of g() can be
essentially doubled by adoption of P0145R0.

While the above code looks a fiction, I think the pattern can be found
in real codes with some replacements:
- pure(): complex math functions, inspection on a range (like strlen())
- non_local: class non-static data members
- unknown: class virtual functions
Also, the pattern can appear as a intermediate result of inlining.


I found only the following about performance concern of P0145R0:
https://isocpp.org/blog/2015/11/kona-standards-meeting-trip-report
> Performance was a concern: will performance suffer? It will for some
> older machine architectures (1% was mentioned), but there can be
> backwards compatibility switches and performance-sensitive
> applications have mostly moved to architectures where there is no
> performance degradation years ago.
>
> This proposal was accepted.
But I think the above mentioned prohibition of transformation is general
issue, not only on older machine architectures, and can be noticeable
performance difference.

Is these kind of concern already discussed?


P.S.
I found that the "formal wording" in P0145R0 is a bit informal:
- "sequenced before/after" are used as a relation between two
expressions. But it is defined as a relation between evaluations
(value computations and side effects).
- "sequenced from left to right" should be something like this?
"value computations and side effects associated with an argument
expression is sequenced before any of the next argument (if any)."

--
k_satoda

[Myriachan]

On Thursday, November 19, 2015 at 12:24:51 PM UTC-8, Kazutoshi SATODA wrote:

But I think the above mentioned prohibition of transformation is general
issue, not only on older machine architectures, and can be noticeable
performance difference.

Is these kind of concern already discussed?

I doubt my opinion matters, but personally, I'd rather have a correct program than a fast one.

Melissa

[Nicol Bolas]

On Thursday, November 19, 2015 at 3:24:51 PM UTC-5, Kazutoshi SATODA wrote:

P0145R0: Refining Expression Evaluation Order for Idiomatic C++ (Revision 1)
http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2015/p0145r0.pdf
> In summary, the following expressions are evaluated in the order
> a, then b, then c, then d:
...
>     3. a(b, c, d)

I have thought of a pattern where specifying evaluation order of
function arguments can result in general and noticeable prohibition
of some compiler optimizations.
(I'm afraid of that this is already discussed, or I'm just writing
 something silly. I'm not a compiler writer, and the paper should
 have been reviewed by some compiler writers...)

Gabriel Dos Reis and Jonathan Caves work on Visual C++, if I'm not mistaken.

[Nicol Bolas]

There are plenty of languages that ensure correctness; nobody's forcing you to use C++.

We shouldn't dismiss performance concerns for something like this out-of-hand. It would instead be better to prove that these concerns are going to be a non-trivial problem.

[Gabriel Dos Reis]

We shouldn’t assume that the authors of the proposal are insensitive to performance reasons. 

We are longtime C++ designers and implementers, very much attune to the essence of C++.

 

However, when writing a correct program has become difficult and common idioms have become traps and not supported by the language rules, we must reassess our design criteria and revise the rules as necessary.  Please see the statement of the problem in the paper.  A programming language is a set of responses to the problems of its time.

As has been pointed our repeatedly, the example code

 

void f()

{

std::string s = “but I have heard it works even if you don’t believe in it”

s.replace(0, 4, “”).replace(s.find(“even”), 4, “only”).replace(s.find(“ don’t”), 6, “”);

assert(s == “I have heard it works only if you believe in it”);

}

 

was published in Bjarne’s book TC++PL4.  Before publication, that particular code was reviewed by world wide leading C++ experts (at least a dozen, if my memory serves me correctly, the majority of whom attend C++ standards meetings and make contributions.) 

 

Interesting enough, the week just before the Kona meeting, an esteemed colleague of mine and I spent a day and half chasing an obscure bug (in a real product) that turned out to be an OEE issue on a very simple-looking code.  Worse: the offending code was authored by myself L

 

-- Gaby

[Kazutoshi Satoda]

On 2015/11/20 5:24 +0900, Kazutoshi Satoda wrote:
> Consider the following transformation from g() to g_transformed():
>
> int f(int a1, int a2, int a3);
> int pure(int);
> int non_local;
>
> int g(int (*unknown)())
> {
> return f(pure(non_local), unknown(), pure(non_local));
> }
>
> int g_transformed(int (*unknown)())
> {
> int temp = pure(non_local);
> return f(temp, unknown(), temp);
> }
>
> Assuming that the compiler can detect or be informed that pure() is a
> pure function (it returns a value depending only on its arguments), this
> transformation is valid as optimization because the compiler is allowed
> to choose the evaluation order as (a1 -> a3 -> a2) so that it can be
> proven that two evaluations of "pure(non_local)" produce a same value.

I got an evidence that GCC (5.2, and also 4.4) actually does this kind
of transformation with "int pure(int) __attribute__((const))".
https://goo.gl/AYYOkj
GCC is smarter than me, as it knows that calling unknown() first is even
better.


For function attributes on GCC:
https://gcc.gnu.org/onlinedocs/gcc/Common-Function-Attributes.html
> const
> Many functions do not examine any values except their arguments, and
> have no effects except the return value. Basically this is just
> slightly more strict class than the pure attribute below, since
> function is not allowed to read global memory.

--
k_satoda

[Gabriel Dos Reis]

| I got an evidence that GCC (5.2, and also 4.4) actually does this kind of
| transformation with "int pure(int) __attribute__((const))".

When the arguments are, the compiler knows it can invoke the "as if" rule and reorder as it pleases -- there is no way to tell.

Note that the issue isn't that there won't be difference in codegen (that actually is the whole point of the proposal.) The question is whether any additional overhead is measurable in typical scenario and if so whether it is tolerable compared to alternatives (the traps we have today.)

I expect compilers to also offer switches for non-standard evaluation order, just like some have -funsafe-math.

PS: I worked on GCC for at least 16 years :-)

-- Gaby

[Zhihao Yuan]

On Thu, Nov 19, 2015 at 3:08 PM, Gabriel Dos Reis <g...@microsoft.com> wrote:
> As has been pointed our repeatedly, the example code
>
>
>
> void f()
>
> {
>
> std::string s = “but I have heard it works even if you don’t believe in it”
>
> s.replace(0, 4, “”).replace(s.find(“even”), 4, “only”).replace(s.find(“
> don’t”), 6, “”);
>
> assert(s == “I have heard it works only if you believe in it”);
>
> }

For this particular case, I personally don't think that we have to
make it work. In many languages, it works because the string
is immutable and `.replace` is creating new objects. IMHO,
referring a mutated object more than once in a sequence of
operations in a statement is a bad idea in general, not just in
C++.

That_map[] example subscribes to the same problem, since []
is an mutating operation in C++ but non-mutating in many other
languages. In my own code, [] of map-like objects is non-
mutating and users are forced to use named member function
for inserting or updating. That's my 0.02.

--
Zhihao Yuan, ID lichray
The best way to predict the future is to invent it.
___________________________________________________
4BSD -- http://bit.ly/blog4bsd

[Matt Calabrese]

On Thu, Nov 19, 2015 at 2:40 PM, Zhihao Yuan <z...@miator.net> wrote:

For this particular case, I personally don't think that we have to
make it work.  In many languages, it works because the string
is immutable and `.replace` is creating new objects.  IMHO,
referring a mutated object more than once in a sequence of
operations in a statement is a bad idea in general, not just in
C++.

I think this is what bothers me most. That we'd be potentially preventing certain optimizations is one thing, but separate from that is that by defining the code and its ordering, we'd be effectively sanctioning the dependence on it by users. This is at least a little bit scary. We'd be changing incorrect code to "correct" but subtle code (of course, the fact that it is currently invalid is also sometimes subtle).

I don't have a strong opinion either way, but I do agree that this is an important point that shouldn't be overlooked.

[Nicol Bolas]

Here's the problem. We have three choices:

1) The status quo. That is, we encourage the writing of such code (having functions that return references to `this` encourages it) while simultaneously making it very difficult for a user to know that they've written something incorrect relative to the standard. At best, we can hope for static analysis tools to step in and say "Hey, you did something possibly wrong here." At worse, users write subtle bugs into their programs that only appear on platforms that happen to use a different evaluation order.

2) Change std::string and various other modifiable types so that they're non-modifiable, thus breaking tons of perfectly valid (and reasonably performing) code that has already been written. Note that it will only fix this particular kind of issue, not the other problems that come from order of evaluation issues.

3) Change the rules of evaluation so that users can know that what they've written is actually valid C++ code.

The status quo helps nobody. And changing existing classes to be non-modifiable is a non-starter. So the only way to address the problem at all is to fix the order of evaluation of things.

Sure, people will still be able to write such unfortunate code. But backwards compatibility, and resistance to against immutable types in general from C++ programmers, means that it's just not going to happen. Better to focus on the solution that's actually possible than the ones that aren't.

[Zhihao Yuan]

On Thu, Nov 19, 2015 at 5:52 PM, Nicol Bolas <jmck...@gmail.com> wrote:
> 1) The status quo. That is, we encourage the writing of such code (having
> functions that return references to `this` encourages it) while
> simultaneously making it very difficult for a user to know that they've
> written something incorrect relative to the standard.

Chaining style is good, but the sample code is more like lasagna -- it
referred the chained target again in the argument list. If string has a
member function called `find_and_replace`, the problem will go away,
and the code will be cleaner; a free function has the same effect, just
without chaining. This is because `find` will be enclosed in the function
body, so it will be evaluated before the next pair of `find` & `replace` call.

[Edward Catmur]

On Thursday, 19 November 2015 23:52:54 UTC, Nicol Bolas wrote:

Here's the problem. We have three choices:

1) The status quo. That is, we encourage the writing of such code (having functions that return references to `this` encourages it) while simultaneously making it very difficult for a user to know that they've written something incorrect relative to the standard. At best, we can hope for static analysis tools to step in and say "Hey, you did something possibly wrong here." At worse, users write subtle bugs into their programs that only appear on platforms that happen to use a different evaluation order.

2) Change std::string and various other modifiable types so that they're non-modifiable, thus breaking tons of perfectly valid (and reasonably performing) code that has already been written. Note that it will only fix this particular kind of issue, not the other problems that come from order of evaluation issues.

3) Change the rules of evaluation so that users can know that what they've written is actually valid C++ code.

 

Yes, let's change the rules to more closely match what users expect, but I don't believe that expectation exists for function arguments specifically; that is, "everyone knows" that function arguments are evaluated in indeterminate order. This feels intuitive because (as with, say, addition) the syntax does not imply any dependency between arguments separated by a syntactic comma.

Note that I'm fine with sequencing the postfix-expression result and object parameter (if any) before the arguments proper. Doing so would fix the "chaining" example without impacting Kazutoshi's motivating example.

Also, if overloaded operators are evaluated according to the corresponding built-in operator (rather than as a function call) then that removes a major motivation for changing the rules for function calls.

[Nicol Bolas]

On Friday, November 20, 2015 at 6:16:13 AM UTC-5, Edward Catmur wrote:

On Thursday, 19 November 2015 23:52:54 UTC, Nicol Bolas wrote:

Here's the problem. We have three choices:

1) The status quo. That is, we encourage the writing of such code (having functions that return references to `this` encourages it) while simultaneously making it very difficult for a user to know that they've written something incorrect relative to the standard. At best, we can hope for static analysis tools to step in and say "Hey, you did something possibly wrong here." At worse, users write subtle bugs into their programs that only appear on platforms that happen to use a different evaluation order.

2) Change std::string and various other modifiable types so that they're non-modifiable, thus breaking tons of perfectly valid (and reasonably performing) code that has already been written. Note that it will only fix this particular kind of issue, not the other problems that come from order of evaluation issues.

3) Change the rules of evaluation so that users can know that what they've written is actually valid C++ code.

 

Yes, let's change the rules to more closely match what users expect, but I don't believe that expectation exists for function arguments specifically; that is, "everyone knows" that function arguments are evaluated in indeterminate order. This feels intuitive because (as with, say, addition) the syntax does not imply any dependency between arguments separated by a syntactic comma.

You say that "everyone knows", and yet people still write code that shows that they don't. "Everyone knows" to destroy objects they allocate, but people still write code where that doesn't happen. We standardized smart pointers to make it easier for people to avoid that.

The same goes here. Regardless of what "everyone knows", we can actually fix it so that their code is reliable.

[Bo Persson]

On 2015-11-19 23:59, 'Matt Calabrese' via ISO C++ Standard - Future

Proposals wrote:
> On Thu, Nov 19, 2015 at 2:40 PM, Zhihao Yuan <z...@miator.net
> <mailto:z...@miator.net>> wrote:
>
> For this particular case, I personally don't think that we have to
> make it work. In many languages, it works because the string
> is immutable and `.replace` is creating new objects. IMHO,
> referring a mutated object more than once in a sequence of
> operations in a statement is a bad idea in general, not just in
> C++.
>
>
> I think this is what bothers me most. That we'd be potentially
> preventing certain optimizations is one thing, but separate from that is
> that by defining the code and its ordering, we'd be effectively

> /sanctioning/ the dependence on it by users. This is at least a little

> bit scary. We'd be changing incorrect code to "correct" but subtle code
> (of course, the fact that it is currently invalid is also sometimes subtle).
>
> I don't have a strong opinion either way, but I do agree that this is an
> important point that shouldn't be overlooked.
>

If the compiler is smart enough, there doesn't have to be any
performance difference from this. If the parameters are independent,
like they have to be now, the compiler can still reorder the evaluation
the way it has always done.

It must just produce a result "as-if" it had evaluated the parameters in
order.


Bo Persson

[Edward Catmur]

There's a big difference between adding facilities to the library and narrowing the semantics of the language itself. When users were making mistakes in memory allocation, the solution was to add smart pointers that can replace raw pointers as desired; it wasn't to make the language GCd.

You say that people are writing code that depends on function argument evaluation; how common is this problem? Does it occur frequently enough to justify the performance impact?

[Arthur O'Dwyer]

On Thursday, November 19, 2015 at 3:52:54 PM UTC-8, Nicol Bolas wrote:

On Thursday, November 19, 2015 at 5:59:07 PM UTC-5, Matt Calabrese wrote:

On Thu, Nov 19, 2015 at 2:40 PM, Zhihao Yuan <z...@miator.net> wrote:

For this particular case, I personally don't think that we have to
make it work.

I would agree that the "motivating example" in the paper (taken from Bjarne's book) is really a terrible example, because OF COURSE no reasonable programmer would write a line of code so convoluted and expect it to work — and when it didn't work, any maintainer's first reaction would be to split up the convoluted expression into several statements, at which point the bug would go away.

However, there are plenty more motivating examples.

There's the motivating example for std::make_unique —

    void capture_as_uniqueptrs(std::unique_ptr<A>, std::unique_ptr<B>);

    int main() { capture_as_uniqueptrs(new A, new B); }

If "new A" and "new B" are unsequenced relative to each other, then the order of evaluation "allocate A - allocate B - construct A - construct B" is possible, and if A's constructor throws, B's memory leaks. If function argument evaluations are sequenced, then this problem goes away, I think.

There's a very wrong but very common "mis-pattern" in parsing code —

    int scan_function_decl(FILE *in) {  // returns bytes consumed from the stream

        return scan_return_type(in) + scan_identifier(in) + scan_parameter_list(in);

    }

As I understand it, this code would NOT be fixed by P0145.

 

I think this is what bothers me most. That we'd be potentially preventing certain optimizations is one thing, but separate from that is that by defining the code and its ordering, we'd be effectively sanctioning the dependence on it by users. This is at least a little bit scary. We'd be changing incorrect code to "correct" but subtle code (of course, the fact that it is currently invalid is also sometimes subtle).

I don't have a strong opinion either way, but I do agree that this is an important point that shouldn't be overlooked.

Here's the problem. We have three choices:

1) The status quo. That is, we encourage the writing of such code (having functions that return references to `this` encourages it) while simultaneously making it very difficult for a user to know that they've written something incorrect relative to the standard. At best, we can hope for static analysis tools to step in and say "Hey, you did something possibly wrong here." At worse, users write subtle bugs into their programs that only appear on platforms that happen to use a different evaluation order.

Don't forget the most relevant aspect of the status quo — New language features tend to be explicitly defined to evaluate things in left-to-right order. :P  At least that's been true of braced initializer-lists (including the way they interact with parameter-packs).  So we've got "New C++" features that tend to well-define evaluation order, mixed in with "Old C++" (a.k.a. "C") features that tend to leave it undefined. This is a bad state to be in, because the user has to constantly remember which kind of construct he's using at the moment. It also leads to stupid template tricks such as

    std::tuple<decay_t<decltype(F(A))>...> t { F(A)... };

    // can't use `auto t = std::make_tuple(F(A)...);` because it doesn't evaluate the operands in the order I want them

As I understand it, P0145 would fix a lot of this problem (but not all of it).

Tangent: My own pet peeve about P0145R0 is that it provides a defined OOE for operator<< and operator>> "because iostreams", but fails to define the OOE of most other operators. So it fails to fix the operator+ example above, and it also misses the opportunity to define OOE for operator| "because ranges" or operator/ "because filesystem" or any other soon-to-be-common chaining cases that I might have missed. I'd like to see P0145 either undefine OOE for << >> (i.e., let's please not use iostreams as a rationale for anything ever), or define OOE for all operators (i.e., let's remove a whole category of questions from Stack Overflow in one fell swoop).

–Arthur

[wher...@gmail.com]

On Saturday, November 21, 2015 at 12:48:51 AM UTC+2, Arthur O'Dwyer wrote:

So it fails to fix the operator+ example above, and it also misses the opportunity to define OOE for operator| "because ranges" or operator/ "because filesystem" or any other soon-to-be-common chaining cases that I might have missed.

If only they left out this rule from P0145:

- Furthermore, we suggest the following additional rule: the order of evaluation of an expression involving an overloaded operator is determined by the order associated with the corresponding built-in operator, not the rules for function calls. This rule is to support generic programming and extensive use of overloaded operators, which are distinctive features of modern C++. 

Without this rule, the order of evaluation for all overloaded operators would have been specified.

[Nicol Bolas]

Wait, I'm confused.

First, there does not appear to be any special case wording in P0145 "because iostreams". From a cursory glance at P0145, particularly the quoted section above, it seems that they do define the order of evaluation for overloaded operators.

Where is OOE undefined for overloaded operators? Chaining seems to be one of the key motivations behind P0145; where did they miss a case that makes evaluation order not defined?

[Nicol Bolas]

Actually, never mind, I see it now. Though they have a good point about reducing the scale of it ("politics is the art of the possible", after all).

I still disagree that the above section is problematic. It's perfectly reasonable for overloaded operators to be sequenced in the order of the standard ones.

[Kazutoshi Satoda]

On 2015/11/20 6:19 +0900, Gabriel Dos Reis wrote:
> Note that the issue isn't that there won't be difference in codegen
> (that actually is the whole point of the proposal.) The question is
> whether any additional overhead is measurable in typical scenario and
> if so whether it is tolerable compared to alternatives (the traps we
> have today.)

Do you have any reasonings (from your experiences?) to presume the
pattern (shown in OP) is not typical, or not measurable, or the overhead
is tolerable?

For example, I think it's OK to add a sequence rule between evaluations
of function and its arguments, because it's not typical, in my
experience, to have complex subexpressions on function parts.

> I expect compilers to also offer switches for non-standard evaluation
> order, just like some have -funsafe-math.

I doubt the usefulness of such switches.

Once the order is specified and people have been allowed to write codes
depending on that order, use of such compiler switches can result in
completely different behavior with far higher possibility than
-funsafe-math. AFAIK, the effect of -funsafe-math is often limited to
the accuracy of floating arithmetics, which is implementation-defined in
the first place.

--
k_satoda

[Kazutoshi Satoda]

On 2015/11/20 5:24 +0900, Kazutoshi Satoda wrote:

> I found only the following about performance concern of P0145R0:
> https://isocpp.org/blog/2015/11/kona-standards-meeting-trip-report
>> Performance was a concern: will performance suffer? It will for some
>> older machine architectures (1% was mentioned), but there can be
>> backwards compatibility switches and performance-sensitive
>> applications have mostly moved to architectures where there is no
>> performance degradation years ago.
>>
>> This proposal was accepted.
> But I think the above mentioned prohibition of transformation is general
> issue, not only on older machine architectures, and can be noticeable
> performance difference.
>
> Is these kind of concern already discussed?

Now I found another trip report with a comment which includes what has
been mentioned as the performance impact of P0145R0.
https://botondballo.wordpress.com/2015/11/09/trip-report-c-standards-meeting-in-kona-october-2015/#comment-219
> One example that came up during the EWG discussion was that different
> platform ABIs require pushing function arguments onto the stack in
> different orders, and it decreases register pressure to evaluate the
> arguments in the order that they will be pushed.
Then it is understandable that the impact was estimated as "1%" "for
some older machine architectures".

It seems that this kind of concern has not been considered as a
consequence of P0145R0 so far.

My concern can be said as a reduction of possibility of "common
subexpression elimination (CSE)"
<https://en.wikipedia.org/wiki/Common_subexpression_elimination>.
The impact may increase in the future as compilers become wiser.

I want EWG reconsider P0145R0 with this concern in mind, and hopefully
drop at least the part of function arguments from the proposal.

--
k_satoda

[Kazutoshi Satoda]

On 2015/11/21 1:45 +0900, Bo Persson wrote:
> If the compiler is smart enough, there doesn't have to be any
> performance difference from this. If the parameters are independent,
> like they have to be now, the compiler can still reorder the evaluation
> the way it has always done.

The difference is, "the parameters are independent" can be assumed (now)
or must be proven (P0145R0). And it can't be proven if a (sub)expression
contains a call to unknown function via a pointer or virtual call.

--
k_satoda

[Nicol Bolas]

What is the difference between this switch and the switch to turn off strict aliasing? Strict aliasing and, let's call it, strict ordering both are intended to improve safety by keeping the compiler from doing something that's probably unsafe. And yet, you have adherents to swear that strict aliasing kills valid compiler optimizations. Just as you believe that strict ordering kills valid compiler optimizations.

So what is the difference?

[Nicol Bolas]

So you see one comment on a trip report, and immediately assume that this was the totality of the discussion at the meeting? That's a pretty huge leap to be making.

My concern can be said as a reduction of possibility of "common
subexpression elimination (CSE)"
<https://en.wikipedia.org/wiki/Common_subexpression_elimination>.
The impact may increase in the future as compilers become wiser.

If "compilers become wiser" about this, it would only be through knowing more about what is being compiled. And if compilers know more about what is being compiled, they will be better able to know when code is not order-dependent.

Indeed, the smarter the compiler gets, the more it knows about the code, the lower the chance of needing to rely on non-strict ordering to get appropriate optimizations. After all, if your code is not order-dependent, and the compiler knows it, then there's no problem; the compiler can reorder things because you can't tell the difference. The problem only happens when your code is not order-dependent, but the compiler can only guess that it is.

Personally, I'd prefer that my compiler not break my code while trying to optimize it. And if my compiler doesn't know that it's safe to re-order various expressions for parameters and such, then it shouldn't.

[Kazutoshi Satoda]

Turning off "strict aliasing" will disable some optimization and may
save some non-portable codes. The optimization is standard conforming.

Turning on "strict ordering" ("switches for non-standard evaluation
order") will enable some optimization and may break some "valid"
(depending on the change in P0145R0) codes. The optimization is not
"standard" conforming.

They are clearly different for me.

--
k_satoda

[Kazutoshi Satoda]

On 2015/11/22 12:53 +0900, Nicol Bolas wrote:
> On Saturday, November 21, 2015 at 3:56:00 PM UTC-5, Kazutoshi SATODA wrote:
>> On 2015/11/20 5:24 +0900, Kazutoshi Satoda wrote:

...

>>> Is these kind of concern already discussed?
>>
>> Now I found another trip report with a comment which includes what has
>> been mentioned as the performance impact of P0145R0.

...

>> It seems that this kind of concern has not been considered as a
>> consequence of P0145R0 so far.
>
> So you see one comment on a trip report, and immediately assume that this
> was the totality of the discussion at the meeting? That's a pretty huge
> leap to be making.

I said "it seems" with some supporting circumstance. If you know it
isn't, please let me know. That is the question of my OP, which is not
answered yet.

>> The impact may increase in the future as compilers become wiser.
>
> If "compilers become wiser" about this, it would only be through knowing
> more about what is being compiled. And if compilers know more about what is
> being compiled, they will be better able to know when code is not
> order-dependent.
>
> Indeed, the smarter the compiler gets, the more it knows about the code,

> the *lower* the chance of needing to rely on non-strict ordering to get

> appropriate optimizations. After all, if your code is not order-dependent,
> and the compiler knows it, then there's no problem; the compiler can
> reorder things because you can't tell the difference. The problem only
> happens when your code is not order-dependent, but the compiler can only
> guess that it is.

My earlier reply to Bo Persson seems applicable here:
https://groups.google.com/a/isocpp.org/d/msg/std-proposals/Ew_0zQl_yBg/IJDqDAamBQAJ

> The difference is, "the parameters are independent" can be assumed (now)
> or must be proven (P0145R0). And it can't be proven if a (sub)expression
> contains a call to unknown function via a pointer or virtual call.

And, AFAIK, compilers in present still can't prove much of independence
between a call to function in different translation unit and a non-local
variable. So GCC has attributes "pure", "const" and they are proposed to
be in the standard.
("The [[pure]] attribute" <http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2015/p0078r0.pdf>)

Do you have any reasoning to foresee so much improvement of
analyzability in the time frame of C++17 (the target of the proposal)?
I don't.

--
k_satoda

[Nicol Bolas]

On Sunday, November 22, 2015 at 1:20:53 AM UTC-5, Kazutoshi SATODA wrote:

On 2015/11/22 12:37 +0900, Nicol Bolas wrote:
> On Saturday, November 21, 2015 at 3:55:51 PM UTC-5, Kazutoshi SATODA wrote:
>> On 2015/11/20 6:19 +0900, Gabriel Dos Reis wrote:
>>> I expect compilers to also offer switches for non-standard evaluation
>>> order, just like some have -funsafe-math.
>>
>> I doubt the usefulness of such switches.
>>
>> Once the order is specified and people have been allowed to write codes
>> depending on that order, use of such compiler switches can result in
>> completely different behavior with far higher possibility than
>> -funsafe-math. AFAIK, the effect of -funsafe-math is often limited to
>> the accuracy of floating arithmetics, which is implementation-defined in
>> the first place.
>
> What is the difference between this switch and the switch to turn off
> strict aliasing? Strict aliasing and, let's call it, strict ordering both
> are intended to improve safety by keeping the compiler from doing something
> that's probably unsafe. And yet, you have adherents to swear that strict
> aliasing kills valid compiler optimizations. Just as you believe that
> strict ordering kills valid compiler optimizations.
>
> So what is the difference?

Turning off "strict aliasing" will disable some optimization and may
save some non-portable codes. The optimization is standard conforming.

That's not what the strict aliasing rule is.

Strict aliasing means that the compiler is free to assume that any two pointers/references are not referring to the same object unless those pointers are of the same or related types. But this also means that if you pass two completely separate pointers to a function that just so happen to be of the same type, the compiler cannot assume that they are different objects. Which means that register usage patterns have to chance and so forth.

When you turn off strict aliasing, you are telling the compiler that the last assumption no longer has to be followed, that it should assume that any two pointers/references always refer to different objects.

However, this also means that code designed for compilation when strict aliasing is off cannot pass two pointers/references to the same object. Or by contrast, code that works under strict aliasing rules is free to pass two pointers/references to the same object. Which means that, if you compile this code with strict aliasing off, the resulting code is broken.

In short, you can write C++ standards conforming code that is broken if you turn off strict aliasing.

Just like you can write C++ standards conforming code (under P0145) which breaks if you turn off the strict ordering rules of P0145. So what's the difference?

[Nicol Bolas]

On Sunday, November 22, 2015 at 2:27:22 AM UTC-5, Kazutoshi SATODA wrote:

On 2015/11/22 12:53 +0900, Nicol Bolas wrote:
> On Saturday, November 21, 2015 at 3:56:00 PM UTC-5, Kazutoshi SATODA wrote:
>> On 2015/11/20 5:24 +0900, Kazutoshi Satoda wrote:
...
>>> Is these kind of concern already discussed?
>>
>> Now I found another trip report with a comment which includes what has
>> been mentioned as the performance impact of P0145R0.
...
>> It seems that this kind of concern has not been considered as a
>> consequence of P0145R0 so far.
>
> So you see one comment on a trip report, and immediately assume that this
> was the totality of the discussion at the meeting? That's a pretty huge
> leap to be making.

I said "it seems" with some supporting circumstance.

With very scant "supporting circumstance".
 

If you know it
isn't, please let me know. That is the question of my OP, which is not
answered yet.

>> The impact may increase in the future as compilers become wiser.
>
> If "compilers become wiser" about this, it would only be through knowing
> more about what is being compiled. And if compilers know more about what is
> being compiled, they will be better able to know when code is not
> order-dependent.
>
> Indeed, the smarter the compiler gets, the more it knows about the code,
> the *lower* the chance of needing to rely on non-strict ordering to get
> appropriate optimizations. After all, if your code is not order-dependent,
> and the compiler knows it, then there's no problem; the compiler can
> reorder things because you can't tell the difference. The problem only
> happens when your code is not order-dependent, but the compiler can only
> guess that it is.

My earlier reply to Bo Persson seems applicable here:
https://groups.google.com/a/isocpp.org/d/msg/std-proposals/Ew_0zQl_yBg/IJDqDAamBQAJ
> The difference is, "the parameters are independent" can be assumed (now)
> or must be proven (P0145R0). And it can't be proven if a (sub)expression
> contains a call to unknown function via a pointer or virtual call.

... so? I never claimed that compilers would develop omniscience, that they could automagically prove every case that we assume now. My point is that compilers getting smarter would improve the situation, not make it worse.

As for the statement itself, the strict aliasing analogy comes into play here too. Strict aliasing favors cases that are provably correct (pointers to unrelated types), rather than simply assuming that everything is fine. The same should be true here: we should prefer optimizations that are provably correct to optimizations that are assumed to be correct.

And this is even more important in cases when users have no way themselves to know which is which. After all, a user certainly can't know that a call via pointer/virtual function won't have some unintended effects. They can assume that this will be the case. They can tell their users not to pass in function pointers or override virtual functions in a way that breaks this assumption. But they cannot know.
 

And, AFAIK, compilers in present still can't prove much of independence
between a call to function in different translation unit and a non-local
variable.

If a compiler can't prove that, how can the compiler even detect common sub-expressions, let alone eliminate them?

Even something like this:

func1(func2(), func3(func2()));

It's not OK for the compiler to eliminate the call to `func2`, unless the compiler knows that `func2` is pure. And that's under today's C++ rules. And if the compiler knows that `func2` is pure... then the compiler can optimize away the second call, regardless of the ordering of the operations.

So exactly what cases would common subexpression elimination be allowed under the current rules but forbidden under P0145?

So GCC has attributes "pure", "const" and they are proposed to
be in the standard.
("The [[pure]] attribute" <http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2015/p0078r0.pdf>)

Do you have any reasoning to foresee so much improvement of
analyzability in the time frame of C++17 (the target of the proposal)?
I don't.

... I don't understand your point here. You said that the negative impacts of P0145 would be increased with compiler intelligence. I showed the opposite: that with more compiler intelligence and understanding, the negative impacts of P0145 will be decreased, not increased. Then you say that compilers won't be getting smarter in the future.

So which is it? Will compilers be getting smarter in the future or not?

[Kazutoshi Satoda]

On 2015/11/22 22:54 +0900, Nicol Bolas wrote:
> On Sunday, November 22, 2015 at 1:20:53 AM UTC-5, Kazutoshi SATODA wrote:
>> On 2015/11/22 12:37 +0900, Nicol Bolas wrote:
>>> On Saturday, November 21, 2015 at 3:55:51 PM UTC-5, Kazutoshi SATODA wrote:
>>>> On 2015/11/20 6:19 +0900, Gabriel Dos Reis wrote:
>>>>> I expect compilers to also offer switches for non-standard evaluation
>>>>> order, just like some have -funsafe-math.
>>>>
>>>> I doubt the usefulness of such switches.

...

>>> What is the difference between this switch and the switch to turn off
>>> strict aliasing?

...

>> Turning off "strict aliasing" will disable some optimization and may
>> save some non-portable codes. The optimization is standard conforming.
>
> That's not what the strict aliasing rule is.

...

> When you turn off strict aliasing, you are telling the compiler that the
> last assumption no longer has to be followed, that it should assume that

> any two pointers/references *always* refer to different objects.

I assumed your "switch to turn off strict aliasing" is something like
"-fno-strict-aliasing" for GCC.
https://gcc.gnu.org/onlinedocs/gcc-5.2.0/gcc/Optimize-Options.html#index-fstrict-aliasing-1049

But your definition is different. Your definition seems much like to put
C99 restrict everywhere. Then yes, I doubt usefulness of such switches
too with similar reasonings, even more strongly, as it will break almost
all programs.

But what compiler provides such option? Who are using the term "strict
aliasing" in such meaning? I have seen none.

--
k_satoda

[Kazutoshi Satoda]

On 2015/11/22 23:22 +0900, Nicol Bolas wrote:
> On Sunday, November 22, 2015 at 2:27:22 AM UTC-5, Kazutoshi SATODA wrote:
>> On 2015/11/22 12:53 +0900, Nicol Bolas wrote:
>>> On Saturday, November 21, 2015 at 3:56:00 PM UTC-5, Kazutoshi SATODA wrote:

...

>>>> The impact may increase in the future as compilers become wiser.
>>>
>>> If "compilers become wiser" about this, it would only be through knowing
>>> more about what is being compiled. And if compilers know more about what is
>>> being compiled, they will be better able to know when code is not
>>> order-dependent.
>>>
>>> Indeed, the smarter the compiler gets, the more it knows about the code,
>>> the *lower* the chance of needing to rely on non-strict ordering to get
>>> appropriate optimizations. After all, if your code is not order-dependent,
>>> and the compiler knows it, then there's no problem; the compiler can
>>> reorder things because you can't tell the difference. The problem only
>>> happens when your code is not order-dependent, but the compiler can only
>>> guess that it is.
>>
>> My earlier reply to Bo Persson seems applicable here:
>> https://groups.google.com/a/isocpp.org/d/msg/std-proposals/Ew_0zQl_yBg/IJDqDAamBQAJ
>>> The difference is, "the parameters are independent" can be assumed (now)
>>> or must be proven (P0145R0). And it can't be proven if a (sub)expression
>>> contains a call to unknown function via a pointer or virtual call.
>
> ... so? I never claimed that compilers would develop omniscience, that they
> could automagically prove every case that we assume now. My point is that
> compilers getting smarter would improve the situation, not make it worse.

Sorry for the confusion.

My "compilers become wiser" was about detecting purity of functions.
As compilers get smarter in detecting purity of functions, the chance of
CSE increase. And I think P0145R0 will reduce such increased chance.
Suppose that P0145R0 will reduce 1% of such chances of CSE. If chances
of CSE increase, the impact of P0145R0 (chance * 1%) will also increase.

Yes, the impact can be reduced if "compilers become wiser" in proving
independence of argument expressions. But I think it is far from status
quo, and will never reach to the point where it can assume that,
especially in the case with a call to unknown function.

> So exactly what cases would common subexpression elimination be allowed
> under the current rules but forbidden under P0145?

I think it is shown in the example at very beginning of this thread.
https://groups.google.com/a/isocpp.org/d/msg/std-proposals/Ew_0zQl_yBg/el_sLD4GBQAJ
If you don't think the example is not showing such cases, please point
out where and how the example is wrong.

--
k_satoda

[Nicol Bolas]

No, I got that backwards. You're right.

Strict aliasing has two parts. One part is what I talked about; namely, what the compiler is allowed to assume that code means.

The other part is the part that says, "doing certain things means undefined behavior." For example, type-punning is forbidden by strict aliasing, and doing it leads to undefined behavior. However, these things are forbidden precisely to allow the first part: to allow the compiler to make assumptions about something.

After all, given pointers to two unrelated types, if you allow type-punning, then the assumption that these pointers point to different objects may not be true. So the user prohibition part of strict aliasing is what allows the compiler assumption part to make sense.

When you use -fno-strict-aliasing, as you said, the compiler must assume nothing about whether pointers alias. Or more to the point, when not using strict aliasing, compilers must assume that pretty much any two pointers can alias.

However, the reason why people would use that switch is because they want type punning, and they want to shut up GCC/Clang's warnings about it not being legal C++.

[Nicol Bolas]

How? As shown below, your initial example very much can be optimized under P0145. So exactly how will P0145 reduce the ability for CSE-based optimizations, given greater compiler knowledge of function purity?

> So exactly what cases would common subexpression elimination be allowed
> under the current rules but forbidden under P0145?

I think it is shown in the example at very beginning of this thread.
https://groups.google.com/a/isocpp.org/d/msg/std-proposals/Ew_0zQl_yBg/el_sLD4GBQAJ
If you don't think the example is not showing such cases, please point
out where and how the example is wrong.

I don't have to; Gabriel Dos Reis did ;)

As he said:

the compiler knows it can invoke the "as if" rule and reorder as it pleases -- there is no way to tell.

If `pure` is a pure function, and the compiler knows it is a pure function, and you invoke it twice, and the compiler knows that the argument you invoke it with is the same in both cases... then the compiler can invoke the "as if" rule and optimize out the second call.

This is true regardless of whether P0145 is in force or not. There is nothing in that document that would prevent this optimization.

The only case where it would matter is if the compiler doesn't know that the function is pure. And if it doesn't know that the function is pure, then it has absolutely no right to optimize out the second call.

Compilers should not be making optimizations based on what it thinks it knows about behavior.

[Kazutoshi Satoda]

On 2015/11/23 0:52 +0900, Nicol Bolas wrote:
> On Sunday, November 22, 2015 at 10:20:18 AM UTC-5, Kazutoshi SATODA wrote:
>> On 2015/11/22 23:22 +0900, Nicol Bolas wrote:

...

>>> So exactly what cases would common subexpression elimination be allowed
>>> under the current rules but forbidden under P0145?
>>
>> I think it is shown in the example at very beginning of this thread.
>> https://groups.google.com/a/isocpp.org/d/msg/std-proposals/Ew_0zQl_yBg/el_sLD4GBQAJ
>> If you don't think the example is not showing such cases, please point
>> out where and how the example is wrong.
>

> If `pure` is a pure function, and the compiler knows it is a pure function,
> and you invoke it twice, and the compiler knows that the argument you
> invoke it with is the same in both cases... then the compiler can invoke
> the "as if" rule and optimize out the second call.
>

> This is true *regardless* of whether P0145 is in force or not. There is

> nothing in that document that would prevent this optimization.

You seem missing the point of the example where the function pure() is
called with argument non_local (non-const variable). That variable can
be modified by the call of unknown() which P0145R0 specify to intervene
the two calls of pure(non_local). The compiler can't perform CSE if the
argument non_local can be different for these two calls.

--
k_satoda

[Nicol Bolas]

I just noticed that `unknown` was a global function of unknown purity which theoretically could have changed "non_local". So the conditions for this problem are:

1: A pure function call, using non-local parameters.
2: A function call to a function of unknown purity.
3: A pure function call, using the same non-local parameters as before.

Exactly how often is that likely to happen? Pure functions aren't exactly the most common thing, particularly by the definition proposed in the paper you cited (no pointer/references in arguments, so no member functions).

[Kazutoshi Satoda]

On 2015/11/23 1:21 +0900, Nicol Bolas wrote:
> I just noticed that `unknown` was a global function of unknown purity which
> theoretically could have changed "non_local". So the conditions for this
> problem are:
>
> 1: A pure function call, using non-local parameters.
> 2: A function call to a function of unknown purity.
> 3: A pure function call, using the same non-local parameters as before.

It's close. Please read below for more cases.

> Exactly how often is that likely to happen? Pure functions aren't exactly
> the most common thing, particularly by the definition proposed in the paper
> you cited (no pointer/references in arguments, so no member functions).

I don't know exactly, but my guess is shown at the part "While the
above code looks a fiction, ..." of my first post.

Note that the "purity" of the condition of these case is not limited to
"pure function." It is enough that a function (as replacement of pure()
in the example) is "pure enough" to perform CSE. For example, it can
read arbitrary objects via pointers or references.

int f(int a1, int a2, int a3);

int g(std::map<int, int> const& m, int (*unknown)())
{
return f(m.at(0), unknown(), m.at(0));
}

The two lookup "m.at(0)" can be eliminated into one under the current
rule, but it is not allowed after adoption of P0145R0.

--
k_satoda

[FrankHB1989]

I am seriously against P0145R0. As a user of C++, I urge EWG and CWG to reconsider the reasons to adopt this proposal.

To be systemic, here are my reasons:

1. It is a breaking change.
2. It complicates the language itself. (If in doubt, compare the wording, please.)
3. As mentioned above, it may harm to optimization.
4. The reason represented by the proposal is unsound. It harms teachability and makes it hard to get consensus on conventional ("best") practice.
   

I feels the first 2 points should be acknowledged here.

To the 3rd point, one key point I'd note here is: this change forbids a portable way to easily express the unsequenced evaluation of an expression intended by the author of the code.

For this purpose, I currently explicitly used the unsequenced function parameter rule and a macro wrapper for readability. (It would probably be better with PR0146R0.) However, the change by this proposal makes it a joke.

Specifically, I can, but don't want to:

// Not portable!
#pragma GCC diagnostic push

#pragma GCC diagnostic warning "-std=c++11" // Huh, is it documented?
// ...
#pragma GCC diagnostic pop

For the 4th point, one key point is: it is nonsense to support bad code.

If the author want the clear evaluation order, do extract the subexpression as a single statement (followed by ';'). This transformation should not be a problem on well-formed code since even constexpr functions now support multiple statements in the body, and there are lambdas.

What if the author do not know what order they want ... who allow they to code such spaghetti?

I don't think anyone should be encourage to write such code except for the purpose of testing the implementation (e.g. [-Wsequenced] or ubsan). Any senior C++ user would probable agree this point easily by their experience. The code should be reject by the contemporary style because it causes confusion. The suggestion of change itself also has caused such problem, see comments on Herb Sutter's poll.

To reduce the potential risks, a programmer who don't have enough common sense about sequence rules (also imply the definition of "undefined behavior"), should not be granted permission of modify the C++ code base in a serious project. This is similar to C which uses similar UB rules with "sequence point" wording. These knowledge should be at very basic level of the language. The unsequenced evaluation rules are excellent examples about the position and importance of these rules. Other subtle rules are usually more difficult to learn. That's why I think the change harms the teachability: we'd lost a chance to tell the newbies to discipline themselves about being responsible to what they'd write, which is hard to rescue later. This is super important for a language has so many traps to use.

There are more details about the rules, e.g. I think CWG222 is a good change. It also loose the requirements on user code, but it does not have the drawbacks above, esp. it did not introduce the confusions like above.