[Patch]Possible poor performance when validating selection

[GerdP]

What steps will reproduce the problem?

1. Load attached file
2. Make sure that "Show informational level" is enabled (preference validator.other)
3. Search for id:236090530 to select way 236090530
4. Run validator

What is the expected result?

Quick response since this is a single object

What happens instead?

Long delay in "Tag Checker (MapCSS based) Geometry" (~18 secs on my machine)

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

Stumbled over this special case while working on #20473. Related problem is #19597.
The data file contains a huge amount of complete multipolygons, that already makes it special. More important: The river multipolygon r1392461 is also complete, and its bbox contains lots of objects.
What happens? The way 236090530 is inside the bbox of r1392461.
Since r15103 we have an additional check to find surrounding objects for spatial tests like overlapping buildings, so that we find a new building overlapping an unchanged one on upload.
The surrounding objects are checked to find if they produce a message with the selected object.
Now, with test

area:closed:areaStyle ⧉ area:closed:areaStyle {
  throwOther: tr("Overlapping Areas");
}

this involves a huge amount of area intersection tests where the complex river multipolygon is checked against all objects inside its bbox. This requires the 18 seconds. In a later step, all messages produced by this check are removed again because none contains the selected way.
The patch avoids this worst case scenario. When the elements "inside the bbox" are searched for intersections, only the selected elements are regarded.
For the example, the delay simply goes away and the validation is done within fractions of a second, but in other situations, esp. with lots of selected elements, the unpatched code might work a bit faster. The patch assumes that the lookup in a HashSet is quicker than the calculation in Geometry.polygonIntersectionResult().
I've worked with this patch for a while and didn't notice a negative impact.

URL:https://josm.openstreetmap.de/svn/trunk
Repository:UUID: 0c6e7542-c601-0410-84e7-c038aed88b3b
Last:Changed Date: 2020-12-28 22:03:23 +0100 (Mon, 28 Dec 2020)
Build-Date:2020-12-30 02:30:55
Revision:17428
Relative:URL: ^/trunk

Identification: JOSM/1.5 (17428 en) Windows 10 64-Bit
OS Build number: Windows 10 Home 2004 (19041)
Memory Usage: 1476 MB / 3641 MB (538 MB allocated, but free)
Java version: 1.8.0_221-b11, Oracle Corporation, Java HotSpot(TM) 64-Bit Server VM
Look and Feel: com.sun.java.swing.plaf.windows.WindowsLookAndFeel
Screen: \Display0 1920×1080 (scaling 1.00×1.00)
Maximum Screen Size: 1920×1080
Best cursor sizes: 16×16→32×32, 32×32→32×32
VM arguments: [-XX:StartFlightRecording=name=MyRecording2,settings=d:\dbg\gerd.jfc, -XX:FlightRecorderOptions=defaultrecording=true,dumponexit=true,dumponexitpath=e:\ld\perf_20210221_084607.jfr]

[GerdP]

test file

[GerdP]

Another possible fix is to actually use a spatial index for relations in QuadBucketPrimitiveStore as with 20514.quadbuckets.patch​.
In fact I wonder why we do all the complex bbox calculations to "update" the index when the shape of a relation changes when this index isn't used.

[GerdP]

Unfortunately, with 20514.quadbuckets.patch​ applied I see some complex MP are no longered rendered as areas, so probably the index doesn't work well.

[GerdP]

Ah, forget patch 20514.quadbuckets.patch​ and comment:2 . It requires more changes to actually maintain the index. With the simple patch no relations are found and thus tests are very fast but also very wrong ;)
With the corrected patch I see no performance improvement for this case. The bbox calculations are needed.

[GerdP]

patch adapted for r18225, to be applied after next release

[Don-vip]

Milestone renamed

[GerdP]

In 18275/josm:

fix #20514: Possible poor performance when validating selection

• Improve performance of validator when a small selection is tested (selected objects or on upload) and there are objects with large bboxes which cover a lot of objects