Improving Stream construction for java.util Collections

[Stefan Zobel]

The main substitutes for the missing Java 8 j.u.Collection#stream() method in this backport are the following static methods from j8.u.s.StreamSupport

1) public static <T> Stream<T> stream(Collection<? extends T> c)
2) public static <T> Stream<T> stream(Collection<? extends T> c, int characteristics)
3) public static <T> Stream<T> stream(Collection<? extends T> c, int characteristics, boolean parallel)

From these, 1) is the easiest to use.

As of release 1.0 all these methods always create a j.u.Collection#iterator() based Spliterator which is not invariably the most efficient road to follow.

Furthermore, in the case of method 1), the current code utilizes the Java 8 spliterator() default implementation from the j.u.Collection interface which doesn't supply any Spliterator characteristics. This is neither efficient nor even correct in all circumstances as the OpenJDK tests show (for some tests it was necessary to use method 2), supplying the correct characteristics manually, to meet the expected behavior).

Method 1) can be improved upon in at least 3 ways:

a) Check for known subinterfaces of j.u.Collection and use the corresponding Java 8 default implementation. This can be done for j.u.List, j.u.Set and j.u.SortedSet

b) Check for concrete Collection implementations where no access to the private implementation is needed and use the Java 8 spliterator() implementation for these classes. This is possible for j.u.LinkedHashSet and j.u.c.ArrayBlockingQueue

c) The "native" case where access to the private implementation is needed and specific Spliterator implementations are used in Java 8. This seems to be doable for at least the array-based Collections. Other Collections still need more investigation.

The plan for release 1.1 is to change the implementation of method 1) to first employ the strategies a) - c) and only then fallback to the current behavior if the passed Collection doesn't match one of these cases.

For case c), I expect it should be possible to support the following Collections "natively":

• j.u.ArrayList

• j.u.Arrays$ArrayList

• j.u.ArrayDeque

• j.u.PriorityQueue

• j.u.c.CopyOnWriteArrayList

• j.u.c.CopyOnWriteArraySet

• j.u.c.PriorityBlockingQueue

A future release (>= 1.2) may feature even more than these.

[Stefan Zobel]

PriorityBlockingQueue can also be done without access to private implementation details

[Stefan Zobel]

Additionally, "native" support for j.u.Vector has been added in 1.1-rc2

[Anonymous]

As of 1.1-rc3 all of the above mentioned specializations have been implemented.

[Stefan Zobel]

It should be noted that j.u.c.CopyOnWriteArrayList and j.u.c.CopyOnWriteArraySet are NOT late-binding as their Spliterators provide a snapshot of the state of the collection when the Spliterator was created (and that happens when the Stream is constructed).

To be clear: Java 8 exhibits the same behavior.

[Stefan Zobel]

The upcoming 1.1.3 release will add two more "native" specializations for

* j.u.c.LinkedBlockingQueue

* j.u.c.LinkedBlockingDeque

Furthermore, a new boolean system property 'java8.util.Spliterators.assume.oracle.collections.impl' will be introduced which allows to switch off the use of "native" (i.e. implementation-dependent) specializations.

This switch is provided for users on non-Sun/Oracle based JREs or for Android programmers to increase the odds that streamsupport may be running on their platform.

However, note that streamsupport will only be tested on Sun/Oracle 6, 7 and 8 JREs in the foreseeable future. For other platforms I rely on your feedback completely.

