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

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

--- ai12s/ai12-0266-1.txt	2018/04/14 05:00:39	1.3
+++ ai12s/ai12-0266-1.txt	2018/06/15 01:03:32	1.4
@@ -1,4 +1,4 @@
-!standard 5.5.1(4/3)                                  18-03-28  AI12-0266-1/01
+!standard 5.5.1(4/3)                                  18-06-14  AI12-0266-1/02
 !standard 5.5.1(6/4)
 !standard 5.5.1(11/3)
 !standard 5.5.2(4/3)
@@ -21,9 +21,9 @@
 
 !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 
+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.
 
@@ -34,9 +34,8 @@
   more parallel execution;
 - To support the development of complete programs that maximize
   parallelism;
-- To efficiently guide the compiler in the creation of effective
-  parallelism (without oversubscription of the parallelism resources) with
-  minimal input from the programmer;
+- To 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.
 
@@ -48,9 +47,17 @@
 for loops that do not have the parallel reserved keyword.
 
 A parallel iterator provides a Split function that can be used to return a
-chunk array that defines the chunk boundaries and cursors needed for iterating
-through the container in parallel, where each chunk of iteration can execute
-in parallel with other chunks. 
+cursor array that defines the chunk boundaries and cursors needed for iterating
+through the container in parallel, where each cursor in the array identifies
+the first cursor of a  different chunk of iterations that can be iterated through
+in parallel with other iteration chunks. Each cursor of the array can be
+obtained by calling the To_Cursor operation passing in the index of the chunk
+as a parameter to the call. The end of a chunk can be determined by calling the
+To_Cursor operation for the next highest chunk index. Calling To_Cursor with
+an index value higher than the number of elements in the cursor array returns
+a No_Element cursor. The idea is that the iteration for a chunk is complete when
+the current cursor gets advanced enough times to give the cursor value associated
+with the next highest index.
 
 In addition, the loop syntax is extended to allow the loops with iterator
 specifications to have the parallel keyword.
@@ -65,35 +72,38 @@
 
 Add after 5.5.1(4/3)
 
-   type Chunk_Array is limited interface
-     with Nonblocking;
+   type Cursor_Array is limited interface
+     -- with Nonblocking
+     ;
 
    function Length
-     (Object  : Chunk_Array) return Natural is abstract;
+     (Object  : Cursor_Array) return Natural is abstract;
 
