Fixing thousands of duplicated nodes scales poorly

[mkoniecz]

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])

[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.

[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.

[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.

[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.

[GerdP]

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

[stoecker]

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

[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

[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.

[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...

[mkoniecz]

Thank you very much for you work on this!

[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.

[stoecker]

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

"auto-fixed validator issues" ?

[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...

[GerdP]

different approach: disable command stack window updates while fixing errors

[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...

[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.

[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.

[GerdP]

cleaner code: switch passive mode by removing/adding listener

[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.

[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 :(

[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.

[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.

[GerdP]

+1

[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?

[stoecker]

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

Or we create another nightmare. Time will show.

[GerdP]

try to revert changes to Dataset when user presses Cancel button

[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.

[GerdP]

In 14845/josm:

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

[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.

[Don-vip]

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

[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...

[Don-vip]

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

[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.

[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

[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.