Opened 4 months ago

Closed 4 months ago

Last modified 4 months ago

#17021 closed enhancement (fixed)

[Patch] Missing index for MapCSSTagChecker rules

Reported by: GerdP Owned by: team
Priority: normal Milestone: 18.12
Component: Core Version:
Keywords: performance Cc:


I've noticed that we have a very efficient index for the mappaint rules, but no index at all for the MapCSSTagChecker rules. At the moment, each OSMPrimitive is checked against all rules, and that is very inefficient.
I can't believe that nobody thought about this before so maybe it turned out to be too complex to use the index also for the MapCSSTagChecker rules?

Attachments (3)

val-index-poc.patch (23.3 KB) - added by GerdP 4 months ago.
val-index-v1.patch (13.7 KB) - added by GerdP 4 months ago.
base_constants.patch (8.0 KB) - added by GerdP 4 months ago.

Download all attachments as: .zip

Change History (23)

comment:1 in reply to:  description Changed 4 months ago by Don-vip

Replying to GerdP:

I can't believe that nobody thought about this before

You can believe it, I didn't think about it. Feel free to add it :)

comment:2 Changed 4 months ago by GerdP

Owner: changed from team to GerdP
Status: newassigned

OK, working on it...

Changed 4 months ago by GerdP

Attachment: val-index-poc.patch added

comment:3 Changed 4 months ago by GerdP

I've attached a first patch as a proof of concept. Performance improvement is not as great as expected, but not bad.
For my test cases I see e.g. 7 instead of 13 seconds for Tag checker (MapCSS based).

The unit tests don't work yet, and the patch copies a lot of code.

comment:4 Changed 4 months ago by GerdP

Some thoughts about MapCSS validator rules:
We have quite a lot of rules like this:

way[amenity=ferry_terminal] > node,
way[man_made=pier] > node {
  set node_in_terminal_pier;

It is followed by

way[route=ferry]!:closed >[index= 1] node[amenity!=ferry_terminal][man_made!=pier]!.node_in_terminal_pier!.node_in_ferry_bridge_tunnel:in-downloaded-area,
way[route=ferry]!:closed >[index=-1] node[amenity!=ferry_terminal][man_made!=pier]!.node_in_terminal_pier!.node_in_ferry_bridge_tunnel:in-downloaded-area { 
  throwWarning: tr("Ferry route is not connected to a ferry terminal or branches.");

The first group of tests is executed for each node in the dataset, but only a few nodes in planet.osm will meet the criteria.
The selectors work this way and probably it is good for the rendering rules, but it seems to be completely wrong for the validator rules.
The property .node_in_terminal_pier is only needed to check the rather few ways with route=ferry. I'd prefer to calculate that property only when needed and - in case that the calculation is costly - remember the result once it is calculated so that it is available for the given OSM primitve.
In short: An index can help but it would only be a work around for a completely wrong algorithm which works bottom - up instead of top down, and in this case it doesn't help at all.
I wonder if we can get both, the power of MapCSS syntax and a reasonable performance for both the rendering style and the validator?

Last edited 4 months ago by Don-vip (previous) (diff)

Changed 4 months ago by GerdP

Attachment: val-index-v1.patch added

comment:5 Changed 4 months ago by GerdP

Owner: changed from GerdP to team
Status: assignednew
Summary: Missing index for MapCSSTagChecker rules[Patch] Missing index for MapCSSTagChecker rules

Please review:
The attached patch reduces run time for MapCSSTagChecker by ~ 40-50 per cent. All unit tests work without changes and I see no differences when I work with the validator, means, results look the same and features like the fix button work as usual.

Let me know if I should add more javadoc or new unit tests.

comment:6 Changed 4 months ago by Don-vip

Milestone: 18.12
  • the log should not change from debug to warn, it will pollute bug reports.
  • the switch/case could probably use String constants instead of literals

otherwise looks good. The improvement sounds impressive :)

comment:7 Changed 4 months ago by GerdP

The log change was only for testing, forgot to remove it in the patch.
I did not use String constants because the existing sources also don't. I agree that it would be better.

Changed 4 months ago by GerdP

Attachment: base_constants.patch added

comment:8 Changed 4 months ago by GerdP

Please check base_constants.patch which is a refactoring only patch.
I am not sure about the javadoc for the constants. I am also not sure if those constants should be placed in class Selector. IMHO it could as well be a new class or part of MapCSSStyleSource or somehwere in MapCSSParser.jj

comment:9 Changed 4 months ago by Don-vip

You can drop the "public static final " statements in interfaces, it is implicit. Looks much better! :)

comment:10 Changed 4 months ago by GerdP

In 14461/josm:

see #17021: use constants for selector base strings

This reduces the memory footprint a bit and probably also improves speed of Selector.matchesBase()

comment:11 Changed 4 months ago by GerdP

@Don-vip and michael2402:
I am not happy with the duplication of code in my val-index-v1.patch. Most of the code in helper class IndexData duplicates code in MapCSSStyleSource, but in opposite to MapCSSStyleSource the MapCSSTagChecker iterates over a collection of TagCheck instances instead of Rules and needs the ruleToCheckMap to be able to find the original check.
I found no simple way to avoid the duplication without adding lots of other code.

Besides that many fields for the index in MapCSSStyleSource are now public, e.g. MapCSSStyleSource.nodeRules. I think that it would be better to keep those index structures private. I found no source in JOSM core that seems to use them.
It also looks a bit dangerous to me when both rules and index can be changed by e.g. plugins.

comment:12 Changed 4 months ago by GerdP

In 14462/josm:

see #17021: fix checkstyle issues

comment:13 Changed 4 months ago by Don-vip

There's a unit test failure.

comment:14 Changed 4 months ago by GerdP

In 14466/josm:

see #17021 : fix unit test failure

comment:15 Changed 4 months ago by Don-vip

Why do you wrap the IllegalArgumentException in a new JosmRuntimeException? Can't we simply catch it in an existing clause, like:

} catch (TokenMgrError | IllegalArgumentException e) {
    Logging.warn(tr("Failed to parse Mappaint styles from ''{0}''. Error was: {1}", url, e.getMessage()));

comment:16 Changed 4 months ago by GerdP

The original switch/case still throws a JosmRuntimeException, although it is unlikely. I didn't want to throw a different exception. Besides that I don't care.

comment:17 Changed 4 months ago by GerdP

Resolution: fixed
Status: newclosed

In 14469/josm:

fix #17021 Use MapCSSRuleIndex to speed up MapCSSTagChecker

comment:18 Changed 4 months ago by GerdP

Sorry, I just noticed that comment 16 sounded rude :(
What I tried to say is that I don't know which solution is better. Feel free to change it.

comment:19 Changed 4 months ago by Don-vip

@GerdP: no offense taken, I understood what you meant :)

comment:20 Changed 4 months ago by Don-vip

In 14474/josm:

see #17021 - simplify exception handling

Modify Ticket

Change Properties
Set your email in Preferences
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.