RFR (S): 8067014: LinearScan::is_sorted significantly slows down fastdebug builds' performance

[Filipp Zhinkin]

Hi All,

here is a new webrev: http://cr.openjdk.java.net/~fzhinkin/8067014/webrev.01/

I've followed Vladimir's suggestion and instead of adding yet another
binary search implementation
IntervalList and IntervalArray were replaced with GrowableArray that
already has find_sorted method.

I've hacked VM sources a bit to run CTW with product bits and C1
compilation time on my x86_64 linux laptop
slowed down by 0.4% (from 51029 ± 306 ms to 51230 ± 293 ms). Please
let me know if it too slow.

With fastdebug bits provided patch allow to reduce C1 compilation time twice.

Regards,
Filipp.

On Mon, Feb 8, 2016 at 11:22 AM, Filipp Zhinkin
<filipp.zhinkin at gmail.com> wrote:
> Hi Vladimir,
>
> thanks for looking at this thread.
>
> I'll provide an updated webrev within this week.
>
> Regards,
> Filipp.
>
> On Fri, Feb 5, 2016 at 2:38 PM, Vladimir Ivanov
> <vladimir.x.ivanov at oracle.com> wrote:
>> (I'd like to revive the thread. It still affects our testing.)
>>
>> Filipp,
>>
>> Overall, the approach you propose looks good.
>>
>> What I'd like to see is unified binary_search implementation being used.
>>
>> There are already many places where custom implementations are used [1] [2]
>> [3] and I don't want to see one more. Please, factor it out.
>> GrowableArray::find_sorted looks like a good candidate (but it suffers from
>> an overflow).
>>
>> Let me know if you don't have time to work on it.
>>
>> Best regards,
>> Vladimir Ivanov
>>
>> [1]
>> http://hg.openjdk.java.net/jdk9/jdk9/hotspot/file/a34b3268a14f/src/share/vm/oops/instanceKlass.cpp#l1360
>>
>> [2]
>> http://hg.openjdk.java.net/jdk9/jdk9/hotspot/file/a34b3268a14f/src/share/vm/utilities/growableArray.hpp#l391
>>
>> [3]
>> http://hg.openjdk.java.net/jdk9/jdk9/hotspot/file/a34b3268a14f/src/share/vm/gc/g1/g1CollectorPolicy.cpp#l659
>>
>>
>> On 3/23/15 1:40 PM, Filipp Zhinkin wrote:
>>>
>>> Hi all,
>>>
>>> sorry for a late reply.
>>>
>>> I don't think that it's possible to remove is_sorted assertion from
>>> create_unhandled_lists, because it's crucial condition for a linear
>>> scan allocation algorithm and it's pretty easy to break it incidentally.
>>> Existing assertion could significantly reduce time required to locate
>>> an issue when something will go wrong.
>>>
>>> However, I believe that it could be relaxed to check only that
>>> intervals in _sorted_intervals list are actually ordered and that
>>> _new_intervals_from_allocation list is empty (in sorting methods
>>> we still will be verifying that sorted and unsorted lists contain
>>> same intervals).
>>>
>>> What do you guys think about that?
>>>
>>> Regards,
>>> Filippp.
>>>
>>>
>>> On Fri, Mar 6, 2015 at 9:24 PM, Filipp Zhinkin <filipp.zhinkin at gmail.com>
>>> wrote:
>>>>
>>>> Hi Aleksey,
>>>>
>>>> thanks for looking at it!
>>>>
>>>> On Fri, Mar 6, 2015 at 2:41 PM, Aleksey Shipilev
>>>> <aleksey.shipilev at oracle.com> wrote:
>>>>>
>>>>> Hi Filipp,
>>>>>
>>>>> On 06.03.2015 14:33, Filipp Zhinkin wrote:
>>>>>>
>>>>>> In certain cases (like -client -Xcomp) C1 compilation is very slow
>>>>>> w/ fastdebug builds. A place where we spent enormous amount of time
>>>>>> is LinearScan::is_sorted method, which simply verifies that a list
>>>>>> that should be sorted is actually sorted and that both sorted and
>>>>>> unsorted lists contains same intervals.
>>>>>
>>>>>
>>>>> Okay, what caller of is_sorted dominates? Maybe instead of optimizing
>>>>> the is_sorted itself, you need to move/relax the assert in some selected
>>>>> places?
>>>>
>>>>
>>>> Well, the dominating caller is LinearScan::create_unhandled_lists [1].
>>>>
>>>>>
>>>>> That is to say I am not fond of complicating the non-product code that
>>>>> does verification without a compelling reason to do so; let's first
>>>>> figure out if we "just" do excess asserts.
>>>>
>>>>
>>>> That's a good point. I'll try to figure a out if an assertion is placed
>>>> to be
>>>> sure that all methods called in the right sequence and if it's true, then
>>>> it may be better to use less expensive approach.
>>>>
>>>> Thanks,
>>>> Filipp.
>>>>
>>>> [1]
>>>> http://hg.openjdk.java.net/jdk9/hs-comp/hotspot/file/de7ca28f8b7d/src/share/vm/c1/c1_LinearScan.cpp#l1486
>>>>
>>>>>
>>>>> Thanks,
>>>>> -Aleksey.
>>>>>
>>