Version 1.3 of ai12s/ai12-0266-1.txt
!standard 5.5.1(4/3) 18-03-28 AI12-0266-1/01
!standard 5.5.1(6/4)
!standard 5.5.1(11/3)
!standard 5.5.2(4/3)
!class Amendment 18-03-28
!status work item 18-03-28
!status received 18-03-28
!priority Medium
!difficulty Medium
!subject Parallel Container Iterators
!summary
parallel iterators are defined for containers.
!problem
AI12-0119 provides mechanisms that can be used to iterate in parallel over the
elements of an array. One would expect that there would be a similar need to
be able to iterate over the elements of a container in parallel. Should such
a capability be provided in Ada? (Yes).
!proposal
This proposal depends on the facilities for parallel loops (AI12-0119-1),
aspect Global (AI12-0079-1), and for aspect Nonblocking (AI12-0064-2).
Those proposals define the tasklet model and allow the compiler to statically
determine where parallelism may be introduced without introducing data races or
deadlocking.
The goals of this proposal are:
- To extend parallel iteration to the standard container libraries
- To permit existing programs to benefit from parallelism through
minimal restructuring of sequential programs into ones that permit
more parallel execution;
- To support the development of complete programs that maximize
parallelism;
- To efficiently guide the compiler in the creation of effective
parallelism (without oversubscription of the parallelism resources) with
minimal input from the programmer;
- To avoid syntax that would make a POP erroneous or produce noticeably
different results if executed sequentially vs in parallel.
This proposal extends the interfaces in Ada.Containers.Iterator_Interfaces
to include two new interfaces, a parallel iterator interface, which
inherits from forward iterator interface, and a reversible parallel iterator
interface which inherits from the reversible iterator interface. Such an iterator
can be used for parallel iteration, but can also be used for sequential iteration
for loops that do not have the parallel reserved keyword.
A parallel iterator provides a Split function that can be used to return a
chunk array that defines the chunk boundaries and cursors needed for iterating
through the container in parallel, where each chunk of iteration can execute
in parallel with other chunks.
In addition, the loop syntax is extended to allow the loops with iterator
specifications to have the parallel keyword.
!wording
Replace 5.5(3/3)
Iteration_scheme ::= while condition
| [parallel] for loop_parameter_specification
| [parallel] for iterator_specification
Add after 5.5.1(4/3)
type Chunk_Array is limited interface
with Nonblocking;
function Length
(Object : Chunk_Array) return Natural is abstract;
function Start
(Object : Chunk_Array;
Index : Natural) return Cursor is abstract;
function Finish
(Object : Chunk_Array;
Index : Natural) return Cursor is abstract;
type Parallel_Iterator is limited interface and Forward_Iterator
with Nonblocking;
function Iterations
(Object : Parallel_Iterator)
return Ada.Containers.Count_Type is abstract;
function Split
(Object : Parallel_Iterator;
Advised_Split : Natural)
return Chunk_Array'Class is abstract;
type Parallel_Reversible_Iterator is limited interface
and Parallel_Iterator and Reversible_Iterator
with Nonblocking;
Modify 5.5.1(6/3)
An iterator type is a type descended from the Forward_Iterator
interface from some instance of Ada.Iterator_Interfaces. A reversible iterator
type is a type descended from the Reversible_Iterator interface from some
instance of Ada.Iterator_Interfaces. {A parallel iterator type is a type
descended from the Parallel_Iterator interface from some instance of
Ada.Iterator_Interfaces. A parallel reversible iterator type is a type
descended from both the Parallel_Iterator interace and the Reversible_Iterator
interface from some instance of Ada.Iterator_Interfaces.} An iterator object is
an object of an iterator type. A reversible iterator object is an object of a
reversible iterator type. { A parallel iterator object is an object of a
parallel iterator type. A parallel reversible iterator object is an object of a
parallel reversible iterator type.} The formal subtype Cursor from the
associated instance of Ada.Iterator_Interfaces is the iteration cursor subtype
for the iterator type.
Modify 5.5.1(11/3)
An iterable container type is an indexable container type with specified
Default_Iterator and Iterator_Element aspects. A reversible iterable container
type is an iterable container type with the default iterator type being a
reversible iterator type. {A parallel iterable container type is an iterable
container type with the default iterator type being a parallel iterator type. A
parallel reversible iterable container type is an iterable container type with
the default iterator type being a parallel reversible iterator type.} An
iterable container object is an object of an iterable container type. A
reversible iterable container object is an object of a reversible iterable
container type. {A parallel iterable container object is an object of a parallel
iterable container type. A parallel reversible iterable container object is an
object of a parallel reversible iterable container type.}
Modify 5.5.2(4/3)
If the reserved word reverse appears, the iterator_specification is a reverse
iterator[.;] {If the reserved word parallel appears, the iterator_specification
is a parallel iterator;} otherwise it is a forward iterator. In a reverse
generalized iterator, the iterator_name shall be of a reversible iterator type.
{In a parallel generalized iterator, the iterator_name shall be of a parallel
iterator type.} In a reverse container element iterator, the default
iterator type for the type of the iterable_name shall be a reversible iterator
type. {In a parallel container element iterator, the default iterator type for
the type of the iterable_name shall be of a parallel iterator type.}
Modify 5.5.2(7/5)
An iterator_specification declares a {set of} loop parameter {objects. If the
keyword parallel is present, multiple objects of the loop parameter are
created where each iteration is associated with a specific loop parameter
object; otherwise a single loop parameter object is created for the loop. Each
loop parameter object is associated with a thread of control where each thread
of control proceeds independently and concurrently between the points
where they interact with other tasks and with each other}. In a generalized
iterator, an array component iterator, or a container element iterator,
if a loop_parameter_subtype_indication is present, it determines the nominal
subtype of the loop parameter{s}. In a generalized iterator, if a
loop_parameter_subtype_indication is not present, the nominal subtype of the
loop parameter{s} is the iteration cursor subtype. In an array component
iterator, if a loop_parameter_subtype_indication is not present, the nominal
subtype of the loop parameter{s are}[ is] the component subtype of the type of
the iterable_name. In a container element iterator, if a
loop_parameter_subtype_indication is not present, the nominal subtype of the
loop parameter{s are}[is] the default element subtype for the type of the
iterable_name.
Modify 5.5.2(8/3)
In a generalized iterator, the loop parameter{s are} [is a] constant. In an
array component iterator, the loop parameter{s are} [is a] constant if the
iterable_name denotes a constant; otherwise [it]{they} denote[s] a variable.
In a container element iterator, the loop parameter{s are}[is a] constant if the
iterable_name denotes a constant, or if the Variable_Indexing aspect is not
specified for the type of the iterable_name; otherwise it is a variable.
Modify AARM 5.5.2(8.a/5)
Ramification: The loop parameter{s} of a generalized iterator {have}[has] the
same accessibility as the loop statement. This means that the loop parameter
object{s} {are}[is] finalized when the loop statement is left. ([It]{They} also
may be finalized as part of assigning a new value to the loop parameter{s}.) For
array component iterators, the loop parameter{s each} directly denotes an
element of the array and [has]{have} the accessibility of the associated array.
For container element iterators, the loop parameter{s each} denotes the result
of [the]{an} indexing function call (in the case of a constant indexing) or a
generalized reference thereof (in the case of a variable indexing). Roughly
speaking, the loop parameter{s have} [has] the accessibility level of a single
iteration of the loop. More precisely, the function result (or the generalized
reference thereof) is considered to be renamed in the declarative part of a
notional block statement which immediately encloses the loop's
sequence_of_statements; the accessibility of the loop parameter{s are} [is] that
of the block statement.
Modify 5.5.2(10/3)
For a generalized iterator, the loop parameter{s are} [is] created, the
iterator_name is evaluated, and the denoted iterator object{s} become[s] the
loop iterator{s}. In a forward generalized iterator, the operation First of the
iterator type is called on the loop iterator, to produce the initial value for
the loop parameter. If the result of calling Has_Element on the initial value is
False, then the execution of the loop_statement is complete. Otherwise, the
sequence_of_statements is executed and then the Next operation of the iterator
type is called with the loop iterator and the current value of the loop
parameter to produce the next value to be assigned to the loop parameter. This
repeats until the result of calling Has_Element on the loop parameter is False,
or the loop is left as a consequence of a transfer of control. For a reverse
generalized iterator, the operations Last and Previous are called rather than
First and Next.
Add after 5.5.2(10/3)
For a parallel generalized iterator, the operation Iterations
of the iterator type is called first to determine the number of iterations
associated with the iterator. If the result of calling Iterations is 0, then the
execution of the loop_statement is complete. Otherwise, the operation Split of
the iterator type is then called on a loop iterator, with the Advised_Split
parameter value set to a value determined by the implementation that indicates a
recommendation for the number of loop parameter objects that should be created.
The result of the call to Split is a Chunk_Array object that indicates the
number of loop parameter objects to be created by the implementation, as well as
the range of cursor values to be uniquely associated with each loop parameter
object. The number of loop parameters to be created is determined by calling
Length operation of the Chunk_Array. The range of cursor values to be associated
with each loop parameter is determined by calling the Start and Finish operation
of the Chunk_Array object using an ordinal index value of the loop parameter
object as the Index parameter for these calls. The result of calling the Start
operation is the initial cursor value to be assigned to a given loop parameter
object. The result of calling the Finish operation is the final cursor value to
be iterated for a given loop parameter object. The sequence_of_statements is
executed for each loop parameter object and then the Next operation of the
iterator type is called with the loop iterator and the current value of the loop
parameter to produce the next value to be assigned to a given loop parameter.
This repeats until the value of the loop parameter is equal to the final cursor
value associated with the given loop parameter, or the loop is left as a
consequence of a transfer of control.
AARM Note
The Advised_Split parameter value is only a recommendation by the
implementation. A container implementation may choose to ignore that
recommendation if a more optimal split can be determined. For instance, a tree
based container might create the split based on the number of branches at the
top levels of the tree.
Modify AARM 5.5.2(10.a/4)
Ramification: The loop parameter{s} of a generalized iterator [is a]{are}
variable{s} of which the user only has a constant view. It follows the normal
rules for a variable of its nominal subtype. In particular, if the nominal
subtype is indefinite, the variable is constrained by its initial value.
Similarly, if the nominal subtype is class-wide, the variable (like all
variables) has the tag of the initial value. Constraint_Error may be raised by a
subsequent iteration if Next{, }[ or] Previous{, or Split} return an object with
a different tag or constraint.
Modify 5.5.2(11/3)
For an array component iterator, the iterable_name is evaluated and the denoted
array object becomes the array for the loop. If the array for the loop is a null
array, then the execution of the loop_statement is complete. Otherwise, the
sequence_of_statements is executed with [the] loop parameter{s that collectively
denote} [denoting] each component of the array for the loop{. If the iterator is
not a parallel array component iterator, the loop is iterated} using a canonical
order of components, which is last dimension varying fastest (unless the array
has convention Fortran, in which case it is first dimension varying fastest).
For a forward array component iterator, the iteration starts with the component
whose index values are each the first in their index range, and continues in the
canonical order. For a reverse array component iterator, the iteration starts
with the component whose index values are each the last in their index range,
and continues in the reverse of the canonical order. {For a parallel array
component iterator, the order of iteration is arbitrary.} The loop iteration
proceeds until the sequence_of_statements has been executed for each component
of the array for the loop, or until the loop is left as a consequence of a
transfer of control.
Modify 5.5.2(12/3)
For a container element iterator, the iterable_name is evaluated and the denoted
iterable container object becomes the iterable container object for the loop.
The default iterator function for the type of the iterable container object for
the loop is called on the iterable container object and the result is the loop
iterator. [An object] {Objects} of the default cursor subtype [is]{are} created
(the loop cursor{s}).
Modify 5.5.2(13/3) [into three paragraphs]
For a forward container element iterator, the operation First of the iterator
type is called on the loop iterator, to produce the initial value for the loop
cursor. If the result of calling Has_Element on the initial value is False, then
the execution of the loop_statement is complete. Otherwise, the
sequence_of_statements is executed with the loop parameter denoting an indexing
(see 4.1.6) into the iterable container object for the loop, with the only
parameter to the indexing being the current value of the loop cursor; then the
Next operation of the iterator type is called with the loop iterator and the
loop cursor to produce the next value to be assigned to the loop cursor. This
repeats until the result of calling Has_Element on the loop cursor is False, or
until the loop is left as a consequence of a transfer of control. For a reverse
container element iterator, the operations Last and Previous are called rather
than First and Next.{
For a parallel container element iterator, the operation Iterations is first
called to determine the number of iterations associated with the iterator. If
the result of calling Iterations is 0, then the execution of the loop_statement
is complete. Otherwise, the operation Split of the iterator type is then called
on a loop iterator, with the Advised_Split parameter value set to a value
determined by the implementation that indicates a recommendation for the number
of loop parameter objects that should be created. The result of the call to
Split is a Chunk_Array object that indicates the number of loop parameter
objects to be created by the implementation, as well as the range of cursor
values to be uniquely associated with each loop parameter object. The number of
loop parameters to be created is determined by calling the Length operation of
the Chunk_Array. The range of cursor values to be associated with each loop
parameter is determined by calling the Start and Finish operation of the
Chunk_Array object using an ordinal index value of the loop parameter object as
the Index parameter for these calls. The result of calling the Start operation
is the initial cursor value to be assigned to a given loop parameter object. The
result of calling the Finish operation is the final cursor value to be iterated
for a given loop parameter object. The sequence_of_statements is executed for
each loop parameter object and then the Next operation of the iterator type is
called with the loop iterator and the current value of the loop parameter to
produce the next value to be assigned to a given loop parameter. This repeats
until the value of the loop parameter is equal to the final cursor value
associated with the given loop parameter, or the loop is left as a consequence
of a transfer of control.
}If the loop parameter is a constant (see above), then the indexing uses the
default constant indexing function for the type of the iterable container object
for the loop; otherwise it uses the default variable indexing function.
Modify 5.5.2(15/3)
-- Array component iterator example:
{parallel}
for Element of Board loop -- See 3.6.1.
Element := Element * 2.0; --
end loop;
Modify A.18.2(74.1/3)
function Iterate (Container : in Vector)
return Vector_Iterator_Interfaces.{Parallel_}Reversible_Iterator'Class;
Modify A.18.2(74.2/3)
function Iterate (Container : in Vector; Start : in Cursor)
return Vector_Iterator_Interfaces.{Parallel_}Reversible_Iterator'Class;
Modify A.18.2(230.1/3)
function Iterate (Container : in Vector)
return Vector_Iterator_Interfaces.{Parallel_}Reversible_Iterator'Class;
Modify A.18.2(230.2/3)
Iterate returns a {parallel} reversible iterator object (see 5.5.1) that will
generate a value for [a] loop parameter{s} (see 5.5.2) designating each node in
Container, starting with the first node and moving the cursor as per the Next
function when used as a forward iterator, and starting with the last node and
moving the cursor as per the Previous function when used as a reverse iterator
{, and starting with all nodes simultaneously using the Split function
to generate cursors for all the iterations of the loop when used as a parallel
iterator}. Tampering with the cursors of Container is prohibited while the
iterator object exists (in particular, in the sequence_of_statements of the
loop_statement whose iterator_specification denotes this object). The iterator
object needs finalization.
Modify A.18.2(230.3/3)
function Iterate (Container : in Vector; Start : in Cursor)
return Vector_Iterator_Interfaces.{Parallel_}Reversible_Iterator'Class;
Modify A.18.2(230.4/3)
If Start is not No_Element and does not designate an item in Container, then
Program_Error is propagated. If Start is No_Element, then Constraint_Error is
propagated. Otherwise, Iterate returns a {parallel }reversible iterator object
(see 5.5.1) that will generate a value for [a] loop parameter{s} (see 5.5.2)
designating each node in Container, starting with the node designated by Start
and moving the cursor as per the Next function when used as a forward iterator,
or moving the cursor as per the Previous function when used as a reverse
iterator {, or all nodes simultaneously using the Split function when used as a
parallel iterator}. Tampering with the cursors of Container is prohibited while
the iterator object exists (in particular, in the sequence_of_statements of the
loop_statement whose iterator_specification denotes this object). The iterator
object needs finalization.
Modify A.18.3(46.1/3)
function Iterate (Container : in List)
return List_Iterator_Interfaces.{Parallel_}Reversible_Iterator'Class;
Modify A.18.3(46.2/3)
function Iterate (Container : in List; Start : in Cursor)
return List_Iterator_Interfaces.{Parallel_}Reversible_Iterator'Class;
Modify A.18.3(144.1/3)
function Iterate (Container : in List)
return List_Iterator_Interfaces.{Parallel_}Reversible_Iterator'Class;
Modify A.18.3(144.2/3)
Iterate returns a {parallel }reversible iterator object (see 5.5.1) that will
generate a value for [a] loop parameter{s} (see 5.5.2) designating each node in
Container, starting with the first node and moving the cursor as per the Next
function when used as a forward iterator, and starting with the last node and
moving the cursor as per the Previous function when used as a reverse iterator
{, and starting with all nodes simultaneously using the Split function to
generate cursors for all the iterations of the loop when used as a parallel
iterator}. Tampering with the cursors of Container is prohibited while the
iterator object exists (in particular, in the sequence_of_statements of the
loop_statement whose iterator_specification denotes this object). The iterator
object needs finalization.
Modify A.18.3(144.3/3)
function Iterate (Container : in List; Start : in Cursor)
return List_Iterator_Interfaces.Parallel_Reversible_Iterator'Class;
Modify A.18.3(144.4/3)
If Start is not No_Element and does not designate an item in Container, then
Program_Error is propagated. If Start is No_Element, then Constraint_Error is
propagated. Otherwise, Iterate returns a {parallel} reversible iterator object
(see 5.5.1) that will generate [a] value{s} for [a] loop parameter{s} (see
5.5.2) designating each node in Container, starting with the node designated by
Start and moving the cursor as per the Next function when used as a forward
iterator, or moving the cursor as per the Previous function when used as a
reverse iterator {or all nodes simultaneously using the Split function when used
as a parallel iterator}. Tampering with the cursors of Container is prohibited
while the iterator object exists (in particular, in the sequence_of_statements
of the loop_statement whose iterator_specification denotes this object). The
iterator object needs finalization.
Modify A.18.5(37.1/3)
function Iterate (Container : in Map)
return Map_Iterator_Interfaces.{Parallel_}[Forward_]Iterator'Class;
Modify A.18.5(61.1/3)
function Iterate (Container : in Map)
return Map_Iterator_Interfaces.{parallel}[Forward]_Iterator'Class;
Modify A.18.5(61.2/3)
Iterate returns a[n] {parallel} iterator object (see 5.5.1) that will generate
[a] value{s} for [a] loop parameter{s} (see 5.5.2) designating each node in
Container, starting with the first node and moving the cursor according to the
successor relation {when used as a forward iterator, and starting with all nodes
simultaneously using the Split function to generate cursors for all the
iterations of the loop when used as a parallel iterator}. Tampering with the
cursors of Container is prohibited while the iterator object exists (in
particular, in the sequence_of_statements of the loop_statement whose
iterator_specification denotes this object). The iterator object needs
finalization.
Modify A.18.6(51.1/3)
function Iterate (Container : in Map)
return Map_Iterator_Interfaces.{Parallel_}Reversible_Iterator'Class;
Modify A.18.6(51.2/3)
function Iterate (Container : in Map; Start : in Cursor)
return Map_Iterator_Interfaces.{Parallel_}Reversible_Iterator'Class;
Modify A.18.6(94.1/3)
function Iterate (Container : in Map)
return Map_Iterator_Interfaces.{Parallel_}Reversible_Iterator'Class;
Modify A.18.6(94.2/3)
Iterate returns a {parallel} reversible iterator object (see 5.5.1) that will
generate [a] value{s} for [a] loop parameter{s} (see 5.5.2) designating each
node in Container, starting with the first node and moving the cursor according
to the successor relation when used as a forward iterator, and starting with the
last node and moving the cursor according to the predecessor relation when used
as a reverse iterator {, and starting with all nodes simultaneously using the
Split function to generate cursors for all the iterations of the loop when used
as a parallel iterator}. Tampering with the cursors of Container is prohibited
while the iterator object exists (in particular, in the sequence_of_statements
of the loop_statement whose iterator_specification denotes this object). The
iterator object needs finalization.
Modify A.18.6(94.3/3)
function Iterate (Container : in Map; Start : in Cursor)
return Map_Iterator_Interfaces.{Parallel_}Reversible_Iterator'Class;
Modify A.18.6(94.4/3)
If Start is not No_Element and does not designate an item in Container, then
Program_Error is propagated. If Start is No_Element, then Constraint_Error is
propagated. Otherwise, Iterate returns a {parallel} reversible iterator object
(see 5.5.1) that will generate [a] value{s} for [a] loop parameter{s} (see
5.5.2) designating each node in Container, starting with the node designated by
Start and moving the cursor according to the successor relation when used as a
forward iterator, or moving the cursor according to the predecessor relation
when used as a reverse iterator {, or all nodes simultaneously using the Split
function when used as a parallel iterator}. Tampering with the cursors of
Container is prohibited while the iterator object exists (in particular, in the
sequence_of_statements of the loop_statement whose iterator_specification
denotes this object). The iterator object needs finalization.
Modify A.18.8(49.1/3)
function Iterate (Container : in Set)
return Set_Iterator_Interfaces.{parallel}[Forward]_Iterator'Class;
Modify A.18.8(85.1/3)
function Iterate (Container : in Set)
return Set_Iterator_Interfaces.{parallel}[Forward]_Iterator'Class;
Modify A.18.8(85.2/3)
Iterate returns a[n] {parallel} iterator object (see 5.5.1) that will generate
[a] value{s} for [a] loop parameter{s} (see 5.5.2) designating each element in
Container, starting with the first element and moving the cursor according to
the successor relation {when used as a forward iterator, and starting with all
nodes simultaneously using the Split function to generate cursors for all the
iterations of the loop when used as a parallel iterator.} Tampering with the
cursors of Container is prohibited while the iterator object exists (in
particular, in the sequence_of_statements of the loop_statement whose
iterator_specification denotes this object). The iterator object needs
finalization.
Modify A.18.9(61.1/3)
function Iterate (Container : in Set)
return Set_Iterator_Interfaces.{Parallel_}Reversible_Iterator'Class;
Modify A.18.9(61.2/3)
function Iterate (Container : in Set; Start : in Cursor)
return Set_Iterator_Interfaces.{Parallel_}Reversible_Iterator'Class;
Modify A.18.9(113.1/3)
function Iterate (Container : in Set; Start : in Cursor)
return Set_Iterator_Interfaces.{Parallel_}Reversible_Iterator'Class;
Modify A.18.9(113.2/3)
Iterate returns a {parallel} reversible iterator object (see 5.5.1) that will
generate [a] value{s} for [a] loop parameter{s} (see 5.5.2) designating each
element in Container, starting with the first element and moving the cursor
according to the successor relation when used as a forward iterator, and
starting with the last element and moving the cursor according to the
predecessor relation when used as a reverse iterator {, and starting with all
nodes simultaneously using the Split function to generate cursors for all the
iterations of the loop when used as a parallel iterator}. Tampering with the
cursors of Container is prohibited while the iterator object exists (in
particular, in the sequence_of_statements of the loop_statement whose
iterator_specification denotes this object). The iterator object needs
finalization.
Modify A.18.9(113.3/3)
function Iterate (Container : in Set; Start : in Cursor)
return Set_Iterator_Interfaces.{Parallel_}Reversible_Iterator'Class;
Modify A.18.9(113.4/3)
If Start is not No_Element and does not designate an item in Container, then
Program_Error is propagated. If Start is No_Element, then Constraint_Error is
propagated. Otherwise, Iterate returns a {parallel} reversible iterator object
(see 5.5.1) that will generate [a] value{s} for [a] loop parameter{s} (see 5.5.2)
designating each element in Container, starting with the element designated by
Start and moving the cursor according to the successor relation when used as a
forward iterator, or moving the cursor according to the predecessor relation
when used as a reverse iterator {, or all nodes simultaneously using the Split
function when used as a parallel iterator}. Tampering with the cursors of
Container is prohibited while the iterator object exists (in particular, in the
sequence_of_statements of the loop_statement whose iterator_specification
denotes this object). The iterator object needs finalization.
Modify A.18.10(44/3)
function Iterate (Container : in Tree)
return Tree_Iterator_Interfaces.{parallel}[Forward]_Iterator'Class;
Modify A.18.10(45/3)
function Iterate_Subtree (Position : in Cursor)
return Tree_Iterator_Interfaces.{parallel}[Forward]_Iterator'Class;
Modify A.18.10(156/3)
function Iterate (Container : in Tree)
return Tree_Iterator_Interfaces.{parallel}[Forward]_Iterator'Class;
Modify A.18.10(157/4)
Iterate returns a[n] {parallel} iterator object (see 5.5.1) that will generate
[a] value{s} for [a] loop parameter{s} (see 5.5.2) designating each element node
in Container, starting from with the root node and proceeding in a depth-first
order {when used as a forward_iterator, and starting with all nodes
simultaneously using the Split function to generate cursors for all the
iterations of the loop when used as a parallel iterator}. Tampering with the
cursors of Container is prohibited while the iterator object exists (in
particular, in the sequence_of_statements of the loop_statement whose
iterator_specification denotes this object). The iterator object needs
finalization.
Modify A.18.10(158/3)
function Iterate_Subtree (Position : in Cursor)
return Tree_Iterator_Interfaces.{parallel}[Forward]_Iterator'Class;
Modify A.18.10(159/3)
If Position equals No_Element, then Constraint_Error is propagated. Otherwise,
Iterate_Subtree returns a[n] {parallel} iterator object (see 5.5.1) that will
generate [a] value{s} for [a] loop parameter{s} (see 5.5.2) designating each
element in the subtree rooted by the node designated by Position, starting from
with the node designated by Position and proceeding in a depth-first order {when
used as a forward iterator, or all nodes simultaneously using the Split function
when used as a parallel iterator}. If Position equals No_Element, then
Constraint_Error is propagated. Tampering with the cursors of the container that
contains the node designated by Position is prohibited while the iterator object
exists (in particular, in the sequence_of_statements of the loop_statement whose
iterator_specification denotes this object). The iterator object needs
finalization.
Add after D.16(5/3)
type Iteration_Count is range 0 .. implementation-defined;
for Iteration_Count'Size use implementation-defined;
type Split_Count is range 0 .. implementation-defined;
function Advised_Split_Count
(Iterations : Iteration_Count) return Split_Count
witn Non_Blocking => False;
Add after D.16(8/3)
The Advised_Split_Count function accepts a parameter that indicates the number
of iterations associated with a parallel loop, and returns a recommended value
for the number of loop parameter objects to be associated with a parallel loop
statement. Such a value is intended to be passed as an actual for the
Advised_Split parameter of the Split operation associated with a parallel
iterator object (see 5.5.1).
!discussion
We extended the parallel loop capability to work with containers as well as arrays,
since there could be a need to iterate in parallel over any of the standard
containers. Containers such as vectors are obvious candidates for parallelisation,
since it is easy to conceptually think of a vector as a being splittable into
a number of smaller vectors, and then applying a divide and conquer approach to
the vector subsets. However, even a sequentially accessed container such as a
linked list can be iterated in parallel, if cursors for each parallel executor
can be obtained prior to execution of the loop. This typically involves iterating
once through the container to obtain the cursors, but can still be benefit from
parallel processing if the amount of time to process each node in the loop is
significantly greater than the amount of time needed to iterate through the list.
Sometimes there are loops that need initialization or finalization for each
executor, that might be too expensive to apply for each iteration, but would be
worthwhile if applied once per chunk of execution. An example might be where
a file needs to be opened for each executor where the loop writes results to
the file, and after the executor completes its chunk, the file needs to be closed.
Other possible uses include memory allocation for temporary data structures.
Such loops would require user-defined chunking, where the user code explicitly calls
the Split function of a Parallel iterator to obtain the Chunk_Array object that
normally the implementation would request. This allows the user to express the
parallelism more explicitly by writing an outer loop that iterates through the
number of chunks and an inner loop that iterates through the elements of each
chunk.
The container writer has the ability to implement the container to define
an optimal number of elements in the chunk array that are to be returned by the
Split call, as well as the cursors associated with each element of the chunk array.
!ASIS
** TBD.
!ACATS test
ACATS B- and C-Tests are needed to check that the new capabilities are
supported.
!appendix
From: Brad Moore
Sent: Wednesday, March 28, 2018 12:06 AM
Here is a new AI split off from AI12-0119 (Parallel Operations).
[This is version /01 of the AI - ED]
This one deals specifically with parallel container iteration.
The writeup is very much the same as before.
****************************************************************
From: Tucker Taft
Sent: Wednesday, March 28, 2018 9:11 PM
Thanks. I am thinking this should probably also be in Chapter 9 after
introducing the notion of tasklets, rather than trying to weave it into the
current discussion of iterators, which is already pretty complex.
****************************************************************
Questions? Ask the ACAA Technical Agent