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

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

!standard 5.5.1(4/3)          18-06-16 AI12-0266-1/04
!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 procedure that can be used to associate with the iterator a set of cursors that define the chunk boundaries for parallel iteration. Each cursor in the array identifies the first element of a different chunk of iterations where each chunk can be iterated through in parallel with other chunks to collectively cover all the elements of the container.
Each cursor of the array can be obtained by calling the Get_Cursor operation, passing in the index of the split as a parameter to the call. The end Cursor of an iteration chunk can be determined by calling the Get_Cursor operation for the next highest split index. Calling Get_Cursor with a split index value higher than the number of splits associated with the iterator returns in a No_Element cursor result. 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 split 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 Parallel_Iterator is limited interface and Forward_Iterator -- with Nonblocking ;
function Iterations (Object : Parallel_Iterator) return Ada.Containers.Count_Type is abstract;
subtype Cursor_Count is Positive; subtype Split_Index is Positive; use type Ada.Containers.Count_Type;
procedure Split (Object : in out Parallel_Iterator; Advised_Split : Cursor_Count) is abstract with Pre'Class => Ada.Containers.Count_Type (Advised_Split) <= Object.Iterations, Post'Class => Object.Split_Count <= Advised_Split;
function Split_Count (Object : Parallel_Iterator) return Cursor_Count is abstract;
function Get_Cursor (Object : Parallel_Iterator; Index : Split_Index) return Cursor is abstract with Pre'Class => Index <= Object.Split_Count + 1;
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 a reversible 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 or a parallel reversible 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 or a parallel reversible 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{s}. 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]{they are} 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 becomes the loop iterator. 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, with the Advised_Split parameter specified as the upper bound for the number of loop parameter objects to be associated with the iterator. The number of loop parameters that were created is determined by calling the Split_Count operation of the iterator. The Initial cursor values to be associated with each loop parameter is determined by calling the Get_Cursor operation of the iterator using an ordinal split 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 split index, 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 loop parameters specified for the Advised_Split parameter of the Split call is only a recommendation by the implementation. A container implementation may choose a lower value 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 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, with the Advised_Split parameter specified as the upper bound for the number of loop parameter objects to be associated with the iterator. The number of loop parameters that were created is determined by calling the Split_Count operation of the iterator. The Initial cursor values to be associated with each loop parameter is determined by calling the Get_Cursor operation of the iterator using an ordinal split 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.
he container writer has the ability to implement the container to define an optimal number of loop parameters to be setup by the Split call, so long as the number of splits is not greater than the advised_split parameter.
This proposal allows the container implementer a fair amount of flexibility in deciding how to implement the cursor array stored in the iterator object. In general, an implementor should allow for as many elements in the cursor array, as there are cores on the multicore processor. But one could still decide to use a fixed sized array with enough elements to provide good parallelism for most typical processors available today. For instance, a fixed size cursor array of size 64 elements might be a reasonable size to provide good parallelism for most uses. On the other hand, it might make sense to allocate the cursor array dynamically during the call to Split. Then the array can be sized to match any number of cores. Another advantage of dynamic allocation is that the storage would not be needed for iterators associated with non-parallel loops. The iterator types of the containers are controlled types, so finalization of the iterator objects is already part of the iteration model.
It would have been nice to specify a post condition for the Split call something like;
with Post => (for all I in 1 .. Object.Split_Count =>
Has_Element (Object.Get_Cursor (I)))
However, this is not allowed because Has_Element cannot be called during a post condition in this package because the Cursor formal type is an untagged incomplete type.
Similarly, it would have been nice to write a Post condition for Get_Cursor where calling Has_Element on the result would return true, however this is also not allowed for the same reason.
Another Post condition that would have been nice would be to add to Get_Cursor,
with Post => (if Index = Object.Split_Count + 1
then Has_Element (Get_Cursor'Result) = False)
but Has_Element cannot be called here, and we would need to add No_Element as a formal object to the package, which would break compatibility.
We could consider adding these as Pre and Post contracts in the derived types in each of the containers, but the iterator types are not declared in the public part of the package, so it seems to be not worthwhile to do so.
!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?

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

From: Randy Brukardt
Sent: Thursday, June 14, 2018   8:10 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?

Sorry, I meant Cursor_Array. I couldn't convince Outlook to let me view your
AI update in anything other than Notepad (which just shows a giant block of
text; it doesn't recognize Linux line endings) so I had to go from a quick
scan of your AI when I wrote this this afternoon (hoping for quick
turnaround). Now that I've posted it, I see what I did wrong here.

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

Answering my own question based on your most recent wording: I don't see
any. If we let the iterator implementor create a (possibly virtual) array
inside their implementation, we don't need any explicit object. It seems to
make *everything* simpler (no strange new aspect, no questions about
where/when the object gets declared, less to talk about in how the iterator
executes, etc.)

> 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??

The actual implementation probably has to give a start/end cursor to each
thread when it is given work, but the format of that should be 100% up to the
implementation. The less we specify, the more likely it is that an implementer
can optimize it and create the fastest possible code.

> So I would suggest that Split is just a call to tell the iterator how
> to organize it's 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.

Note that the internal cursor array (inside of a Parallel_Iterator'Class
object) could be fixed length (meaning that no more splits than the max number
is supported) or it could be dynamically allocated. I don't see much reason to
support massive numbers of splits anyway, certainly not to require it. (Perhaps
we might give a minimum number in Implementation Advice?)

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

We'd need say what happens here if procedure Split hasn't been called. I'd
suggest saying that it returns 1.

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

Again, if Split hasn't been called, the first cursor is Object.First, and the
rest are No_Element.

> Do you need anything else?

I don't think so, based on my reading of your current text.

Assuming you concur, if you could update the AI this way before the deadline,
it would help progress it in Lisbon.

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

From: Brad Moore
Sent: Thursday, June 14, 2018   10:54 PM

Thanks Randy, the idea of hiding the cursor array inside the iterator hadn't
occurred to me, but it looks like it does simplify things a lot, as well as
gives more flexibility to the implementation.

I will attempt to update the AI to include these ideas.

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

From: Brad Moore
Sent: Friday, June 15, 2018   11:22 AM

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


I am thinking of going with the function version, because

a) It is easier to work with, as it possibly saves having to declare two
objects, since the client needs both a start and end cursor, and

b) Because I suspect compilers would typically apply a transformation of
the users code to a procedure call accepting two cursors. The function results
can be inline expressions for the parameters to the call, so I dont think we'd
be saving an assignment in that case. Otherwise you have to assign to the
declared cursor variables, and then assign again to the parameters of the
call.

eg.

      --  2% Raise to everyone!
      parallel
      for Employee of List loop
          Employee.Salary := @ + @ * 0.02;
      end loop;

might get transformed to something like;

   declare
      procedure Give_Raise
        (From, To    : Employee_Lists.Cursor)
      is
         Position : Employee_Lists.Cursor := From;
         use type Employee_Lists.Cursor;
      begin --  Get_Payroll

         while Position /= To loop

            --  2% Raise to everyone!
            List (Position).Salary := @ + @ * 0.02;
            Employee_Lists.Next (Position);
         end loop;

      end Give_Raise;

      Iterator : Emp_List_Iterators.Parallel_Reversible_Iterator'Class :=
        List.Iterate;

   begin

      Iterator.Split (Advised_Split => 4);

      parallel
      for Chunk in 1 .. Iterator.Split_Count loop
         Give_Raise (From => Iterator.Get_Cursor (Chunk),
                     To   => Iterator.Get_Cursor (Chunk + 1));
      end loop;

   end;

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

From: Brad Moore
Sent: Friday, June 15, 2018   11:43 AM

> Note that the internal cursor array (inside of a
> Parallel_Iterator'Class
> object) could be fixed length (meaning that no more splits than the
> max number is supported) or it could be dynamically allocated. I don't
> see much reason to support massive numbers of splits anyway, certainly
> not to require it. (Perhaps we might give a minimum number in
> Implementation Advice?)

The number of splits should typically be at least as many as the number of
available cores. For some platforms that number might be unknown.
For example, for IRTAW, I was interacting with a couple of people from the
Barcelona supercomputing center, where they were experimenting with
parallelism on 50 core computers. They managed to get my Paraffin code
running on that system, so I think it was a Linux based system.

I think storing the cursor array in the iterator for such a system would
suggest that the cursor array would needs to be dynamically allocated, (by
the Split call). As otherwise, the iterator object could become a very large
object to accomodate the largest possible number of cores, and that might
cause troubles if declared on a stack. If you know your target platform only
supports a small number of cores, then a fixed size array could be
appropriate. Another advantage of dynamically allocating is that if the Split
function is not called, (for example for a non-parallel loop), then nothing
needs to be freed upon finalization of the iterator, and no storage is needed
for the cursor array during the lifetime of the iterator object.

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

From: Randy Brukardt
Sent: Friday, June 15, 2018   2:37 PM

I mentioned using a statically sized array because this has to work in the
bounded forms, where dynamic allocation and finalization is strongly
discouraged. Perhaps there is some way to use the secondary stack in GNAT
for this allocation, but otherwise the size needs to be known early.

I thought that a 64 cursor array probably would be enough for most existing
targets, and the size of that (128 words) is not going to be so large as to
cause stack problems. There's probably going to be memory use issues if
someone has 10,000 cores, but that's mostly theoretical (and I've read that
the number of cores is likely to be limited by memory contention issues).

