A
Adam DePrince
I frequently find myself in a situation where I wish I could say "the
execution order of these two lines just doesn't matter."
Proposed here are two freshly drafted PEP's advocating for the addition
of nondeterminism as a spring board for future automatic parallelism.
The first calls for core language changes, the second calls for a minor
(and likely symbolic) change to list comprehension's semantics to better
support future parallelism.
PEP: XXX
Title: Nondeterminism
Version: $Revision$
Last-Modified: $Date$
Author: Adam DePrince <[email protected]>
Status: Draft
Python-Version: 3.0
Type: Standards
Content-Type: text/plain
Created: 24-Mar-2006
Post-History:
Abstract
Proposed herein is are two new control flow structures that allow
the explicit specification of parallelism by defining the order of
expression evaluation as non-deterministic, thus removing the
requirement of sequential execution.
Background
A number of mechanisms have been proposed in Python that have the
side effect of permitting the automatic discovery of parallelism.
PEP 288 presents the notion of a generator, an object that
inherently lends itself to concurrent operation and possibility
automatic self organization of a pipeline.
Stackless Python in PEP 219/220 presents a mechanism by which a
large number micro threads could be efficiently supported, thus
allowing for a realistic manifestation of a deep generator based
software pipeline.
Additionally, this PEP's sibling, XXX, proposes that the
execution order of list comprehensions be made non-deterministic
to permit future parallel implementations.
DISCUSSION
Two new control flow structures are proposed. While as of yet no
name is proposed, for the sake of brevity we will refer to them as
any and first.
The any structure would call for the execution of all expressions
within the any block in an non-determinate order. The user would
warrant that no side effects exist between the expressions, and
assigned to the variable the any block would be a list
representing the return values of each of the expressions in the
order they appear in the code (but not necessarily in the order of
execution.)
The first structure would execute all enclosed expressions
concurrently, again, the order of execution being
non-deterministic, other than the promise that all would be
started. The return value of the first expression to finish would
be assigned to the variable associated with the first block and
the execution of the other operations terminated.
SPECIFICATION
The use of the word 'any' and 'first' is only a convenience. I do
not yet propose a keyword for these structures.
...
any retval:
1
2+3
my_function_that_returns_17()
...
retval would be assigned [1, 5, 17] Only the order of evaluation
is not deterministic.
first retval:
urllib.open( 'mirror1' ).read()
urllib.open( 'mirror2' ).read()
urllib.open( 'mirror3' ).read()
....
retval would contain the data from the fastest mirror, the other
threads would be disposed of.
IMPLEMENTATION
TBD - Incomplete
REFERENCES
TBD
COPYRIGHT
This document has been placed in the public domain.
PEP: XXX
Title: Nondeterministic List comprehensions
Version: $Revision$
Last-Modified: $Date$
Author: Adam DePrince <[email protected]>
Status: Draft
Python-Version: 3.0
Type: Standards
Content-Type: text/plain
Created: 24-Mar-2006
Post-History:
Abstract
The semantics of the list comprehension offer the future benefit
of multi-threading and parallel execution, assuming that the
programmer treat the order of evaluation as non-deterministic and
avoids the introduction of dependencies and side-effects.
Background
A number of mechanisms have been proposed in Python that have the
side effect of permitting the automatic discovery of parallelism.
PEP 288 presents the notion of a generator, an object that
inherently lends itself to concurrent operation and possibility
of automatic self organization of pipelined, and thus parallel,
operation.
Stackless Python in PEP 219/220 presents a mechanism by which a
large number micro threads could be efficiently supported, thus
allowing for a realistic manifestation of a deep generator based
software pipeline.
DISCUSSION
Generators and generator comprehension are often regarded as
superior to list comprehension due to the reduced footprint of
in-flight data and the future potential of vertical parallelism via
pipelining.
List comprehensions, while having the drawback of requiring the
presence of the entire working set in-flight, places no inherent
restriction on the order of execution. This permits us to
distribute the execution effort horizontally across multiple
micro-threads, with a far higher potential for parallelism than
generators at the expense of requiring the user warrant the
absence of side effects of dependencies between each passing of
the list comprehension loop.
This minor semantic requirement that list comprehension possess
no interdependencies or side effects permits us to operate on the
list in an arbitrary order, including dispatching the execution
across multiple threads.
SPECIFICATION
We change the semantics of a the list comprehension to
explicitly state that the order of evaluation is
non-deterministic, and that there should exist no dependencies or
side effects. This leaves open the potential for future
parallelization.
PROBLEMS
There are a currently a number of problems. Generators provide an
intuitive and natural partitioning of the problem. The future
partitioning of a list comprehension is a more capricious;
generally, we choose a fixed number of threads to dovetail across,
but little guidance can be gleaned from the use.
The second drawback is the current state of python. With the
global interpreter lock firmly in place, we have no compelling
argument by which to parallelize our list comprehension, even if
they were partitioned. Currently the creation of said
micro-threads and the dovetailing of the workload would actually
increase the execution time in the current 2.4 implementation of
Python. Generators, even with the current lack of real
parallelism to the resulting pipeline, benefit from the drastic
reduction in the amount of in-flight data during their execution.
The third problem is in the near term, this PEP calls for no
implementation change, its only a request that users regard the
execution order as non-deterministic. There is a reasonable change
that this would be ignored.
Lastly, there has been discussion of recasting list comprehension
as generator comprehensions as an easy of normalizing the
semantics of the iterator variable with respect to the callee's
name-space. Such an effort would assign an explicit order of
execution to the list comprehension.
REFERENCES
TBD
COPYRIGHT
This document has been placed in the public domain.
execution order of these two lines just doesn't matter."
Proposed here are two freshly drafted PEP's advocating for the addition
of nondeterminism as a spring board for future automatic parallelism.
The first calls for core language changes, the second calls for a minor
(and likely symbolic) change to list comprehension's semantics to better
support future parallelism.
PEP: XXX
Title: Nondeterminism
Version: $Revision$
Last-Modified: $Date$
Author: Adam DePrince <[email protected]>
Status: Draft
Python-Version: 3.0
Type: Standards
Content-Type: text/plain
Created: 24-Mar-2006
Post-History:
Abstract
Proposed herein is are two new control flow structures that allow
the explicit specification of parallelism by defining the order of
expression evaluation as non-deterministic, thus removing the
requirement of sequential execution.
Background
A number of mechanisms have been proposed in Python that have the
side effect of permitting the automatic discovery of parallelism.
PEP 288 presents the notion of a generator, an object that
inherently lends itself to concurrent operation and possibility
automatic self organization of a pipeline.
Stackless Python in PEP 219/220 presents a mechanism by which a
large number micro threads could be efficiently supported, thus
allowing for a realistic manifestation of a deep generator based
software pipeline.
Additionally, this PEP's sibling, XXX, proposes that the
execution order of list comprehensions be made non-deterministic
to permit future parallel implementations.
DISCUSSION
Two new control flow structures are proposed. While as of yet no
name is proposed, for the sake of brevity we will refer to them as
any and first.
The any structure would call for the execution of all expressions
within the any block in an non-determinate order. The user would
warrant that no side effects exist between the expressions, and
assigned to the variable the any block would be a list
representing the return values of each of the expressions in the
order they appear in the code (but not necessarily in the order of
execution.)
The first structure would execute all enclosed expressions
concurrently, again, the order of execution being
non-deterministic, other than the promise that all would be
started. The return value of the first expression to finish would
be assigned to the variable associated with the first block and
the execution of the other operations terminated.
SPECIFICATION
The use of the word 'any' and 'first' is only a convenience. I do
not yet propose a keyword for these structures.
...
any retval:
1
2+3
my_function_that_returns_17()
...
retval would be assigned [1, 5, 17] Only the order of evaluation
is not deterministic.
first retval:
urllib.open( 'mirror1' ).read()
urllib.open( 'mirror2' ).read()
urllib.open( 'mirror3' ).read()
....
retval would contain the data from the fastest mirror, the other
threads would be disposed of.
IMPLEMENTATION
TBD - Incomplete
REFERENCES
TBD
COPYRIGHT
This document has been placed in the public domain.
PEP: XXX
Title: Nondeterministic List comprehensions
Version: $Revision$
Last-Modified: $Date$
Author: Adam DePrince <[email protected]>
Status: Draft
Python-Version: 3.0
Type: Standards
Content-Type: text/plain
Created: 24-Mar-2006
Post-History:
Abstract
The semantics of the list comprehension offer the future benefit
of multi-threading and parallel execution, assuming that the
programmer treat the order of evaluation as non-deterministic and
avoids the introduction of dependencies and side-effects.
Background
A number of mechanisms have been proposed in Python that have the
side effect of permitting the automatic discovery of parallelism.
PEP 288 presents the notion of a generator, an object that
inherently lends itself to concurrent operation and possibility
of automatic self organization of pipelined, and thus parallel,
operation.
Stackless Python in PEP 219/220 presents a mechanism by which a
large number micro threads could be efficiently supported, thus
allowing for a realistic manifestation of a deep generator based
software pipeline.
DISCUSSION
Generators and generator comprehension are often regarded as
superior to list comprehension due to the reduced footprint of
in-flight data and the future potential of vertical parallelism via
pipelining.
List comprehensions, while having the drawback of requiring the
presence of the entire working set in-flight, places no inherent
restriction on the order of execution. This permits us to
distribute the execution effort horizontally across multiple
micro-threads, with a far higher potential for parallelism than
generators at the expense of requiring the user warrant the
absence of side effects of dependencies between each passing of
the list comprehension loop.
This minor semantic requirement that list comprehension possess
no interdependencies or side effects permits us to operate on the
list in an arbitrary order, including dispatching the execution
across multiple threads.
SPECIFICATION
We change the semantics of a the list comprehension to
explicitly state that the order of evaluation is
non-deterministic, and that there should exist no dependencies or
side effects. This leaves open the potential for future
parallelization.
PROBLEMS
There are a currently a number of problems. Generators provide an
intuitive and natural partitioning of the problem. The future
partitioning of a list comprehension is a more capricious;
generally, we choose a fixed number of threads to dovetail across,
but little guidance can be gleaned from the use.
The second drawback is the current state of python. With the
global interpreter lock firmly in place, we have no compelling
argument by which to parallelize our list comprehension, even if
they were partitioned. Currently the creation of said
micro-threads and the dovetailing of the workload would actually
increase the execution time in the current 2.4 implementation of
Python. Generators, even with the current lack of real
parallelism to the resulting pipeline, benefit from the drastic
reduction in the amount of in-flight data during their execution.
The third problem is in the near term, this PEP calls for no
implementation change, its only a request that users regard the
execution order as non-deterministic. There is a reasonable change
that this would be ignored.
Lastly, there has been discussion of recasting list comprehension
as generator comprehensions as an easy of normalizing the
semantics of the iterator variable with respect to the callee's
name-space. Such an effort would assign an explicit order of
execution to the list comprehension.
REFERENCES
TBD
COPYRIGHT
This document has been placed in the public domain.