Version 1.3 of ai12s/ai12-0266-1.txt

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).

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

- To support the development of complete programs that maximize

- To efficiently guide the compiler in the creation of effective

- To avoid syntax that would make a POP erroneous or produce noticeably

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.

Replace 5.5(3/3)

Add after 5.5.1(4/3)

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.

Modify A.18.2(74.1/3)

Modify A.18.2(74.2/3)

Modify A.18.2(230.1/3)

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)

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)

Modify A.18.3(46.2/3)

Modify A.18.3(144.1/3)

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)

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)

Modify A.18.5(61.1/3)

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)

Modify A.18.6(51.2/3)

Modify A.18.6(94.1/3)

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)

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)

Modify A.18.8(85.1/3)

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)

Modify A.18.9(61.2/3)

Modify A.18.9(113.1/3)

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)

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)

Modify A.18.10(45/3)

Modify A.18.10(156/3)

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)

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)

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).

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.

** TBD.

ACATS B- and C-Tests are needed to check that the new capabilities are supported.

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.

****************************************************************