RFR: 7950: Better DisjointBuilder performance for events not ordered by event end attribute

[Henrik Dafgård]

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

Marked as reviewed by hdafgard (Reviewer).

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

PR: https://git.openjdk.org/jmc/pull/449