RFR: 8223504: improve performance of forall loops by better inlining of "iterator()" methods.

[Vladimir Ivanov]

Thanks for the thorough explanation, Sergey.

What I like about the patch you propose is its simplicity.

More accurate heuristic which takes inlining effects into account (e.g., 
on EA) would scale to a much wider range of use cases and C2 has a rich 
toolkit to make such heuristic possible, but it would definitely require 
more effort.

Thinking about it for a while, I agree with your proposal: the heuristic 
is acceptable for the case of iterators, the benefits are evident, and 
risks (with overinlining and premature inlining) are low.

I still hope there'll be a more generic solution available at some point 
which will supersede such special case for Iterable.

Regarding the check itself, I'm in favor of limiting it 
toIterable::iterator() overrides/overloads, but I'm OK with a more 
generic check on return type.

Best regards,
Vladimir Ivanov

On 10/05/2019 21:47, Sergey Kuksenko wrote:
> Let me do a broader description.
> 
> When hotspot makes a decision to the "ultimate question compilation, 
> optimization and everything"  inline or not inline there are two key 
> part of that decision. It is check of sizes (callee and caller) and 
> check of frequencies (invocation count). Frequency check is reasonable, 
> why should we inline rarely invoked method? But sometimes we loose 
> optimization opportunities with that.
> 
> Let's narrow the scenario. We have a loop and a method invocation before 
> the loop. Inline of the method is a vital  for the loop performance. I 
> see at least two key optimizations here: constant propagation and scalar 
> replacement, maybe more. But if the loop has large enough amount of 
> iterations -> hotspot has large enough backedge counters -> but it means 
> that prolog is considered as relatively cold code (small amount of 
> invocation counter) -> that method (potentially vital for performance) 
> is not inlined (due to frequency/MinInlineThreashold cut off).
> 
> We can't say if inlining is important until we look into the loop (even 
> if there is a loop there). But we have to make a decision about inline 
> before that. So let's try to make reasonable heuristic and narrow the 
> scenario again. Limit our sight to Iterators. There is a very high 
> probability that after Iterable::iterator() invocation there is a loop 
> (covers all for-all loop). Also there is a high correlation between 
> collection size and amount of loop iterations. Let's inline all 
> iterators. I don't think the idea to analyze if "returned Iterator is a 
> freshly-allocated instance" makes sense. First of all it's unnecessary 
> complication.  Moreover, I have results when we have chain of iterators, 
> hotspot can't inline the whole chain due to absence of profile (and/or 
> profile pollution), but partial inline of the chain have shown 
> performance benefits. To get more effective prediction if that 
> particular inline is important we should look not into the method, but 
> to the usage of the method results (into the loop).
> 
> About the first comment (to broad or to narrow check). I have to note 
> that this fix doesn't force inline for all methods with "iterator" name. 
> The fix only excludes frequency cut off. All other checks (by sizes) are 
> still in place. I did broader check for two reasons: to simplify 
> modifications and to have wider appliances when it works. I could narrow 
> it if you insist, but at the same time I think we have to make that 
> check broader - don't look into method name at all. If you have 
> something  that returns Iterator - there will be loop after that with a 
> very high probability. So I'd vote for making that wider - check only 
> return type.
> 
> On 5/8/19 3:10 PM, Vladimir Ivanov wrote:
>>> http://cr.openjdk.java.net/~skuksenko/hotspot/8223504/webrev.01/
>> returned Iterator is a freshly-allocated instance
>> src/hotspot/share/opto/bytecodeInfo.cpp:
>>
>> +  if (callee_method->name() == ciSymbol::iterator_name()) {
>> +    if 
>> (callee_method->signature()->return_type()->is_subtype_of(C->env()->Iterator_klass())) 
>> {
>> +      return true;
>> +    }
>> +  }
>>
>> The check looks too broad for me: it returns true for any method with 
>> a name "iterator" which returns an instance of Iterator which is much 
>> broader that just overrides/overloads of Iterable::iterator().
>>
>> Can you elaborate, please, why did you decide to extend the check for 
>> non-Iterables?
>>
>> Commenting on the general approach, it looks like a good candidate for 
>> a fist-line filter before performing a more extensive analysis. I'd 
>> prefer to see BCEscapeAnalyzer extended to determine that returned 
>> Iterator is a freshly-allocated instance and decide whether to inline 
>> or not based on that instead. Among java.util classes you mentioned 
>> most iterators are trivial, so even naive analysis should get decent 
>> results.
>>
>> And then the analysis can be applied to any method which returns an 
>> Object to see whether EA may benefit from inlining.
>>
>> What do you think?
>>
>> Best regards,
>> Vladimir Ivanov
>>
>>> On 5/7/19 11:56 AM, Aleksey Shipilev wrote:
>>>> On 5/7/19 8:39 PM, Sergey Kuksenko wrote:
>>>>> Hi All,
>>>>>
>>>>> I would like to ask for review the following change/update:
>>>>>
>>>>> https://bugs.openjdk.java.net/browse/JDK-8223504
>>>>>
>>>>> http://cr.openjdk.java.net/~skuksenko/hotspot/8223504/webrev.00/
>>>> The idea sounds fine.
>>>>
>>>> Nits (the usual drill):
>>>>
>>>>   *) Copyright years need to be updated, at least in bytecodeInfo.cpp
>>>>
>>>>   *) Do we need to put Iterator_klass initialization this early in 
>>>> WK_KLASSES_DO? It feels safer to
>>>> initialize it at the end, to avoid surprising bootstrap issues.
>>>>
>>>>   *) Backslash indent is off here in vmSymbols.hpp:
>>>>
>>>>   129   template(java_util_Iterator, 
>>>> "java/util/Iterator")               \
>>>>
>>>>   *) Space after "if"? Also, I think you can use 
>>>> ciType::is_subtype_of instead here. Plus, since you
>>>> declared iterator in WK klasses, SystemDictionary::Iterator_klass() 
>>>> should be available.
>>>>
>>>>   100     if(retType->is_klass() && 
>>>> retType->as_klass()->is_subtype_of(C->env()->Iterator_klass())) {
>>>>