[OpenJDK Rasterizer] Marlin renderer contribution for review

[Jim Graham]

One thing I'd like to hear from Joe or Phil or Dalibor is if it is OK 
for us to check in the current version to the graphics-rasterizer-dev 
java.net repo as long as we resolve this before we push to the client or 
master repos?  I'd like to get Laurent's current work in so that we can 
start tweaking it and right now it is a huge webrev to slog through for 
even simple changes.  I'm guessing that since every changeset in the 
master repo requires a bug id that we'll end up collapsing this initial 
push and a number of subsequent tweaks into a single changeset for the 
eventual integration so any files that we obsolete during that process 
may never make it to the main repos.

Or do we want "due diligence" of contributing sources on any change that 
gets hosted on any repo (even sandboxes) on java.net?

			...jim

On 3/27/15 2:19 AM, Laurent Bourgès wrote:
> 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
>     <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
>         <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
>         <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