-   function Start
-     (Object : Chunk_Array;
+   function To_Cursor
+     (Object : Cursor_Array;
       Index  : Natural) return Cursor is abstract;
 
-   function Finish
-     (Object : Chunk_Array;
-      Index  : Natural) return Cursor is abstract;
+   procedure Set_Cursor
+     (Object : in out Cursor_Array;
+      Index : Natural;
+      Position : Cursor) is abstract;
 
    type Parallel_Iterator is limited interface and Forward_Iterator
-      with Nonblocking;
+      -- with Nonblocking
+      ;
 
    function Iterations
      (Object : Parallel_Iterator)
       return Ada.Containers.Count_Type is abstract;
 
-   function Split
+   procedure Split
      (Object        : Parallel_Iterator;
-      Advised_Split : Natural)
-      return Chunk_Array'Class is abstract;
+      Into          : out Cursor_Array'Class) is abstract;
 
    type Parallel_Reversible_Iterator is limited interface
      and Parallel_Iterator and Reversible_Iterator
-       with Nonblocking;
+       -- with Nonblocking
+       ;
 
 Modify 5.5.1(6/3)
 
@@ -112,16 +122,27 @@
 associated instance of Ada.Iterator_Interfaces is the iteration cursor subtype
 for the iterator type.
 
+Add after 5.5.1(9.a/3)
+
+Iteraetor_Cursor_Array
+
+This aspect is specified by a name that denotes a subtype. This is the default
+cursor array subtype for T.
+
+Aspect Description for Iterator_Cursor_Array: Cursor array type to be used for
+parallel iteration.
+
 Modify 5.5.1(11/3)
 
 An iterable container type is an indexable container type with specified
 Default_Iterator and Iterator_Element aspects. A reversible iterable container
 type is an iterable container type with the default iterator type being a
 reversible iterator type. {A parallel iterable container type is an iterable
-container type with the default iterator type being a parallel iterator type. A
-parallel reversible iterable container type is an iterable container type with
-the default iterator type being a parallel reversible iterator type.} An
-iterable container object is an object of an iterable container type. A
+container type with a specified Iterator_Cursor_Array aspect with the default
+iterator type being a parallel iterator type. A parallel reversible iterable
+container type is an iterable container type with a specified Iterator_Cursor_Array
+aspect with the default iterator type being a parallel reversible iterator type.}
+An iterable container object is an object of an iterable container type. A
 reversible iterable container object is an object of a reversible iterable
 container type. {A parallel iterable container object is an object of a parallel
 iterable container type. A parallel reversible iterable container object is an
@@ -207,35 +228,36 @@
 For a parallel generalized iterator, the operation Iterations
 of the iterator type is called first to determine the number of iterations
 associated with the iterator. If the result of calling Iterations is 0, then the
-execution of the loop_statement is complete. Otherwise, the operation Split of
-the iterator type is then called on a loop iterator, with the Advised_Split
-parameter value set to a value determined by the implementation that indicates a
-recommendation for the number of loop parameter objects that should be created.
-The result of the call to Split is a Chunk_Array object that indicates the
-number of loop parameter objects to be created by the implementation, as well as
-the range of cursor values to be uniquely associated with each loop parameter
-object. The number of loop parameters to be created is determined by calling
-Length operation of the Chunk_Array. The range of cursor values to be associated
-with each loop parameter is determined by calling the Start and Finish operation
-of the Chunk_Array object using an ordinal index value of the loop parameter
-object as the Index parameter for these calls. The result of calling the Start
-operation is the initial cursor value to be assigned to a given loop parameter
-object. The result of calling the Finish operation is the final cursor value to
-be iterated for a given loop parameter object. The sequence_of_statements is
-executed for each loop parameter object and then the Next operation of the
-iterator type is called with the loop iterator and the current value of the loop
-parameter to produce the next value to be assigned to a given loop parameter.
-This repeats until the value of the loop parameter is equal to the final cursor
-value associated with the given loop parameter, or the loop is left as a
-consequence of a transfer of control.
+execution of the loop_statement is complete. Otherwise, a Cursor array object of
+the type specified by the Iterator_Cursor_Array aspect is declared, with the
+number of elements associated with the Cursor array object being set to a value
+determined by the implementation that indicates a recommendation for the number
+of loop parameter objects that should be created. The operation Split of
+the iterator type is then called.
+The result of the call to Split is the Cursor_Array
+object is assigned a set of cursor values indicating the initial cursor values
+to be uniquely associated with each loop parameter object. The number of loop
+parameters to be created is determined by calling Length operation of the
+Cursor_Array. The Initial cursor values to be associated with each loop parameter
+is determined by calling the To_Cursor operation of the Cursor_Array object using
+an ordinal index value of the loop parameter object as the Index parameter for the
+call. The sequence_of_statements is executed for each loop parameter object and
+then the Next operation of the iterator type is called with the loop iterator and
+the current value of the loop parameter to produce the next value to be assigned
+to a given loop parameter. This repeats until the value of the loop parameter is
+equal to the initial cursor value associated with the next highest next loop parameter,
+or if the Has_Element operation associated with the Iterator object returns False,
+or if the loop is left as a consequence of a transfer of control.
 
 AARM Note
 
-The Advised_Split parameter value is only a recommendation by the
-implementation. A container implementation may choose to ignore that
+The number of elements specified for the Cursor_Array object is only a
+recommendation by the implementation. A container implementation may choose to ignore that
 recommendation if a more optimal split can be determined. For instance, a tree
 based container might create the split based on the number of branches at the
-top levels of the tree.
+top levels of the tree. Any resulting elements of a Cursor_Array object that are
+not to be used should be to be set to the No_Element value associated with
+the Cursor type.
 
 Modify AARM 5.5.2(10.a/4)
 
@@ -245,7 +267,7 @@
 subtype is indefinite, the variable is constrained by its initial value.
 Similarly, if the nominal subtype is class-wide, the variable (like all
 variables) has the tag of the initial value. Constraint_Error may be raised by a
-subsequent iteration if Next{, }[ or] Previous{, or Split} return an object with
+subsequent iteration if Next or Previous return an object with
 a different tag or constraint.
 
 Modify 5.5.2(11/3)
@@ -296,28 +318,34 @@
 For a parallel container element iterator, the operation Iterations is first
 called to determine the number of iterations associated with the iterator. If
 the result of calling Iterations is 0, then the execution of the loop_statement
-is complete. Otherwise, the operation Split of the iterator type is then called
-on a loop iterator, with the Advised_Split parameter value set to a value
+is complete. Otherwise, a Cursor array object of the type specified by the
+Iterator_Cursor_Array aspect is declared, with the number of elements
+associated with the Cursor array object being set to a value
 determined by the implementation that indicates a recommendation for the number
-of loop parameter objects that should be created. The result of the call to
-Split is a Chunk_Array object that indicates the number of loop parameter
-objects to be created by the implementation, as well as the range of cursor
-values to be uniquely associated with each loop parameter object. The number of
-loop parameters to be created is determined by calling the Length operation of
-the Chunk_Array. The range of cursor values to be associated with each loop
-parameter is determined by calling the Start and Finish operation of the
-Chunk_Array object using an ordinal index value of the loop parameter object as
-the Index parameter for these calls. The result of calling the Start operation
-is the initial cursor value to be assigned to a given loop parameter object. The
-result of calling the Finish operation is the final cursor value to be iterated
-for a given loop parameter object. The sequence_of_statements is executed for
-each loop parameter object and then the Next operation of the iterator type is
-called with the loop iterator and the current value of the loop parameter to
-produce the next value to be assigned to a given loop parameter. This repeats
-until the value of the loop parameter is equal to the final cursor value
-associated with the given loop parameter, or the loop is left as a consequence
-of a transfer of control.
+of loop parameter objects that should be created. The operation Split of
+the iterator type is then called.
 
+The result of the call to Split is the Cursor_Array
+object is assigned a set of cursor values indicating the initial cursor values
+to be uniquely associated with each loop parameter object. The number of loop
+parameters to be created is determined by calling Length operation of the
+Cursor_Array. The Initial cursor values to be associated with each loop parameter
+is determined by calling the To_Cursor operation of the Cursor_Array object using
+an ordinal index value of the loop parameter object as the Index parameter for the
+call.
+The Initial cursor values to be associated with each loop parameter
+is determined by calling the To_Cursor operation of the Cursor_Array object using
+an ordinal index value of the loop parameter object as the Index parameter for the
+call.
+The sequence_of_statements is executed for each loop parameter object and then the
+Next operation of the iterator type is called with the loop iterator and the
+current value of the loop parameter to produce the next value to be assigned to
+a given loop parameter.
+This repeats until the value of the loop parameter is
+equal to the initial cursor value associated with the next highest next loop parameter,
+or if the Has_Element operation associated with the Iterator object returns False,
+or if the loop is left as a consequence of a transfer of control.
+
 }If the loop parameter is a constant  (see above), then the indexing uses the
 default constant indexing function for the type of the iterable container object
 for the loop; otherwise it uses the default variable indexing function.
