[Patch] MapCSS uses slow sorted ArrayLists

[michael2402]

Currently, MapCSS creates and sorts an ArrayList for every OSM primitive it handles. This is pretty slow because we only want to walk the rules in the right order.

Speed can be improved significantly (30% for render phase 1 in styles that use many non-key-value-rules).

Here is a patch:
​https://github.com/michaelzangl/josm/commit/b547b1f4f5b055213ce5140d6176c48229fb7351

The dupplicate test never triggered for me, but I left it there just to be sure and not break anything.

[bastiK]

Replying to openstreetmap@…:

Currently, MapCSS creates and sorts an ArrayList for every OSM primitive it handles. This is pretty slow because we only want to walk the rules in the right order.

Speed can be improved significantly (30% for render phase 1 in styles that use many non-key-value-rules).

Great! Which style did you use?

Here is a patch:
​https://github.com/michaelzangl/josm/commit/b547b1f4f5b055213ce5140d6176c48229fb7351

Does it work like this? According to Javadoc, iteration over PriorityQueue is not sorted.

The dupplicate test never triggered for me, but I left it there just to be sure and not break anything.

I think this test is not needed.

[michael2402]

Replying to bastiK:

Replying to openstreetmap@…:

Currently, MapCSS creates and sorts an ArrayList for every OSM primitive it handles. This is pretty slow because we only want to walk the rules in the right order.

Speed can be improved significantly (30% for render phase 1 in styles that use many non-key-value-rules).

Great! Which style did you use?

I used the coloured streets style. That style has lots of non-key-value nodes.

Here is a patch:
​https://github.com/michaelzangl/josm/commit/b547b1f4f5b055213ce5140d6176c48229fb7351

Does it work like this? According to Javadoc, iteration over PriorityQueue is not sorted.

No, it does not work. I cut a bit too much.
Here is the corrected patch: ​https://github.com/michaelzangl/josm/commit/45b6b3b88171f941af420d442690c3a2b997087c

This is probably also why render times were that good. They were reduced only by max. 15% in my tests with the new patch (Same setting, with and without patch). I could find some situations where the time required to walk the queue increased compared to walking an array list, but in most situations it decreased. I tested all this using sort of a benchmark comparing the new and old version:
​https://github.com/michaelzangl/josm/tree/mapcss-priorityqueue-benchmark
Benchmarking this way (running old and new version for each node) is not that easy, because the second call accessed the cached memory the first one used.

The dupplicate test never triggered for me, but I left it there just to be sure and not break anything.

I think this test is not needed.

I checked the rest of the source. Styles are added only once from the css file, so unless any plugin messes with this, we should be fine removing that check.

[bastiK]

In 8141/josm:

applied #11231 - MapCSS: Use PriorityQueue instead of sorting an ArrayList (patch by Michael Zangl)

[bastiK]

There seems to be even an improvement for the default style, nice!