AI22-0069-1
!standard 4.5.10(21/5) 23-03-23 AI22-0069-1/01
!standard 4.5.10(27/5)
!standard 4.5.10(28/5)
!class ramification 23-03-23
!status work item 23-03-23
!status received 23-03-23
!priority Low
!difficulty Easy
!subject Empty subsequences in parallel reduction expressions
Empty chunks (subsequences) do not participate in parallel reduction expressions.
4.5.10(21/5) says, in the parallel case, that "the sequence of values is generated by a parallel iteration (as defined in 5.5, 5.5.1, and 5.5.2), as a set of non-empty, non-overlapping contiguous chunks (subsequences)".
However, nothing in the referenced subclauses prevents empty chunks. Specifically, 5.5.1(22/5) lets the First operation of a chunk return a cursor for which Has_Element is False, giving an empty subsequence. The wording in 5.5.2(10.3/5) expects empty subsequences.
But 4.5.10 does not say how to reduce an empty subsequence; 4.5.10(27/5) assumes that each subsequence has a "first value". We need to explain how empty subsequences work.
(See Summary.)
Add after AARM 4.5.10(21.a/5):
AARM Ramification: The word "non-empty" in the above wording is very important. It means that any empty chunks (subsequences) do not participate in the parallel reduction activity, and in particular do not participate in the Reducer step described below. Note that the description of the execution of each logical thread only makes sense for non-empty subsequences. Implementations must take care as nothing prevents empty subsequences from being generated by the iterator interfaces (and that will necessarily happen if the entire sequence is empty). Such subsequences need to be ignored somehow such that they have no effect on the result of the reduction.
It should be clear that it would be impractical to require user-written code to never return any empty subsequence. Moreover, if the entire set of values is empty, it's hard to see any alternative to returning an empty subsequence. So we have to assume that they could happen.
The author of the issue suggested that the fix would be for 4.5.10(27/5) to say that if a subsequence is empty, the corresponding logical thread completes without further actions, and 4.5.10(28/5) should apply Reducer only to the non-empty subsequences.
However, this suggestion causes an implementation issue, as one would need to keep around a bitmap or other means to determine which thread accumulators are ignored. That seems pretty expensive.
We believe that the answer to this question is much simpler (at least from a language perspective). Clearly, the inclusion of "non-empty" in 4.5.10(21/5) was intentional. If one presumes that the intent is in fact as specified, that any empty subsequences do not participate. Essentially, any such subsequences are discarded.
Thus, we conclude that the wording is correct as written, but an AARM ramification is suggested.
Doing so lets implementations determine for themselves how to handle the possibility of empty subsequences. An implementation could map the non-empty subsequences to a contiguous set of local accumulators (making the reduction easy), or it could map the subsequences directly to threads (and accumulators), allowing easier management of the threads but requiring the reduction step to be skipped for empty subsequences. We don't care how the ignoring of empty subsequences is implemented, so we want to specify as little as possible.
An ACATS C-Test should be constructed to check that empty chunks do not participate
in reductions. That could be accomplished by creating a user-defined iterator type that
returns multiple empty chunks interspersed with non-empty chunks.
This AI was created from GitHub issue #36 (https://github.com/Ada-Rapporteur-Group/User-Community-Input/issues/36).