Changeset 17582 in josm


Ignore:
Timestamp:
2021-03-17T22:15:57+01:00 (4 years ago)
Author:
simon04
Message:

see #20613 - Avoid heap allocations in DividedScale.getWithRange

4.74% in AbstractMapRendererPerformanceTestParent#testCity amount to Range from DividedScale.getWithRange

Location:
trunk
Files:
2 edited

Legend:

Unmodified
Added
Removed
  • trunk/src/org/openstreetmap/josm/gui/mappaint/DividedScale.java

    r10236 r17582  
    3737
    3838    /* list of boundaries for the scale ranges */
    39     private final List<Double> bd;
     39    private final List<Range> ranges;
    4040    /* data objects for each scale range */
    4141    private final List<T> data;
    4242
    4343    protected DividedScale() {
    44         bd = new ArrayList<>();
    45         bd.add(0.0);
    46         bd.add(Double.POSITIVE_INFINITY);
     44        ranges = new ArrayList<>();
     45        ranges.add(Range.ZERO_TO_INFINITY);
    4746        data = new ArrayList<>();
    4847        data.add(null);
     
    5049
    5150    protected DividedScale(DividedScale<T> s) {
    52         bd = new ArrayList<>(s.bd);
     51        ranges = new ArrayList<>(s.ranges);
    5352        data = new ArrayList<>(s.data);
    5453    }
     
    6463            throw new IllegalArgumentException("scale must be <= 0 but is "+scale);
    6564        for (int i = 0; i < data.size(); ++i) {
    66             if (bd.get(i) < scale && scale <= bd.get(i+1)) {
     65            Range range = ranges.get(i);
     66            if (range.contains(scale)) {
    6767                return data.get(i);
    6868            }
     
    8282            throw new IllegalArgumentException("scale must be <= 0 but is "+scale);
    8383        for (int i = 0; i < data.size(); ++i) {
    84             if (bd.get(i) < scale && scale <= bd.get(i+1)) {
    85                 return new Pair<>(data.get(i), new Range(bd.get(i), bd.get(i+1)));
     84            Range range = ranges.get(i);
     85            if (range.contains(scale)) {
     86                return new Pair<>(data.get(i), range);
    8687            }
    8788        }
     
    110111     * ASCII-art explanation:
    111112     *
    112      *              data[i]
    113      *  --|-------|---------|--
    114      * bd[i-1]  bd[i]    bd[i+1]
    115      *
    116      *         (--------]
    117      *       lower     upper
     113     *    data[i-1]      data[i]      data[i+1
     114     * |--------------|------------|--------------|
     115     * (--range[i-1]--]
     116     *                (--range[i]--]
     117     *                             (--range[i+1]--]
     118     *                       (--------]
     119     *                     lower     upper
    118120     * @param o data object
    119121     * @param lower lower bound
     
    122124    private void putImpl(T o, double lower, double upper) {
    123125        int i = 0;
    124         while (bd.get(i) < lower) {
     126        while (ranges.get(i).getUpper() <= lower) {
    125127            ++i;
    126128        }
    127         if (bd.get(i) == lower) {
    128             if (upper > bd.get(i+1))
    129                 throw new RangeViolatedError("the new range must be within a single subrange (1)");
    130             if (data.get(i) != null)
    131                 throw new RangeViolatedError("the new range must be within a subrange that has no data");
    132 
    133             if (bd.get(i+1) == upper) {
    134                 //  --|-------|--------|--
    135                 //   i-1      i       i+1
    136                 //            (--------]
    137                 data.set(i, o);
    138             } else {
    139                 //  --|-------|--------|--
    140                 //   i-1      i       i+1
    141                 //            (-----]
    142                 bd.add(i+1, upper);
    143                 data.add(i, o);
    144             }
     129        Range split = ranges.get(i);
     130        if (split.getUpper() < upper) {
     131            throw new RangeViolatedError("the new range must be within a single subrange");
     132        } else if (data.get(i) != null) {
     133            throw new RangeViolatedError("the new range must be within a subrange that has no data");
     134        } else if (split.getLower() == lower && split.getUpper() == upper) {
     135            data.set(i, o);
     136        } else if (split.getLower() == lower) {
     137            ranges.set(i, new Range(split.getLower(), upper));
     138            ranges.add(i + 1, new Range(upper, split.getUpper()));
     139            data.add(i, o);
     140        } else if (split.getUpper() == upper) {
     141            ranges.set(i, new Range(split.getLower(), lower));
     142            ranges.add(i + 1, new Range(lower, split.getUpper()));
     143            data.add(i + 1, o);
    145144        } else {
    146             if (bd.get(i) < upper)
    147                 throw new RangeViolatedError("the new range must be within a single subrange (2)");
    148             if (data.get(i-1) != null)
    149                 throw new AssertionError();
    150 
    151             //  --|-------|--------|--
    152             //   i-1      i       i+1
    153             //       (--]   or
    154             //       (----]
    155             bd.add(i, lower);
    156             data.add(i, o);
    157 
    158             //  --|--|----|--------|--
    159             //   i-1 i   i+1      i+2
    160             //       (--]
    161             if (bd.get(i+1) > upper) {
    162                 bd.add(i+1, upper);
    163                 data.add(i+1, null);
    164             }
     145            ranges.set(i, new Range(split.getLower(), lower));
     146            ranges.add(i + 1, new Range(lower, upper));
     147            ranges.add(i + 2, new Range(upper, split.getUpper()));
     148            data.add(i + 1, o);
     149            data.add(i + 2, null);
    165150        }
    166151    }
     
    171156     */
    172157    public void consistencyTest() {
    173         if (bd.size() < 2) throw new AssertionError(bd);
     158        if (ranges.size() < 1) throw new AssertionError(ranges);
    174159        if (data.isEmpty()) throw new AssertionError(data);
    175         if (bd.size() != data.size() + 1) throw new AssertionError();
    176         if (bd.get(0) != 0) throw new AssertionError();
    177         if (bd.get(bd.size() - 1) != Double.POSITIVE_INFINITY) throw new AssertionError();
     160        if (ranges.size() != data.size()) throw new AssertionError();
     161        if (ranges.get(0).getLower() != 0) throw new AssertionError();
     162        if (ranges.get(ranges.size() - 1).getUpper() != Double.POSITIVE_INFINITY) throw new AssertionError();
    178163        for (int i = 0; i < data.size() - 1; ++i) {
    179             if (bd.get(i) >= bd.get(i + 1)) throw new AssertionError();
     164            if (ranges.get(i).getUpper() != ranges.get(i + 1).getLower()) throw new AssertionError();
    180165        }
    181166    }
     
    186171        if (obj == null || getClass() != obj.getClass()) return false;
    187172        DividedScale<?> that = (DividedScale<?>) obj;
    188         return Objects.equals(bd, that.bd) &&
     173        return Objects.equals(ranges, that.ranges) &&
    189174                Objects.equals(data, that.data);
    190175    }
     
    192177    @Override
    193178    public int hashCode() {
    194         return Objects.hash(bd, data);
     179        return Objects.hash(ranges, data);
    195180    }
    196181
    197182    @Override
    198183    public String toString() {
    199         return "DS{" + bd + ' ' + data + '}';
     184        return "DS{" + ranges + ' ' + data + '}';
    200185    }
    201186}
  • trunk/test/unit/org/openstreetmap/josm/gui/mappaint/DividedScaleTest.java

    r17575 r17582  
    103103                .put("foo", new Range(4., 8.));
    104104        Exception ex = assertThrows(DividedScale.RangeViolatedError.class, () -> scale.put("bar", new Range(4., 9.)));
    105         assertEquals("the new range must be within a single subrange (1)", ex.getMessage());
     105        assertEquals("the new range must be within a single subrange", ex.getMessage());
    106106    }
    107107
     
    125125                .put("foo", new Range(4., 8.));
    126126        Exception ex = assertThrows(DividedScale.RangeViolatedError.class, () -> scale.put("bar", new Range(2., 5.)));
    127         assertEquals("the new range must be within a single subrange (2)", ex.getMessage());
     127        assertEquals("the new range must be within a single subrange", ex.getMessage());
    128128    }
    129129}
Note: See TracChangeset for help on using the changeset viewer.