<html><body><div style="font-family: arial, helvetica, sans-serif; font-size: 12pt; color: #000000"><div><br></div><div><br></div><hr id="zwchr" data-marker="__DIVIDER__"><div data-marker="__HEADERS__"><blockquote style="border-left:2px solid #1010FF;margin-left:5px;padding-left:5px;color:#000;font-weight:normal;font-style:normal;text-decoration:none;font-family:Helvetica,Arial,sans-serif;font-size:12pt;"><b>From: </b>"Viktor Klang" <viktor.klang@oracle.com><br><b>To: </b>"Remi Forax" <forax@univ-mlv.fr>, "core-libs-dev" <core-libs-dev@openjdk.java.net><br><b>Sent: </b>Wednesday, January 17, 2024 8:48:07 PM<br><b>Subject: </b>Re: Gatherer: spliterator characteristics are not propagated<br></blockquote></div><div><style style="display:none;"> P {margin-top:0;margin-bottom:0;} </style></div><div data-marker="__QUOTED_TEXT__"><blockquote style="border-left:2px solid #1010FF;margin-left:5px;padding-left:5px;color:#000;font-weight:normal;font-style:normal;text-decoration:none;font-family:Helvetica,Arial,sans-serif;font-size:12pt;">
<div class="elementToProof" style="font-family: Aptos, Aptos_EmbeddedFont, Aptos_MSFontService, Calibri, Helvetica, sans-serif; font-size: 12pt; color: rgb(0, 0, 0);">
Hi Rémi,</div>
<div class="elementToProof" style="font-family: Aptos, Aptos_EmbeddedFont, Aptos_MSFontService, Calibri, Helvetica, sans-serif; font-size: 12pt; color: rgb(0, 0, 0);">
<br>
</div>
<div class="elementToProof"><span style="font-family: Aptos, Aptos_EmbeddedFont, Aptos_MSFontService, Calibri, Helvetica, sans-serif; font-size: 12pt; color: rgb(0, 0, 0);">You can find some of my benches here:
</span><span style="font-family: Aptos, Aptos_EmbeddedFont, Aptos_MSFontService, Calibri, Helvetica, sans-serif; font-size: 12pt; color: rgb(0, 0, 0);"><a href="https://github.com/openjdk/jdk/tree/master/test/micro/org/openjdk/bench/java/util/stream/ops/ref" id="LPlnk435534" target="_blank">https://github.com/openjdk/jdk/tree/master/test/micro/org/openjdk/bench/java/util/stream/ops/ref</a></span><br data-mce-bogus="1"></div>
<div class="elementToProof" style="font-family: Aptos, Aptos_EmbeddedFont, Aptos_MSFontService, Calibri, Helvetica, sans-serif; font-size: 12pt; color: rgb(0, 0, 0);">
<br>
</div>
<div class="elementToProof" style="font-family: Aptos, Aptos_EmbeddedFont, Aptos_MSFontService, Calibri, Helvetica, sans-serif; font-size: 12pt; color: rgb(0, 0, 0);">
Initially I had Characteristics such as ORDERED etc on Gatherer but it just didn't end up worth it when looking at the bench results over a wide array of stream sizes and number of operations.</div></blockquote><div><br></div><div>I think there are 3 gatherer characteristics that make sense: KEEP_SORTED, KEEP_DISTINCT and KEEP_SIZED,<br data-mce-bogus="1"></div><div>all of them say that if the stream was sorted/distinct/sized then the stream returned by a call to gather() is still sorted (with the same comparator), distinct or sized.<br data-mce-bogus="1"></div><div><br data-mce-bogus="1"></div><div>As examples, map() is KEEP_SIZED, filter() is KEEP_SORTED | KEEP_DISTINCT and windowFixed is KEEP_DISTINCT.<br data-mce-bogus="1"></div><div><br data-mce-bogus="1"></div><div>[CC Paul, so he can correct me if i'm saying something stupid]<br data-mce-bogus="1"></div><div><br data-mce-bogus="1"></div><div>Now for the benchmarks, it depends what you want to measure, benchmarking streams is tricky. This is what i know about benchmarking streams.</div><div>First, the JIT has two ways to profile types at runtime,<br data-mce-bogus="1"></div><div>Either a method takes a function as parameter<br data-mce-bogus="1"></div><div> void map(Function function) {<br data-mce-bogus="1"></div><div> function.apply(...)<br data-mce-bogus="1"></div><div> }<br data-mce-bogus="1"></div><div>and when map is called with a subtype of Function, the JIT will propagate the exact type when map is inlined,<br data-mce-bogus="1"></div><div>Or a method use a field<br data-mce-bogus="1"></div><div> class Op {<br data-mce-bogus="1"></div><div> Function function;<br data-mce-bogus="1"></div><div><br data-mce-bogus="1"></div><div> void map() {<br data-mce-bogus="1"></div><div> function.apply(...)<br data-mce-bogus="1"></div><div> }<br data-mce-bogus="1"></div><div> }<br data-mce-bogus="1"></div><div>in that case, the VM records the profile of function.apply() and if there are more than two different profiles, the VM declare profile poluttion and do not try to optimize.<br data-mce-bogus="1"></div><div><br data-mce-bogus="1"></div><div>The Stream implementation tries very hard to use only parameters instead of fields, that's why it does not use classical Iterator that are pull iterator (a filter iterator requires a field) but a Spliterator which is a push iterator, the element is sent as parameter of the consumer.That's also why collect does not use the builder pattern (that accumulate values in fields) but a Collector that publish the functions to be called as parameter.<br data-mce-bogus="1"></div><div><br data-mce-bogus="1"></div><div>Obvisously, this is more complex than that, a Collector stores the functions in fields so it should not work well but the implementation uses a record that plays well with escape analysis. Escape analysis see the fields of an instance as parameters so the functions of a Collector are correctly propagated (if the escape analysis works). And lambdas are using invokedynamic, and the VM tries really hard to inline invokedynamic, so lambdas (that captures value or not) are routinely fully inlined with the intermediate operation of a stream.</div><div><br data-mce-bogus="1"></div><div>In your tests, i've not seen comparaisons between an existing method like map() or filter() followed by a sorted()/distinct()/count()/toList(), i.e. operations where the characteristics KEEP_* have an impact and their equivalent using a Gatherer.<br data-mce-bogus="1"></div><div><br data-mce-bogus="1"></div><blockquote style="border-left:2px solid #1010FF;margin-left:5px;padding-left:5px;color:#000;font-weight:normal;font-style:normal;text-decoration:none;font-family:Helvetica,Arial,sans-serif;font-size:12pt;"><div class="elementToProof" style="font-family: Aptos, Aptos_EmbeddedFont, Aptos_MSFontService, Calibri, Helvetica, sans-serif; font-size: 12pt; color: rgb(0, 0, 0);"><br>
</div>
<div class="elementToProof" style="font-family: Aptos, Aptos_EmbeddedFont, Aptos_MSFontService, Calibri, Helvetica, sans-serif; font-size: 12pt; color: rgb(0, 0, 0);">
<br>
</div>
<div id="Signature">
<div style="font-family: Calibri, Arial, Helvetica, sans-serif; font-size: 12pt; color: rgb(0, 0, 0);">
Cheers,<br>
√</div></div></blockquote><div><br></div><div>regards,<br data-mce-bogus="1"></div><div>Rémi<br data-mce-bogus="1"></div><div><br data-mce-bogus="1"></div><blockquote style="border-left:2px solid #1010FF;margin-left:5px;padding-left:5px;color:#000;font-weight:normal;font-style:normal;text-decoration:none;font-family:Helvetica,Arial,sans-serif;font-size:12pt;"><div id="Signature">
<div style="font-family: Calibri, Arial, Helvetica, sans-serif; font-size: 12pt; color: rgb(0, 0, 0);">
<br>
</div>
<div style="font-family: Calibri, Arial, Helvetica, sans-serif; font-size: 12pt; color: rgb(0, 0, 0);">
<b><br></b></div>
<div style="font-family: Calibri, Arial, Helvetica, sans-serif; font-size: 12pt; color: rgb(0, 0, 0);">
<b>Viktor Klang</b></div>
<div style="font-family: Calibri, Arial, Helvetica, sans-serif; font-size: 12pt; color: rgb(0, 0, 0);">
Software Architect, Java Platform Group<br>
Oracle</div>
</div>
<hr style="display:inline-block;width:98%">
<div id="divRplyFwdMsg" dir="ltr"><font face="Calibri, sans-serif" style="font-size:11pt" color="#000000"><b>From:</b> core-libs-dev <core-libs-dev-retn@openjdk.org> on behalf of Remi Forax <forax@univ-mlv.fr><br><b>Sent:</b> Wednesday, 17 January 2024 16:48<br><b>To:</b> core-libs-dev <core-libs-dev@openjdk.java.net><br><b>Subject:</b> Gatherer: spliterator characteristics are not propagated</font>
<div> </div>
</div>
<div class="BodyFragment"><font size="2"><span style="font-size:11pt;"><div class="PlainText">While doing some benchmarking of the Gatherer API, i've found that the characteristics of the spliterator was not propagated by the method Stream.gather() making the stream slower than it should.<br>
<br>
As an example, there is no way when reimplementing map() using a Gatherer to say that this intermediate operation keep the size, which is important if the terminal operation is toList() because if the size is known, toList() will presize the List and avoid
the creation of an intermediary ArrayList.<br>
<br>
See <a href="https://github.com/forax/we_are_all_to_gather/blob/master/src/main/java/com/gihtub/forax/wearealltogather/bench/MapGathererBenchmark.java" target="_blank">
https://github.com/forax/we_are_all_to_gather/blob/master/src/main/java/com/gihtub/forax/wearealltogather/bench/MapGathererBenchmark.java</a><br>
<br>
I think that adding a way to propagate the spliterator characteristics through a Gatherer would greatly improve the performance of commons streams (at least all the ones that end with a call to toList).<br>
<br>
I have some idea of how to do that, but I prefer first to hear if i've overlook something and if improving the performance is something worth changing the API.<br>
<br>
regards,<br>
Rémi<br>
</div></span></font></div><br></blockquote></div></div></body></html>