RFR 8014824: Document Spliterator characteristics and binding policy of java util collection impls

Paul Sandoz paul.sandoz at oracle.com
Mon Aug 12 09:17:36 UTC 2013

On Aug 9, 2013, at 9:01 PM, Mike Duigou <mike.duigou at oracle.com> wrote:
> On Aug 9 2013, at 06:04 , Paul Sandoz wrote:
>> Hi Peter,
>> On Aug 8, 2013, at 12:44 PM, Peter Levart <peter.levart at gmail.com> wrote:
>>> Hi Paul,
>>> Shouldn't Spliterators.EmptySpliterator also be IMMUTABLE, DISTINCT and ORDERED? Like Collections.singletonSpliterator...
>> Perhaps, for consistency. IIRC at the time it was felt a little odd to declare such characteristics when no elements are present.
> Not commenting on the specific decisions but to express general policy:
> For the empty/singleton cases it seems like the flags should match as close as possible those which would be found on a "real" collection used in the same context. The "specialness" of singleton/empty should be mostly for source efficiency and not alter the computation.

To be clear: computation may be altered (that is the why the characteristics are useful) but the results should be consistent. The characteristics allow for "wiggle room" to optimize.

This email thread promoted to me think a little more and while i don't think there is any issue spliterators of empty collections, there could be an issue with singletons when used with flatMap.

  Collections.singletonList(1).flatMap(x -> Stream.of(1, 2, 3)).parallel()...
  Collections.singleton(1).flatMap(x -> Stream.of(1, 2, 3)).parallel()...

The first stream should retain encounter order for 1 substituted for 1, 2, 3, where as the second stream does not have to. It just so happens the current flatMap implementation imputes order and thus preserves any order (elements are substituted sequentially at the leafs after splitting has occurred, which for this case is no splits).

The flatMap implementation could change to have better parallel performance, although it is currently hard to imagine it doing so at least for JDK 8. To be on the safe side the shared singleton implementation should report ORDERED (which it currently does), but this implies we will need to specify this for any shared use between singleton collections.

OK, i am gonna about turn on singletons, and keep things simple, and update the package private Collection.singletonSpliterator to take a characteristics parameter to ensure consistency with the collection type.

>> There are currently no type safe ways to obtain a singleton NavigableMap/SortedSet, but perhaps there could be in the future? (there was probably a good reason for not adding them with the empty versions but i dunno what that reason was).
> They weren't added mostly to keep the scope of adding the checked/unmodifiable/synchronized issue from being too involved. They could still be added.


>> Reporting SORTED for all singletons is problematic because the singleton element may not be Comparable.
> There's also the question of what to do when someone calls sort on it. There's an open question on whether Collections.sort should pre-check for size <= 1 and do nothing rather than throw UOE for Collections.singletonList(). It turns out most people find the UOE merely annoying and not useful. 


- Collections/Arrays.sort do not throw UOE and Collections.singletonList(...).sort(...) is a no-op.

- Collections.unmodifiableList(...).sort(...) throws a UOE.

In a hybrid world of the mutable and unmodifiable it is likely there will be subtle differences:


  List l = new ArrayList(Arrays.asList(1));


When can i have persistent collections in Java? :-)


More information about the core-libs-dev mailing list