[PATCH] Decrease cost of Geometry#polygonIntersectionResult (specifically for geometry.mapcss)

[taylor.smock]

When profiling the validator with an overpass download of ​Mesa County, Colorado, ~50% of the total CPU time are taken up by Geometry#polygonIntersectionResult. With the attached patch, the total CPU time for that method are reduced to ~7% of the total CPU cycles.

Specific measurements:

	CPU	Memory Allocations	Total Validator Time
No patch	522,778ms	54.13 GB	~840s
Patch	22,581ms	1.13 GB	~210s
Difference	-500,197ms	-53 GB	-630s
Difference %	-95.7%	-97.9%	-77.7%

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

@@ -693 +693 @@
      * @since 15938
      */
     public static Pair<PolygonIntersection, Area> polygonIntersectionResult(Area a1, Area a2, double eps) {
+        // Simple intersect check (if their bounds don't intersect, don't bother going further; there will be no intersection)
+        // This avoids the more expensive Area#intersect call some of the time (decreases CPU and memory allocation by ~95%)
+        // in Mesa County, CO geometry validator test runs.
+        final Rectangle2D a12d = a1.getBounds2D();
+        final Rectangle2D a22d = a2.getBounds2D();
+        if (!a12d.intersects(a22d) || !a1.intersects(a22d) || !a2.intersects(a12d)) {
+            return new Pair<>(PolygonIntersection.OUTSIDE, new Area());
+        }
         Area inter = new Area(a1);
         inter.intersect(a2);
 
         if (inter.isEmpty() || !checkIntersection(inter, eps)) {
             return new Pair<>(PolygonIntersection.OUTSIDE, inter);
-        } else if (a2.getBounds2D().contains(a1.getBounds2D()) && inter.equals(a1)) {
+        } else if (a22d.contains(a12d) && inter.equals(a1)) {
             return new Pair<>(PolygonIntersection.FIRST_INSIDE_SECOND, inter);
-        } else if (a1.getBounds2D().contains(a2.getBounds2D()) && inter.equals(a2)) {
+        } else if (a12d.contains(a22d) && inter.equals(a2)) {
             return new Pair<>(PolygonIntersection.SECOND_INSIDE_FIRST, inter);
         } else {
             return new Pair<>(PolygonIntersection.CROSSING, inter);

[GerdP]

That's interesting. I thought area.intersect() always performs the boundary check first.

[taylor.smock]

Nope; Area#intersect always attempts to calculate the intersection, even if there is no intersection.
The JDK probably should check to see if there actually is an intersection, but I can see arguments for and against that. It would probably have even better performance characteristics if it were done in the JDK (by avoiding at least two instantiations of a Rectangle2D object).

If I were to do it in the ​JDK, Area#intersect would look something like this:

    public void intersect(Area rhs) {
        final var lhsBounds = this.getCachedBounds();
        final var rhsBounds = rhs.getCachedBounds();
        if (!lhsBounds.intersects(rhsBounds) || !this.intersects(rhsBounds) || !rhs.intersects(lhsBounds)) {
            curves = EmptyCurves;
        } else {
            curves = new AreaOp.IntOp().calculate(this.curves, rhs.curves);
        }
        invalidateBounds();
    }

[GerdP]

Right, only area.intersects() checks the boundaries first.

[taylor.smock]

I just sent an email to ​client-libs-dev; maybe they'll make some improvements in the JDK.

In any case, I'll apply the patch next week -- I doubt that the JDK will be modified to sanity check bounds prior to doing the more expensive calculation.

[taylor.smock]

In 18990/josm:

Fix #23472: Decrease cost of Geometry#polygonIntersectionResult (specifically for geometry.mapcss)

When profiling the validator with an overpass download of Mesa County, Colorado,
~50% of the total CPU time are taken up by Geometry#polygonIntersectionResult.

Specifically (inside the function), the improvements for this patch are as follows:

• CPU cycles: -95.7%
• Memory allocations: -97.9%

When taken as a whole, the total time taken by the validator was reduced by ~75%.