[OpenJDK Rasterizer] Marlin renderer contribution for review

[Laurent Bourgès]

Hi Phil & Joe,

Thanks for your opinions, but let me explain the impact of ceil(float) in
the Marlin renderer:
- for every line, 2 ceil calls are performed => depends on the shape
complexity
- for every rendering pass, typically every 32 pixel stride, 4 ceil calls
are performed => depends on the shape's vertical coverage

=> In my benchmarks, I experienced that the Math.ceil(float) method is
called million times (I can gather numbers if you want).

As I want to achieve the best possible performance, I used that "trick" to
have a faster (but accurate enough) alternative which gives in my MapBench
benchmarks ~ 3% performance.

I advocate 3% is small but it will depend on the drawing complexity: the
more complex your shapes are, the bigger is the speedup.

Since JDK 7 the JDK has used a pure-Java implementation of floor and ceil:
>
>     6908131 Pure Java implementations of StrictMath.floor(double) &
> StrictMath.ceil(doublele)
>     https://bugs.openjdk.java.net/browse/JDK-6908131
>

Thanks for the pointer, I will look at the StrictMath.ceil code to see if I
can optimize it for general use (any kind of inputs).


> So in this case I would suggest we follow the implications of Knuth's
> observation that "premature optimization is the root of all evil" and only
> look to further speed up floor / ceil if there is some appreciable
> performance problem  with them today as shown in benchmarks, etc.
>

I know that principle, but I am pragmatic: ceil(float) has a noticeable
impact on rendering performance according to my benchmarks which are based
on real map use cases (geoserver).

On 3/25/2015 2:44 PM, Phil Race wrote:
>
>> FastMath: http://cr.openjdk.java.net/~lbourges/marlin/marlin.3/src/
>> java.desktop/share/classes/sun/java2d/marlin/FastMath.java.html
>>
>> says its from here : http://www.java-gaming.org/index.php?topic=24194.0
>>
>> but that in turn may be from somewhere else unknown ..
>>
>> Aside from the provenance of the code, and even though its a 'trick'
>> rather than a body of code,
>> other options are preferable, so it might be interesting to get Joe's
>> input on what other options
>> there are that maintain correctness and give better performance - I
>> assume this gives
>> a measurable benefit ?
>>
>
1. I agree that trick comes from a java forum, but it is more an idea that
a body of code:
    ceil = upper_bound_integer - (int) ( upper_bound_double - x_float)

As I said, the code could be rewritten to ensure values are positive so a
integer cast is enough. Of course, the floating-point precision can have
tricky side-effects (and also overflow / NaN handling).

2. Yes, it gives speedup: here are the synthetic benchmark results with /
without the trick enabled [-Dsun.java2d.renderer.useFastMath=true|false] :

==> marlin_TL_Tile_1.log <==

Tests    27    9    9    9
Threads    4    1    2    4
Pct95    132.498    131.176    132.641    133.677

==> marlin_TL_Tile_noFM_3.log <==

Tests    27    9    9    9
Threads    4    1    2    4
Pct95    135.669    134.989    135.541    136.477


>
>> Is the limitation on the input range an issue ? There's no test here for
>> that, and
>> correctness-wise this does seem to break down if the input is NaN.
>>
>
1. In Pisces / Marlin, ceil is used in a specific context to upper integer
values:

    private void addLine(float x1, float y1, float x2, float y2) {
...
        /* convert subpixel coordinates (float) into pixel positions (int)
*/
        // upper integer (inclusive)

        final int firstCrossing = Math.max(FastMath.ceil(y1), _boundsMinY);

        // upper integer (exclusive ?)
        final int lastCrossing  = Math.min(FastMath.ceil(y2),
_boundsMaxY);


    boolean endRendering() {
...

        /* bounds as inclusive intervals */
        final int spminX = Math.max(Math.ceil(edgeMinX), boundsMinX);
        final int spmaxX = Math.min(Math.ceil(edgeMaxX), boundsMaxX - 1);
        final int spminY = Math.max(Math.ceil(edgeMinY), boundsMinY);
        final int spmaxY = Math.min(Math.ceil(edgeMaxY), boundsMaxY - 1);

However, to improve the coordinate rounding arround subpixel centers, it
should be rewritten (as jim pointed out):
ceil(float) => ceil(x - 0.5f) or floor(x + 0.5f)

Anway, the returned values are then clamped into [min | max] ranges.

Do you know any faster alternative to do such rounding + boundary clipping ?


2. I agree it does not handle overflow or NaN but that is a real problem
with Pisces in general: I think it should be tested and fixed in a second
step.

For example, I you draw a vertical or horizontal line with x / y = NaN then
it fails !
Moreover, as coordinates are multiplied by 8, it can overflow float and
integer maximum values !!

I think clipping should be implemented to ensure all coordinates belongs to
the clip boundaries.


To conclude, I propose to remove the FastMath utility class now and later
use a new Renderer utility method to perform both rounding and bound checks
at the same time with your help.

Cheers,
Laurent
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://mail.openjdk.java.net/pipermail/graphics-rasterizer-dev/attachments/20150327/a901d2ab/attachment-0001.html>