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

[Vladimir Ivanov]

> http://cr.openjdk.java.net/~skuksenko/hotspot/8223504/webrev.03/

Reviewed.

Best regards,
Vladimir Ivanov

> Now, only return type is checked. It works the same way on all forall 
> loops. Besides it perfectly works on "descendingIterator()" methods and 
> all other methods returning iterator but having other names like 
> Enumeration::asIterator.
> 
> On 5/22/19 10:47 AM, Vladimir Ivanov wrote:
>> 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())) {
>>>>>>