Modify

Opened 5 months ago

Closed 3 months ago

Last modified 2 months 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 5 months ago.
styled-map-renderer-use-parallel-sort.patch (1.2 KB) - added by michael2402 5 months ago.

Download all attachments as: .zip

Change History (13)

Changed 5 months ago by michael2402

Changed 5 months ago by michael2402

comment:1 in reply to:  description Changed 5 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 4 months ago by michael2402

Summary: MapCSS sorting speed[Patch] MapCSS sorting speed

comment:3 Changed 4 months ago by Don-vip

Milestone: 17.0317.04

comment:4 Changed 4 months ago by michael2402

Owner: changed from team to michael2402

comment:5 Changed 3 months ago by Don-vip

Milestone: 17.0417.05

comment:6 Changed 3 months ago by michael2402

Resolution: fixed
Status: newclosed

In 12054/josm:

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

comment:7 Changed 3 months ago by bastiK

Unit tests are failing.

comment:8 Changed 3 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 3 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 3 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 2 months ago by michael2402

In 12208/josm:

See #14485: Fix order of disabled style elements

Modify Ticket

Change Properties
Set your email in Preferences
Action
as closed The owner will remain michael2402.
as The resolution will be set. Next status will be 'closed'.
The resolution will be deleted. Next status will be 'reopened'.

Add Comment


E-mail address and name can be saved in the Preferences.

 
Note: See TracTickets for help on using tickets.