in reply to Re^33: Why is the execution order of subexpressions undefined? (magic ruts)
in thread Why is the execution order of subexpressions undefined?

The trouble with your lockstep game is that each step is dependant upon a single previous step--but most operations in computing have two operands.

With your chain of events (a->b->c->d->e->f), there is no opportunity for parallelisation, but with every two operand operation, there is such an opportunity.

The thing to remember is that we are talking about Perl 6 and Parrot. At the Parrot level, every Perl level operation becomes a method call. That means that for every non-simple expression (ie. any expression that involves anything other than directly referencable simple scalar operands), there is the opportunity to overlap the execution of the derivation of those operands.

I'll try to clarify that. In these expressions: 

my $scalar = $untied_var1 <op> $untied_var2;
my $scalar = func1() <op> $untied_var;
my $scalar = $untied_var <op> func1();

[download]

There is no opportunity for parallelisation, because there is nothing to overlap.

However, in these expressions: 

my $scalar = func1() <op> func2();
my $scalar = $tied_var1 <op> $tied_var2;
my $scalar = $tied_var <op> func1();
my $scalar = func1() <op> $tied_var;
my $scalar = $obj1->method() <op> $obj2->method();
# and all the other combinations

[download]

There is an opportunity for parallelisation.

The processing involved in calculating the operands to <op> could involve a db access, or network IO or File IO or just a long mathematical calculation that would benefit from using a second cpu, or a floating point calculation that could be executing within the FPU whilst the main CPU does something else.

Some of this type of paralellism is already performed by the pipelining and hyperthreading architectures, but it is very limited--by locality--to sequential steps within a given routine.

In order to extend the acceptance of the opportunites, it traditionally requires the programmer to manually perform the steps required to asynchronously invoke the overlappable routines and then perform the resyncing required to pull the results back together. This is tedious and error prone. If these steps can be automated, then the potential of the soon-to-be-ubiquitous availablity of multi-cored, multi-processing arcutectures can be more easily and reliably utilised.

Now imagine that there was some mechanism for indicating that a subroutine or method may take some time to calculate or obtain, and could benefit from being overlapped. Ignore what that mechanism would be, or under what circumstances it could be used for now.

The compiler now knows that when it encounters two such subroutines or methods as the source of operands to a single, non-serialising operation, it can make those calls asyncronously and await their completion before using the results the produce as arguments to the operation in question. The compiler writers can get the mechanism right and it will be used whenever and whereever the opportunity arises. That is transparency.

But the compiler can only do this, if the programmer can clearly indicate that there are no dependancies--and that requires that EO be defined.

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?

Replies are listed 'Best First'.
Re^35: Why is the execution order of subexpressions undefined? (magic ruts)
by Corion (Patriarch) on Apr 16, 2005 at 19:02 UTC

    First of all, you did silently ignore my second, upper town example. I don't know why, as it fits very well with your idea of "two operands" yet does not require order of execution/evaluation to be totally defined.

    But the compiler can only do this, if the programmer can clearly indicate that there are no dependancies--and that requires that EO be defined.

    Bogus. If the execution order is left undefined, the programmer can still clearly indicate the order by moving out the expressions into different statements. So this is no requirement for parallelization. In fact, it actually prevents parallelization, because the compiler/interpreter/CPU (generally) cannot determine if a function call will have side effects and thus must delay all further execution until the one function call has finished and produced the result.

[reply]
      First of all, you did silently ignore my second, upper town example.

      Because there is never any opportunity for transparent overlapping. The final results of the two chains (C & F), never come together.

      All the compiler sees is two entirely unconnected sequences of operations. When written in the source code, one set will come before the other or vice versa. For the compiler to determine that some of those parts can be overlapped would require extensive analysis of all of those steps in order to ensure that there were no hidden interdependancies. This would require the hugely intelligent compiler that tye, rightly, dismissed as a possibility.

      There have been some attempts to do this, and with an entirely side-effects free language (Haskell, OCAML etc.), and very, very compilcated compilers (eg. GHC), then you can perform that kind of analysis, but for Perl, which is not, and will not be, side-effects free, the analysis would have no boundaries. Every step could have an interdependancy upon a previous step, and that on a previous step and ultimately, the first two steps in any two apparently unconnected chains could share an interdependancy. That means that the compiler would have to reanalyse every step in every pair of dependancy chains, and that is the NP-complete/Halting problem.

      That's why it must be the programmers that make these determinations. The authors of routines indicate that there is some scope within each routine for parallelisation.

      The callers of those routines, decide whether the particular combination of two routines that the need to call at any given point in their code, if so marked by their authors, can be overlapped.

      Bogus. If the execution order is left undefined, the programmer can still clearly indicate the order by moving out the expressions into different statements

      But, as soon as you move the routines into separate statements, all opportunity for the compiler to overlap those routines is lost, unless the compiler is going to solve the Halting problem.

      The only time the compiler can transparently decide to overlap the routines, is when the they produce the operands to a non-serialising operation. And that means that they must be in the same expression.

      I'm sorry for all the emphasis and repetition, but it is so clear (to me), that there is a single sequence of logical steps in this conversation. If A is true, then B can be so. If B is true, then C is so. It feels to me when I am reading your posts that you keep considering one part in isolation of the rest and and drawing conclusions on that basis, but you have to consider the entire chain to see the full picture--just as the compiler would have to do in order to parallelise your Uptown sequence.

      And at the basis of the whole thing, is this weddedness to an undefined EO, which serves no good purpose to start with. I simply do not understand why people continue to argue in support of something that has no benefits and only ever causes them extra work.

      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?
[reply]

        We are still not communicating. You are actively ignoring the one fact that my two examples highlight. EO enforces an execution order. That is, all lists you will ever see, will be of the lower town kind. While, with undefined EO, you will also see lists of the kind that the upper town example has. And there is no need for them to come together. Which is the central point, at least to me. That you dismiss this means that you are talking about something completely different, or have a position/outlook completely different from mine. But as this discussion has now taken a depth of 37 levels, and people certainly smarter than I haven't conveyed their understanding to me, I'll leave it at that - sorry for not communicating my view better.

[reply]

In Section Seekers of Perl Wisdom