RFR: 8274066: Polygon filled outside its area when very large coordinates are used [v2]

[Kevin Rushforth]

On Mon, 10 Jan 2022 00:04:00 GMT, Laurent Bourgès <lbourges at openjdk.org> wrote:

>> Changelog for this MarlinFX 0.9.4.5 release:
>> 
>> The Marlin-renderer 0.9.4.5 release provides bug fixes on Marlin's path clipper:
>> - improved Stroker to handle huge coordinates, up to 1E15
>> - improved PathClipFilter (filler) to handle huge coordinates, up to 1E15
>> 
>> 
>> This is the Marlin-renderer 0.9.4.3 release providing few bug / enhancement fixes in the MarlinRenderingEngine:
>> - Update DPQS to latest OpenJDK 14 patch
>> - Improve cubic curve offset computation
>> 
>> 
>> The Marlin-renderer 0.9.4.2 release provides a single long-standing bug fix in the MarlinRenderingEngine: 
>> - JDK-8230728, https://bugs.openjdk.java.net/browse/JDK-8230728.
>> 
>> 
>> Marlin-renderer 0.9.4.1 provides only a single bug fix in the path clipper, reported first against JavaFX 11: 
>> - JDK-8226789, https://bugs.openjdk.java.net/browse/JDK-8226789.
>> 
>> 
>> This is the Marlin-renderer 0.9.4 release providing an updated Dual Pivot Quick Sort (19.05) as its internal sorter faster than the Marlin's optimized MergeSort (x-position + edge indices) for arrays larger than 256.
>> 
>> Special Thanks to Vladimir Yaroslavskiy that provided me up-to-date DPQS 19.05 with many variants, improving almost-sorted datasets. We are collaborating to provide a complete Sort framework (15 algorithms, many various datasets, JMH benchmarks) publicly on github:
>> see https://github.com/bourgesl/nearly-optimal-mergesort-code
>
> Laurent Bourgès has updated the pull request incrementally with one additional commit since the last revision:
> 
>   added test for huge polygon coords

Here are my general review comments.

The new version of Marlin fixes the specific problem identified in [JDK-8274066](https://bugs.openjdk.java.net/browse/JDK-8274066). It also seems inherently more robust for large coordinates, which is a plus. All my testing looks good, although the new system test fails for me on my Mac:


HugePolygonClipTest > TestHugePolygonCoords FAILED
    java.lang.AssertionError: bad pixel at (300, 198) = -16711426 expected: -16776961
        at org.junit.Assert.fail(Assert.java:89)
        at test.com.sun.marlin.HugePolygonClipTest.checkColumn(HugePolygonClipTest.java:231)
        at test.com.sun.marlin.HugePolygonClipTest.lambda$TestHugePolygonCoords$1(HugePolygonClipTest.java:207)


I have a Retina display, so it might have something to do with that. I recommend sampling a few pixels at locations slightly away from the boundaries to avoid this problem.

This updated version of Marlin is a large change, especially when coupled with the performance improvements provided by the newly added Dual-Pivot QuickSort, DQPS (more on this below). It's really an enhancement to update to a new version of Marlin rather than a bug fix. It's out of scope to try and get into JavaFX 18 during ramp-down. This should go into `master` for JavaFX 19 so it can get more bake time. We should file a new JBS Enhancement issue -- similar to what was done for Marlin 0.9.2 via [JDK-8204621](https://bugs.openjdk.java.net/browse/JDK-8204621) rather than using a narrow bug, since that bug is only part of what's being done. The current bug can either be added to the PR, or else that JBS bug (JDK-8274066) can be closed as a duplicate of the new Enhancement.

Regarding the Dual-Pivot QuickSort (DQPS) code, I'm still not sure that the extra maintenance burden of having our own modified copy of DPQS is justified. It seems like the improvements are mostly in corner cases. Do you have any real world examples that would correlate to the benchmark cases you ran?

I also have a question about the provenance of this DQPS code. Much of it is already in the JDK, which is OK (leaving aside the maintenance aspect of having a copy of the code), so my questions are around the modifications. You indicated that this is being developed by you and Vladimir in [bourgesl/nearly-optimal-mergesort-code](https://github.com/bourgesl/nearly-optimal-mergesort-code), which is a fork of [sebawild/nearly-optimal-mergesort-code](https://github.com/sebawild/nearly-optimal-mergesort-code). Can you assert that the modifications you are making to the code imported from the JDK are entirely form you? Or from other OCA signatories who have explicitly agreed to contribute these modifications under the terms of the OCA?

-------------

PR: https://git.openjdk.java.net/jfx/pull/674