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

[Sergey Kuksenko]

Please review the next version:

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

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())) {
>>>>>