RFR: 7950: better DisjointBuilder performance for overlapping or unordered events

[Richard Startin]

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

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

Commit messages:
 - 7950: better DisjointBuilder performance for overlapping or unordered events

Changes: https://git.openjdk.org/jmc/pull/449/files
 Webrev: https://webrevs.openjdk.org/?repo=jmc&pr=449&range=00
  Issue: https://bugs.openjdk.org/browse/JMC-7950
  Stats: 64 lines in 1 file changed: 40 ins; 8 del; 16 mod
  Patch: https://git.openjdk.org/jmc/pull/449.diff
  Fetch: git fetch https://git.openjdk.org/jmc pull/449/head:pull/449

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