@@ -622,25 +650,6 @@
 iterator_specification denotes this object). The iterator object needs
 finalization.
 
-Add after D.16(5/3)
-
-   type Iteration_Count is range 0 .. implementation-defined;
-   for Iteration_Count'Size use implementation-defined;
-
-   type Split_Count is range 0 .. implementation-defined;
-
-   function Advised_Split_Count
-     (Iterations :  Iteration_Count) return Split_Count
-       witn Non_Blocking => False;
-
-Add after D.16(8/3)
-
-The Advised_Split_Count function accepts a parameter that indicates the number
-of iterations associated with a parallel loop, and returns a recommended value
-for the number of loop parameter objects to be associated with a parallel loop
-statement. Such a value is intended to be passed as an actual for the
-Advised_Split parameter of the Split operation associated with a parallel
-iterator object (see 5.5.1).
 
 !discussion
 
@@ -656,23 +665,15 @@
 parallel processing if the amount of time to process each node in the loop is
 significantly greater than the amount of time needed to iterate through the list.
 
-Sometimes there are loops that need initialization or finalization for each
-executor, that might be too expensive to apply for each iteration, but would be
-worthwhile if applied once per chunk of execution. An example might be where
-a file needs to be opened for each executor where the loop writes results to
-the file, and after the executor completes its chunk, the file needs to be closed.
-Other possible uses include memory allocation for temporary data structures.
-
-Such loops would require user-defined chunking, where the user code explicitly calls
-the Split function of a Parallel iterator to obtain the Chunk_Array object that
-normally the implementation would request. This allows the user to express the
-parallelism more explicitly by writing an outer loop that iterates through the
-number of chunks and an inner loop that iterates through the elements of each
-chunk.
-
-The container writer has the ability to implement the container to define
-an optimal number of elements in the chunk array that are to be returned by the 
-Split call, as well as the cursors associated with each element of the chunk array.
+Originally, we had the Split operation as a function rather than a procedure.
+It was felt that returning a class-wide type as a function result was undesirable,
+and possibly inefficient. So the Split call was modified to be a procedure.
+However, that means the real cursor array type needs to be declared before calling
+split, and since the compiler is to be making this call, there needed to be a
+way to tell the implementation which type should be used to create the cursor array
+object. The solution to this problem was to create a Interator_Cursor_Array
+aspect, similar to the Iterator_Element aspect, that allows the container implementer
+to specify the cursor array type to be passed to the Split call for parallel iteration.
 
 !ASIS
 
