Improve performance when loading or validating complex multipolygon relation

[GerdP]

Someone created a real monster : ​https://www.openstreetmap.org/relation/9427189
More than 30_000 ways and + 1 Mio nodes. While writing this ticket it was deleted.
It takes quite long to load this relation even when it is stored in pbf format.
One major bottleneck is the method Multipolygon.joinWays() which frequently modifies a list of nodes. In current JOSM this list is an instance of CopyList, and CopyList doesn't implement addAll() and thus calls add() in a loop.
Another problem is that the collecion wayids is stored as a list. This collection is often searched like this: getWayIds().contains(p.getUniqueId()) which is fast enough for the typically small lists but slow for these monsters.

[GerdP]

In 15178/josm:

fix #17819

• Create ArrayList instead of modifying a CopyList instance in joinWays()
• Avoid to remove node, instead add sublist to avoid duplicate nodes, always use addAll().
• use HashSet to store larger collections of way ids, Collections.singleton for single ids

Result: Multipolygon.load() performance is much better for very complex multipolygons (1.6 secs instead of 30), no changes for normal sized relations.

[Don-vip]

Monsters are great to stress-test JOSM :)

[Don-vip]

In 15182/josm:

see #17819 - minor performance improvement, avoid to compute size twice

[GerdP]

backport from MultipolygonBuilder

[GerdP]

With really complex MP like the one above or Lake Huron (Relation 1205151) the calculation of the inner/outer rings still requires some seconds. The attached patch adds the multithreaded version that was implemented in MultipolygonBuilder.
I see a typically decrease in run time of 33% (e.g. 11 secs instead of 16 for Lake Huron).
It would probably be better to also re-add the IntersectionMatrix class as cache, but that requires more work.

While documenting this patch I found an error in the method makeFromWays(), it doesn't work properly when inner rings are touching. This problem is not related to the patch, maybe I'll revert the changes to MultipolygonBuilder if I cannot fix it soon (see #17768).

[GerdP]

implement same cache as in MultipolygonBuilder

[GerdP]

@Vincent
With patch v2 the run time for validation of Lake Huron is down to 7 secs. In general it is ~50 % faster. Not sure if the additional code complexity is worth the improvement. I don't commit the patch for now because I'll have no time to fix anything for the next 5-6 weeks and I think multithreading code should always be reviewed.
Most of it is a simple copy of the old code in MultipolygonBuilder before r15160.