parallelize validator checks

[Matt Toups <mtoups@…>]

Hi, I run JOSM on a quad-core system and I want to validate some very large pieces of OSM data. Some checks with validator run for a long time, and only one CPU core is in use while the check runs.

It would be nice if checks could be run in parallel to utilize the other idle CPU cores on my system. (Perhaps even some "fix" operations could be parallelized for performance gains.)

Thanks!

[Don-vip]

Some work in progress I had some time ago. Solution may be need to be redesigned to implement UI stuff

[Don-vip]

This could also be interesting to see if tests taking a long time to perform could benefit from the new ​Fork/Join framework introduced in Java 7.

[Don-vip]

Too complicated/risky for this release.

[Don-vip]

Move all tickets for which no work has been done yet to next milestone

[Don-vip]

Move some tickets to next milestone

[Don-vip]

In 7423/josm:

see #9680, see #4626 - multithreaded multipolygon creation

[anonymous]

Currently, MapCSS validation takes way too long on large datasets (few hundred MB). Is it possible to run the check as a multithreaded process?
My 4 core, 8 threaded CPU used 15% while running MapCSS validation. But the speedup welcomed on the other checks as well.

[simon04]

In 17615/josm:

see #4626 - Extract PerformanceTestUtils.getNeubrandenburgDataSet

[simon04]

In 17616/josm:

see #4626 - Extract class ValidationTask

[simon04]

In 17617/josm:

see #4626 - Add ValidationTaskPerformanceTest

[simon04]

In 17618/josm:

see #4626 - PerformanceTestUtils.PerformanceTestTimer: use Stopwatch

[simon04]

In 17619/josm:

see #4626 - Extract class MapCSSTagCheckerRule

[simon04]

In 17620/josm:

see #4626 - Extract interface MapCSSTagCheckerFixCommand

[simon04]

In 17623/josm:

see #4626 - ​https://errorprone.info/bugpattern/ProtectedMembersInFinalClass

[simon04]

In 17625/josm:

see #4626 - Fix StyleCacheTest (cannot use PerformanceTestUtils)

[simon04]

Running all tests (that is, subclasses of org.openstreetmap.josm.data.validation.Test) in parallel yields only a

@@ ValidationTaskPerformanceTest
-[8307, 7321, 7285, 7293, 7280, 7410, 7424, 7298] ms
+[7016, 6383, 6421, 6369, 6307, 6121, 6156, 6384] ms

Running MapCSSTagChecker parallel on all primitives yields a nice performance gain, but sporadically triggers some ConcurrentModificationException (the various HashMap instances make a parallel usage dangerous/impossible)

+[3876, 3400, 3000, 3045, 2938, 2919, 3027, 3222] ms

Running MapCSSTagChecker parallel on the MapCSSTagChecker#checks yields a smaller speed-up:

+[2950, 3691, 3129, 4401, 5933, 4363, 3287, 4877] ms

[GerdP]

Some tests may require lots of memory per primitive, esp. the geometry tests for overlaps or insidness. Please make sure that you test this as well.

[simon04]

In 17640/josm:

see #4626 - ​https://errorprone.info/bugpattern/ProtectedMembersInFinalClass

[GerdP]

Performance improvemant with 4626.patch​ really looks good. So far I've not seen a ConcurrentModificationException. Did you find a fix for that already?
A few things that I noticed:

• Cancel button doesn't work
• tests seem to be executed in random order? Might cause trouble because we have some logic that expects the current order
• Progress monitor doesn't show the MapCSSTests at all and "blames" a random - typically fast - java test for quite a while, probably when a complex geometry test takes long
• I see wrong results when I use upload and my data contains new objects which should produce warnings, e.g. with two new water areas inside the same water area I get only one warning

[GerdP]

Reg. upload:
This seems to help, maybe you have an idea how to avoid the code duplication?

src/org/openstreetmap/josm/actions/upload/ValidateUploadHook.java

@@ -19 +19 @@
 import org.openstreetmap.josm.data.validation.Severity;
 import org.openstreetmap.josm.data.validation.Test;
 import org.openstreetmap.josm.data.validation.TestError;
+import org.openstreetmap.josm.data.validation.tests.MapCSSTagChecker;
 import org.openstreetmap.josm.data.validation.util.AggregatePrimitivesVisitor;
 import org.openstreetmap.josm.gui.ExtendedDialog;
 import org.openstreetmap.josm.gui.MainApplication;
@@ -63 +64 @@
             test.setBeforeUpload(true);
             test.setPartialSelection(true);
             test.startTest(null);
-            test.visit(selection);
+            if (test instanceof MapCSSTagChecker) {
+                // VARIANT 1
+                selection.parallelStream()
+                        .filter(test::isPrimitiveUsable)
+                        .forEach(p -> p.accept(test));
+            } else {
+                test.visit(selection);
+            }
+
             test.endTest();
             if (ValidatorPrefHelper.PREF_OTHER.get() && ValidatorPrefHelper.PREF_OTHER_UPLOAD.get()) {
                 errors.addAll(test.getErrors());

I see a potential problem regarding the HashSet surrounding in MapCSSTagChecker:
With the default validator rules there is only geometry.mapcss that requires this, but if a user adds his own spatial tests in another *.mapcss file we'll see problems with concurrent updates. Same is probably true for mpAreaCache.

[GerdP]

Ah, stop. The new code simply skips the test of the surrounding objects with a partial selection, so this requires more work.

[simon04]

Replying to GerdP:

So far I've not seen a ConcurrentModificationException. Did you find a fix for that already?

The synchronized (errors) accommodates for the exceptions I've seen while testing. Unsynchronised access to HashMap is a ticking time-bomb, as have shown various bugs in the past.

A few things that I noticed:

• Cancel button doesn't work
• Progress monitor doesn't show the MapCSSTests at all and "blames" a random - typically fast - java test for quite a while, probably when a complex geometry test takes long

I've deliberately left out those aspects for the proof-of-concept.

• tests seem to be executed in random order? Might cause trouble because we have some logic that expects the current order

Yeah. If there are inter-dependencies between different tests, parallelising the validator will never work unless we ensure those dependencies via e.g. Future or CompletableFuture.

Sigh, in principle everything sounds easy, but JOSM has accumulated various peculiarities over 15 years...

[GerdP]

Reg. the order I might be wrong. There was a patch that required this but I think it wasn't committed yet.

[GerdP]

Found it, see last patch for #17528