RFR: 7950: Better DisjointBuilder performance for events not ordered by event end attribute
Erik Gahlin
egahlin at openjdk.org
Wed Nov 9 09:58:06 UTC 2022
On Sun, 30 Oct 2022 22:10:57 GMT, Richard Startin <duke at openjdk.org> wrote:
> When events are not disjoint and sorted by the end quantity, a lot of time can be spent in `DisjointBuilder.add`. Profiling shows that this is because of the linear search for the first lane ending before the added event starts, and then in the sort afterwards.
>
> This patch uses binary search to improve the handling of non-disjoint or non-sorted cases. It also adds checks whether the modification will disrupt descending order to avoid doing any work reordering the array.
>
> With a parameterised benchmark exercising some pathological cases:
>
>
> import org.openjdk.jmc.common.item.IMemberAccessor;
> import org.openjdk.jmc.common.unit.IQuantity;
> import org.openjdk.jmc.common.unit.UnitLookup;
> import org.openjdk.jmc.flightrecorder.internal.util.DisjointBuilder;
> import org.openjdk.jmh.annotations.Benchmark;
> import org.openjdk.jmh.annotations.Level;
> import org.openjdk.jmh.annotations.Param;
> import org.openjdk.jmh.annotations.Scope;
> import org.openjdk.jmh.annotations.Setup;
> import org.openjdk.jmh.annotations.State;
>
> import java.util.concurrent.ThreadLocalRandom;
>
> @State(Scope.Benchmark)
> public class DisjointBuilderBenchmark {
>
> private static class RangeObject {
> private final IQuantity start;
> private final IQuantity end;
>
> RangeObject(IQuantity start, IQuantity end) {
> this.start = start;
> this.end = end;
> }
>
> }
>
> private final static IMemberAccessor<IQuantity, RangeObject> START = inObject -> inObject.start;
>
> private final static IMemberAccessor<IQuantity, RangeObject> END = inObject -> inObject.end;
>
> public enum Scenario {
> ASCENDING {
> @Override
> void fill(RangeObject[] rangeObjects) {
> long min = 0;
> long max = 1;
> for (int i = 0; i < rangeObjects.length; i++) {
> rangeObjects[i] = new RangeObject(UnitLookup.NUMBER_UNITY.quantity(min),
> UnitLookup.NUMBER_UNITY.quantity(max));
> min++;
> max++;
> }
> }
> },
> DESCENDING {
> @Override
> void fill(RangeObject[] rangeObjects) {
> long min = 2L * (rangeObjects.length - 1);
> long max = 2L * rangeObjects.length - 1;
> for (int i = 0; i < rangeObjects.length; i++) {
> rangeObjects[i] = new RangeObject(UnitLookup.NUMBER_UNITY.quantity(min),
> UnitLookup.NUMBER_UNITY.quantity(max));
> min--;
> max--;
> }
> }
> },
> SCRAMBLED {
> @Override
> void fill(RangeObject[] rangeObjects) {
> ASCENDING.fill(rangeObjects);
> shuffle(rangeObjects);
> }
>
> private void shuffle(RangeObject[] data) {
> for (int i = data.length; i > 1; i--) {
> swap(data, i - 1, ThreadLocalRandom.current().nextInt(i));
> }
> }
>
> private void swap(RangeObject[] arr, int i, int j) {
> RangeObject tmp = arr[i];
> arr[i] = arr[j];
> arr[j] = tmp;
> }
>
> },
> OVERLAPS {
> @Override
> void fill(RangeObject[] rangeObjects) {
> long min = 0;
> long max = 2;
> for (int i = 0; i < rangeObjects.length; i++) {
> rangeObjects[i] = new RangeObject(UnitLookup.NUMBER_UNITY.quantity(min),
> UnitLookup.NUMBER_UNITY.quantity(max));
> min++;
> max++;
> }
> }
> },
> STACKED {
> @Override
> void fill(RangeObject[] rangeObjects) {
> long min = 0;
> long max = 2L * rangeObjects.length;
> for (int i = 0; i < rangeObjects.length; i++) {
> rangeObjects[i] = new RangeObject(UnitLookup.NUMBER_UNITY.quantity(min),
> UnitLookup.NUMBER_UNITY.quantity(max));
> min++;
> max--;
> }
> }
> },
> SHALLOW_STACKS {
> @Override
> void fill(RangeObject[] rangeObjects) {
> int stackDepth = 5;
> long min = 0;
> long max = 2 * stackDepth;
> for (int i = 0; i < rangeObjects.length; i++) {
> rangeObjects[i] = new RangeObject(UnitLookup.NUMBER_UNITY.quantity(min),
> UnitLookup.NUMBER_UNITY.quantity(max));
> min++;
> max--;
> if (min == max) {
> max += 2 * stackDepth;
> }
> }
> }
> };
>
> abstract void fill(RangeObject[] rangeObjects);
> }
>
> @Param({"ASCENDING", "DESCENDING", "SCRAMBLED", "OVERLAPS", "STACKED", "SHALLOW_STACKS"})
> Scenario scenario;
>
> @Param({"10000"})
> int numEvents;
> private RangeObject[] input;
>
> @Setup(Level.Trial)
> public void setup() {
> input = new RangeObject[numEvents];
> scenario.fill(input);
> }
>
> @Benchmark
> public DisjointBuilder<RangeObject> build() {
> DisjointBuilder<RangeObject> builder = new DisjointBuilder<>(START, END);
> for (RangeObject rangeObject : input) {
> builder.add(rangeObject);
> }
> return builder;
> }
> }
>
>
> Good performance is maintained in the common ascending/disjoint case, but the degenerate cases perform much better:
>
> Before:
>
> Benchmark (numEvents) (scenario) Mode Cnt Score Error Units
> DisjointBuilderBenchmark.build 10000 ASCENDING avgt 5 96.050 ± 1.240 us/op
> DisjointBuilderBenchmark.build 10000 DESCENDING avgt 5 300246.685 ± 2101.505 us/op
> DisjointBuilderBenchmark.build 10000 SCRAMBLED avgt 5 3977.733 ± 29.612 us/op
> DisjointBuilderBenchmark.build 10000 OVERLAPS avgt 5 187.701 ± 6.161 us/op
> DisjointBuilderBenchmark.build 10000 STACKED avgt 5 268306.481 ± 980.223 us/op
> DisjointBuilderBenchmark.build 10000 SHALLOW_STACKS avgt 5 414.298 ± 5.719 us/op
>
> After:
>
> Benchmark (numEvents) (scenario) Mode Cnt Score Error Units
> DisjointBuilderBenchmark.build 10000 ASCENDING avgt 5 91.583 ± 1.070 us/op
> DisjointBuilderBenchmark.build 10000 DESCENDING avgt 5 608.281 ± 9.338 us/op
> DisjointBuilderBenchmark.build 10000 SCRAMBLED avgt 5 596.601 ± 18.243 us/op
> DisjointBuilderBenchmark.build 10000 OVERLAPS avgt 5 181.349 ± 1.012 us/op
> DisjointBuilderBenchmark.build 10000 STACKED avgt 5 555.167 ± 13.316 us/op
> DisjointBuilderBenchmark.build 10000 SHALLOW_STACKS avgt 5 353.700 ± 9.387 us/op
When I wrote the original code in 2010 collisions were rare. I think I saw a few cases of 2-3 lanes (for the same event type and thread), typically when doing recursive events. I wonder what has changed, if this is no longer a case? The JVM usually doesn't write overlapping events. Is it thread buffers coming out of order?
-------------
PR: https://git.openjdk.org/jmc/pull/449
More information about the jmc-dev
mailing list