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

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