Modify

Opened 7 weeks ago

Closed 6 weeks ago

Last modified 5 weeks ago

#17401 closed defect (fixed)

Fixing thousands of duplicated nodes scales poorly

Reported by: mkoniecz Owned by: team
Priority: normal Milestone: 19.03
Component: Core validator Version:
Keywords: template_report command Cc:

Description

What steps will reproduce the problem?

  1. Find area with bad import and thousands of duplicated nodes (coastal Texas as of now)
  2. Run validator
  3. Select autofix for 8k duplicated nodes
  4. wait 3 hours

What is the expected result?

Autofix completes or there is some progress bar.

What happens instead?

No signs of progress and work is not completed.

Please provide any additional information below. Attach a screenshot if possible.

URL:https://josm.openstreetmap.de/svn/trunk
Repository:UUID: 0c6e7542-c601-0410-84e7-c038aed88b3b
Last:Changed Date: 2019-02-23 17:46:51 +0100 (Sat, 23 Feb 2019)
Build-Date:2019-02-24 02:30:49
Revision:14802
Relative:URL: ^/trunk

Identification: JOSM/1.5 (14802 en) Linux Ubuntu 16.04.5 LTS
Memory Usage: 334 MB / 869 MB (88 MB allocated, but free)
Java version: 1.8.0_201-b09, Oracle Corporation, Java HotSpot(TM) 64-Bit Server VM
Screen: :0.0 1920x1080
Maximum Screen Size: 1920x1080

Plugins:
+ OpeningHoursEditor (34867)
+ buildings_tools (34867)
+ continuosDownload (82)
+ imagery_offset_db (34867)
+ measurement (34867)
+ reverter (34867)
+ todo (30306)

Validator rules:
+ ${HOME}/Desktop/tmp/test.validator.mapcss

Last errors/warnings:
- W: No configuration settings found.  Using hardcoded default values for all pools.
- W: Region [TMS_BLOCK_v2] Resetting cache
- W: Expecting test '{0.tag}' (i.e., [*[name=parking][amenity=parking], *[name=playground][leisure=playground], *[name=shop][shop][shop'NEQ'no], *[name=building][building][building'NEQ'no], *[name=kiosk][shop=kiosk], *[name=cemetery][amenity=graveyard], *[name=cemetery][landuse=cemetery], *[name=cmentarz][amenity=graveyard], *[name=cmentarz][landuse=cemetery]]) to match relation name=PLAYGROUND leisure=playground (i.e., TagMap[name=PLAYGROUND,leisure=playground])
- W: Expecting test '{0.tag}' (i.e., [*[name=parking][amenity=parking], *[name=playground][leisure=playground], *[name=shop][shop][shop'NEQ'no], *[name=building][building][building'NEQ'no], *[name=kiosk][shop=kiosk], *[name=cemetery][amenity=graveyard], *[name=cemetery][landuse=cemetery], *[name=cmentarz][amenity=graveyard], *[name=cmentarz][landuse=cemetery]]) to match relation name=parking amenity=Parking (i.e., TagMap[amenity=Parking,name=parking])
- W: Expecting test '{0.tag}' (i.e., [*[name=parking][amenity=parking], *[name=playground][leisure=playground], *[name=shop][shop][shop'NEQ'no], *[name=building][building][building'NEQ'no], *[name=kiosk][shop=kiosk], *[name=cemetery][amenity=graveyard], *[name=cemetery][landuse=cemetery], *[name=cmentarz][amenity=graveyard], *[name=cmentarz][landuse=cemetery]]) to match node name=PLaYGrOUNd leisure=playground (i.e., TagMap[name=PLaYGrOUNd,leisure=playground])
- W: Expecting test '{0.tag}' (i.e., [*[name=parking][amenity=parking], *[name=playground][leisure=playground], *[name=shop][shop][shop'NEQ'no], *[name=building][building][building'NEQ'no], *[name=kiosk][shop=kiosk], *[name=cemetery][amenity=graveyard], *[name=cemetery][landuse=cemetery], *[name=cmentarz][amenity=graveyard], *[name=cmentarz][landuse=cemetery]]) to match node name=parking amenity=Parking (i.e., TagMap[amenity=Parking,name=parking])
- W: Expecting test '{0.tag}' (i.e., [*[name=parking][amenity=parking], *[name=playground][leisure=playground], *[name=shop][shop][shop'NEQ'no], *[name=building][building][building'NEQ'no], *[name=kiosk][shop=kiosk], *[name=cemetery][amenity=graveyard], *[name=cemetery][landuse=cemetery], *[name=cmentarz][amenity=graveyard], *[name=cmentarz][landuse=cemetery]]) to match way name=parking amenity=Parking (i.e., TagMap[amenity=Parking,name=parking])