The switch will be assumed to be on by default (even if it's absent). To turn it off you have to explicitly specify the system property

java8.util.Spliterators.assume.oracle.collections.impl=false

[Almon B. Strowger]

Hey Stefan,

This is a great project, and I appreciate it a lot.
I'm experimenting with it on Android. I had some trouble at first with java
throwing an exception on build, but once I downgraded retrolambda to 1.7.0, it
started working. Glad you added the new property to allow non-oracle collections which
allows it to work on Android. Android has its own version of java.util.concurrent, its own
different version of sun.misc.Unsafe, so I won't try to use any parallel stream
and hope things continue to be okay.

Thanks for your efforts.

[Stefan Zobel]

Hi Almon,

thank you very much for your kind feedback.

I'm actually planning to add some "native" (reflection based) specialized Spliterator implementations for Android in the 1.1.4 release (ticket#15), disabling them altogether with said property is maybe a bit too brutal :-)

I'm aware of the differences in the Collections library (downloaded the Android SDK) - but I didn't see a sun.misc.Unsafe?

Can you tell me more about the differences compared to Sun's Java 6 version? Where can I have a look at the API definition (javadoc would be sufficient)?

Until recently, Android support wasn't on my radar at all - thus, no testing so far. But I hope to change that.

I have the OpenJDK TestNG test suite now as Java 6 jar file (backported manually and with the help of retrolambda, of course).
But still no clue on how to execute that on a Android device or an emulator. Do you have any ideas, tips or tricks?

[Stefan Zobel]

Yikes! I see. It's (Unsafe) in

https://android.googlesource.com/platform/libcore/+/master/libart/src/main/java/sun/misc/Unsafe.java

I've been blissfully ignorant. That's much worse than the Java 5 situation. Have to rethink my Android plans then ...

[Stefan Zobel]

On closer inspection there is only one method missing in the current master version of Android's Unsafe and this method can be replaced.

However, j8.u.c.ForkJoinWorkerThread does pose a real problem because of substantial implementation differences in java.lang.Thread.

[Almon B. Strowger]

Hey, I haven't looked at the code, but how did you get around the java.lang.Thread changes
required to run on a vanilla java 6 anyway? I would have figured that you already did
much of that heavy lifting in that regard already. Anyway--Maybe just forget about the
Fork/Join framework on Android versions prior to API 21/Lollipop? API 21 has its own
implementation of the Fork/Join framework anyway. Is it too much trouble to have
java8.util... use the Android versions of java.util.concurrent (or parts thereof) under the
hood when available and only use Fork/Join at all if Android's version is available?

[Stefan Zobel]

You are right, ForkJoinPool had a lot of dependencies on new Java 8 Thread class members. Those were replaced by ThreadLocals in TLRandom - not exactly rocket science.

As it turns out, ForkJoinWorkerThread poses no problems at all. The code in question is only used under circumstances that cannot arise on Android, namely when System.getSecurityManager() does NOT return null.

In fact, the current 1.1.4 snapshot already passes all tests in the OpenJDK test suite on a Nexus 5 API 21 AVD (5.0.1 x86_64) emulator. There are some problems on a Nexus 4 API 19 emulator though (stacksize too low for some tests and a Android JIT compiler bug, I guess).

I'm not sure if I'll be able to run all tests on a real device (because they require a lot of heap space). Anyway, I'll perhaps try that next weekend on a Lollipop quad-core tablet.

[Almon B. Strowger]

Awesome.

[Stefan Zobel]

Btw, using Android's Fork/Join would not be an option because it is more or less a kind of Java 7 Fork/Join. You'd have to replace the Java 7 F/J even when your target platform is Java 7.

[Almon B. Strowger]

Okay, so Android will be able to take advantage of some parallel processing?
Are you making a wrapper for sun.misc.Unsafe in UnsafeAccess to grab "THE_ONE",
etc?

[Stefan Zobel]

so Android will be able to take advantage of some parallel processing?

I hope so. The proof of the pudding is successfully running the tests on a real device where we are not constrained to a single core.

making a wrapper for sun.misc.Unsafe in UnsafeAccess to grab "THE_ONE"

That's not necessary. It's only a single usage of a write to a Boolean that can easily be replaced by an Integer. I haven't done that yet (doesn't get caught by the OpenJDK test) but it is easy.

[Almon B. Strowger]

Cool. How fortunate. Thanks.
Any guesstimate of when I can play w/ a 1.1.4? :)

[Stefan Zobel]

Depends on whether 1.1.4 will be a "improve Android support" release only - you Android fans could vote for that :-)

If yes, then February or March, not later.

[Stefan Zobel]

The upcoming 1.1.4 release will add only one additional "native" specialization for

• j.u.LinkedList

Furthermore, support for the Android platform has been incorporated into this release. The full set of available reflection-based Spliterator implementations will also be supported on Android. In addition, parallel streams should work just as well. However, note that Android developers should still set the "java8.util.Spliterators.assume.oracle.collections.impl" property to false for compatibility with future releases.

[Anonymous]

Seems like my recent post in Bugs forum is related to this post! Does this mean that from v1.1.4 I can use this library in my Android project? Is an artifact is already available?

[Stefan Zobel]

You can also use the 1.1.3 release with Android (but don't try to use parallel streams - they will only be supported from 1.1.4 onwards).

Just set

System.setProperty("java8.util.Spliterators.assume.oracle.collections.impl", "false");

to circumvent your problem.

1.1.4 will be released soon. Maybe this evening.

[Stefan Zobel]

Which Android (API) version do you use?

Might be that 1.1.3 will not work even when the above mentioned property is set. But 1.1.4 will.

[Anonymous]

I am using 21.1.1 version of API. With that property everything is working now! Thanks a lot.

[Stefan Zobel]

The current 1.1.5 release adds new "native" specializations for

j.u.HashSet  (Ticket#32)

and for the Collections (Ticket#30) returned from

j.u.HashMap#values()
j.u.HashMap#keySet()
j.u.HashMap#entrySet()

The new specializations will only be enabled on OpenJDK based JVMs (i.e., not on Android).

Furthermore, a new runtime feature has been added (Ticket#11) that allows the library to delegate to the internal Java 8 Spliterators for any Collection passed to the j8.u.s.StreamSupport methods

public static <T> Stream<T> stream(Collection<? extends T> c)
public static <T> Stream<T> parallelStream(Collection<? extends T> c)

This feature kicks in automatically whenever the library detects at runtime that it is running on a JRE that knows about the Stream API - i.e., for a Java 8 (or higher) VM. This feature can be disabled by setting the new property

"java8.util.Spliterators.jre.delegation.enabled"

to false.

Due to the introduction of the native specializations for Hash-based Collections Android developers are now absolutely required to set the flag

java8.util.Spliterators.assume.oracle.collections.impl=false

In addition, with that property set to false, the 1.1.5 release should now also work on IBM Java 6 / Java 7 JREs. It should work out of the box on IBM Java 8 (both, without setting any property - taking advantage of Spliterator delegation - and also with Spliterator delegation disabled).

As for additional "specializations" in the future I guess that is as good as it gets.

Though, while e.g. j.u.c.LinkedTransferQueue (for Java 7) could also be done, I believe it wouldn't carry its weight. The same probably holds for a #sublist() specialization that would also be possible.

In short: There are currently no plans to add anything further in this area.

[Anonymous]

Would it be possible to also add runtime detection for java8.util.Spliterators.assume.oracle.collections.impl=false? This would be very useful for android.