RFR: 8280579: Shenandoah: Skip regions in the back of sorted array when choosing cset

[Aleksey Shipilev]

On Tue, 25 Jan 2022 10:10:04 GMT, Yude Lin <duke at openjdk.java.net> wrote:

> Can I have review on this small change that skips some unnecessary work in cset choosing?
> 
> When choosing regions to add to cset, we sort the regions from most garbage to least garbage. We then iterate the sorted array. We can break early from the loop if we find a region with (garbage <= garbage_threshold). Because we know the regions left won't have enough garbage and won't be added anyway.

I am still not quite convinced about the performance gains here -- my point tests show there is slight regression in "Choose Collection Set" (use `-Xlog:gc+stats` to get it, and look at the table before JVM shutdown). Have you have any promising performance data?

Meanwhile, if we do this, I suggest two things:

1) Update the large "logic" comment like this:


  // Therefore, we start by sorting the regions by garbage. Then we unconditionally add the best candidates
  // before we meet min_garbage. Then we add all candidates that fit with a garbage threshold.
  // If max_cset is hit during that phase, we terminate the cset selection. Note that in this scheme,
  // ShenandoahGarbageThreshold is the soft threshold which would be ignored until min_garbage is hit.

2) Assert sorting invariants like this:


    } else if (cur_garbage >= min_garbage) {
      // Min garbage condition satisfied, and the regions left would never meet
      // the garbage threshold, because we sorted by garbage. Can break here.
#ifdef ASSERT
      for (size_t c_idx = idx; c_idx < size; c_idx++) {
        assert(data[c_idx]._region->garbage() <= garbage_threshold, "Sorting invariant");
      }
#endif
      break;
    }

-------------

PR: https://git.openjdk.java.net/jdk/pull/7211