[Patch] MapCSS rules using index are slow

[GerdP]

For the validator we have several rules like this:

way >[index=1] node,
way >[index=-1] node {
  set first_last_node;
}

The current implementation for the index test works like this:
Perform a sequential search for the given node in the parent way. If found, compare the position with the value given with index.
I think it should work the other way around: Check if the node at the given position exists and if so compare it with the given node.

[GerdP]

Probably not a problem with real OSM data. I've noticed this with a generated file containing coastline data for Great Britain. The data has several ways with 64000 nodes. Only with this extreme case the sequential search is a problem.

For normal data the additional checks to avoid this search are even more complex.

[GerdP]

The attached patch improves performance drastically for the mentioned special cases, saw no changes with average data.
is it worth the additional code?

[Don-vip]

I'd say yes. Just make the firstAndLastOnly a private method so that the calling code simplifies to:

private boolean firstAndLastOnly() {
    for (Condition c : link.conds) {
        if (!(c instanceof IndexCondition) || !((IndexCondition) c).isFirstOrLast) {
            return false;
        }
    }
    return true;
}

/// ...

int step = firstAndLastOnly() ? count - 1 : 1;

[GerdP]

In 16199/josm:

fix #18964: MapCSS rules using index are slow
Avoid a sequential search through all nodes when index matches first or last node only