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?

Why do I claim that the following statement is parallelisable (if EO is defined)? 

    my $result = func1( $a ) + func2( $a++ );

[download]

The simple answer is "Because there is nothing to prevent it!".

In the absence of defined EO, the compiler is theoretically free to process that line as follows:

  1. Increment $a
  2. Stack an alias to $a.
  3. Call func2().
  4. Returning from func2() leaves it's result on the stack.
  5. Stack an alias to $a.
  6. Call func1().
  7. Returning from func1() leaves it's result on the stack.
  8. Call add().
  9. The result of Add() is left on the stack.
  10. Add a variable $result to the pad and initialise it with the value popped from the stack.

Or, it could do that

  1. Stack an alias to $a.
  2. Call func1().
  3. Returning from func1() leaves it's result on the stack.
  4. Increment $a
  5. Stack an alias to $a.
  6. Call func2
  7. Returning from func2() leaves it's result on the stack.
  8. Call add().
  9. The result of Add() is left on the stack.
  10. Add a variable $result to the pad and initialise it with the value popped from the stack.

The results will be different, even without the possibility of either function modifying their parameter.

The value of $a will be different, dependant upon the unknowable order in which the compiler executes the code.

With EO undefined, the programmer cannot indicate the required order, and so must place the calls to func1() and func2() in separate statements, and that explicitly prevents the two functions being called in parallel.

With defined EO, there is only one possible sequence:

  1. Place an alias to $a somewhere (for func1()).
  2. Increment $a.
  3. Place an alias to $a somewhere (for func2()).
  4. * see below.
  5. Invoke an asyncronous call to func1() also passing a semaphore.
  6. Invoke an asyncronous call to func2() also passing a semaphore.
  7. Wait until both semaphores clear.
  8. Retrieve the results from func1() and stack.
  9. Retrieve the results from func2() and stack.
  10. Call Add().
  11. The result of Add() is left on the stack.
  12. Add a variable $result to the pad and initialise it with the value popped from the stack.

*Because there are no other dependancies or ambiguities, the compiler can know that (if they are parallelisable), it only needs the results from func1() and func2() in order to call Add(), so it is free to parallelise func1() and func2().

Because of defined EO, 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".

The onus is on the programmer, and is completely within his control, and the compiler does not need to make that determination.

That is the salient point.

Without defined EO, the only control the programmer has over the order of execution is to use separate statements, but separate statements automatically precludes transparent parallelism.

With defined EO, the programmer is explicitly indicating that any two functions (methods) that are marked as being parallelisable, that appear in the same statement, as co-operands to a non-serialising operation, can be parallelised.

He is telling the compiler this by that placement. The compiler cannot make this determination without huge amounts of complex analysis, but the programmer can make that determination--IF EO is defined.

Without EO, it requires complicated extra syntax, which entirely negates the concept of transparent parallelisation.

You may argue that the concept of transparent parallelisation isn't usful--I'd say you where wrong, but that's a philosophical argument.

You may argue that extra syntax is the way to go--again, I will argue with you about that.

But if the concept is useful, and I strongly believe it is, then having a defined EO is an unarguable necessity.

I also happen to think that it will be seen to be a requirement for other parts of the Perl 6 syntax to work also, but that's still not completely clear.

I also think that as the supposed benefit of potentially improved efficency, through statement reordering, has never, and can never be realised, the only reason for not defining EO is a myth.

That leaves us with gaining a benefit from defining it and loosing nothing, or not defining it and not gaining something.

I do not see why people are arguing for retaining ambiguity for no gain.

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 EO undefined? (More details!)
by Corion (Patriarch) on Apr 16, 2005 at 18:40 UTC

    With your explanation, I finally got that by "with defined EO, that func1() and func2() can be parallelised.", you actually mean "In some cases, it's possible to parallelize even with a defined EO, and give the user a well-defined result". In no way does an undefined EO prevent parallelization, as I've shown in another node. It merely frees the compiler/interpreter/CPU from the requirement to produce reproducible results if the subexpressions contain side effects.

    Your "defined execution/evaluation order" cannot protect against side effects, even if you place semaphores everywhere, because IO or other deep/unprotected sideeffects will get in the way, unless you factually reduce the whole expression evaluation to a single thread. "defined execution/evaluation order" is the promise to the user that, no matter what, subexpression A will always be evaluated before subexpression B. Which obviously prevents parallelization.

    Let's assume a simple order of execution of left-to-right. Your expression evaluation then obviously needs to perform all of func1, before it ever is allowed to enter func2, because it doesn't know what side effects func1 and func2 will share (assuming that a list of the side effects of both, func1 and func2 is not available before the two are called).

    Your idea that "With defined EO, the programmer is explicitly indicating that any two functions (methods) that are marked as being parallelisable, that appear in the same statement, as co-operands to a non-serialising operation, can be parallelised." does in no part rely on the defined EO. If two pieces of code are marked as being parallelisable, then the only time you will notice the difference in the result is, if they are not actually parallelisable, because then the side-effects in the undefined EO can produce differing results in two executions of the program. With a defined EO, there can never be two differing results, because the program can effectively only be executed in a single path of execution.

[reply]
      If two pieces of code are marked as being parallelisable, then the only time you will notice the difference in the result is, if they are not actually parallelisable

      Again, I have to disagree. This would mean that the only time a routine could be marked as parallelisable, is if the author of that routine knew exactly all circumstances under which it could be called--and that's not possible.

      I want the authors of libraries and classes to be able to mark their routines as parallelisable, based upon what they do--without consideration to when and where they might be called. This is the only way they will be able to do so ubiquitously, without being responsible for testing every possibilty-which is impossible, and will therefore prevent anyone ever so marking their subroutines and methods.

      The onus and responsibility for chosing whether to use sub and methods marked as parallelisable, in circumstances in which they will actually be called in parallel, must lie entirely with the caller--else authors will never provide that possibility. No other way will ever work.

      And that requires defined EO.

      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]
Re^35: Why is EO undefined? (More details!)
by Anonymous Monk on Apr 18, 2005 at 08:57 UTC
    • Invoke an asyncronous call to func1() also passing a semaphore.
    • Invoke an asyncronous call to func2() also passing a semaphore.
    • Wait until both semaphores clear.
    Either both functions get the same semaphore, and in effect, they run in serial. Or they don't, and the semaphore is in principle bogus. And there's no order of execution here, since you don't know in which order the functions are going to be performed.

    But we've said this dozens of times already.

[reply]
      Either both functions get the same semaphore, and in effect, they run in serial. Or they don't, and the semaphore is in principle bogus.

      Wrong. See WaitForMultipleObjects--but in case the source of the reference scares you, here is the salient point:

      The WaitForMultipleObjects function returns when any one or all of the specified objects are in the signaled state.

      Emphasis added

      And there's no order of execution here, since you don't know in which order the functions are going to be performed.

      Only by your definition, not mine. My definition explicitly allows concurrent derivation of the operands to any non-serialising, binary operator.

      And the principle is well known. It is termed "dataflow threading" or Sheduled Dataflow Architecture.

      But we've said this dozens of times already.

      Wrongly each time.

      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]
[d/l]
        My definition explicitly allows concurrent derivation of the operands to any non-serialising, binary operator.
        Oh, sure, your definition allows it. Noone is questioning that. Your definition isn't the point.

        The point being made is that in general, any implementation will effectively be serialized.

        You haven't made a convincing argument that the run-time can figure out which parts can be run in parallel, without violating a defined order of execution.

[reply]

In Section Seekers of Perl Wisdom