CVS difference for ai12s/ai12-0266-1.txt

Differences between 1.6 and version 1.7
Log of other versions for file ai12s/ai12-0266-1.txt

--- ai12s/ai12-0266-1.txt	2018/06/30 00:53:42	1.6
+++ ai12s/ai12-0266-1.txt	2018/10/17 04:36:32	1.7
@@ -1,4 +1,4 @@
-!standard 5.5.1(4/3)                                  18-06-16  AI12-0266-1/04
+!standard 5.5.1(4/3)                                  18-10-14  AI12-0266-1/05
 !standard 5.5.1(6/4)
 !standard 5.5.1(11/3)
 !standard 5.5.2(4/3)
@@ -23,9 +23,8 @@
 
 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.
+Those proposals allow the compiler to statically determine where
+parallelism may be introduced without introducing data races.
 
 The goals of this proposal are:
 - To extend parallel iteration to the standard container libraries
@@ -36,30 +35,28 @@
   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
+- To avoid syntax that could generate erroneous behaviour 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.
+to include two new interfaces, a parallel iterator interface, and a
+reversible parallel 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_Into_Chunks procedure that can be used to
+associate with the iterator a set of cursors that define the chunk boundaries
+for parallel iteration. Each cursor is assigned to a different logical thread of
+control and 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.
+
+The starting cursor for each chunk of iteration can be obtained by calling the
+Start_Of_Chunk operation, passing in the chunk index of the split as a parameter
+to the call. A Chunk_Finished operation is provided to allow a logical thread of
+control to determine if all elements of the chunk have been processed. The idea
+is that the iteration for a chunk is complete when the current cursor gets
+advanced enough times to cause Chunk_Finished to return False.
 
 In addition, the loop syntax is extended to allow the loops with iterator
 specifications to have the parallel keyword.
@@ -72,39 +69,62 @@
    | [parallel] for loop_parameter_specification
    | [parallel] for iterator_specification
 
+Modify 5.5.1 (2/5 - 4/3)
+
+generic
+   type Cursor;
+   with function Has_Element (Position : Cursor) return Boolean;
+package Ada.Iterator_Interfaces
+   with Pure[, Nonblocking => False] is
+
+   type Forward_Iterator is limited interface {with Nonblocking => False};
+   function First (Object : Forward_Iterator) return Cursor is abstract;
+   function Next (Object : Forward_Iterator; Position : Cursor)
+      return Cursor is abstract;
+
+   type Reversible_Iterator is limited interface and Forward_Iterator
+     {with Nonblocking => False};  [Author: Redundant since inherited]
+   function Last (Object : Reversible_Iterator) return Cursor is abstract;
+   function Previous (Object : Reversible_Iterator; Position : Cursor)
+      return Cursor is abstract;
+
 Add after 5.5.1(4/3)
 
+   type Iteration_Count_Type is mod System.Max_Binary_Modulus;
+
    type Parallel_Iterator is limited interface and Forward_Iterator
-      -- with Nonblocking
-      ;
+      with Nonblocking;
 
    function Iterations
      (Object : Parallel_Iterator)
-      return Ada.Containers.Count_Type is abstract;
+      return Iteration_Count_Type is abstract;
 
    subtype Cursor_Count is Positive;
-   subtype Split_Index is Positive;
-   use type Ada.Containers.Count_Type;
+   subtype Chunk_Index is Positive;
 
-   procedure Split
+   procedure Split_Into_Chunks
      (Object        : in out Parallel_Iterator;
-      Advised_Split : Cursor_Count) is abstract
+      Maximum_Split : Cursor_Count) is abstract
      with Pre'Class =>
-       Ada.Containers.Count_Type (Advised_Split) <= Object.Iterations,
-          Post'Class => Object.Split_Count <= Advised_Split;
+       Iteration_Count_Type (Maximum_Split) <= Object.Iterations,
+          Post'Class => Object.Chunk_Count <= Maximum_Split;
 
-   function Split_Count
+   function Chunk_Count
      (Object  : Parallel_Iterator) return Cursor_Count is abstract;
 
-   function Get_Cursor
+   function Start_Of_Chunk
      (Object : Parallel_Iterator;
-      Index  : Split_Index) return Cursor is abstract
-     with Pre'Class => Index <= Object.Split_Count + 1;
+      Chunk  : Chunk_Index) return Cursor is abstract
+     with Pre'Class => Chunk <= Object.Chunk_Count;
 