For the unbounded forms, it's probably better to use dynamic allocation, but
obviously that's up to the implementation.

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

From: Randy Brukardt
Sent: Friday, June 15, 2018   2:50 PM

> I am thinking of going with the function version, because
>
> a) It is easier to work with, as it possibly saves having to declare
> two objects, since the client needs both a start and end cursor, and

I thought the compiler would declare them somewhere anyway. In any case,
having thought on it more, I doubt that there would be any difference since
the objects in question are compiler-generated and thus it is not necessary
to preserve Ada semantics for their assignments.

> b) Because I suspect compilers would typically apply a transformation
> of the users code to a procedure call accepting two cursors. The
> function results can be inline expressions for the parameters to the
> call, so I dont think we'd be saving an assignment in that case.
> Otherwise you have to assign to the declared cursor variables, and
> then assign again to the parameters of the call.

I expected that the "manager" (the main thread) would set of an array of "job"
records, and the procedure call would simply pass one of the job records. For
this sort of iterator, the job would contain the two cursors.

Note that you're not really saving anything by directly passing cursors this
way. Cursors don't fit in a parameter on most targets, so they're probably
getting passed by reference. So there has to be a temporary object declared
somewhere to allow that.

If you're generating this expansion at the intermediate code level (as we
would do in Janus/Ada), you have declare all of these things explicitly anyway
(nothing implicit in intermediate code!). So while there might be a small
convinience when using a library (like Paraffin), it's irrelevant to an
implementation. (At least some compilers implement functions like this as
procedure calls anyway, so there isn't any difference at the implementation
level - unless an extra temporary is needed to meet Ada semantics, as in an
assignment.)

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

