Modify

Opened 3 months ago

Closed 2 months ago

Last modified 2 months 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 3 months ago.
17401-bad.patch (1.1 KB) - added by GerdP 3 months ago.
17401-v2.patch (3.3 KB) - added by GerdP 3 months ago.
17401-v3.patch (4.4 KB) - added by GerdP 3 months ago.
17401-v4-poc.patch (3.3 KB) - added by GerdP 3 months ago.
different approach: disable command stack window updates while fixing errors
17401-v5.patch (2.5 KB) - added by GerdP 3 months ago.
cleaner code: switch passive mode by removing/adding listener
17401-v6.patch (4.2 KB) - added by GerdP 3 months ago.
17401-v7.patch (5.7 KB) - added by GerdP 3 months ago.
try to revert changes to Dataset when user presses Cancel button

Download all attachments as: .zip

Change History (42)

comment:1 Changed 3 months 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 3 months 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 3 months ago by GerdP

Attachment: 17401.patch added

comment:3 Changed 3 months 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 3 months 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 3 months 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 3 months ago by stoecker

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

Changed 3 months ago by GerdP

Attachment: 17401-bad.patch added

comment:7 Changed 3 months 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 3 months 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 3 months ago by GerdP

Attachment: 17401-v2.patch added

comment:9 Changed 3 months 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 3 months ago by GerdP

Attachment: 17401-v3.patch added

comment:10 Changed 3 months ago by mkoniecz

Thank you very much for you work on this!

comment:11 Changed 3 months 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 3 months ago by stoecker

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

"auto-fixed validator issues" ?

comment:13 Changed 3 months 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 3 months ago by GerdP

Attachment: 17401-v4-poc.patch added

different approach: disable command stack window updates while fixing errors

comment:14 Changed 3 months 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 3 months 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 3 months 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 3 months ago by GerdP

Attachment: 17401-v5.patch added

cleaner code: switch passive mode by removing/adding listener

comment:17 Changed 3 months 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 3 months 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 3 months ago by GerdP

Attachment: 17401-v6.patch added

comment:19 Changed 3 months 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 3 months 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 3 months ago by GerdP

+1

comment:22 Changed 3 months 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 3 months ago by stoecker

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

Or we create another nightmare. Time will show.

Changed 3 months ago by GerdP

Attachment: 17401-v7.patch added

try to revert changes to Dataset when user presses Cancel button

comment:24 Changed 3 months 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 2 months 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 2 months 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 2 months ago by Don-vip

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

comment:28 Changed 2 months 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 2 months ago by Don-vip

Keywords: command added

comment:30 Changed 2 months ago by Don-vip

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

comment:31 Changed 2 months 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 2 months 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 2 months 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 2 months 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.