Beefy Boxes and Bandwidth Generously Provided by pair Networks
We don't bite newbies here... much
 
PerlMonks  

Re: Why is the execution order of subexpressions undefined? (basics)

by tye (Sage)
on Apr 16, 2005 at 21:04 UTC ( [id://448528]=note: print w/replies, xml ) Need Help??


in reply to Why is the execution order of subexpressions undefined?

There is one point that BrowserUk keeps insisting on that everyone else in this thread (as far as I can tell) has the opposite conclusion. So let's discuss just that one point: Does a defined or undefined evaluation order allow or prevent the compiler from introducing implicit parallelization?

If I write $x = f() + g(); and the order of evaluation is defined, let's say from left to right, then f() must be called before g(). If the evaluation order is undefined, then f() could be called first or g() could be called first or f() and g() could be called in parallel.

So, undefined evaluation order allows the compiler to perform operations in parallel (because the programmer can indicate that f() and g() can be done in any order by putting them into the same expression, inside of which evaluation order is not restricted by a definition).

If EO is defined, then f() and g() can't be optimized to be called in parallel unless the compiler can fully analyze f() and g() and determine that they have no effect on each other. This is a fundamentally difficult problem and so, in the general case, this analysis cannot be done. So defined EO prevents the compiler from automatically adding parallelization (or other optimizations made possible by changing the order in which steps are performed).

With undefined EO, if f() and g() should not be called in parallel, then the program instead writes $x= f(); $x += g();. With defined EO, there is no difference between the two ways of writing that sum so the programmer has no way to communicate a distinction between "these must be run in a particular order" from "these can be run in parallel".

Now, BrowserUk had an example closer to $x = f($i) + g(++$i); and so perhaps BrowserUk is thinking that a defined EO is important to allow the compiler to add parallelization because otherwise writing this expression is basically an error -- because what gets passed to f() and/or g() depends on the implementation. If so, then he has a point there. But that point is invalidated by two points.

Firstly, the first part of this node shows that this same definition of EO prevents f() and g() from being parallelized so the ability to write $x = f($i) + g(++$i); can't provide the specified gain. You can now write this expression safely, but the compiler can't (in general) do any optimization on it that involves calling g() other than after f() has finished.

Secondly, defined EO is not required for the programmer to express that. If that is what the programmer wants, then they write

$x = f($i) + g(1+$i); $i+=1;
or
$i+=1; $x = f($i-1) + g();
or
my $t = $i++; $x = f($t) + g($i);

or whatever they really meant (I don't know, because I don't know what precise evaluation order was in the mind of this theoretical programmer when they wrote that expression which is ambiguous in the absense of a specific, strict definition of EO).

Note that such an expression of the algorithm would prevent the compiler from moving the assignment to $i around because the programmer ends up specifying the assignment in a separate statement which introduces a sequence point (denoted by the semicolor, ";") across which the compiler is forbidden to move operations (in time) -- well, unless the compiler can perform an analysis that shows that such a movement would not change the outcome.

So, you could make the point that the undefined EO has required the programmer to write code in a way that prevents the compiler from optimizing parts of the code. This is true. However, the gain of being able to call f() and g() in parallel is likely much greater than any gain to be had by being able to move around the much simpler operation of assigning to $i. Further, the compiler is much more likely to be smart enough to be able to tell when a simple assignment can be moved than to be able to tell when two arbitrary expressions (calls to the f and g functions in our examples) are totally independent.

And that is part of the point. f() and g() are stand-ins for arbitrary expressions and so are the important things to consider parallelizing. And the process of making them parallelizible (because EO is undefined) while still well-defined (in the face of undefined EO) is easy to do by, at worst, introducing temporary variables. And the fact that the simple assignments to these temporary variables are restricted by being in separate statements is still a net win because 1) they are tiny operations so optimizing them is much less important and 2) they are extremely simple operations so analysing them to the point of determining that they can be safely moved despite the sequence points is often feasible.

In summary, a defined EO prevents the compiler from moving around operations (in time) in order to optimize them (including running them in parallel) unless the compiler can analyse the operations to the point of determining that such a move does not impact the results.

An undefined EO allows the programmer to write expressions that tell the compiler "you don't need to perform a difficult or impossible analysis of the parts of this expression in order to be able to prove that the order in which parts are done doesn't matter, because I am confident that the order doesn't matter" but can also require the programmer to move certain simple operations out in to separate statements. This prevents the compiler from optimizing these separate statements, except (as in the previous paragraph) when it can prove that the optimizations are safe.

Finally, from experience, I assert that it is not hard to come across cases of f() and g() in the real world where it is easy for the programmer to understand (without being able to prove it) that they are not intertwined while the amount of analysis required by a compiler to prove independence is substantial, often to the point of being infeasible or even impossible.

