Wording issue with reduction expressions involving empty subsequences

[sttaft]

Niklas Holsti provided this comment on the ARG website:

---

(This is a problem that I discussed in e-mail with Randy Brukardt in connection with the ISO WG9 meeting in October 2022. Randy suggested that I should write a bug report. Apologies for the delay in writing this bug report.)RM section 4.5.10 defines reduction expressions. The text in 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 [my emphasis], non-overlapping contiguous chunks (subsequences)".My problem is that as I understand the referenced text in 5.5, 5.5.1, and 5.5.2, the chunks/subsequences there generated can be empty. 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. Ditto for 5.5.2(10.3/5). 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". An empty subsequence has no "first value".

---

It seems to me that 4.5.10(27/5) should 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.

---

Niklas Holsti | niklas.holsti@tidorum.fi

12/26/2022 8:41:35

[ARG-Editor]

This issue is addressed in AI22-0069-1 (which will be available shortly).

[ARG-Editor]

After thinking about this a lot, I am proposing that this is a Ramification AI and that no normative wording be changed. I believe the existing wording is correct, if very subtle.

The key is the word "non-empty" in 4.5.10(21/5). This paragraph says that logical threads are assigned to each non-empty subsequence. Obviously, by this wording, logical threads are not assigned to any empty subsequences. And then the rest of the wording works so long as this fact is understood.

Of course, this should be clearer, so an AARM Note is suggested.

The purpose of parallel reductions is extra performance. So we don't want to write any overly specific rules that would require an implementation to add overhead. A literal implementation of Niklas' suggested changes would require a bitmap to know which local accumulators to reduce. But it might be easier to not generate logical threads at all for empty subsequences, or possibly the Reducer call could be part of the logical thread. We want implementers to use whatever works best in their environment, so the less we say the better.

                Randy.

[sttaft]

I think the problem is perhaps associated with filters, where we presumably don't actually evaluate a filter until after splitting a parallel iteration into subsequences, and then it is unclear what happens if no values pass the condition of the filter. For efficiency, I would expect that, in the presence of a filter, you would 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. 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.

So perhaps we should say something "normatively" about this situation...

The semantics are defined as they are to allow the "initial value" to not be an identity of the reduction operator, and that seems important to preserve. So we don't want to fall back to the initial value for the subsequences. So the wording Niklas proposes might be appropriate.

[sttaft]

AI22-0069-1 now incorporates some of the wording suggested in this issue:

https://docs.google.com/document/d/126XWToAuEWVlSNOnivcafJ8tzpEYSW2xQg-bJoB00NU

[ARG-Editor]

AI22-0069-1 is now ARG approved.