Version 1.8 of ai12s/ai12-0196-1.txt

Unformatted version of ai12s/ai12-0196-1.txt version 1.8
Other versions for file ai12s/ai12-0196-1.txt

!standard A.18(2/2)          16-12-27 AI12-0196-1/07
!standard A.18.2(125/2)
!standard A.18.2(133/3)
!standard A.18.2(135/3)
!standard A.18.3(81/3)
!standard A.18.4(36/3)
!standard A.18.7(34/2)
!standard A.18.10(116/3)
!class binding interpretation 16-10-10
!status Amendment 1-2012 16-11-11
!status ARG Approved 9-0-0 16-10-10
!status work item 16-06-07
!status received 16-06-05
!priority Low
!difficulty Hard
!subject Concurrent access to Ada container libraries
!summary
The definition of the containers is modified to allow simple parallel processing of containers.
!question
With the advent of multi-core computers, the performance of certain algorithms and data structures can be improved. The Ada standard containers are such data structures that could be involved in lengthy processing and could be candidates for parallelism. Unfortunately, Ada currently says that for concurrent calls, the language-defined subprograms are only required to work if the parameters of the call are nonoverlapping. Most container calls involve a controlling parameter of the container type, yet the call on the container may only be affecting a subset of the elements in the container, and may not affect state that is global to all of the elements being modified. Other calls only read elements of the container without modification.
Should it be possible to apply parallelism to such cases so long as each independent thread operates on a unique, nonoverlapping set of elements from the container? (Yes.)
!recommendation
We propose to require certain operations that manipulate or examine cursors (ie. Next, Previous, and Element) to work for concurrent calls if the calls only accept a Cursor as a parameter. This is achieved by specifying that cursors only overlap with the element they designate. For Vector containers, we also specify that To_Cursor is Reentrant.
!wording
Modify A.18(2/2):
A cursor referencing an element in a container is considered to be overlapping {only} with the {element}[container object] itself.
Modify AARM A.18(2.a/2)
Reason: The last sentence is intended to clarify that operations that just use a cursor {do not interfere if the cursor objects designate different elements of the container}[are on the same footing as operations that use a container] in terms of the {concurrent call}[reentrancy] rules of Annex A.
{Ramification: A cursor is not considered to overlap with other elements of the associated container, thus parallel operations involving a set of cursors each operating on mutually exclusive sets of elements from the same container are expected to work.}
Modify AARM A.18(5.o/2):
Library packages must {allow concurrent calls}[be reentrant] -- multiple tasks can use the packages as long as they operate on separate containers. Thus, it is only necessary for a user to protect a container if a single container needs to be used by multiple tasks {and concurrent calls to operations of the container have overlapping parameters.}.
Append to A.18.2(125/2):
For the purposes of determining whether the parameters overlap in a call to To_Cursor, the Container parameter is not considered to overlap with any object Redundant[(including itself)].
AARM Reason: Without the preceding rule, concurrent calls to To_Cursor on the same container would interfere by the concurrent call rules in Annex A, since the container object of the concurrent calls would overlap with itself. We want these to not interfere, for example to allow the Vector elements to be split into separate "chunks" for parallel processing.
Append to A.18.2(133/3):
For the purposes of determining whether the parameters overlap in a call to Replace_Element, the Container parameter is not considered to overlap with any object Redundant[(including itself)], and the Index parameter is considered to overlap with the element at position Index.
Append to A.18.2(135/3):
For the purposes of determining whether the parameters overlap in a call to Replace_Element, the Container parameter is not considered to overlap with any object Redundant[(including itself)].
Append to A.18.3(81/3):
For the purposes of determining whether the parameters overlap in a call to Replace_Element, the Container parameter is not considered to overlap with any object Redundant[(including itself)].
Append to A.18.4(36/3):
For the purposes of determining whether the parameters overlap in a call to Replace_Element, the Container parameter is not considered to overlap with any object Redundant[(including itself)].
Append to A.18.7(34/2):
For the purposes of determining whether the parameters overlap in a call to Replace_Element, the Container parameter is not considered to overlap with any object Redundant[(including itself)].
Append to A.18.10(116/3):
For the purposes of determining whether the parameters overlap in a call to Replace_Element, the Container parameter is not considered to overlap with any object Redundant[(including itself)].
!discussion
The needs of parallel programs are quite different than those of general concurrent programs. The goal is to achieve performance rather than satisfy needs for access from multiple threads of execution. Parallel programs typically apply a divide and conquer strategy to reduce a bigger problem into smaller ones that can be handed out to separate cores of a multicore processor. By this very nature, the smaller pieces of work tend to be separate independent work items. A good example of such a problem is container iteration, where similar processing needs to be applied to all the elements of the container.
The Ada standard container libraries do not support such concurrent access, even though implementations exist that provide this support. This level of support should be standardized so that parallel programs can be portable across different compiler implementations.
The first obstacle is that the standard says that a language-defined subprogram call is required to work with concurrent calls only if all the parameters of the call are nonoverlapping with respect to other active calls.
The standard also says that a cursor for a container is to be treated as though it overlaps with the container object.
To iterate through a container in parallel however, multiple concurrent cursor objects are needed, so that each can be assigned to process separate portions of the container elements. To allow this to happen we relax the above overlapping rule to say that a cursor is treated only as though it overlaps with the element in the container that it designates. So long as cursor operations are not applied to two or more cursors designating the same element of the container, concurrent calls to separate cursors of the same container object are possible. This allows various cursor manipulation subprograms (eg. Next, Previous, and Element), to be executed concurrently in parallel, since they only accept a single parameter.
For Vector containers, this still leaves us with the problem of obtaining the multiple cursors in the first place, since one normally would want to directly obtain the initial cursor for each chunk of the vector. The To_Cursor subprogram however has a parameter that is the container associated with the cursor to be generated, and thus still is considered to be an overlapping call if concurrent calls are applied to the same container object. We solve that by simply declaring otherwise.
Thus, To_Cursor can safely be called concurrently since its container parameter is said above to not overlap with any object including itself. Similarly, the Index parameter is not a problem for concurrent calls, since elementary types are passed by copy, according to 6.2(3/3). We do not believe that there is any implementation problem here, as To_Cursor should not need to write to the container or any other object.
The above allows parallel iteration of the containers but does not allow the container to be updated in parallel. For that we need to also allow the Replace_Element subprograms to be called concurrently. The Replace_Element subprograms have the same issue as To_Cursor in that they have a parameter that is the container containing the element that is to be replaced, and would ordinarily not be required to work if concurrent calls are applied to the same container object, since the container parameter would be overlapping. We address this with similar wording that was used for To_Cursor to declare that the container parameter does not overlap with anything.
For Vector containers, there is a Replace_Element variant that takes an Index instead of a cursor for a parameter. For that call, we need to specify that Index is considered to overlap with the element at that Index in the container, as otherwise two concurrent calls to Replace_Element for the same Index value would not conflict (requiring some sort of locking).
These changes allow Replace_Element for all the containers to safely be called concurrently, similarly to To_Cursor for Vector containers.
Containers that allow random access such as vectors are ideally suited for parallel processing, but other containers such as Doubly_Linked_Lists can still be processed in parallel. For those cases, it can be worthwhile if the amount of time needed to iterate through the container is small relative to the amount of time needed to process the elements in the container.
In this case, one thread of control can be used to sequentially iterate through the entire container, while other threads of execution can be started as the iterating thread reaches the next chunk of iterations to be processed in parallel. These parallel threads then iterate through their respective chunks applying the processing in parallel.
The subprograms Next, Previous, Element, and possibly Replace_Element are all that are needed for this type of parallel processing. With the exception of Replace_Element, these subprograms (for all the containers) have only a cursor parameter. Since they do not have a container parameter, and since cursors are considered to only overlap with the element they designate, these calls can be made concurrently as long as each of the concurrent calls designates a different element in the container. Overlapping might be considered a problem for the cursor object itself, but for parallel iteration through a container, separate cursor objects are expected to be used, as each cursor is an independent cursor that processes a mutually exclusive set of elements of the container concurrently, so overlapping of cursor objects does not need to be prevented for parallel iteration.
This AI provides the bare minimum to allow parallel processing of the container libraries. All other rules involving tampering and parameter overlapping still apply, which means that insertion or deletion from the container are not allowed while parallel operations to that container are occurring concurrently.
Note that for container updates, the only mechanism for parallel updates to the containers is via the Replace_Element calls. Other techniques such as use of Update_Element, or using generalized loop iteration (see 5.5.2) or user defined indexing (see 4.1.6) are not allowed, since they trigger tampering check processing that would cause failures unless these checks are suppressed. We would also have had to supply wording for these calls that mentioned that the container parameter did not overlap with anything, as we did for To_Cursor and the Replace_Element calls. Since Replace_Element provides a capability for parallel update of the containers, and because of the issues with the tampering checks of these other calls, it was decided to not support concurrent calls to these subprograms.
A full parallelism solution is needed for parallel loops and container iteration and usage, but that is expected to be covered by a different AI or set of AIs that deal with other issues such as eliminating data races.
This AI just allows some basic parallelism to occur with minimal impact to the standard.
!examples
As an example of usage for a Vector container, consider the problem of adding two vectors together to produce a result vector. Suppose a user defined parallelism library call exists with the following profile;
procedure Parallel_Loop
(From : Natural;
To : Natural; Process : not null access procedure (Start, Finish : Natural))
Where From and To identify the full range of iteration for the loop, and Process identifies a user supplied routine to process a separate "chunk" of loop iterations.
The following code fragment should compile and execute to generate the expected results.
declare
N : constant := 1_000_000;
subtype Loop_Index is Natural range 1 .. N;
package Integer_Vectors is new Ada.Containers.Vectors (Index_Type => Loop_Index, Element_Type => Integer);
Vector1, Vector2 : constant Integer_Vectors.Vector := Integer_Vectors.To_Vector (New_Item => 1, Length => Containers.Count_Type (N));
Result : Integer_Vectors.Vector := Integer_Vectors.To_Vector (Length => Containers.Count_Type (N));
procedure Process (Start, Finish : Parallel.Loop_Index) is begin for I in Start .. Finish loop Result (I) := Vector1 (I) + Vector2 (I); end loop; end Process;
begin Parallel_Loop (From => 1, To => N, Process => Process'access); end;
As an example of processing a Doubly_Linked_List in parallel, consider the problem of applying the same update to all elements in a linked list.
For this example, assume a different user defined library exists with the following profile;
generic type Cursor is private; procedure Generic_Parallel_Loop (From : Cursor; -- First Cursor of the container Iterations : Natural; Get_Cursor : not null access function (Position : Cursor; Offset : Positive) return Cursor; Process : not null access procedure (Iterations : Iteration_Count; Work_Item : in out Cursor));
From is passed a cursor corresponding to the first element in the container. Iterations identifes the number of elements in the container. The Get_Cursor function is a user supplied function that generates a new cursor as an offset from an existing cursor. The Process parameter identifies the user supplied processing that is to be applied to each element in the container.
declare package Integer_Lists is new Containers.Doubly_Linked_Lists (Element_Type => Integer);
procedure Parallel_Loop is new Generic_Parallel_Loop (Cursor => Integer_Lists.Cursor);
function Get_Cursor (Position : Integer_Lists.Cursor; Offset : Natural) return Integer_Lists.Cursor is New_Position : Integer_Lists.Cursor := Position; begin for I in 1 .. Offset loop New_Position := Integer_Lists.Next (New_Position); end loop;
return New_Position; end Get_Cursor;
Integer_List : Integer_Lists.List;
procedure Process (Iterations : Containers.Count_Type; Work_Item : in out Integer_Lists.Cursor) is begin for I in 1 .. Iterations loop Integer_List.Replace_Element ( Work_Item, Integer_Lists.Element (Work_Item) + 1); Integer_Lists.Next (Work_Item); end loop; end Process;
begin
List1.Append (New_Item => 1, Count => Containers.Count_Type (N));
Parallel_Loop (From => Integer_Lists.First, Iterations => N, Get_Cursor => Get_Cursor'access, Process => Process'access); end;
!corrigendum A.18(2/2)
Replace the paragraph:
A variety of sequence and associative containers are provided. Each container includes a cursor type. A cursor is a reference to an element within a container. Many operations on cursors are common to all of the containers. A cursor referencing an element in a container is considered to be overlapping with the container object itself.
by:
A variety of sequence and associative containers are provided. Each container includes a cursor type. A cursor is a reference to an element within a container. Many operations on cursors are common to all of the containers. A cursor referencing an element in a container is considered to be overlapping only with the element itself.
!corrigendum A.18.2(125/2)
Replace the paragraph:
If Index is not in the range First_Index (Container) .. Last_Index (Container), then No_Element is returned. Otherwise, a cursor designating the element at position Index in Container is returned.
by:
If Index is not in the range First_Index (Container) .. Last_Index (Container), then No_Element is returned. Otherwise, a cursor designating the element at position Index in Container is returned. For the purposes of determining whether the parameters overlap in a call to To_Cursor, the Container parameter is not considered to overlap with any object (including itself).
!corrigendum A.18.2(133/3)
Replace the paragraph:
If Index is not in the range First_Index (Container) .. Last_Index (Container), then Constraint_Error is propagated. Otherwise, Replace_Element assigns the value New_Item to the element at position Index. Any exception raised during the assignment is propagated. The element at position Index is not an empty element after successful call to Replace_Element.
by:
If Index is not in the range First_Index (Container) .. Last_Index (Container), then Constraint_Error is propagated. Otherwise, Replace_Element assigns the value New_Item to the element at position Index. Any exception raised during the assignment is propagated. The element at position Index is not an empty element after successful call to Replace_Element. For the purposes of determining whether the parameters overlap in a call to Replace_Element, the Container parameter is not considered to overlap with any object (including itself), and the Index parameter is considered to overlap with the element at position Index.
!corrigendum A.18.2(135/3)
Replace the paragraph:
If Position equals No_Element, then Constraint_Error is propagated; if Position does not designate an element in Container, then Program_Error is propagated. Otherwise, Replace_Element assigns New_Item to the element designated by Position. Any exception raised during the assignment is propagated. The element at Position is not an empty element after successful call to Replace_Element.
by:
If Position equals No_Element, then Constraint_Error is propagated; if Position does not designate an element in Container, then Program_Error is propagated. Otherwise, Replace_Element assigns New_Item to the element designated by Position. Any exception raised during the assignment is propagated. The element at Position is not an empty element after successful call to Replace_Element. For the purposes of determining whether the parameters overlap in a call to Replace_Element, the Container parameter is not considered to overlap with any object (including itself).
!corrigendum A.18.3(81/3)
Replace the paragraph:
If Position equals No_Element, then Constraint_Error is propagated; if Position does not designate an element in Container, then Program_Error is propagated. Otherwise, Replace_Element assigns the value New_Item to the element designated by Position.
by:
If Position equals No_Element, then Constraint_Error is propagated; if Position does not designate an element in Container, then Program_Error is propagated. Otherwise, Replace_Element assigns the value New_Item to the element designated by Position. For the purposes of determining whether the parameters overlap in a call to Replace_Element, the Container parameter is not considered to overlap with any object (including itself).
!corrigendum A.18.4(36/3)
Replace the paragraph:
If Position equals No_Element, then Constraint_Error is propagated; if Position does not designate an element in Container, then Program_Error is propagated. Otherwise, Replace_Element assigns New_Item to the element of the node designated by Position.
by:
If Position equals No_Element, then Constraint_Error is propagated; if Position does not designate an element in Container, then Program_Error is propagated. Otherwise, Replace_Element assigns New_Item to the element of the node designated by Position. For the purposes of determining whether the parameters overlap in a call to Replace_Element, the Container parameter is not considered to overlap with any object (including itself).
!corrigendum A.18.7(34/2)
Replace the paragraph:
If Position equals No_Element, then Constraint_Error is propagated; if Position does not designate an element in Container, then Program_Error is propagated. If an element equivalent to New_Item is already present in Container at a position other than Position, Program_Error is propagated. Otherwise, Replace_Element assigns New_Item to the element designated by Position. Any exception raised by the assignment is propagated.
by:
If Position equals No_Element, then Constraint_Error is propagated; if Position does not designate an element in Container, then Program_Error is propagated. If an element equivalent to New_Item is already present in Container at a position other than Position, Program_Error is propagated. Otherwise, Replace_Element assigns New_Item to the element designated by Position. Any exception raised by the assignment is propagated. For the purposes of determining whether the parameters overlap in a call to Replace_Element, the Container parameter is not considered to overlap with any object (including itself).
!corrigendum A.18.10(116/3)
Replace the paragraph:
If Position equals No_Element, then Constraint_Error is propagated; if Position does not designate an element in Container (including if it designates the root node), then Program_Error is propagated. Otherwise, Replace_Element assigns the value New_Item to the element designated by Position.
by:
If Position equals No_Element, then Constraint_Error is propagated; if Position does not designate an element in Container (including if it designates the root node), then Program_Error is propagated. Otherwise, Replace_Element assigns the value New_Item to the element designated by Position. For the purposes of determining whether the parameters overlap in a call to Replace_Element, the Container parameter is not considered to overlap with any object (including itself).
!ASIS
No impact.
!ACATS test
An ACATS C-Test can be constructed to check that parallel access works, but the probability of causing a problem is low.
!appendix

From: Brad Moore
Sent: Thursday, June 2, 2016  1:49 AM

My task was to look specifically at referencing separate elements of a container
in parallel. The example to consider is adding two Vectors element by element to
produce a third result vector.

I tried this with the GNAT implementation of Ada.Containers.Vectors, and found
that the issue shows itself during finalization of the container, as the
tampering counts get messed up which concurrent access, and should be zero when
the Vector is finalized but are not.

I found I could correct this issue, by wrapping the updates of these tampering
checks with lock-free atomic primitives.

Using a lock free compare and swap operation, provides the needed safety, while
introducing minimal overhead.

It this the sort of solution we are looking for?

Another idea would be to have a way to disable the tampering checks altogether
such as via an aspect or pragma.

Eg. pragma Suppress (Tamper_Check).

This would have the benefit of providing a faster implementation of containers,
which I recall was a concern raised in the past, but at the expense of safety.
This would also likely result in eliminating the finalization bug mentioned
above for concurrent access, since there would be no tampering flags to get
messed up, and otherwise the concurrent access seems to work fine for the
problem at hand.

Perhaps both solutions would be needed, the first provides better guarantees
that the tamper checks are working properly, for concurrent usage, and the
second allows more efficient processing when tampering is known not to occur in
the users code?

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

From: Randy Brukardt
Sent: Thursday, June 2, 2016  6:35 PM

I don't think the exact implementation is particularly relevant (other than to
provide a proof of concept). I trust implementers to figure that sort of thing
out. Especially as the Standard has no such thing as "tampering counts"; they
themselves are an implementation artifact.

