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

Unformatted version of ai12s/ai12-0266-1.txt version 1.4
Other versions for file ai12s/ai12-0266-1.txt

!standard 5.5.1(4/3)          18-06-14 AI12-0266-1/02
!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
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 cursor array that defines the chunk boundaries and cursors needed for iterating through the container in parallel, where each cursor in the array identifies the first cursor of a different chunk of iterations that can be iterated through in parallel with other iteration chunks. Each cursor of the array can be obtained by calling the To_Cursor operation passing in the index of the chunk as a parameter to the call. The end of a chunk can be determined by calling the To_Cursor operation for the next highest chunk index. Calling To_Cursor with an index value higher than the number of elements in the cursor array returns a No_Element cursor. The idea is that the iteration for a chunk is complete when the current cursor gets advanced enough times to give the cursor value associated with the next highest index.
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 Cursor_Array is limited interface -- with Nonblocking ;
function Length (Object : Cursor_Array) return Natural is abstract;
function To_Cursor (Object : Cursor_Array; Index : Natural) return Cursor is abstract;
procedure Set_Cursor (Object : in out Cursor_Array; Index : Natural; Position : 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;
procedure Split (Object : Parallel_Iterator; Into : out Cursor_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.
Add after 5.5.1(9.a/3)
Iteraetor_Cursor_Array
This aspect is specified by a name that denotes a subtype. This is the default cursor array subtype for T.
Aspect Description for Iterator_Cursor_Array: Cursor array type to be used for parallel iteration.
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 a specified Iterator_Cursor_Array aspect with the default iterator type being a parallel iterator type. A parallel reversible iterable container type is an iterable container type with a specified Iterator_Cursor_Array aspect 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, a Cursor array object of the type specified by the Iterator_Cursor_Array aspect is declared, with the number of elements associated with the Cursor array object being set to a value determined by the implementation that indicates a recommendation for the number of loop parameter objects that should be created. The operation Split of the iterator type is then called. The result of the call to Split is the Cursor_Array object is assigned a set of cursor values indicating the initial 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 Cursor_Array. The Initial cursor values to be associated with each loop parameter is determined by calling the To_Cursor operation of the Cursor_Array object using an ordinal index value of the loop parameter object as the Index parameter for the call. 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 initial cursor value associated with the next highest next loop parameter, or if the Has_Element operation associated with the Iterator object returns False, or if the loop is left as a consequence of a transfer of control.
AARM Note
The number of elements specified for the Cursor_Array object 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. Any resulting elements of a Cursor_Array object that are not to be used should be to be set to the No_Element value associated with the Cursor type.
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 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, a Cursor array object of the type specified by the Iterator_Cursor_Array aspect is declared, with the number of elements associated with the Cursor array object being set to a value determined by the implementation that indicates a recommendation for the number of loop parameter objects that should be created. The operation Split of the iterator type is then called.
The result of the call to Split is the Cursor_Array object is assigned a set of cursor values indicating the initial 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 Cursor_Array. The Initial cursor values to be associated with each loop parameter is determined by calling the To_Cursor operation of the Cursor_Array object using an ordinal index value of the loop parameter object as the Index parameter for the call. The Initial cursor values to be associated with each loop parameter is determined by calling the To_Cursor operation of the Cursor_Array object using an ordinal index value of the loop parameter object as the Index parameter for the call. 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 initial cursor value associated with the next highest next loop parameter, or if the Has_Element operation associated with the Iterator object returns False, or if 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; -- Double each element of Board, a two-dimensional array. 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.
!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.
Originally, we had the Split operation as a function rather than a procedure. It was felt that returning a class-wide type as a function result was undesirable, and possibly inefficient. So the Split call was modified to be a procedure. However, that means the real cursor array type needs to be declared before calling split, and since the compiler is to be making this call, there needed to be a way to tell the implementation which type should be used to create the cursor array object. The solution to this problem was to create a Interator_Cursor_Array aspect, similar to the Iterator_Element aspect, that allows the container implementer to specify the cursor array type to be passed to the Split call for parallel iteration.
!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.

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

From: Brad Moore
Sent: Thursday, June 14, 2018   1:15 AM

Here is an update to AI12-0266, [This is version /02 of the AI - Editor.]

The main changes are;

- Changed Chunk_Array type to be called Cursor_Array type.

The reason is that "Chunk" is not well defined in the RM, and an array of
chunks leaves a bit to the imagination.

A cursor array however seems a lot easier to visualize.

The semantics of Chunk_Array was that for every chunk there was a Start and
Finish call that could be used to determine the first and last cursor of each
chunk. One problem with this is that it is not clear if the last cursor is
inclusive or exclusive to the set of cursors to be iterated over.

With a cursor array, there is only one cursor per chunk, and only one call,
To_Cursor, available to get the starting cursor. To get the end cursor you
use the next highest index value, which should be more obvious that this is
an exclusive cursor value. The idea also is that if you specify an index value
higher than the number of chunks in the cursor array, you get a No_Element
result. So calling To_Cursor with index + 1 consistently gives you a cursor
value that can be compared against for chunk iteration termination.

Another change is that the Split operation is no longer a function returning
an object of a class-wide type. Instead, Split is a procedure that has an out
parameter of a class-wide type. (A change requested by Tucker)

By doing this, I think there needed to be a way for the container implementer
to tell the compiler which type to use for declaring the cursor array type. So
I added an Iterator_Cursor_Array aspect, similar to Iterator_Element aspect,
that may be specified on a container type declaration for this purpose.

Since the implementation is now responsible for declaring the cursor array
type, the idea is that the number of elements of the cursor array is now the
means to indicate to the container implementer, how many chunks to create.

A container implementer can use less than the number of elements of the cursor
array, but then must leave the remaining elements set as No_Element.

As a result of this, there no longer needs to be an Advised_Split parameter to
the Split call.

Another change is that since the Split function needs to store cursors into an
out parameter Cursor_Array class-wide object, there needed to be a way to
store a cursor into a cursor array object. So I added a Set_Cursor procedure
to the Cursor_Array interface.

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

From: Brad Moore
Sent: Thursday, June 14, 2018  10:30 AM

A question I have about this approach, is it enough to use the
Iterator_Cursor_Array aspect to tell the compiler how to set up the cursor
array object?

Specifically, in my test example using Ada.Containers.Doubly_Linked_Lists, I
have the cursor array type having a visible discriminant to set the length of
the array.

Do we need to specify in the RM that it is expected that all cursor array
types will have a single discriminant of a type (Natural) indicating the
number of elements in a cursor array?

Or maybe we need another aspect to somehow tell the compiler how to specify
the cursor array length?

Or we could add a Set_Length function to the interface, but then that likely
implies a controlled type with dynamic memory allocation, which seems to be
undesirable.

This also has me wondering if we might have been better off leaving the Split
subprogram as a function rather than a procedure. Then the container
implementor can create tne cursor array object inside the Split call with the
desired length. We can then also simplify the interface by eliminating the
Set_Cursor call.

I note also that we do have other iterator calls that are functions returning
class-wide types, such as Iterate in the containers.

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

From: Randy Brukardt
Sent: Thursday, June 14, 2018   1:46 PM

> A question I have about this approach, is it enough to use the
> Iterator_Cursor_Array aspect to tell the compiler how to set up the
> cursor array object?

Let's start further back. Why do we need a Iterator_Cursor_Array object at all?

There would have been value to that approach if you could have declared an
actual array (fewer subprogram calls), but since it has to be private,
getting each cursor is going to involve a subprogram call.

So, what is the separate object gaining over just putting the Get_Cursor call
directly on the iterator object (the implementation of which is totally
user-controlled, so it could have an array of cursors internally if it wants)?
The "user" of this structure is the parallel loop, and it obviously has an
iterator object it is going to use to iterate. Why does it need anything
more??

So I would suggest that Split is just a call to tell the iterator how to
organize its internal data structure. Still need the Advised_Split parameter,
something like:

   procedure Split
     (Object        : in out Parallel_Iterator;
      Advised_Split : in Natural) is abstract;
      -- Tell Object to create split data with the advised number of splits.

   function Split_Length (Object : in Parallel_Iterator) return Natural is abstract;
      -- Determine the actual split length.

   function Split_Cursor (Object : in Parallel_Iterator;
                          Split_Index : in Natural) return Cursor;

or, since it would save an assignment in many implementations:

   procedure Split_Cursor (Object : in Parallel_Iterator;
                           Split_Index : in Natural;
                           Result : out Cursor);

Either of these would have the semantics you suggested yesterday (chunk ends
with the 'Succ index, get No_Element if Split_Index >= Length).

Do you need anything else?

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

Questions? Ask the ACAA Technical Agent