Modify

Opened 20 months ago

Last modified 5 months ago

#15170 needinfo enhancement

[Patch] SimplifyWayAction optimizations.

Reported by: shinigami Owned by: shinigami
Priority: normal Milestone:
Component: Core Version:
Keywords: performance Cc:

Description (last modified by shinigami)

I suppose it is not problem in common use case, but this action is used by OpenData plugin, where it is called for every loaded (sometimes very long) way.

It seems that delNodes and newNodes (in simplifyWay) often contains same data. Problem is that in such case AbstractSet.removeAll is processed as repetitive scanning of given collection and it leads to o(n2) complexity.

Another big slowdown is counting of node frequency in method isRequiredNode, it iterates all way for every node. Simple precounted histogram of nodes makes it much faster.

Attachments (3)

simplifyway.patch (898 bytes) - added by shinigami 20 months ago.
simplifyway2.patch (4.8 KB) - added by shinigami 20 months ago.
course.patch (1.1 KB) - added by shinigami 20 months ago.

Download all attachments as: .zip

Change History (8)

Changed 20 months ago by shinigami

Attachment: simplifyway.patch added

comment:1 Changed 20 months ago by shinigami

Description: modified (diff)

Changed 20 months ago by shinigami

Attachment: simplifyway2.patch added

comment:2 Changed 20 months ago by Don-vip

Keywords: performance added
Summary: SimplifyWayAction optimizations.[Patch] SimplifyWayAction optimizations.

Thanks, some questions:

  • can you please share the dataset showing the slowdown?
  • how much is is faster?
  • did you test with java 9?

comment:3 Changed 20 months ago by shinigami

One of sets is http://efele.net/maps/tz/world/tz_world.zip - borders of all timezones.
I measured time of OsmImporter.createLayer, it id ~4x faster now.

Other data I used to test are borders of countries extracted from OSM, one multipolygon for one country.
OsmImporter.createLayer takes about 16s now, did not measure it before, but it was enough to have
a lunch:).

Both were measured with latest jdk8.

Changed 20 months ago by shinigami

Attachment: course.patch added

comment:4 Changed 20 months ago by shinigami

One little update yet - two invocations of cos(lat2) extracted to variable.

comment:5 Changed 5 months ago by GerdP

Owner: changed from team to shinigami
Status: newneedinfo

Please check. I tried your patches with r14469 and found no improvement in performance with tz_world.zip. I assume the changes in r13540 helped already.

Modify Ticket

Change Properties
Set your email in Preferences
Action
as needinfo The owner will remain shinigami.
as The resolution will be set.
to The owner will be changed from shinigami to the specified user.
to The owner will be changed from shinigami to the specified user.
as duplicate The resolution will be set to duplicate.The specified ticket will be cross-referenced with this ticket
The owner will be changed from shinigami to anonymous.

Add Comment


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

 
Note: See TracTickets for help on using tickets.