Slow geometry check in canvec area

[taylor.smock]

A user (jmarchon) on OSM JOSM (OSM World Discord, I think) has an issue with mapcss geometry checks taking a long time in some areas.

I've attached the test area he provided and I was able to reproduce with.

[taylor.smock]

Test area

[taylor.smock]

In 19272/josm:

See #24046: Reduce cost of Geometry#filterInsidePolygon when a primitive is a relation

This was done by checking that the bounds of the polygon contain the bounds of
the multipolygon ring before creating an area from the multipolygon ring.

If the polygon does not contain the bounds of the ring, then at least part
of the ring is outside the polygon, and thus is not inside the polygon.

Measurements using validators at (57.5183581,-75.0512982),(57.2181217,-73.9434821):

• CPU: -87%
• Memory: -62%

Please note that the test area is still very expensive in
Geometry#filterInsideMultipolygon (note the Multipolygon).

[taylor.smock]

I was able to decrease the cost for Geometry#filterInsideMultipolygon by 98% CPU and 99% memory.

I don't like this solution. I'll have to spend some time figuring out how to do the cache, and (maybe) how to pass it in.

I'm inclined to do something like MultipolygonCache (or maybe extend it), but I'll think on it.

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

@@ -14 +14 @@
 import java.util.Collection;
 import java.util.Collections;
 import java.util.Comparator;
+import java.util.HashMap;
 import java.util.Iterator;
 import java.util.LinkedHashSet;
 import java.util.List;
+import java.util.Map;
 import java.util.Set;
 import java.util.TreeSet;
 import java.util.function.Predicate;
@@ -1211 +1213 @@
         return res;
     }
 
+    private static Map<Relation, Pair<List<JoinedPolygon>, List<JoinedPolygon>>> jpCache = new HashMap<>();
     /**
      * Find all primitives in the given collection which are inside the given multipolygon. Members of the multipolygon are
      * ignored. Unclosed ways and multipolygon relations with unclosed outer rings are ignored.
@@ -1225 +1228 @@
             return res;
 
         final Pair<List<JoinedPolygon>, List<JoinedPolygon>> outerInner;
-        try {
-            outerInner = MultipolygonBuilder.joinWays(multiPolygon);
-        } catch (MultipolygonBuilder.JoinedPolygonCreationException ex) {
-            Logging.trace(ex);
-            Logging.debug("Invalid multipolygon " + multiPolygon);
-            return res;
+        if (jpCache.containsKey(multiPolygon)) {
+            outerInner = jpCache.get(multiPolygon);
+        } else {
+            try {
+                outerInner = MultipolygonBuilder.joinWays(multiPolygon);
+            } catch (MultipolygonBuilder.JoinedPolygonCreationException ex) {
+                Logging.trace(ex);
+                Logging.debug("Invalid multipolygon " + multiPolygon);
+                return res;
+            }
+            jpCache.put(multiPolygon, outerInner);
         }
 
         Set<OsmPrimitive> members = multiPolygon.getMemberPrimitives();

[stoecker]

Is this really worth the effort? Typically you will only fill such a cache, but never use the results. Normally you will check different elements with the next upload.

[jmarchon]

I often end up running the validator 2-3 times on the same data when I'm working on importing Canvec.

[taylor.smock]

Replying to stoecker:

Is this really worth the effort? Typically you will only fill such a cache, but never use the results. Normally you will check different elements with the next upload.

What I put in comment:2 was more of a POC. In that case, in the event that someone does the following:

1. Download data
2. Edit
3. Validate/Upload
4. Delete current layer
5. Download more data

your issue with only filling the cache but never reusing the results would be valid (if we were able to avoid rebuilding the multipolygon area multiple times).

In all other cases, it is not. And for the above case, extending MultipolygonCache to have another per-dataset cache would fix that particular issue.

I'll try to remember to check to see which geometry check(s) are causing the slowdown and why, but my suspicion is that it is a contains check -- e.g. check if water area contained in water multipolygon. In that case, we do the following:

1. Get any water multipolygons that intersect the bounding box for the water area we are checking
2. Pass in a singleton list of the water area and the multipolygon to the method
3. Repeat for each water area

The problem is in step 2, where we rebuild an Area for the multipolygon outer/inner areas for each way that we are checking.

If we are able to change the check such that we can pass multiple water areas to the method with a single multipolygon, then that would also fix the problem. But that would (IMO) be much more complicated, since we would have to create a map in the check and then go back to it when we "end" the test to perform the actual checks. Something like Map<Relation, List<OsmPrimitive>> would work for the map.

Alternatively, we can add something similar to the mpAreaCache(?) on the environment that would cache the multipolygon calculations used by filterInsideMultipolygon. Note that we cannot reuse mpAreaCache(?) since it caches an area calculation that isn't (directly) used by filterInsideMultipolygon. I did try rewriting filterInsideMultipolygon to use mpAreaCache(?), and it didn't work as well as I had hoped.

FTR, I also tried making the area calculations lazy, and while that helped, it was at most 10% improvement with the problem data, so I thought it wasn't worth the potential issues (the area used is calculated at object initialization, and is a public variable used directly).

@jmarchon's test area is an egregious example, and most people won't run into it. But when it slows down the validator enough that users are wondering what they would lose if they disable the geometry validations, we have a problem.

Note: mpAreaCache is what I remember the cache map being called, but I could be wrong. That is why I put (?) after it. I'm not on my standard dev machine right now, and I probably won't be until after the new year, but (IIRC), mpAreaCache was a Map<IPrimitive, Area> object. This doesn't work for multipolygons since it would need to be Map<IPrimitive, List<Area>>, and (more importantly) the JoinedWay objects used by filterInsideMultipolygon do the calculation for a sorted collection of way nodes.

[taylor.smock]

Extend MultipolygonCache to cache JoinedPolygon calculations

[taylor.smock]

Cache stored in test

[taylor.smock]

I like attachment:24046.patch​ due to simplicity, and every caller gets the optimizations automatically.
I like attachment:24046.1.patch​ since it doesn't keep unnecessary data in memory after a validation run. I'm leaning towards the second patch, just to avoid adding to the static memory size.

[stoecker]

Ticket retargeted after milestone closed

[jmarchon]

I've created an account now. Just commenting here so I get an email if there are any updates.

[stoecker]

In 19336/josm:

fix #24046 - improve speed of multipolygon validator - patch by taylor.smock