RFR (S): Sorting the regions for collection set takes a while during pause

[Aleksey Shipilev]

No sorting with default heuristics, the "prepare evac" times are slightly better
than the previous patch. I would need to construct a proper torture test to say
something about the pauses now :)

Thanks,
-Aleksey

On 01/26/2017 07:50 PM, Roman Kennke wrote:
> Ok.
> 
> What's the profile saying?
> 
> Roman
> 
> 
> Am Donnerstag, den 26.01.2017, 19:45 +0100 schrieb Aleksey Shipilev:
>> Okay, let's do this:
>>
>> 1) Do not even try to sort when heuristics is fine with unsorted
>> (some need
>> sorted anyway, and probably some in the future would).
>>
>> 2) Trim down the candidate list first, and then sort a hopefully
>> smaller list.
>>
>> See:
>>  http://cr.openjdk.java.net/~shade/shenandoah/pause-sort-better/webre
>> v.02/
>>
>> -Aleksey
>>
>> On 01/26/2017 06:53 PM, Roman Kennke wrote:
>>> Duh. We don't even seem to stop at the first region that exceeds
>>> the
>>> threshold. This whole sorting seems not necessary, and lots of
>>> wasted
>>> space too (for the _sorted_regions list).
>>>
>>> Roman
>>>
>>> Am Donnerstag, den 26.01.2017, 18:48 +0100 schrieb Aleksey
>>> Shipilev:
>>>> Maybe! Let's see...
>>>>
>>>> -Aleksey
>>>>
>>>> On 01/26/2017 06:43 PM, Roman Kennke wrote:
>>>>> Or maybe not sort the list at all? Downside: we need to scan
>>>>> all
>>>>> regions and decide on their garbage, instead of stopping at the
>>>>> first
>>>>> region that exceeds the garbage threshold. Upside: no sorting
>>>>> necessary. May be worth a try.
>>>>>
>>>>> Roman
>>>>>
>>>>>
>>>>> Am Donnerstag, den 26.01.2017, 18:39 +0100 schrieb Aleksey
>>>>> Shipilev:
>>>>>> Hi,
>>>>>>
>>>>>> Profiled the pause-intensive application for fun, and spotted
>>>>>> an
>>>>>> easy
>>>>>> optimization target. In final mark pause, we select
>>>>>> collection
>>>>>> set,
>>>>>> and for
>>>>>> that, we sort the regions by garbage. This incurs (N log N)
>>>>>> calls
>>>>>> to
>>>>>> comparator,
>>>>>> which calls SHHR->garbage() and handles nulls, etc.
>>>>>>
>>>>>> Doing a simple trick:
>>>>>>  http://cr.openjdk.java.net/~shade/shenandoah/pause-sort-bett
>>>>>> er/w
>>>>>> ebre
>>>>>> v.01/
>>>>>>
>>>>>> ...improves timings:
>>>>>>
>>>>>> before:
>>>>>>
>>>>>>   Final Mark Pauses (gross) = 7.05 s (a = 1059 us) (n
>>>>>> =  6659)
>>>>>>     (lvls, us = 717, 805, 830, 912, 9376)
>>>>>>
>>>>>>   Final Mark Pauses (net)   = 3.03 s (a =  454 us) (n
>>>>>> =  6659)
>>>>>>     (lvls, us = 102, 211, 221, 270, 8728)
>>>>>>
>>>>>>   Prepare Evacuation = 2.04 s (a = 306 us) (n =  6659)
>>>>>>     (lvls, us = 273, 293, 297, 301, 1490)
>>>>>>
>>>>>> after:
>>>>>>
>>>>>>   Final Mark Pauses (gross) = 6.12 s (a = 851 us) (n =  7195)
>>>>>>     (lvls, us = 547, 605, 629, 689, 5335)
>>>>>>
>>>>>>   Final Mark Pauses (net)   = 3.15 s (a = 438 us) (n =  7195)
>>>>>>     (lvls, us = 98, 203, 211, 260, 4877)
>>>>>>
>>>>>>   Prepare Evacuation = 0.75 s (a = 105 us) (n =  7195)
>>>>>>     (lvls, us = 82, 96, 105, 109, 187)
>>>>>>
>>>>>> 0.2 ms off the already low pause time.
>>>>>>
>>>>>> Thanks,
>>>>>> -Aleksey
>>>>>>
>>>>>>
>>>>
>>>>
>>
>>