Modify

Opened 5 weeks ago

Closed 5 weeks ago

Last modified 4 weeks ago

#17819 closed enhancement (fixed)

Improve performance when loading or validating complex multipolygon relation

Reported by: GerdP Owned by: team
Priority: normal Milestone: 19.06
Component: Core Version:
Keywords: multipolygon performance Cc:

Description

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.

Attachments (2)

17819-multi-thread.patch (5.5 KB) - added by GerdP 4 weeks ago.
backport from MultipolygonBuilder
17819-multi-thread-v2.patch (15.2 KB) - added by GerdP 4 weeks ago.
implement same cache as in MultipolygonBuilder

Download all attachments as: .zip

Change History (8)

comment:1 Changed 5 weeks ago by GerdP

Resolution: fixed
Status: newclosed

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.

comment:2 Changed 5 weeks ago by GerdP

Summary: Improve performance when loading or varifying complex multipolygon relationImprove performance when loading or validating complex multipolygon relation

comment:3 Changed 4 weeks ago by Don-vip

Monsters are great to stress-test JOSM :)

comment:4 Changed 4 weeks ago by Don-vip

In 15182/josm:

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

Changed 4 weeks ago by GerdP

Attachment: 17819-multi-thread.patch added

backport from MultipolygonBuilder

comment:5 Changed 4 weeks ago by 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).

Changed 4 weeks ago by GerdP

Attachment: 17819-multi-thread-v2.patch added

implement same cache as in MultipolygonBuilder

comment:6 Changed 4 weeks ago by 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.

Modify Ticket

Change Properties
Set your email in Preferences
Action
as closed The owner will remain team.
as The resolution will be set.
The resolution will be deleted.

Add Comment


E-mail address and name can be saved in the Preferences.

 
Note: See TracTickets for help on using tickets.