+   function Chunk_Finished
+     (Object   : Parallel_Iterator;
+      Chunk    : Chunk_Index;
+      Position : Cursor) return Boolean is abstract
+     with Pre'Class => Chunk <= Object.Chunk_Count;
+
    type Parallel_Reversible_Iterator is limited interface
-     and Parallel_Iterator and Reversible_Iterator
-       -- with Nonblocking
-       ;
+     and Parallel_Iterator and Reversible_Iterator with Nonblocking;
 
 Modify 5.5.1(6/3)
 
@@ -113,15 +133,15 @@
 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.
+Ada.Iterator_Interfaces. A parallel reversible iterator type is a type descended
+from the Parallel_Iterator interface 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)
 
@@ -141,15 +161,15 @@
 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
+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 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.}
+shall be of a parallel iterator type or a parallel reversible iterator type.}
 
 Modify 5.5.2(7/5)
 
@@ -220,27 +240,28 @@
 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.
+loop_statement is complete. Otherwise, the operation Split_Into_Chunks of the
+iterator type is then called, with the Maximum_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 Chunk_Count operation of the iterator. Each loop parameter is
+assigned to a different logical thread of control, with an ordinal chunk index
+value. The Initial cursor values to be associated with each loop parameter is
+determined by calling the Start_Of_Chunk operation of the iterator using the
+chunk index value of the loop parameter object as the Chunk parameter for the
+call. The sequence_of_statements is executed for each loop parameter object and
+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. The Chunk_Finished operation is called with the chunk
+index value and current loop parameter value to determine if the iteration
+assigned to the logical thread of control is complete. Otherwise the iteration
+continues unless 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
+The number of loop parameters specified for the Maximum_Split parameter of the
+Split_Into_Chunks 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.
 
@@ -284,7 +305,7 @@
 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]
+Modify 5.5.2(13/3) [into two 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
@@ -303,24 +324,25 @@
 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.
+is complete. Otherwise, the operation Split_Into_Chunks of the iterator type is
+then called, with the Maximum_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
+Chunk_Count operation of the iterator. Each loop parameter is assigned to a
+different logical thread of control, with an ordinal chunk index value. The
+Initial cursor values to be associated with each loop parameter is determined by
+calling the Start_Of_Chunk operation of the iterator using the chunk index value
+of the loop parameter object as the Chunk parameter for the call. The
+sequence_of_statements is executed for each loop parameter object and 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. The Chunk_Finished operation is called with the chunk index
+value and current loop parameter value to determine if the iteration assigned to
+the logical thread of control is complete. Otherwise, the iteration continues
+unless 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)
 
@@ -402,10 +424,10 @@
 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