Attachments (8)

17401.patch (859 bytes) - added by GerdP 7 weeks ago.
17401-bad.patch (1.1 KB) - added by GerdP 7 weeks ago.
17401-v2.patch (3.3 KB) - added by GerdP 7 weeks ago.
17401-v3.patch (4.4 KB) - added by GerdP 7 weeks ago.
17401-v4-poc.patch (3.3 KB) - added by GerdP 6 weeks ago.
different approach: disable command stack window updates while fixing errors
17401-v5.patch (2.5 KB) - added by GerdP 6 weeks ago.
cleaner code: switch passive mode by removing/adding listener
17401-v6.patch (4.2 KB) - added by GerdP 6 weeks ago.
17401-v7.patch (5.7 KB) - added by GerdP 6 weeks ago.
try to revert changes to Dataset when user presses Cancel button

Download all attachments as: .zip

Change History (42)

comment:1 Changed 7 weeks ago by GerdP

I can reproduce rather slow performance, but not 3 hours. On my laptop it takes ~2 minutes. The result is that the command stack contains 8k delete actions, and it seems that the time is spent updating the command stack window, the rest is done within a few seconds. I thought I did already post a patch for that, but I can't find it right now.

comment:2 Changed 7 weeks ago by GerdP

Reproduce like this:
1) Download area with ~8k nodes
2) Search "type:node" to mark all nodes
3) Ctrl+C to copy
4) Paste at source position (Ctrl+Alt+V)
5) Esc to unselect all
6) Run validator to produce thounsands of "Duplicate Node" errors
7) Select all errors and press Fix button

I see two approaches to improve this:
1) Add a single SequenceCommand "Auto-Fixed" to the UndoRedoHeandler containing all the "Merge 2 nodes" actions.
2) Set the CommandStack to invisible while the commands are added and make it vsisible

I'd prefer Option 1) because it would also allow to completely undo the mass action while the current implementation only allows to undo the last n (1000) actions.

Changed 7 weeks ago by GerdP

Attachment: 17401.patch added

comment:3 Changed 7 weeks ago by GerdP

The attached patch is a work around: It reduces the number of added commands to the max. number kept in the undo/redo list.
Of course, the effect of this work around depends on the preference configured in undo.max. If the value is e.g. 10000 the patch has no effect.

comment:4 Changed 7 weeks ago by mkoniecz

I can reproduce rather slow performance, but not 3 hours.

Is it possible that additional data slow it down? For me the worst cases happen when I have large dataset already loaded (not sure is it just coincidence). Also, my computer is really old.

comment:5 Changed 7 weeks ago by GerdP

Can you confirm that the problem disappears when you close the command stack window before pressing the Fix button?

comment:6 Changed 7 weeks ago by stoecker

Hmm, the correct fix should be to use a sequence command to join all auto-fixes into one command.

Changed 7 weeks ago by GerdP

Attachment: 17401-bad.patch added

comment:7 Changed 7 weeks ago by GerdP

Yes, see comment:2. I've already tried to implement that but my simple approach to create a SequenceCommand containing the list from field `fixCommands' doesn't work (Undo has no effect). See 17401-bad.patch

comment:8 Changed 7 weeks ago by mkoniecz

Can you confirm that the problem disappears when you close the command stack window before pressing the Fix button?

It seems to be working as a workaround.

Changed 7 weeks ago by GerdP

Attachment: 17401-v2.patch added

comment:9 Changed 7 weeks ago by GerdP

