RFR 8148115: Stream.findFirst for unordered source optimization

[Tagir F. Valeev]

Hello, Paul!

Thank you for review. I implemented it according to your suggestions,
here's issue:
https://bugs.openjdk.java.net/browse/JDK-8148115
And webrev:
http://cr.openjdk.java.net/~tvaleev/webrev/8148115/r1/

This patch required some changes in existing tests as FindFirstOpTest
asserted that findFirst() result must be equal to .iterator().next()
even if the source is HashSet. I extracted the relevant part of
FindAnyOpTest into assertContains(Optional, Iterator) method and
placed it into LambdaTestHelpers.

The corresponding changes in primitive tests are unnecessary, because
it seems that primitive data providers never produce unordered
streams. I can try to add unordered primitive sources and correct
these tests as well if it's necessary.

With best regards,
Tagir Valeev.


PS> Hi Tagir,

PS> Thanks for looking at this.

PS> I would prefer if a boolean was passed into the task constructor e.g.:

PS> @Override
PS> public <P_IN> O evaluateParallel(PipelineHelper<T> helper,
PS>                                  Spliterator<P_IN> spliterator) {
PS>     // This takes into account the upstream ops flags and the terminal
PS>     // op flags and therefore takes into account findFirst or findAny
PS>     boolean mustFindFirst =
PS> StreamOpFlag.ORDERED.isKnown(helper.getStreamAndOpFlags());
PS>     return new FindTask<>(this, mustFindFirst, helper, spliterator).invoke();
PS> }

PS> so we keep the flag evaluation logic within the evaluate method.

PS> Then change FindOp.mustFindFirst to be an int of the opFlags calculated in the constructor:

PS>   this.opFlags = StreamOpFlag.IS_SHORT_CIRCUIT | (mustFindFirst ? 0 : StreamOpFlag.NOT_ORDERED);

PS> Paul.

>> On 22 Jan 2016, at 07:19, Tagir F. Valeev <amaembo at gmail.com> wrote:
>> 
>> Hello!
>> 
>> Seems that currently Stream.findFirst is not optimized for unordered
>> source. I think it should work as findAny in this case. Here's a small
>> patch which fixes this:
>> 
>> http://cr.openjdk.java.net/~tvaleev/patches/findFirst/find_patch.txt
>> 
>> Simple JMH test:
>> http://cr.openjdk.java.net/~tvaleev/patches/findFirst/FindTest.java
>> 
>> Original:
>> http://cr.openjdk.java.net/~tvaleev/patches/findFirst/jmh_out_orig.txt
>> # JMH 1.11.2 (released 85 days ago)
>> # VM version: JDK 9-ea, VM 9-ea+99-2015-12-23-183325.javare.4146.nc
>> Benchmark                    Mode  Cnt      Score      Error  Units
>> FindTest.findAny             avgt   30  12439,631 ± 1787,866  us/op
>> FindTest.findAnyUnordered    avgt   30  12923,080 ± 1072,537  us/op
>> FindTest.findFirst           avgt   30  48047,467 ± 2713,489  us/op
>> FindTest.findFirstUnordered  avgt   30  52648,893 ± 3934,682  us/op
>> 
>> Patched:
>> http://cr.openjdk.java.net/~tvaleev/patches/findFirst/jmh_out_patched.txt
>> Benchmark                    Mode  Cnt      Score      Error  Units
>> FindTest.findAny             avgt   30  11312,238 ±  386,627  us/op
>> FindTest.findAnyUnordered    avgt   30  12136,953 ± 1536,817  us/op
>> FindTest.findFirst           avgt   30  47517,776 ± 2844,607  us/op
>> FindTest.findFirstUnordered  avgt   30  13147,492 ± 1140,592  us/op
>> 
>> If you think it's a reasonable thing to patch, I can log an issue,
>> generate webrev and check whether jtreg tests pass.
>> 
>> With best regards,
>> Tagir Valeev.
>>