Changeset 18589 in josm for trunk/src

Timestamp:

2022-11-08T18:51:13+01:00 (18 months ago)

Author:

taylor.smock

Message:

Fix #22453: Decrease allocations/CPU samples in Geometry.getDistanceSegmentSegment

Statistics, using Mesa County, CO as the data ("nwr in 'Mesa County, CO'") with
the MapWithAI plugin validations enabled (validation run):

• CPU samples: 54,604 -> 39,146 (-15,458, -28.3%)
• Memory allocations: 170,983,028,400 -> 4,645,539,624 (-166,337,488,776, -97.3%)
  • All remaining allocations are from creating a new LatLon during interpolation.
• .7% improvement in GC threads (overall, see notes).

Notes:

• getDistanceWayNode was also modified to avoid EastNorth allocations.
• All remaining allocations come from the creation of new LatLon objects. This may be alleviated when value classes become a thing in Java LTS, and we start using them.
• Profiling was done from application startup to shut down.

Location:

trunk/src/org/openstreetmap/josm

Files:

• data/coor/ILatLon.java (modified) (1 diff)
• data/coor/LatLon.java (modified) (2 diffs)
• tools/Geometry.java (modified) (5 diffs)

trunk/src/org/openstreetmap/josm/data/coor/ILatLon.java

@@ -144 +144 @@
         return bearing;
     }
+
+    /**
+     * Does a linear interpolation between two ILatLon instances.
+     * @param ll2 The other ILatLon instance.
+     * @param proportion The proportion the other instance influences the result.
+     * @return The new {@link ILatLon} position.
+     * @since 18589
+     */
+    default ILatLon interpolate(ILatLon ll2, double proportion) {
+        // this is an alternate form of this.lat() + proportion * (ll2.lat() - this.lat()) that is slightly faster
+        return new LatLon((1 - proportion) * this.lat() + proportion * ll2.lat(),
+                (1 - proportion) * this.lon() + proportion * ll2.lon());
+    }
+
+    /**
+     * Returns the square of euclidean distance from this {@code Coordinate} to a specified coordinate.
+     *
+     * @param lon the X coordinate of the specified point to be measured against this {@code Coordinate}
+     * @param lat the Y coordinate of the specified point to be measured against this {@code Coordinate}
+     * @return the square of the euclidean distance from this {@code Coordinate} to a specified coordinate
+     * @since 18589
+     */
+    default double distanceSq(final double lon, final double lat) {
+        final double dx = this.lon() - lon;
+        final double dy = this.lat() - lat;
+        return dx * dx + dy * dy;
+    }
+
+    /**
+     * Returns the euclidean distance from this {@code ILatLon} to a specified {@code ILatLon}.
+     *
+     * @param other the specified coordinate to be measured against this {@code ILatLon}
+     * @return the euclidean distance from this {@code ILatLon} to a specified {@code ILatLon}
+     * @since 18589
+     */
+    default double distanceSq(final ILatLon other) {
+        return this.distanceSq(other.lon(), other.lat());
+    }
 }

trunk/src/org/openstreetmap/josm/data/coor/LatLon.java

@@ -259 +259 @@
 
     /**
-     * Interpolate between this and a other latlon
+     * Interpolate between this and a other latlon. If you don't care about the return type, use {@link ILatLon#interpolate(ILatLon, double)}
+     * instead.
      * @param ll2 The other lat/lon object
      * @param proportion The proportion to interpolate
@@ -265 +266 @@
      */
     public LatLon interpolate(LatLon ll2, double proportion) {
-        // this is an alternate form of this.lat() + proportion * (ll2.lat() - this.lat()) that is slightly faster
-        return new LatLon((1 - proportion) * this.lat() + proportion * ll2.lat(),
-                (1 - proportion) * this.lon() + proportion * ll2.lon());
+        ILatLon interpolated = ILatLon.super.interpolate(ll2, proportion);
+        if (interpolated instanceof LatLon) {
+            return (LatLon) interpolated;
+        }
+        return new LatLon(interpolated);
     }
 

trunk/src/org/openstreetmap/josm/tools/Geometry.java

@@ -492 +492 @@
         double pdx = point.getX() - p1.getX();
         double pdy = point.getY() - p1.getY();