@Dirk:
The attached patch v2 improves performance a lot and allows complete undo. However, there is room for more improvement.
The method ValidatorTreePanel.primitivesRemoved(PrimitivesRemovedEvent event) is still executed thousands of times with a non-empty list, probably because actions are performed out of order. I'll try to improve it further...

Changed 7 weeks ago by GerdP

Attachment: 17401-v3.patch added

comment:10 Changed 7 weeks ago by mkoniecz

Thank you very much for you work on this!

comment:11 Changed 7 weeks ago by GerdP

Please review:
v3 of the patch seems to work quite well. In my test case I see ~3 seconds instead of ~ 2 minutes for the fix command, performance doesn't depend much on existence of command stack window and undo / redo works. Only remaining issue is redoing the "fixed by Validator" requires more than 3 seconds as this again calls the expensive ValidatorTreePanel.primitivesRemoved(PrimitivesRemovedEvent event) for each sub command.
Please suggest a better text for "fixed by Validator".
I'll dig through older tickets to find possible problems with this patch.

comment:12 Changed 7 weeks ago by stoecker

Please suggest a better text for "fixed by Validator".

"auto-fixed validator issues" ?

comment:13 Changed 7 weeks ago by GerdP

Hmm, seems the patch causes trouble, I see a crash with

Caused by: java.lang.IllegalArgumentException: {Node id=-134149 version=0 MVD lat=52.89309260000001,lon=8.4330538} is already deleted

Probably two different errors create the same "delete" command to "fix" a problem.
I'll try to find a better solution...

Changed 6 weeks ago by GerdP

Attachment: 17401-v4-poc.patch added

different approach: disable command stack window updates while fixing errors

comment:14 Changed 6 weeks ago by GerdP

I am not sure if this is a good idea. 17401-v4-poc.patch partly implements a "passive" mode in which the command stack dialog ignores added commands. This can be used when it is known that many commands are added to the tree and visual updates are not required.
When the passive mode is ended the dialog is rebuild.
A complete patch should probably change more methods.
Disadvantage to v3: No SequenceCommand is build, undoing all actions in a single step is not possible.
I still try to make up my mind how this has to be implemented. Maybe I have to implement something like in JoinAreasAction.makeCommitsOneAction() but that would also not work with too many commands...

comment:15 in reply to:  13 Changed 6 weeks ago by stoecker

Replying to GerdP:

Hmm, seems the patch causes trouble, I see a crash with

Caused by: java.lang.IllegalArgumentException: {Node id=-134149 version=0 MVD lat=52.89309260000001,lon=8.4330538} is already deleted

Probably two different errors create the same "delete" command to "fix" a problem.
I'll try to find a better solution...

I'd assume that checking the fixes is the proper way. ATM it seems the "fix" does not check and simply issues commands which are conflicting and then lets other software parts handling that. You probably need to handle that at the place, where the fixes are created. Or even where the validator creates the issues.

comment:16 Changed 6 weeks ago by GerdP

ATM it seems the "fix" does not check and simply issues commands which are conflicting

I don't think so. With the current control flow each error creates a correct command. The problems only start when I first create all commands and then try to execute them. As long as each command is executed right after creation the data is consistent, but we see a huge amount of complex routines to keep everything updated.
The approach in JoinAreasAction looks better, there we execute the generated command and analyse the effects on other primitives and then undo the command before finally creating the complete sequence.
My current thinking is that this should be done in a method implemented in SequenceCommand so that all routines which create
sequence commands can profit.

Changed 6 weeks ago by GerdP

Attachment: 17401-v5.patch added

cleaner code: switch passive mode by removing/adding listener

comment:17 Changed 6 weeks ago by stoecker

The problems only start when I first create all commands and then try to execute them

That's clear. But for duplicate nodes it should be possible to create an errorset which does not have conflicting commands. I.e. join all errors which affect the same node into one command.

Without checking code: I assume that for 3 nodes we have 3 errors a==b, b==c, a==c. When fixing, two of these are executed and the third dropped because one node is missing. Instead an a==b==c error could be used which is conflictless.

comment:18 Changed 6 weeks ago by GerdP