I hope that helps cut through the near total lack of communication that I perceive in the majority of this thread and allows someone to get to the crux of this persistent misunderstanding.

- tye        

Replies are listed 'Best First'.
Re^2: Why is the execution order of subexpressions undefined? (basics)
by BrowserUk (Patriarch) on Apr 17, 2005 at 03:21 UTC

    Maybe, just maybe, I've hit upon the explanation that will calrify the defined EO thing.

    Your assertion is that :

    If I write $x = f() + g(); and the order of evaluation is defined, let's say from left to right, then f() must be called before g().

    First, let's assume that for reasons of generalisation, that the order defined is right to left. That's okay in your example because addition is communicative, so your expression will still do the right thing.

    But, now let's switch to a non communicative operator:  $x = f() - g();. What happens?

    Nothing. Because the defined EO only pertains to the order in which the functions are called, not to the order in which the results they produce are used. The defined EO doesn't force the results to be used in reverse.

    Now come back to your assertion that defined EO means that f() and g() cannot be parallelised because f() must be called before g().

    Why?

    Once f() and g() have returned their values, you have a simple expression: $rv1 + $rv2; and there is nothing about defined EO that prevents that from being completed.

    And prior to that, f() and g() can be called in parallel, because I'm explicitly stating that with defined EO, parallelisable operations either side of a non-serialising operator can be called in parallel.

    That is, I'm not just saying I think they can, I'm saying that defined EO can be defined such that it is so.

    Where the defined EO comes into play is when you have a compound expression. This is, as you picked up on when you said:

    Now, BrowserUk had an example closer to $x = f($i) + g(++$i); and so perhaps BrowserUk is thinking that a defined EO is important to allow the compiler to add parallelization because otherwise writing this expression is basically an error -- because what gets passed to f() and/or g() depends on the implementation. If so, then he has a point there.

    the purpose of the parameters I showed in my examples. They are the simplest sub-expressions that have a side effect, which is their entire purpose for being there.

    It is at the level of the compound expression, where the defined EO becomes important.

    I'm going to contrive an example for the purposes of discussion. It will probably be a weak and somewhat non-sensical in it's contrivance, but I'm admitting that up front to avoid the ensuing argument about it. I'm contriving the circumstance using the simplest expressions possible to demonstrate the point, but the expressions and logic behind them act as placeholders for any similar set of circumstances that could exist.

    Here I want the first value returned by $o->next given to f() and the second to g():

    $x = f( $o->next ) + g( $o->next ); $y = f( $o->next ) - g( $o->next );

    Here, I want the reverse:

    $x = g( $o->next ) + f( $o->next ); $y = -g( $o->next ) + f( $o->next );

    Yes, I can achieve the same thing in the presence of undefined EO by doing:

    my $temp1 = $o->next; my $temp2 = $o->next; $x = f( $temp1 ) + g( $temp2 ); $temp1 = $o->next; $temp2 = $o->next; $y = g( $temp1 ) - f( $temp2 );

    and reversed

    my $temp1 = $o->next; my $temp2 = $o->next; $x = f( $temp2 ) + g( $temp1 ); $temp1 = $o->next; $temp2 = $o->next; $y = f( $temp1 ) - g( $temp2 );

    but why should I have to? Did you see how much clearer the first pair are than the second?

    And did you notice that the second pair contain an error? An error that would have stood out like a sore thumb in the first pair, but that gets lost in the noise of the second.

    Of course, nothing is forcing anyone to use the first form if EO is defined, it just enables it for those that wish to. There is no shotgun either way with defined EO, but without it one option is excluded--not very Perlish.

    And yes, in the presence of defined EO, f() and g() can be executed in parallel--if we chose to allow that. No compiler analysis is required, the programmer is explicitly condoning it.

    If that does not convince you that defined EO is a gain-something, lose-nothing proposal, then probably nothing will, but your being unconvinced will not change that it is so.


    Examine what is said, not who speaks -- Silence betokens consent -- Love the truth but pardon error.
    Lingua non convalesco, consenesco et abolesco.
    Rule 1 has a caveat! -- Who broke the cabal?

      Your definition of EO is significantly different from what I think everyone else assumed it could mean. And, I would like to make the observation that your definition of EO is counter-intuitive - at least to the majority of those who have participated in this thread.

      For all intents and purposes, your defined EO is pretty much undefined. Which gets called first - f or g? You're saying that you're not defining this. This is a seriously underdefined execution order, because only bits and pieces (and a very difficult bit and piece to define, as is evidenced by this thread) are defined, but not the entire expression.

      It's an interesting definition. I don't think there is much of a gain if only because you've left it pretty much completely undefined. (What if f or g affect $o? What order then?) We've gained so little, and so counter-intuitively, that I'm not sure it's significant enough to put forth code to implement it.

      Parallelism is not something we've gained - it's something we still lose. Any definition of execution order is, well, by definition, a definition of serialisation. For example, no matter what, the addition of the two values must happen prior to the assignment to the LHS. We can't add and assign in parallel. Similarly, if we must evaluate all the arguments to functions prior to calling any of them, then we are introducing a sequence point (which is quite invisible, which is why it's counter-intuitive) where we must synchronise everything before paralellising anything.

      Further, I'm not sure why you're only defining this for arguments to functions. Why not full subexpressions? That is, defining whether the LHS of a binary operator is evaluated before or after the RHS. Why the arbitrariness of the definition? It would be more intuitive if the whole expression was defined. It's confusing to only go half way, and to stop at some arbitrary point which doesn't seem to have any purpose to it.

      You may think I'm opposing you for the sake of opposing. And I'm definitely not as tactful as TimToady. But, at the very least, I hope that I'm helping to refine your idea, or at least the presentation of it. At this moment, however, I do remain unconvinced that there is an idea here that would make life better, so, at the most, I'm hoping that I convince you to see the light. ;-)

        What if f or g affect $o? What order then?

        Then, as TimToady put it:

        you are implicitly promising that the parallel branches either A) don't have side effects, or that if they do, B) you don't think the side effects will interact, or C) the side effects are idempotent so it doesn't matter in which order they happen, or D) you just don't give a rip

        Or as I put it:

        the programmer has explicitly indicated that there are no interdependancies between func1() and func2(), or if there are any interdependancies, he knows that they will "do the right thing".

        If there are interdependancies between f() and g(), for example, they modify $o in some way that precludes their being parallelised, then then programmer must not put them in the same statement.

        my $rv1 = f( $o->next ); my $rv2 = g( $o->next ); my $x = $rv1 + $rv2;

        No paralleisation is possible because they are no longer in the same expression.

        Further, I'm not sure why you're only defining this for arguments to functions.

        As stated, I have been restricting myself to the simplest possible case that demonstrates the possibility of parallelism, and the need for defined EO.

        The mechanism does, by implication, extend to all sub expressions within expressions.

        my $x = $i + ++$i;

        Because ++$i involves a unary operator, it is a subexpression. With undefined EO, the programmer cannot know what this will produce, with defined EO he can. I'm not for one moment suggesting that it is a good thing to do in practice, but it demonstrates the point. But it is not a good example for the wider discussion because there is not scope for parallelism.

        And in this:

        $x = f( g() + h() ) * p( q() - r() );

        has 3 points of possible paralellism. Each of g() & h(), q() & r() and f() & p().

        And with defined EO, if h() has a dependancy on r(), and must be executed first, then I can write that as:

        $x = p( q() - r() ) * f( g() + h() );

        and know it will do the right thing. Without it, I have to write:

        my $temp1 = p( q() - r() ); my $temp2 = f( g() + h() ); $x = $temp1 * $temp2;

        and lose the oportunity for one level of parallelism. Or as:

        $temp1 = q() - r(); $temp2 = g() + h(); $x = f( $temp2 ) * p( $temp1 );

        Which anyway you cut it is less clear and more open to maintainance errors than the first one above.

        I do not consider my definition of EO incomplete--for one thing, I haven't outlined what my definition would be--but the point remains that it can be whatever is required to achieve the desired effect. The point is that subexpression must be evaluated before the expression they are a part of. Once the complex expression is reduce to a simple expression, the rules can change, if that is what is required to achieve the result.

        You say it is unintuative--which I take to mean that you cannot think of any other reason to oppose it--but you do not find the current Perl 5 "the compiler might do it this way or it might do it that way" intuative?

        And I'm definitely not as tactful as TimToady

        Strange, but I saw many confirmations of my position, though I agree not complete agreement, in his posts. Maybe I misread him, but much of the little he said echoed things I have been saying in this thread.

        For now, I admit defeat--I am not going to change your mind and nothing I have seen here has changed mine. So, I'll stop right here.


        Examine what is said, not who speaks -- Silence betokens consent -- Love the truth but pardon error.
        Lingua non convalesco, consenesco et abolesco.
        Rule 1 has a caveat! -- Who broke the cabal?

Log In?
Username:
Password:

What's my password?
Create A New User
Domain Nodelet?
Node Status?
node history
Node Type: note [id://448528]
help
Chatterbox?
and the web crawler heard nothing...

How do I use this?Last hourOther CB clients
Other Users?
Others meditating upon the Monastery: (8)
As of 2024-03-28 21:55 GMT
Sections?
Information?
Find Nodes?
Leftovers?
    Voting Booth?

    No recent polls found