Modify

Opened 9 months ago

Closed 7 months ago

Last modified 4 days ago

#14485 closed enhancement (fixed)

[Patch] MapCSS sorting speed

Reported by: michael2402 Owned by: michael2402
Priority: normal Milestone: 17.05
Component: Core mappaint Version:
Keywords: mapcss performance Cc:

Description

I experimented with the sorting speed of MapCSS.

This is what I got on 8 cores for the big MapCSS performance test:

  • Current implementation: 116ms
  • Using parallel sort instead of default sort: 40ms
  • Removing the branches for the comparator function: 53ms
  • Both: 28ms

The disadvantage of the branch removal is that I changed the z-index to be a fixed-point decimal (24 bits of which 8 are behind the decimal). This allows to pack the Z-Indexes and the flags into a long that can then be compared more easily.

If there are no objections to this rescriction I'd like to commit it.

Attachments (2)

styled-map-renderer-precompute-order.patch (3.7 KB) - added by michael2402 9 months ago.
styled-map-renderer-use-parallel-sort.patch (1.2 KB) - added by michael2402 9 months ago.

Download all attachments as: .zip

Change History (18)

Changed 9 months ago by michael2402

Changed 9 months ago by michael2402

comment:1 in reply to:  description Changed 9 months ago by bastiK

Replying to michael2402:

The disadvantage of the branch removal is that I changed the z-index to be a fixed-point decimal (24 bits of which 8 are behind the decimal).

So in decimal terms, the maximum z-index is 65535 and it should not have more than 2 digits after the decimal point? Sounds okay to me.

comment:2 Changed 8 months ago by michael2402

Summary: MapCSS sorting speed[Patch] MapCSS sorting speed

comment:3 Changed 8 months ago by Don-vip

Milestone: 17.0317.04

comment:4 Changed 8 months ago by michael2402

Owner: changed from team to michael2402

comment:5 Changed 7 months ago by Don-vip

Milestone: 17.0417.05

comment:6 Changed 7 months ago by michael2402

Resolution: fixed
Status: newclosed

In 12054/josm:

Fix #14485: Increase sorting speed by removing compareTo complexity.

comment:7 Changed 7 months ago by bastiK

Unit tests are failing.

comment:8 Changed 7 months ago by stoecker

Causes following warnings:

    [javac] /var/lib/jenkins/jobs/JOSM-Integration/workspace/jdk/JDK8/src/org/openstreetmap/josm/data/osm/visitor/paint/StyledMapRenderer.java:146: warning: [OperatorPrecedence] Use grouping parenthesis to make the operator precedence explicit
    [javac]             long highestBitMask = 1L << totalBits - 1;
    [javac]                                                   ^
    [javac]     (see http://errorprone.info/bugpattern/OperatorPrecedence)
    [javac]   Did you mean 'long highestBitMask = 1L << (totalBits - 1);'?
    [javac] /var/lib/jenkins/jobs/JOSM-Integration/workspace/jdk/JDK8/src/org/openstreetmap/josm/data/osm/visitor/paint/StyledMapRenderer.java:149: warning: [OperatorPrecedence] Use grouping parenthesis to make the operator precedence explicit
    [javac]             return signBit | value & valueMask;

The second seems correct and should obviously be "signBit | (value &valueMask)". Should the first really be "1L << (totalBits - 1)? Please add the correct brackets.

comment:9 Changed 7 months ago by michael2402

In 12078/josm:

See #14485: Fix and test MapCSS sorting.

This adds support for real floating point values instead of fixed point decimal and tests for corner cases (infinity, nan, ...)

comment:10 Changed 7 months ago by bastiK

Could you please document the limitations?

Btw., it wouldn't be a problem to loose one or two bits in the exponent, e.g. S/360 floats have only 7 bits in the exponent.

comment:11 Changed 6 months ago by michael2402

In 12208/josm:

See #14485: Fix order of disabled style elements

comment:12 Changed 5 days ago by Klumbumbus

So are there limitations in use of z-index, object-z-index and major-z-index after r12054 and r12078?

comment:13 Changed 4 days ago by michael2402

Yes. We do not support 32 bit floats but only 24 bit floats.

You should not notice a much of difference unless your are using z-index values with more than 4 decimal digits - which may only happen when using complex computations.

If you encounter any issues with shorter z-indexes, there is a bug somewhere ;-)

comment:14 Changed 4 days ago by Klumbumbus

So what exactly is the range that can be used? Can you please document at wiki:Help/Styles/MapCSSImplementation?

Last edited 4 days ago by Klumbumbus (previous) (diff)

comment:15 Changed 4 days ago by michael2402

How exact should the documentation be? As far as I know, MapCSS has no real requirements on floating point values since there is no real spec for it.

The numeric range is approx -3.4 * 1038 ... 3.4 * 1038, with a precision of ~5 decimal digits. So having 1.0001 and 1.0002 should be fine, and having 10001 and 10002 should be fine as well ;-).

There are many other limitations on floating point values we have (e.g. numbers are not allowed to start with a '.'). I don't think we can document them all - if we would do that we could as well write a real MapCSS specification with exact grammar and so on and then state our differences.

Last edited 4 days ago by michael2402 (previous) (diff)

comment:16 Changed 4 days ago by Klumbumbus

Modify Ticket

Change Properties
Set your email in Preferences
Action
as closed The owner will remain michael2402.
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.