From: Brad Moore
Sent: Friday, June 15, 2018   2:14 PM

Here is an update to AI12-266, Container Iterators [This is version /03 of the
AI - Editor.]

The main changes are to eliminate the cursor_array interface, and instead
imply that a cursor array or set of cursors is stored in the iterator object,
when Split is called. This approach overall is a lot simpler than the previous
version. There is no need for the Iterator_Cursor_Array aspect that the '
previous proposal had.

This gives the container implementor more freedom in designing data structures
for storing the loop parameters needed for parallel iteration.

I also changed the name of the calls, from To_Cursor to Get_Cursor, and from
Length to Split_Count, which I think adds clarity.

Also, instead of using Natural as the subtype for split indexes and cursor
counts, I defined

   subtype Cursor_Count is Positive;
   subtype Split_Index is Positive;

Which I think also adds clarity and ties the calls Split, Split_Count,
Get_Cursor, together more meaningfully.

Finally, I also added some pre and post conditions which help to make it
clearer how these calls work.

I would have liked to specify post conditions that check that
Has_Element(Get_Cursor (I)) for all I in 1 .. Object.Split_Count is true
after calling Split, or a post condition for Get_Cursor such as Post =>
(if Index = Object.Split_Count + 1 then Has_Element(Get_Cursor'Result) = False

But the compiler tells me that one cannot use Has_Element in a Pre or Post
condition in this package because the call involves a non tagged incomplete
type (Cursor)

I suppose we could add these as Pre and Post contracts to each of the
containers but the iterator types are not visible in the public part of the
package, so it seems not worthwhile to do so.

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

From: Randy Brukardt
Sent: Friday, June 15, 2018   9:07 PM

> Here is an update to AI12-266, Container Iterators
> 
> The main changes are to eliminate the cursor_array interface, and 
> instead imply that a cursor array or set of cursors is stored in the 
> iterator object, when Split is called. This approach overall is a lot 
> simpler than the previous version.
> There is no need for the Iterator_Cursor_Array aspect that the '
> previous proposal had.

Thanks, this seems a lot simpler.

For the record, I one editorial fix.

Part of the interface referenced the package "Ada202x". I presume this is
something you used in your testing, since there is no such thing proposed
here or anywhere else (nor did it appear in the previous version of the AI).
So I replaced all of those with "Ada".


I'd probably add a bit of discussion similar to our recent back-and-forth on 
how the cursor array could get implemented in the iterator object. Some people
might be concerned about the apparent need for dynamic allocation, and that 
should explicitly addressed.

...
> I would have liked to specify post conditions that check that 
> Has_Element(Get_Cursor (I)) for all I in 1 ..
> Object.Split_Count is true after calling Split, or a post condition 
> for Get_Cursor such as Post => (if Index = Object.Split_Count + 1 then 
> Has_Element(Get_Cursor'Result) = False
> 
> But the compiler tells me that one cannot use Has_Element in a Pre or 
> Post condition in this package because the call involves a non tagged 
> incomplete type
> (Cursor)

That sounds correct. Perhaps the rule is a bit more restrictive than it needs 
to be (one could allow the calls and then require a recheck for an instance - 
an assume-the-best rule), but changing that doesn't sound pleasant.

> I suppose we could add these as Pre and Post contracts to each of the 
> containers but the iterator types are not visible in the public part 
> of the package, so it seems not worthwhile to do so.

Don't see the point. The most important use of such Pre/Post is to eliminate 
the need to describe these restrictions and results in English. And they 
wouldn't apply to user-defined iterators if you only put them into the 
container.

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

From: Brad Moore
Sent: Saturday, June 16, 2018  12:21 AM

> For the record, I one editorial fix.
> 
> Part of the interface referenced the package "Ada202x". I presume this 
> is something you used in your testing, since there is no such thing 
> proposed here or anywhere else (nor did it appear in the previous version of
> the AI). So I replaced all of those with "Ada".

Yes, that was just for testing, I forgot to do the change you did this time 
round.

> I'd probably add a bit of discussion similar to our recent 
> back-and-forth on how the cursor array could get implemented in the 
> iterator object. Some people might be concerned about the apparent 
> need for dynamic allocation, and that should explicitly addressed.

I have attached another version with the discussion section updated to mention 
the possibility of implementation using fixed size array vs dynamic allocation. 
[This is version /04 of the AI - Editor.]

> ...
>> I would have liked to specify post conditions that check that 
>> Has_Element(Get_Cursor (I)) for all I in 1 ..
>> Object.Split_Count is true after calling Split, or a post condition 
>> for Get_Cursor such as Post => (if Index = Object.Split_Count + 1 
>> then Has_Element(Get_Cursor'Result) = False
>> 
>> But the compiler tells me that one cannot use Has_Element in a Pre or 
>> Post condition in this package because the call involves a non tagged 
>> incomplete type
>> (Cursor)
> 
> That sounds correct. Perhaps the rule is a bit more restrictive than 
> it needs to be (one could allow the calls and then require a recheck 
> for an instance - an assume-the-best rule), but changing that doesn't 
> sound pleasant.

The more I think about this, the more I think one ought to be able to specify 
such class-wide pre and post conditions for abstract subprograms.

I wonder if there might be a way to relax the rules in a simple way to allow 
this at least. Anyway, you are probably right that it might not be pleasant, 
but maybe something to consider if it would be worthwhile, at some point.

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

From: Randy Brukardt
Sent: Saturday, June 16, 2018  2:56 AM

> > I'd probably add a bit of discussion similar to our recent 
> > back-and-forth on how the cursor array could get implemented in the 
> > iterator object. Some people might be concerned about the apparent 
> > need for dynamic allocation, and that should explicitly addressed.
> 
> I have attached another version with the discussion section updated to 
> mention the possibility of implementation using fixed size array vs 
> dynamic allocation.

You'll excuse me if I don't post this now; it's 12 hours past the deadline,
I've already posted the agenda and the files and loaded my laptop and there's
water on the floor in here from a severe thunderstorm that just went thru...
 
> > 
...
> > That sounds correct. Perhaps the rule is a bit more restrictive than 
> > it needs to be (one could allow the calls and then require a recheck 
> > for an instance - an assume-the-best rule), but changing that 
> > doesn't sound pleasant.
> > 
> 
> The more I think about this, the more I think one ought to be able to 
> specify such class-wide pre and post conditions for abstract 
> subprograms.

The problem has nothing to do with preconditions of abstract subprograms.
It's that you're doing it in a generic with a formal incomplete type that 
isn't supposed to be used in any way other than to declare access types and
subprogram parameters. And that was because we needed this generic to work on
a *private* cursor. And you might remember that we were never able to find an
adequate solution for *that* problem.

> I wonder if there might be a way to relax the rules in a simple way to 
> allow this at least.
> Anyway, you are probably right that it might not be pleasant, but 
> maybe something to consider if it would be worthwhile, at some point.

I was thinking that we might be able to allow it in a generic if we require 
the recheck. However, the recheck would fail in this case (the type being
private) so I don't think that helps much. In any case, incomplete types are 
not supposed to have any sort of object created for them, and allowing this 
case without allowing anything that causes real trouble sounds painful. It 
would have been better if we didn't need to use this hack to get an instance
of a private type - but we *know* that was painful.

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


Questions? Ask the ACAA Technical Agent