RFR 8148115: Stream.findFirst for unordered source optimization

[Tagir F. Valeev]

Here's updated webrev:

http://cr.openjdk.java.net/~tvaleev/webrev/8148115/r2/

PS>  293             if (!this.mustFindFirst) {
PS>  310             if (this.mustFindFirst) {
PS> Small thing, no need for “this”.

Done.


PS> You can now use Optional.ifPresentOrElse, which was added in 9:

PS>   ifPresentOrElse(
PS>     t -> { …},
PS>     () -> assertFalse(it.hasNext()):

Done. I also added printing of the searched value if it's not found:

assertTrue(contained, "Not found: "+r);

Hopefully additional toString() and string concatenation does not eat
much time. Alternatively it could be rewritten as

if(!contained)
  fail("Not found: "+r);

PS> For primitive streams, you are correct there are no unordered
PS> providers of data. in certain cases unordered is induced e.g. forEach testing.

PS> A focused fix would be to exercise with say
PS> s.filter().unordered(), a more general fix would be as you say to
PS> add another provider for int, long and double (backed by say
PS> HashSet, or more simply/efficiently using unordered()).

PS> We have to carefully review that because that may increase test
PS> times. We don’t have to apply to all data sets, plus we could also
PS> refine the ref data sets too in that regard, thus keep the overall actions similar or even smaller.

PS> Shall we separate that in a new issue?

Yes, I guess it would be better to log a new issue. Though I don't
know how to formulate it correctly. "Add tests for unordered primitive
sources for Stream operations"? "Refine test data sets for Stream
API"? Probably it would be better if you open an issue by yourself :-)

With best regards,
Tagir Valeev.

PS> —

PS> I will take this and other patches (close/limit etc) you propose in bulk.

PS> Thanks,
PS> Paul.

>> On 23 Jan 2016, at 13:43, Tagir F. Valeev <amaembo at gmail.com> wrote:
>> 
>> 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.
>>>> 
>>