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

[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/webrev.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-better/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
>>>>
>>>>
>>
>>