CVS difference for ai22s/ai22-0069-1.html

Differences between 1.2 and version 1.3
Log of other versions for file ai22s/ai22-0069-1.html

--- ai22s/ai22-0069-1.html	2023/03/24 08:00:50	1.2
+++ ai22s/ai22-0069-1.html	2023/06/06 06:07:33	1.3
@@ -1,7 +1,7 @@
-<html><head><meta content="text/html; charset=UTF-8" http-equiv="content-type"><title>AI22-0069-1/01</title>
+<html><head><meta content="text/html; charset=UTF-8" http-equiv="content-type"><title>AI22-0069-1/02</title>
 <style type="text/css">
 table td,table th{padding:0}
-.c13{color:inherit;text-decoration:inherit}
+.c17{color:inherit;text-decoration:inherit}
 BODY.body{background-color:#ffffff; max-width:468pt; padding:72pt 72pt 72pt 72pt}
 P.head{margin-bottom:0; margin-top:0; margin-left:0; margin-right:0; padding-top:0pt; color:#000000; font-size:14pt; padding-bottom:0pt; font-family:"Arial","Liberation Sans",sans-serif; line-height:1.15; orphans:2; widows:2; text-align:left; font-weight:
400; text-decoration:none; vertical-align:baseline; font-style:normal}
 H2.head{margin-bottom:0; margin-top:0; margin-left:0; margin-right:0; padding-top:12pt; color:#000000; font-size:14pt; padding-bottom:6pt; font-family:"Arial","Liberation Sans",sans-serif; line-height:1.15; page-break-after:avoid; orphans:2; widows:2; tex
t-align:left; font-weight:400; text-decoration:none; vertical-align:baseline; font-style:normal}
@@ -9,13 +9,16 @@
 P.word{margin-bottom:0; margin-top:0; margin-left:36pt; margin-right:0; padding-top:0pt; color:#000000; font-size:11pt; padding-bottom:3pt; font-family:"Times New Roman","Times",serif; line-height:1.15; orphans:2; widows:2; text-align:left; font-weight:40
0; text-decoration:none; vertical-align:baseline; font-style:normal}
 P.text{margin-bottom:0; margin-top:0; margin-left:0; margin-right:0; padding-top:0pt; color:#000000; font-size:11pt; padding-bottom:0pt; font-family:"Arial","Liberation Sans",sans-serif; line-height:1.15; text-align:left; font-weight:400; text-decoration:
none; vertical-align:baseline; font-style:normal}
 P.txts{margin-bottom:0; margin-top:0; margin-left:0; margin-right:0; padding-top:0pt; color:#000000; font-size:11pt; padding-bottom:11pt; font-family:"Arial","Liberation Sans",sans-serif; line-height:1.15; text-align:left; font-weight:400; text-decoration
:none; vertical-align:baseline; font-style:normal}
-P.l3h{margin-bottom:0; margin-top:0; margin-left:0; margin-right:0;color:#000000;font-size:26pt;font-family:"Arial","Liberation Sans",sans-serif; padding-top:0pt; padding-bottom:3pt; line-height:1.15; page-break-after:avoid; orphans:2; widows:2; text-alig
n:left; font-weight:400; text-decoration:none; vertical-align:baseline; font-style:normal}
+SPAN.ins{color:#007700}
+SPAN.del{color:#cc8888}
+SPAN.ntrm{font-family:"Arial","Liberation Sans",sans-serif}
+P.jxz{margin-bottom:0; margin-top:0; margin-left:0; margin-right:0;color:#000000;font-size:26pt;font-family:"Arial","Liberation Sans",sans-serif; padding-top:0pt; padding-bottom:3pt; line-height:1.15; page-break-after:avoid; orphans:2; widows:2; text-alig
n:left; text-decoration:none; vertical-align:baseline; font-style:normal; font-weight:400}
 SPAN.g6p{text-decoration-skip-ink:none; -webkit-text-decoration-skip:none; color:#1155cc; text-decoration:underline}
 </style>
-</head><body class="body"><p class="l3h">AI22-0069-1</p>
+</head><body class="body"><p class="jxz">AI22-0069-1</p>
 <p class="head">!standard 4.5.10(21/5) &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp;
 &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp;
-&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;23-03-23 &nbsp;AI22-0069-1/01</p>
+&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;23-05-29 &nbsp;AI22-0069-1/02</p>
 <p class="head">!standard 4.5.10(27/5)</p>
 <p class="head">!standard 4.5.10(28/5)</p>
 <p class="head">!class ramification 23-03-23</p>
@@ -36,57 +39,74 @@
 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.</p>
 
+<p class="txts">In addition, empty subsequences can be produced in the presence of an
+iterator_filter, presuming that the overall sequence might be split up into subsequences
+<i>before</i> applying the filter, so that the filter computation can be performed in parallel.</p>
+
 <p class="text">But 4.5.10 does not say how to reduce an empty subsequence; 4.5.10(27/5) assumes
 that each subsequence has a &quot;first value&quot;. We need to explain how empty subsequences
 work.</p>
 <h2 class="head">!recommendation</h2>
 <p class="text">(See Summary.)</p>
 <h2 class="head">!wording</h2>
-<p class="inst">Add after AARM 4.5.10(21.a/5):</p>
-<p class="word">AARM Ramification: The word &quot;non-empty&quot; 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.</p>
+<p class="inst">Modify 4.5.1(21/5):</p>
+<p class="word">If the <span class="ntrm">value_sequence</span> does not have the reserved word
+<b>parallel</b>, it is produced as a single sequence of values by a single logical thread of
+control. If the reserved word <b>parallel</b> is present in the<span class="ntrm">
+</span><span class="ntrm">value_sequence</span>, the enclosing
+<span class="ntrm">reduction_attribute_reference</span> is a parallel construct, and 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
+<span class="del">[non-empty,]</span> non-overlapping contiguous chunks (<i>subsequences</i>) with
+one logical thread of control (see Clause 9) associated with each subsequence. If there is a
+<span class="ntrm">chunk_specification</span>, it determines the maximum number of chunks, as
+defined in 5.5; otherwise the maximum number of chunks is implementation defined.</p>
+<p class="inst">Modify 4.5.10(27/5):</p>
+<p class="word">Each logical thread of control creates a local accumulator for processing its
+subsequence. The accumulator for a subsequence is initialized to the first value
+<span class="ins">{conditionally produced for}</span> <span class="del">[of]</span> the
+subsequence<span class="ins">{, if any}</span>, and calls on Reducer start with the second value of
+the subsequence (if any). The result for the subsequence<span class="ins">{, if non-empty,}</span>
+is the final value of its local accumulator.</p>
+<p class="inst">Modify 4.5.10(28/5):</p>
+<p class="word">After all logical threads of control of a parallel reduction expression have
+completed, Reducer is called for each <span class="ins">{non-empty}</span>
+subsequence<span class="ins">{, if any}</span>, in the original sequence order, passing the local
+accumulator for that subsequence as the second (Value) parameter, and the overall accumulator
+<span class="del">[(initialized above to the initial value)]</span> as the first (Accumulator)
+parameter, with the result saved back in the overall accumulator. The parallel reduction expression
+yields the final value of the overall accumulator.</p>
 <h2 class="head">!discussion</h2>
 <p class="txts">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&#39;s hard
 to see any alternative to returning an empty subsequence. So we have to assume that they could
-happen.</p>
+happen. </p>
 
-<p class="txts">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.</p>
+<p class="txts">Filters, in particular, can result in empty subsequences, because we presumably
+don&#39;t actually evaluate a filter until <i>after</i> splitting a parallel iteration into
+subsequences, and then it is quite possible that no values pass the condition of the filter. The
+semantics of parallel reduction are defined as they are to allow the &quot;initial value&quot; to
+not be an identity of the reduction operator, and that seems important to preserve. So we don&#39;t
+want to fall back to the initial value for the subsequences.</p>
+
+<p class="txts">So for efficiency in the presence of a filter, you might want to have two loops,
+the first would be to find the first element that passes the filter, to use to initialize the
+accumulator, and then the second loop would combine any further elements that pass the filter into
+that accumulator, calling the Reduce operation with each one. If the first loop ends without
+finding a value that satisfies the filter condition, then that chunk needs to be omitted from the
+final reduction pass.</p>
 
-<p class="txts">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.</p>
-
-<p class="txts">We believe that the answer to this question is much simpler (at least from a
-language perspective). Clearly, the inclusion of &quot;non-empty&quot; 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.</p>
-
-<p class="txts">Thus, we conclude that the wording is correct as written, but an AARM ramification
-is suggested.</p>
-
-<p class="text">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&#39;t care how the ignoring of empty
-subsequences is implemented, so we want to specify as little as possible.</p>
+<p class="text">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. We have followed that
+suggestion above.</p>
 <h2 class="head">!ACATS test</h2>
 <p class="text">An ACATS C-Test should be constructed to check that empty chunks do not
 participate</p>
-<p class="text">in reductions. That could be accomplished by creating a user-defined iterator type
-that</p>
-<p class="text">returns multiple empty chunks interspersed with non-empty chunks.</p>
+<p class="text">in reductions. That could be accomplished by defining a filter that excludes most
+of the elements, such that one or more of the subsequences end up empty, after applying the
+filter.</p>
 <h2 class="head">!appendix</h2>
 <p class="txts">This AI was created from GitHub issue #36
-(<span class="g6p"><a class="c13" href="https://github.com/Ada-Rapporteur-Group/User-Community-Input/issues/36">https://github.com/Ada-Rapporteur-Group/User-Community-Input/issues/36</a></span>).</p>
+(<span class="g6p"><a class="c17" href="https://github.com/Ada-Rapporteur-Group/User-Community-Input/issues/36">https://github.com/Ada-Rapporteur-Group/User-Community-Input/issues/36</a></span>).</p>
 
 </body></html> 

Questions? Ask the ACAA Technical Agent