+{, and starting with all nodes simultaneously using the Split_Into_Chunks
+procedure 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.
 
@@ -423,11 +445,11 @@
 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.
+reverse iterator {or all nodes simultaneously using the Split_Into_Chunks
+procedure 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)
 
@@ -445,8 +467,8 @@
 [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
+simultaneously using the Split_Into_Chunks procedure 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
@@ -475,11 +497,11 @@
 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.
+Split_Into_Chunks procedure 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)
 
@@ -495,11 +517,12 @@
 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.
+when used as a reverse iterator {, or all nodes simultaneously using the
+Split_Into_Chunks procedure 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)
 
@@ -517,9 +540,9 @@
 [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
+nodes simultaneously using the Split_Into_Chunks procedure 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.
@@ -547,9 +570,9 @@
 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
+nodes simultaneously using the Split_Into_Chunks procedure 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.
@@ -564,15 +587,16 @@
 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.
+(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_Into_Chunks procedure 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)
 
@@ -595,8 +619,8 @@
 [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
+simultaneously using the Split_Into_Chunks procedure 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
@@ -614,49 +638,48 @@
 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.
+used as a forward iterator, or all nodes simultaneously using the
+Split_Into_Chunks procedure 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
+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.
+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. 
+The container writer has the ability to implement the container to define
+an optimal number of loop parameters to be setup by the Split_Into_Chunks call, so long as
+the number of splits is not greater than the Maximum_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;
+It would have been nice to specify a post condition for the Split_Into_Chunks
+call something like;
 
   with Post => (for all I in 1 .. Object.Split_Count =>
                  Has_Element (Object.Get_Cursor (I)))
@@ -665,18 +688,10 @@
 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
+Similarly, it would have been nice to write a Post condition for Start_Of_Chunk
 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.
@@ -1155,10 +1170,10 @@
 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 
+>
+> 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.
@@ -1173,34 +1188,34 @@
 So I replaced all of those with "Ada".
 
 
-I'd probably add a bit of discussion similar to our recent back-and-forth on 
+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 
+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 
+> 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 
+> 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 
+>
+> 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 - 
+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 
+> 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 
+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.
 
 ****************************************************************
@@ -1209,46 +1224,46 @@
 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 
+>
+> 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 
+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 
+> 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. 
+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 
+>> 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 
+>> 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 
+>>
+>> 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 
+>
+> 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 
+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, 
+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.
 
 ****************************************************************
@@ -1256,50 +1271,136 @@
 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 
+> > 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 
+>
+> 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 
+> > 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 
+> >
+>
+> 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 
+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 
+> 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 
+> 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 
+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 
+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.
+
+****************************************************************
+
+From: Brad Moore
+Sent: Sunday, October 14, 2018  3:53 PM
+
+Here is a modest update to AI12-0266-1 Parallel Container Iteration.
+[This is version /05 of the AI - Editor.]
+
+Mostly the changes involve renaming types and subprograms to address ARG
+comments. A Chunk_Finished call was added to the Iterator_Interfaces, rather
+than expecting the compiler to compare the current cursor with another cursor
+value, which cant be counted on, since equality checks are not part of the
+interface.
+
+One thought for consideration was to have the Split_Into_Chunks call somehow
+temporary invalidate all existing cursors, and have the First, Next, Last, and
+Previous only allow retrieving cursors associated with the current chunk and a
+particular logical thread of control.
+
+That idea held some appeal, as it would seem to add safety to the containers. It
+would be more difficult for the user to write code to iterate from one chunk
+into another. That would also allow us to eliminate the call to Chunk_Finished.
+Since we are already calling Next to Advance the cursor, we could define Next to
+return No_Element if one advances to the end of a chunk, and do the usual
+comparison against No_Element to terminate the iteration.
+
+In any case, this idea did not make it into the AI in any form. Just food for
+thought. Perhaps that idea could be discussed at the meeting if it has any
+merit.
+
+****************************************************************
+
+From: Randy Brukardt
+Sent: Tuesday, October 16, 2018  11:36 PM
+
+...
+> One thought for consideration was to have the
+> Split_Into_Chunks call somehow
+> temporary invalidate all existing cursors, and have the
+> First, Next, Last, and Previous only
+> allow retrieving cursors associated with the current chunk
+> and a particular logical thread of control.
+>
+> That idea held some appeal, as it would seem to add safety to
+> the containers. ...
+
+Sure, but what would the implementation be? A canonical cursor is a pair of
+access values (one to the container, one to the node containing the element).
+How would the implementation figure out if the cursors are "temporarily
+invalidated"? Walking lists in the container might work, but would be O(N) and
+cursors are supposed to be O(1). And you'd have to worry about tasking
+interactions (there are many logical threads going here at once). Sounds to me
+like it would make tampering look like a cheap idea in contrast. :-)
+
+---
+
+A nitpick:
+
+>A parallel iterator provides a Split_Into_Chunks procedure that can be used
+>to associate with the iterator a set of cursors that define the chunk
+>boundaries for parallel iteration. Each cursor is assigned to a different
+>logical thread of control ...
+
+Probably should be "can be assigned", since there is no requirement on the
+implementation to use different threads of control for each chunk. (One might
+like that, but it's not always practical.) Or, maybe just drop the whole
+discussion about "logical thread of control" here and just focus on the chunk.
+I'll let you decide on this, I know you are sending me another change that we've
+been discussing privately.
+
+---
+
+> ... A parallel reversible iterator type is a type descended
+from both the Parallel_Reversible_Iterator interace from some
+instance of Ada.Iterator_Interfaces.}
+
+"both"? There's only one "interace" mentioned. "Interace" sounds like it could
+get political. :-)
+
+I fixed both of these.
+
+---
+
+I reformatted a lot of paragraphs to keep the lines under 80 characters. Some
+people appreciate that.
 
 ****************************************************************
 

Questions? Ask the ACAA Technical Agent