@@ -692,7 +693,7 @@
 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. 
+This one deals specifically with parallel container iteration.
 The writeup is very much the same as before.
 
 ****************************************************************
@@ -703,5 +704,139 @@
 Thanks.  I am thinking this should probably also be in Chapter 9 after
 introducing the notion of tasklets, rather than trying to weave it into the
 current discussion of iterators, which is already pretty complex.
+
+****************************************************************
+
+From: Brad Moore
+Sent: Thursday, June 14, 2018   1:15 AM
+
+Here is an update to AI12-0266, [This is version /02 of the AI - Editor.]
+
+The main changes are;
+
+- Changed Chunk_Array type to be called Cursor_Array type.
+
+The reason is that "Chunk" is not well defined in the RM, and an array of
+chunks leaves a bit to the imagination.
+
+A cursor array however seems a lot easier to visualize.
+
+The semantics of Chunk_Array was that for every chunk there was a Start and
+Finish call that could be used to determine the first and last cursor of each
+chunk. One problem with this is that it is not clear if the last cursor is
+inclusive or exclusive to the set of cursors to be iterated over.
+
+With a cursor array, there is only one cursor per chunk, and only one call,
+To_Cursor, available to get the starting cursor. To get the end cursor you
+use the next highest index value, which should be more obvious that this is
+an exclusive cursor value. The idea also is that if you specify an index value
+higher than the number of chunks in the cursor array, you get a No_Element
+result. So calling To_Cursor with index + 1 consistently gives you a cursor
+value that can be compared against for chunk iteration termination.
+
+Another change is that the Split operation is no longer a function returning
+an object of a class-wide type. Instead, Split is a procedure that has an out
+parameter of a class-wide type. (A change requested by Tucker)
+
+By doing this, I think there needed to be a way for the container implementer
+to tell the compiler which type to use for declaring the cursor array type. So
+I added an Iterator_Cursor_Array aspect, similar to Iterator_Element aspect,
+that may be specified on a container type declaration for this purpose.
+
+Since the implementation is now responsible for declaring the cursor array
+type, the idea is that the number of elements of the cursor array is now the
+means to indicate to the container implementer, how many chunks to create.
+
+A container implementer can use less than the number of elements of the cursor
+array, but then must leave the remaining elements set as No_Element.
+
+As a result of this, there no longer needs to be an Advised_Split parameter to
+the Split call.
+
+Another change is that since the Split function needs to store cursors into an
+out parameter Cursor_Array class-wide object, there needed to be a way to
+store a cursor into a cursor array object. So I added a Set_Cursor procedure
+to the Cursor_Array interface.
+
+****************************************************************
+
+From: Brad Moore
+Sent: Thursday, June 14, 2018  10:30 AM
+
+A question I have about this approach, is it enough to use the
+Iterator_Cursor_Array aspect to tell the compiler how to set up the cursor
+array object?
+
+Specifically, in my test example using Ada.Containers.Doubly_Linked_Lists, I
+have the cursor array type having a visible discriminant to set the length of
+the array.
+
+Do we need to specify in the RM that it is expected that all cursor array
+types will have a single discriminant of a type (Natural) indicating the
+number of elements in a cursor array?
+
+Or maybe we need another aspect to somehow tell the compiler how to specify
+the cursor array length?
+
+Or we could add a Set_Length function to the interface, but then that likely
+implies a controlled type with dynamic memory allocation, which seems to be
+undesirable.
+
+This also has me wondering if we might have been better off leaving the Split
+subprogram as a function rather than a procedure. Then the container
+implementor can create tne cursor array object inside the Split call with the
+desired length. We can then also simplify the interface by eliminating the
+Set_Cursor call.
+
+I note also that we do have other iterator calls that are functions returning
+class-wide types, such as Iterate in the containers.
+
+****************************************************************
+
+From: Randy Brukardt
+Sent: Thursday, June 14, 2018   1:46 PM
+
+> A question I have about this approach, is it enough to use the
+> Iterator_Cursor_Array aspect to tell the compiler how to set up the
+> cursor array object?
+
+Let's start further back. Why do we need a Iterator_Cursor_Array object at all?
+
+There would have been value to that approach if you could have declared an
+actual array (fewer subprogram calls), but since it has to be private,
+getting each cursor is going to involve a subprogram call.
+
+So, what is the separate object gaining over just putting the Get_Cursor call
+directly on the iterator object (the implementation of which is totally
+user-controlled, so it could have an array of cursors internally if it wants)?
+The "user" of this structure is the parallel loop, and it obviously has an
+iterator object it is going to use to iterate. Why does it need anything
+more??
+
+So I would suggest that Split is just a call to tell the iterator how to
+organize its internal data structure. Still need the Advised_Split parameter,
+something like:
+
+   procedure Split
+     (Object        : in out Parallel_Iterator;
+      Advised_Split : in Natural) is abstract;
+      -- Tell Object to create split data with the advised number of splits.
+
+   function Split_Length (Object : in Parallel_Iterator) return Natural is abstract;
+      -- Determine the actual split length.
+
+   function Split_Cursor (Object : in Parallel_Iterator;
+                          Split_Index : in Natural) return Cursor;
+
+or, since it would save an assignment in many implementations:
+
+   procedure Split_Cursor (Object : in Parallel_Iterator;
+                           Split_Index : in Natural;
+                           Result : out Cursor);
+
+Either of these would have the semantics you suggested yesterday (chunk ends
+with the 'Succ index, get No_Element if Split_Index >= Length).
+
+Do you need anything else?
 
 ****************************************************************

Questions? Ask the ACAA Technical Agent