Ah, maybe a misunderstanding. The problem occurs for some nodes with deprecated tagging. First the node is removed and next the fix for the deprecated tagging tries to update it. I can avoid that by checking OsmPrimitive::isDeleted for all primitives in the TestError, but only when I execute each single one. So, I was not yet able to produce a single SequenceCommand :(

Changed 6 weeks ago by GerdP

Attachment: 17401-v6.patch added

comment:19 Changed 6 weeks ago by GerdP

@Dirk: Please review v6: I've now managed to create a SequenceCommand, but it requires some "tricks". I am now working on a better synchronization between the validator tree and the command stack so that an undo/redo removes errors which refer to deleted elements.
See also #17412 which is just a special case of this.

comment:20 Changed 6 weeks ago by stoecker

Hmm. My feeling says that these tricks are dangerous. OTOH it probably could make life easier in many places.

In any case it should be thoroughly tested.

comment:21 Changed 6 weeks ago by GerdP

+1

comment:22 Changed 6 weeks ago by GerdP

Reg. dangerous: I'll add code to undo the executed commands in case of an error
I see many open tickets where problems are probably caused by creating a SequenceCommand in the same way as I tried in the bad patch v3. So, what we do right now in e.g. SplitWayAction or the reverter plugin is probably more likely to corrupt data as sub commands are created making assumptions about the effects of previous sub commands.
In other words: It is probably better to use a pattern like in the patch, isn't it?

comment:23 Changed 6 weeks ago by stoecker

As said: "it probably could make life easier in many places" :-)

Or we create another nightmare. Time will show.

Changed 6 weeks ago by GerdP

Attachment: 17401-v7.patch added

try to revert changes to Dataset when user presses Cancel button

comment:24 Changed 6 weeks ago by GerdP

As always I am not sure about the handling of the exceptions, so please review again and suggest improvements, else I'll commit v7 tomorrow.

comment:25 Changed 6 weeks ago by GerdP

Resolution: fixed
Status: newclosed

In 14845/josm:

fix #17401: create a SequenceCommand instead of adding single commands for each fixed error

comment:26 Changed 6 weeks ago by GerdP

@team: I thought about a different approach to create a SequenceCommand from already executed commands:
We might implement that in UndoRedoHandler, something like a new method buildSequenceCommand(String name, int n) which would
take the last n commands from the command stack and replace it by a new SequenceCommand with the given name.
Problem: n could be bigger than the stack size limit.
Or maybe even better: Use something like startSequenceCommand(String name) which returns a handle x followed by n calls addToSequence(Handle x, Command c) and a final finishSequenceCommand(Handle x)
Just thoughts, I think each approach opens its own box of worms when it comes to situations where the calling procedure crashes, so I did not try to implement it. Still I wanted to share the ideas.

comment:27 Changed 6 weeks ago by Don-vip

Be careful when changing signatures of public API. This breaks at least one plugin, maybe more.

comment:28 Changed 6 weeks ago by GerdP

In 14848/josm:

see #17401: re-add public method addNoRedraw(Command c)

I used to have this in my local patch but it got lost somehow...

comment:29 Changed 6 weeks ago by Don-vip

Keywords: command added

comment:30 Changed 6 weeks ago by Don-vip

@GerdP see #13036 and #14526 for previous related work and discussions about commands.

comment:31 Changed 6 weeks ago by GerdP

@Vincent: Thanks for the hints. If I got that right we still have no real way to check if Command.executeCommand() worked since most implementations of Command simply always return true. Fortunately most fix commands are rather simple as they either remove things or just change tags.
My current plan is to further improve performance in the ValidatorTreePanel, for example I see no need to sort the list of errors more than once, but there are problems. See #17431.

comment:32 Changed 6 weeks ago by GerdP

In 14855/josm:

see #17401: Improve performance: Use cached icon in MultipleNameVisitor
Drastically reduces the time to open a tree with thousands of errors

comment:33 Changed 6 weeks ago by GerdP

In 14857/josm:

see #17401, #17431

  • make sure that list of errors is never null
  • performance: avoid to sort list of errors when only elemets were removed from an already sorted list. This reduces time spent to rebuild the tree when primitives are removed or errors are fixed with the Fix button.

comment:34 Changed 5 weeks ago by GerdP

Milestone: 19.03

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.