What we do need, however, is to figure out what rules need to be changed in the
Standard in order to provide the needed operations. Which operations are those
exactly? Making everything task-safe is clearly too expensive (and seems like
overkill to me).

> Another idea would be to have a way to disable the tampering checks
> altogether such as via an aspect or pragma.
>
> Eg. pragma Suppress (Tamper_Check).

That idea was suggested long ago, supposedly is implemented in GNAT (I say
"supposedly" only because I've never had any reason to try it), and is currently
assigned to Bob Duff to write up. Ergo, it's hardly novel here, and probably
should only be mentioned in your write-up for completeness. (If Bob never
follows through, we can revisit it.)

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

From: Tucker Taft
Sent: Thursday, June 2, 2016  9:43 PM

> That idea was suggested long ago, supposedly is implemented in GNAT (I
> say "supposedly" only because I've never had any reason to try it),
> and is currently assigned to Bob Duff to write up.

Yes it is implemented.  The relevant Suppress identifiers are:

   Container_Checks
      -- controls all sorts of run-time checks on containers, including
      -- tampering
   Tampering_Check
      -- controls only the tampering check

If you suppress either one, the tampering checks are omitted.

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

From: Brad Moore
Sent: Friday, June 3, 2016 10:28 AM

Wow. That makes quite a difference!

(About 10 times faster for adding two Vectors of 100_000_000 integers for the
sequential case)

I also notice that the just released GNAT GPL version also fixed the problems I
was seeing with vector finalization for the parallel case caused by corruption
of the tampering counts.

I think these suppress pragmas were not available in last years GPL release.

Interesting, when I try to parallelize this, with tampering checks enabled, it
actually takes quite a bit longer than sequential. 1 min 6 seconds instead of 40
seconds. I believe this is because of all the locking needed to make the
tampering checks work correctly. (It appears GNAT is using lock free mechanisms
similar to the approach I described, but there is overhead with using these
locks when there is enough contention for the locks.

With tampering checks disabled however, and 4 cores, I see 4 times faster than
sequential. The run took 1 second instead of 4 seconds. (or 66 times faster for
the parallel case, when tampering checks are enabled. )

So it seems to me that the approach described in AI12-0139-1 of creating a copy
of the entire Ada libraries under a Ada.Protected parent package is unnecessary,
(at least to allow parallel usage of the containers) But we need the Suppress
pragmas to make parallelizing the containers worthwhile. Assuming Bob will
eventually write that part up, I will focus on a writeup that just says that the
containers should work for parallel processing.

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

From: Tucker Taft
Sent: Friday, June 3, 2016  10:36 AM

...
> (About 10 times faster for adding two Vectors of 100_000_000 integers
> for the sequential case) ...
> With tampering checks disabled however, and 4 cores, I see 4 times
> faster than sequential.
> The run took 1 second instead of 4 seconds. (or 66 times faster for
> the parallel case, when tampering checks are enabled. )

Glad to hear that!

> So it seems to me that the approach described in AI12-0139-1 of
> creating a copy of the entire Ada libraries under a Ada.Protected
> parent package is unnecessary, (at least to allow parallel usage of
> the
> containers) But we need the Suppress pragmas to make parallelizing the
> containers worthwhile. Assuming Bob will eventually write that part
> up, I will focus on a writeup that just says that the containers
> should work for parallel processing.

Sounds good.

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

From: Brad Moore
Sent: Friday, September 23, 2016  7:35 PM

Here is my homework for ai12-0196-1. [This is version /02 of the AI - Editor.]

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

From: Bob Duff
Sent: Monday, September 26, 2016  8:09 AM

Looks good.

Are things like First reentrant?  Do we need to say so?

> overlaps with the element in the container that it designates. So song 
> as
                                                                    ^^^^ "So long as"

> cursor operations are not applied to two or more cursors designating 
> the same

>       Parallel_Loop (From           => Integer.First,

Integer_List.First

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

From: Brad Moore
Sent: Monday, September 26, 2016  10:05 AM

> Are things like First reentrant?  Do we need to say so?

First/Last is not reentrant since it has a Container parameter, and also
because it is not needed for parallelism. For Vectors, To_Cursor would be used
to generate all the cursors from index values. Length would be called before
the parallelism to determine the chunk boundaries. For the other containers,
First (or Last) is used to obtain the initial cursor, but that is done
sequentially before the parallelism starts, and is not called again.

To add some basic parallelism capabilities to the containers, we only need
Next, Previous, Element, and To_Cursor to be reentrant.

We would really like calls like Replace to be reentrant as well, but I'm
thinking we would want to rely on the capabilities of another AI, such as
the Global aspects, to make this possible. I suppose we could just say that
Replace is reentrant, but it might be tricky to explain why or how it is.

I think it would probably be good to mention this, probably as an AARM note
or ramification.

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

From: Randy Brukardt
Sent: Monday, October 3, 2016  9:12 PM

Question: Is "reentrant" sufficiently defined to use it in the way that it is
used in A.18.2(125) here: "To_Cursor is reentrant."

A 3(4) sort of defines it, but I don't see how that definition is sufficient
to apply it as a subprogram requirement. After all, it says that all
language-defined subprograms are reentrant, so that would make the above
statement the null statement. I'm pretty sure that's not what we want.

My presumption from the meeting is that we were going to define the term
"reentrant subprogram" in some meaningful way and then we could apply that
to To_Cursor and any other subprograms that need it.

Perhaps an alternative would be to say that "for the purposes of determining
whether To_Cursor is required to be reenterant, the Container parameter is
considered to not overlap with any other object Redundant[even with itself]".
Since this seems to be the only place where you need to override the default
meaning of A 3(4).

---

I have to wonder if it would be better to define that all language-defined
functions with Global = null (what Brad mentions as a "pure function") are
fully reenterant. Then apply Global = null to To_Cursor and the other functions
in question. Maybe too radical.

---

OTOH, the decscription of To_Cursor is pretty simplistic. It says:

  To_Cursor however, is trivial to implement as a reentrant routine since it
  only needs to contruct an object that designates the container and contains
  an index to the vector. To_Cursor has no side effects, and is thus what we
  might call a pure function, if the language defined such a thing. We specify
  in the wording that this subprogram is reentrant to ensure that it can be
  safely called.

This assumes a very particular implementation of both cursors and To_Cursor.

First of all, a vector cursor needs to have some sort of reference to the
element, but it doesn't necessarily need to be the index of the element. It
could use a pointer at the element instead (Matt and I had a long discussion
on this point). This implementation would necessarily make To_Index more
expensive, but that could be implemented with an address calculation, and it
certainly would make element access by cursor cheaper. That's especially true
if the implementation choose a chunked allocation implementation rather than
allocating one large glob. (That would still meet the O(n) requirements if the
chunk size were fixed and it used a two-level index. Such an implementation
would be optimized for Vector expansion, which might be valuable in some
circumstances.) Also note that if both of these things are true, creating a
cursor will require reading data from the container object.

Similarly, the Janus/Ada cursors will include serial numbers used to detect
dangling cursors. Those serial numbers will need to be initialized from the
matching element in the vector -- so again To_Cursor will need to read the
container object. (Indeed, that is true for all cursor operations that create
a new cursor, including Next and Previous.)

We definitely don't want to prevent implementations like either of these. So
we need to be careful about what assumptions we make about the implementation.
(I could imagine To_Cursor having a side-effect; luckily neither of these
implementations do. It might be OK to ban such things, but we have to remember
that we're adding additional constraints on implementations, and ensure that
we're not throwing out the baby with the bathwater.)

At the very least, the discussion of To_Cursor shouldn't refer to any
particular implementation model, but rather discuss the abstract properties of
a cursor.

---

Since Next, Previous, and Element are all that is needed for this type of
parallel processing, which are now all defined to be reentrant, no container
specific wording is needed for these types of containers.

???

This statement seems like nonsense. You seem to have left out a bunch of steps!

You ought to explain why Next, et. al. are "now defined to be reentrant", since
there is no wording that does that and the logic needed to figure that out is
not obvious. (That is, say something about cursors no longer being overlapping,
so these functions are now required to be reenterant. The normative wording is
all about overlapping, after all.)

---


Typos: paragraph 5 of the discussion: "(eg. next, previous, and Elemen)," the
capitalization is wrong and a T is missing.

Bob had two typos as well.

I updated the AI fixing these typos after posting your original version.

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

From: Brad Moore
Sent: Monday, October 3, 2016  11:04 PM

>> Here is my homework for ai12-0196-1.
>
> Question: Is "reentrant" sufficiently defined to use it in the way 
> that it is used in A.18.2(125) here: "To_Cursor is reentrant."
>
> A 3(4) sort of defines it, but I don't see how that definition is 
> sufficient to apply it as a subprogram requirement. After all, it says 
> that all language-defined subprograms are reentrant, so that would 
> make the above statement the null statement. I'm pretty sure that's not what
> we want.

Good point!

> My presumption from the meeting is that we were going to define the 
> term "reentrant subprogram" in some meaningful way and then we could 
> apply that to To_Cursor and any other subprograms that need it.

I had something like that before in the previous version of the AI, where I
defined "concurrently callable" which was meant to be a label that could be
applied to indicate the reentrant properties of a subprogram.

> Perhaps an alternative would be to say that "for the purposes of 
> determining whether To_Cursor is required to be reenterant, the 
> Container parameter is considered to not overlap with any other object 
> Redundant[even with itself]". Since this seems to be the only place 
> where you need to override the default meaning of A 3(4).

This sounds like a better alternative to me. Especially since so far, it seems
this is the only place where this is needed. OTOH, if we want to identify many
other such subprograms, it will get annoying very quickly to have to repeat
this paragraph everywhere.

> ---
>
> I have to wonder if it would be better to define that all 
> language-defined functions with Global = null (what Brad mentions as a 
> "pure function") are fully reenterant. Then apply Global = null to 
> To_Cursor and the other functions in question. Maybe too radical.

I think Global = null would not be enough, as you'd want to also be able to
rely on "in" mode parameters not being modified using the Rosen technique.
Otherwise even though the function may be pure, it would not be safe to supply
the same object as a parameter in two concurrent calls.

> ---
>
> OTOH, the decscription of To_Cursor is pretty simplistic.
...
> At the very least, the discussion of To_Cursor shouldn't refer to any 
> particular implementation model, but rather discuss the abstract 
> properties of a cursor.

Agreed. With your proposed wording above, I think there is less of a need for
an explanation here.

How about replacing that paragraph with;

"To_Cursor can safely be called concurrently since its container parameter is
said above to not overlap with any object including itself. Similarly, the
Index parameter is not a problem for concurrent calls, since elementary types
are passed by copy, according to 6.2(3/3)"

> ---
>
> Since Next, Previous, and Element are all that is needed for this type 
> of parallel processing, which are now all defined to be reentrant, no 
> container specific wording is needed for these types of containers.
>
> ???
>
> This statement seems like nonsense. You seem to have left out a bunch 
> of steps!
>
> You ought to explain why Next, et. al. are "now defined to be 
> reentrant", since there is no wording that does that and the logic 
> needed to figure that out is not obvious. (That is, say something 
> about cursors no longer being overlapping, so these functions are now 
> required to be reenterant. The normative wording is all about 
> overlapping, after all.)

Ok, how about replacing that paragraph with;

"The functions and procedures Next, Previous, and Element for all the
containers have only a cursor parameter. Since they do not have a container
parameter, and since cursors are considered to only overlap with the element
they designate, these calls can be made concurrently as long as each of the
concurrent calls designates a different element in the container. Overlapping
might be considered a problem for the cursor object itself, but for parallel
iteration through a container, separate cursor objects are expected to be
used, as each cursor is an independent cursor that processes a mutually
exclusive set of elements of the container concurrently, so overlapping of
cursor objects does not need to be prevented for parallel iteration."

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

From: Randy Brukardt
Sent: Monday, October 3, 2016  9:12 PM

Thanks for the quick turnaround.

...
> > Perhaps an alternative would be to say that "for the purposes of 
> > determining whether To_Cursor is required to be reenterant, the 
> > Container parameter is considered to not overlap with any other 
> > object Redundant[even with itself]". Since this seems to be the only 
> > place where you need to override the default meaning of A 3(4).
> 
> This sounds like a better alternative to me. Especially since so far, 
> it seems this is the only place where this is needed.
> OTOH, if we want to identify many other such subprograms, it will get 
> annoying very quickly to have to repeat this paragraph everywhere.

OK, I made this change.

> ...
> > At the very least, the discussion of To_Cursor shouldn't refer to 
> > any particular implementation model, but rather discuss the abstract 
> > properties of a cursor.
> 
> Agreed. With your proposed wording above, I think there is less of a 
> need for an explanation here.
> 
> How about replacing that paragraph with;
> 
> "To_Cursor can safely be called concurrently since its container 
> parameter is said above to not overlap with any object including 
> itself.
> Similarly, the Index parameter is not a problem for concurrent calls, 
> since elementary types are passed by copy, according to 6.2(3/3)"

I tried that, but it reads weirdly as the previous paragraph said the opposite.
And it never said why this is OK (even in the abstract). So I made a couple of
changes to this suggestion and the preceding paragraph:

For Vector containers, this still leaves us with the problem of obtaining the
multiple cursors in the first place, since one normally would want to directly
obtain the initial cursor for each chunk of the vector. The To_Cursor
subprogram however has a parameter that is the container associated with the
cursor to be generated, and thus still is considered to be an overlapping call
that is not reentrant if concurrent calls are applied to the same container
object. We solve that by simply declaring otherwise.

Thus, To_Cursor can safely be called concurrently since its container parameter
is said above to not overlap with any object including itself.
Similarly, the Index parameter is not a problem for concurrent calls, since
elementary types are passed by copy, according to 6.2(3/3). We do not believe
that there is any implementation problem here, as To_Cursor should not need to
write to the container or any other object.


Hope this works!

...
> Ok, how about replacing that paragraph with;
> 
> "The functions and procedures Next, Previous, and Element for all the 
> containers have only a cursor parameter. Since they do not have a 
> container parameter, and since cursors are considered to only overlap 
> with the element they designate, these calls can be made concurrently 
> as long as each of the concurrent calls designates a different element 
> in the container. Overlapping might be considered a problem for the 
> cursor object itself, but for parallel iteration through a container, 
> separate cursor objects are expected to be used, as each cursor is an 
> independent cursor that processes a mutually exclusive set of elements 
> of the container concurrently, so overlapping of cursor objects does 
> not need to be prevented for parallel iteration."

Pretty good, but you lost the point about these routines being the only ones
needed for parallel processing. (That seems like a pretty important point!)

So I redid the first sentence of the paragraph:

The subprograms Next, Previous, and Element are all that are needed for this
type of parallel processing. These subprograms (for all the containers) have
only a cursor parameter. Since they do not have a container parameter, ...

I also put all of the wording into more standard format, which gets rid of
all of those quote marks. [This is version /04 of the AI - Editor.]

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

From: Brad Moore
Sent: Tuesday, October 4, 2016  9:52 AM

...
> Hope this works!

Looks good to me.

...
> I also put all of the wording into more standard format, which gets 
> rid of all of those quote marks.

This looks good also.
Thanks.

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

From: Brad Moore
Sent: Tuesday, October 4, 2016  10:39 AM

>>> Perhaps an alternative would be to say that "for the purposes of 
>>> determining whether To_Cursor is required to be reenterant, the 
>>> Container parameter is considered to not overlap with any other 
>>> object Redundant[even with itself]". Since this seems to be the only 
>>> place where you need to override the default meaning of A 3(4).

I'm wondering if we should also apply this paragraph to the Replace_Element
calls of all the containers. To do that though, we'd also have to say
something about suppressing the tampering checks for these calls. This
would allow us to update all the elements of a container in parallel
however. Eg. Increment each element of an Integer Vector.

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

From: Brad Moore
Sent: Tuesday, October 4, 2016  11:17 AM

Nevermind that, as having to suppress tampering checks is messy.
But we could apply to all the Update_Element calls. Those calls do not
involve tampering checks. If you like, I could resubmit with the wording
for that. 

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

From: Randy Brukardt
Sent: Tuesday, October 4, 2016  2:09 PM

There's two things here, and I suspect you have them confused.

Replace_Element is a tampering with elements operation (since the
discriminants/bounds/specific type can be changed with it) - so it makes a
tampering check when it starts, but it does not change the tampering state of
the container (which is the problematic operation). The latter isn'r necessary
because no tampering can happen while the call is in progress, at least not
without "overlapping calls", which is not required to work).

OTOH, Update_Element (and Reference) are not tampering operations (since the
discriminants/bounds/specific type cannot be changed with these), but these do
change the tampering state of the container. That's because one could call
(say) Insert on the container while doing the update (or using the reference),
and that would cause problems.

Tucker has proposed eliminating tampering with elements for definite
containers, but that won't change the requirement for the tampering check for
Update_Element (and Reference) -- it will just change it to "tampering with
cursors".

So I think your original thinking was correct (use Replace_Element here).

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

From: Brad Moore
Sent: Wednesday, October 5, 2016  2:05 AM

This is an update to this AI. [This is version /05 of this AI - Editor.]

It mostly provides wording to allow Replace_Element to be called concurrently
for all the containers.

I also added some more text to the discussion about how other mechanisms to
update containers such as via Update_Element, or Generalized Loop Iteration,
or User-Defined Indexing, or via calls to Reference are not supported, because
these mechanisms cause issues with the tampering checks.

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

From: Randy Brukardt
Sent: Wednesday, October 5, 2016  8:51 PM

> This is an update to this AI.

Sadly, you started with an old version of the AI with all of the previously
fixed typos and formatting issues. As such, I can't really tell what you did
or did not change, other than the following. (A file compare says that the
entire thing is different.)
 
> It mostly provides wording to allow Replace_Element to be called 
> concurrently for all the containers.
> 
> I also added some more text to the discussion about how other 
> mechanisms to update containers such as via Update_Element, or 
> Generalized Loop Iteration, or User-Defined Indexing, or via calls to 
> Reference are not supported, because these mechanisms cause issues 
> with the tampering checks.

Hopefully, I didn't lose anything important. Sorry.

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

From: Brad Moore
Sent: Friday, December 23, 2016  4:51 PM

> Letter Ballot to Approve AI12-0200-1/05:
...
> _X__ Reject AI
> 
> comments
> ___This will cause rework for AI 196, as it depends quite heavily on the
term "reentrant" as it was defined in this paragraph.
I think reentrant term will still be needed, at least by AI 196. If AI 196
can be resolved without defining the term Reentrant, then I approve, othewise,
I think we need to at least reintroduce the term to apply to the new
definition, so that it can simplify wording elsewhere in the RM.

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

From: Erhard Ploedereder
Sent: Friday, December 23, 2016  9:16 PM

> I think reentrant term will still be needed, at least by AI 196. If AI 
> 196 can be resolved without defining the term Reentrant, then I 
> approve, othewise, I think we need to at least reintroduce the term to 
> apply to the new definition, so that it can simplify wording elsewhere 
> in the RM.

Well, the old text did not exactly define the term either ("shall be reentrant
in the sense that << very special and even incompletely described case >>...")
and, even if you let that count as a definition, it is counter to the usual
definition of the term.

So, if a term needs to be invented, fine, but please not "reentrant" and please
no "in the sense that". "non-interfering" perhaps, or "race free".

E.g.

Two concurrent calls on any two (possibly the same) language-defined subprograms
are said to be race free if they perform as specified, as long as all pairs of
objects (one from each call) that are either denoted by parameters that could
be passed by reference, or are designated by parameters of an access type, are
nonoverlapping.

The implementation shall ensure that all concurrent calls on all
language-defined subprograms are race free.

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

From: Brad Moore
Sent: Friday, December 23, 2016  10:07 PM

> So, if a term needs to be invented, fine, but please not "reentrant" and
> please no "in the sense that". "non-interfering" perhaps, or "race free".
> 

I agree that reentrant is not the right word. I was just looking for some
label that we could refer to in other places. I wonder if "race free" might be
over-promising, that is, I'm not sure the definition guarantees that there are
no unprotected global variables being referenced by the subprogram. Maybe the
definition needs to be expanded to cover that case as well.

In the original version of AI 196, I had defined "concurrently-callable",
which we decided to get rid of, once we thought it could be replaced by the
"reentrant" definition we had. Now that reentrant is gone, maybe
concurrently-callable is another option to reconsider. "Non-interfering" also
seems like a reasonable choice.

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

From: Tucker Taft
Sent: Saturday, December 24, 2016  8:51 AM

I suspect Randy will be a bit annoyed you didn't mention this issue earlier!

As it is now, AI196 doesn't use "reentrant" in normative wording, so we don't
really need to define it in the RM.  On the other hand, I agree it might be
handy to have a word like "non-interfering" available for use, though at least
as far as AI196, we could define the term in an AARM annotation.

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

From: Brad Moore
Sent: Saturday, December 24, 2016  10:28 AM

> I suspect Randy will be a bit annoyed you didn't mention this issue 
> earlier!

I suspect so also, but I honestly didn't think of this until yesterday. 
I was about to approve. So probably the synapses would have fired sooner if I
hadn't procrastinated until now to put my X somewhere on the ballot.

But I think trying to apply a label to this is illuminating. Erhard's
suggestion to use "race-free" actually sounds like what we really want, but
that points out that we are missing some details in our definition about
also ensuring there are no modifications to unprotected global variables.

This seems useful also for amendment AI12-0079 on the global aspect, though
that is farther off in the future.

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

From: Randy Brukardt
Sent: Tuesday, December 27, 2016  9:40 PM

> I suspect Randy will be a bit annoyed you didn't mention this issue 
> earlier!

I would have been, but luckily his vote doesn't matter.

The vote was Approve (with or without changes): Baird, Barnes, Brukardt,
Burns, Cousins, Dismukes, Ploedereder, Rosen, Taft, and Vardanega.

Reject: Moore.

Abstain: Duff.

Thus we have a vote of 10-1-1. Given our new procedures, we require a majority
of the responding members (12 here) to vote for it (that would mean at least 7
approve votes in this case); and no more than 17% rejection votes (that's 2.04
votes in this case). All of these are clearly met, so this vote (to approve
AI12-0200-1) passes.
 
> As it is now, AI196 doesn't use "reentrant" in normative wording, so 
> we don't really need to define it in the RM.  On the other hand, I 
> agree it might be handy to have a word like "non-interfering" 
> available for use, though at least as far as AI196, we could define 
> the term in an AARM annotation.

Right, it just changes the AARM notes, which don't require any formal action.
And those notes really don't need a term, as it is primarily used to identify
the rules in question. The problem being that just identifying them as the
rules in A isn't very helpful. There's a reason that the drafting rules for
Standards do not allow text in places like the header of an Annex!
(And also why we never put any rules in such places except these rules in
Annex A.)

I guess it is a big editorial review update, but since nothing normative needs
to be changed, we don't need to vote on either of these again.

In any case, this is a problem with AI12-0196-1, not with AI12-0200-1, so
Brad's vote is misplaced. (I filed this thread on AI12-0196-1).

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

From: Randy Brukardt
Sent: Wednesday, December 27, 2016  8:51 PM

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

Questions? Ask the ACAA Technical Agent