Confusion (or bugs) regarding the 'UNORDERED' Collector Characteristic

[Stuart Marks]

On 10/27/17 1:56 PM, Chris Dennis wrote:
> I’m very confused about what was intended with the ‘UNORDERED’ Collector characteristic.  My logical inference was that unordered as a Collector characteristic meant that the result of this collector applied to any stream was independent of the order of element delivery.  This means that the stream backend could safely elide any ordered characteristic of the stream driving the collector and open up more possible execution pathways (parallelism for example).  The javadoc for unordered is two sentences:
> 
> /**
>   * Indicates that the collection operation does not commit to preserving
>   * the encounter order of input elements.  (This might be true if the
>   * result container has no intrinsic order, such as a {@link Set}.)
>   */
> 
> The first sentence makes sense, although it is phrased in a way that also explains the behavior seen if you flag an order sensitive collector as unordered.  The second sentence is weird, it implies a relation between collectors, encounter order, and an inherent ordering or iteration order of a collection object that might be the target of a collection. To me the important property of a Collection object with regards to ordering of a Collector that fills it is whether reordering the insertions to the collection can change the resultant state, for a Set this is clearly true since only the first presented element that is equal will be stored.

I think you need to be very careful making any assumptions about which of equal 
elements will end up in a set. Consider the spec of Set.addAll:

     Adds all of the elements in the specified collection to this set
     if they're not already present.

Suppose the source collection has several non-identical elements that are equal 
to each other. This says nothing about which of them is preserved, and indeed 
there is no mention whatsoever about the identity of equal objects. The entire 
Set spec is defined in terms of equals, not identity. So I think it's mistaken 
to assume that the first of equal but non-identical objects will be stored.

(This is also the reason I changed the specification of Set.copyOf in my recent 
draft, to remove the requirement that the first such element be preserved. 
Set.addAll and Collectors.toSet make no such stipulation.)

> There is also a paragraph in the Collector javadoc:
> 
> * <p>For collectors that do not have the {@code UNORDERED} characteristic,
> * two accumulated results {@code a1} and {@code a2} are equivalent if
> * {@code finisher.apply(a1).equals(finisher.apply(a2))}.  For unordered
> * collectors, equivalence is relaxed to allow for non-equality related to
> * differences in order.  (For example, an unordered collector that accumulated
> * elements to a {@code List} would consider two lists equivalent if they
> * contained the same elements, ignoring order.)
> 
> This seems weird, why would we try to define correctness of a parallel reduction against a collector that was sensitive to ordering.

This is indeed a bit odd, but it makes sense. You might have a collector that 
collects into a List, because you want to collect duplicates. But you might not 
actually care about the order; you just want all the elements. The fact that 
List stores elements in some order is irrelevant. In this case such a collector 
would quite reasonably have the UNORDERED characteristic.

> Finally, when investigating the properties of the collectors returned from the Collectors static factory I was surprised to discover that none of the collectors that are truly unordered were marked as such (counting, min, max, averaging, summing, summarizing), and the only collector that was marked as unordered was Collectors.toSet(), which although it is explicitly marked as unordered seems like it really shouldn’t be.
> 
> Whats going on here?  Which parts of all this are intended and which (if any) are bugs?

Well I think it does make sense for the toSet() collector to be UNORDERED. It 
may be the case, though, that other collectors are lacking the UNORDERED 
characteristic that they should have. That sounds like it might be a bug.

s'marks


> 
> Thanks in advance for any enlightenment,
> 
> Chris Dennis
> 
> P.S. Coincidentally the unordered toSet() collector works perfectly at the moment due to the happy interaction of the Spliterator.trySplit() contract and the folding/combining behavior of the stream implementations parallel reduction algorithm.
>