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

[Vladimir Ivanov]

(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.
>>>