+
+        double offset = (pdx * ldx + pdy * ldy) / (ldx * ldx + ldy * ldy);
+
+        if (segmentOnly && offset <= 0)
+            return p1;
+        else if (segmentOnly && offset >= 1)
+            return p2;
+        else
+            return p1.interpolate(p2, offset);
+    }
+
+    /**
+     * Get the closest point to a segment
+     * @param p1 Point 1 of the segment
+     * @param p2 Point 2 of the segment
+     * @param point The point to use to get the closest point on the segment
+     * @param segmentOnly {@code true} if the point <i>must</i> be on the segment
+     * @return The closest point on the segment if {@code segmentOnly = true}, otherwise the closest point on the infinite line.
+     */
+    private static ILatLon closestPointTo(ILatLon p1, ILatLon p2, ILatLon point, boolean segmentOnly) {
+        CheckParameterUtil.ensureParameterNotNull(p1, "p1");
+        CheckParameterUtil.ensureParameterNotNull(p2, "p2");
+        CheckParameterUtil.ensureParameterNotNull(point, "point");
+
+        double ldx = p2.lon() - p1.lon();
+        double ldy = p2.lat() - p1.lat();
+
+        //segment zero length
+        if (ldx == 0 && ldy == 0)
+            return p1;
+
+        double pdx = point.lon() - p1.lon();
+        double pdy = point.lat() - p1.lat();
 
         double offset = (pdx * ldx + pdy * ldy) / (ldx * ldx + ldy * ldy);
@@ -1501 +1534 @@
 
         double smallest = Double.MAX_VALUE;
-        EastNorth en0 = node.getEastNorth();
         // go through the nodes as if they were paired
         Iterator<Node> iter = way.getNodes().iterator();
-        EastNorth en1 = iter.next().getEastNorth();
+        Node en1 = iter.next();
         while (iter.hasNext()) {
-            EastNorth en2 = iter.next().getEastNorth();
-            double distance = getSegmentNodeDistSq(en1, en2, en0);
+            Node en2 = iter.next();
+            double distance = getSegmentNodeDistSq(en1, en2, node);
             if (distance < smallest)
                 smallest = distance;
@@ -1561 +1593 @@
         Iterator<Node> iter1 = w1.getNodes().iterator();
         Node w1N1 = iter1.next();
+        List<Node> w2Nodes = w2.getNodes();
         while (iter1.hasNext()) {
             Node w1N2 = iter1.next();
-            Iterator<Node> iter2 = w2.getNodes().iterator();
+            Iterator<Node> iter2 = w2Nodes.iterator();
             Node w2N1 = iter2.next();
             while (iter2.hasNext()) {
@@ -1602 +1635 @@
      */
     public static double getDistanceSegmentSegment(Node ws1Node1, Node ws1Node2, Node ws2Node1, Node ws2Node2) {
-        EastNorth enWs1Node1 = ws1Node1.getEastNorth();
-        EastNorth enWs1Node2 = ws1Node2.getEastNorth();
-        EastNorth enWs2Node1 = ws2Node1.getEastNorth();
-        EastNorth enWs2Node2 = ws2Node2.getEastNorth();
-        if (enWs1Node1 == null || enWs1Node2 == null || enWs2Node1 == null || enWs2Node2 == null)
+        if (!ws1Node1.isLatLonKnown() || !ws1Node2.isLatLonKnown() || !ws2Node1.isLatLonKnown() || !ws2Node2.isLatLonKnown()) {
             return Double.NaN;
-        if (getSegmentSegmentIntersection(enWs1Node1, enWs1Node2, enWs2Node1, enWs2Node2) != null)
+        }
+        if (getSegmentSegmentIntersection(ws1Node1, ws1Node2, ws2Node1, ws2Node2) != null)
             return 0;
 
-        double dist1sq = getSegmentNodeDistSq(enWs1Node1, enWs1Node2, enWs2Node1);
-        double dist2sq = getSegmentNodeDistSq(enWs1Node1, enWs1Node2, enWs2Node2);
-        double dist3sq = getSegmentNodeDistSq(enWs2Node1, enWs2Node2, enWs1Node1);
-        double dist4sq = getSegmentNodeDistSq(enWs2Node1, enWs2Node2, enWs1Node2);
+        double dist1sq = getSegmentNodeDistSq(ws1Node1, ws1Node2, ws2Node1);
+        double dist2sq = getSegmentNodeDistSq(ws1Node1, ws1Node2, ws2Node2);
+        double dist3sq = getSegmentNodeDistSq(ws2Node1, ws2Node2, ws1Node1);
+        double dist4sq = getSegmentNodeDistSq(ws2Node1, ws2Node2, ws1Node2);
         double smallest = Math.min(Math.min(dist1sq, dist2sq), Math.min(dist3sq, dist4sq));
         return smallest != Double.MAX_VALUE ? Math.sqrt(smallest) : Double.NaN;
@@ -1649 +1679 @@
      * @return the square of the euclidean distance from p to the closest point on the segment
      */
-    private static double getSegmentNodeDistSq(EastNorth s1, EastNorth s2, EastNorth p) {
-        EastNorth c1 = closestPointTo(s1, s2, p, true);
-        return c1.distanceSq(p);
+    private static double getSegmentNodeDistSq(ILatLon s1, ILatLon s2, ILatLon p) {
+        ILatLon c1 = closestPointTo(s1, s2, p, true);
+        return c1.distanceSq(p.lon(), p.lat());
     }
 }