8287604: Update MarlinFX to 0.9.4.6

[bourgesl]

Changelog for this MarlinFX 0.9.4.6 release:

The Marlin-renderer 0.9.4.6 release provides one bug fix in Stroker: skip repeated endpoint to preserve mitter orientation: see JDK-8264999, https://bugs.openjdk.org/browse/JDK-8264999

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 See JDK-8274066, https://bugs.openjdk.org/browse/JDK-8274066

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

---

Progress

• [x] Change must not contain extraneous whitespace
• [x] Commit message must refer to an issue
• [ ] Change must be properly reviewed (2 reviews required, with at least 1 Reviewer, 1 Author)

Issue

• JDK-8287604: Update MarlinFX to 0.9.4.6

Reviewing

Using git

Checkout this PR locally:
$ git fetch https://git.openjdk.org/jfx pull/674/head:pull/674
$ git checkout pull/674

Update a local copy of the PR:
$ git checkout pull/674
$ git pull https://git.openjdk.org/jfx pull/674/head

Using Skara CLI tools

Checkout this PR locally:
$ git pr checkout 674

View PR using the GUI difftool:
$ git pr show -t 674

Using diff file

Download this PR as a diff file:
https://git.openjdk.org/jfx/pull/674.diff

[bridgekeeper[bot]]

:wave: Welcome back lbourges! A progress list of the required criteria for merging this PR into master will be added to the body of your pull request. There are additional pull request commands available for use with this pull request.

[johanvos]

@bourgesl can you rename the title of this PR to 8274066: Polygon filled outside its area when very large coordinates are used

[mlbridge[bot]]

Webrevs

• 05: Full - Incremental (0e739a9c)
• 04: Full - Incremental (b348079b)
• 03: Full - Incremental (eb85b946)
• 02: Full - Incremental (f7e5eb5e)
• 01: Full - Incremental (94874a15)
• 00: Full (8859d244)

[bourgesl]

Sorry I forgot to explain why I did not write any new test:

• I wrote a quadrant test in my own project that tests this clipper bug exhaustively, using all combinations, but it was visual, not automated like a robot.
• existing ClipShapeTest already validates using a fuzzy testing approach all clipper possible cases with small coords in range [-300, 300]. The new clipper algorithm in this patch still passes this hardness test on small coords, so no regression is present. I tested up to 10^6 random shapes for every test cases (order 1,2,3) + all cap/join/fill combinations. To conclude, I decided to skip writing another test for this bug.

Cheers

[kevinrushforth]

/reviewers 2

[kevinrushforth]

Would a targeted test for the failing case from the bug report make sense?

[openjdk[bot]]

@kevinrushforth The number of required reviews for this PR is now set to 2 (with at least 1 of role reviewers).

[bourgesl]

Would a targeted test for the failing case from the bug report make sense?

I agree the rule is to have a test, I will write a basic test derived from user's case asap.

[bourgesl]

Would a targeted test for the failing case from the bug report make sense?

I added the HugePolygonClipTest that fails on jdk11, 17 ... but now passes.

[bourgesl]

@kevinrushforth I added a new test: it fails on jfx11 & 17, passes with the patch. Ready for review ?

[kevinrushforth]

I did an initial build / test (on macOS) along with a quick look at the changes. This will take a bit more time to complete. As a P3 regression, it is a possible candidate for fixing during RDP1, provided the fix is safe and well-tested.

General comments:

Why did you need to make a copy of the JDK DualPivotQuicksort class, DualPivotQuicksort20191112Ext? This is a maintenance burden that we don't want without a very compelling reason.

What additional testing would you recommend?

[johanvos]

Building and testing works, I am looking into the diffs as well now. The DualPivotQuicksort20191112Ext seems to be an improved version of what is in java.util. Ideally, we can somehow extend or leverage the version in java.util without duplicating the original code. For testing: one of the tests I would like to do is to see if the complexity increases as expected when increasing coordinates. Since the original Dual-Pivot quicksort has O(n log(n)) time complexity, it should be possible to have an upper bound on the number of invocations.

[bourgesl]

I advocate I did not give more information on the current patch. Do you need a detailled change log ?

Concerning DualPivotQuicksort20191112Ext, it was developped in collaboration with Vladimir to have a new sort algorithm based on two int arrays: a[] vector contains crossing x positions, b[] vector contains the edge indices. Both arrays are returned sorted by a (positions) to satisfy my MergeSort.

It was developped in the following repository (intensively tested like the current DPQS in jdk17 or the new proposed patch for JDK19?): https://github.com/bourgesl/nearly-optimal-mergesort-code

Here are java2d results with complex random polygons (1k to 100k random segments): https://raw.githubusercontent.com/bourgesl/bourgesl.github.io/master/marlin-0.9.4/diff-marlin-094-gain.png from https://github.com/bourgesl/marlin-renderer/releases/tag/v0_9_4_b2 It mostly fixes performance in case of insanely complex polygons; but it could happen with large text blocks + complex fonts or overly detailed maps.

Thanks

[kevinrushforth]

Here are my general review comments.

The new version of Marlin fixes the specific problem identified in 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 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, which is a fork of 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?

[bourgesl]

Hi Kevin, I am running again MapBench tests to determine good conditions proving this DPQS patch has much benefits in real cases. I added a new TextPage (50 lines of long text) scene.

I remember (2019) that dpqs rocks really when the edge density is high (200 to 1000 items to sort per scanline) but it can happen quite easily:

• AA disabled => 8 times more crossings to sort at each scanline (the test case of the plot https://raw.githubusercontent.com/bourgesl/bourgesl.github.io/master/marlin-0.9.4/diff-marlin-094-gain.png)
• zoomed out scene so the all complex paths are really small that maximizes the density, like 1/8 ot 1/20 ... of course, the scene must contain long paths (many edges) like a complex polyline, polygon or text (as shape)

@iaroslavski could you answer the IP / legal question ?

More results soon, Laurent

[iaroslavski]

Hi all, I'm the dpqs author and I worked with Laurent, so the proposed dpqs patch is our own IP that we agree to contribute under OCA to both openjdk & openjfx projects.

[kevinrushforth]

Thank you for confirming.

[bourgesl]

Hi, Time is going short before openjfx 19...

2 options:

• keep dpqs for corner cases and keep my coding life simple
• disable or remove dpqs code in marlinFX for openjfx, so my branches will diverge...

Any advice, @kevinrushforth ?

[kevinrushforth]

keep dpqs for corner cases and keep my coding life simple

I think this approach is fine. Diverging the code would likely make it less stable, and you answered the question about the provenance of the code, so there's no issue there. We should try to get this in before RDP1 of JavaFX 19 if possible.

One more thing, as I wrote in my above comment:

We should file a new JBS Enhancement issue -- similar to what was done for Marlin 0.9.2 via 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.

I took the liberty of filing JDK-8287604 for this enhancement. Can you change the title to:

8287604: Update MarlinFX to 0.9.4.5

[bourgesl]

Thx @kevinrushforth I will look at fixing the test with hidpi very soon

[bourgesl]

I fixed the test using fuzzy logic (green vs red components). Could you @johanvos or @kevinrushforth confirm it passes now on mac ? My macbook is not ready yet to build openjfx...

I will merge with my latest marlin code asap = 0.9.4.6 (2 more bugs fixed), low risk (few lines) if you agree.

Cheers, Laurent

[kevinrushforth]

Yes, the tests now all pass on my MacBook Pro which has a retina display.

I will merge with my latest marlin code asap = 0.9.4.6 (2 more bugs fixed), low risk (few lines) if you agree.

Yes, that would be fine. Let's change the titles of this PR and the JBS issue to reflect the .6 patch version. Also, can you merge in the latest upstream master? Your branch is very out of date.

Since I am just starting the review, I'm not sure whether we will be able to get this in before the RDP1 deadline, so it will either just barely make JavaFX 19 (if right before RDP1) or it can be integrated early in JavaFX 20.

[kevinrushforth]

I will merge with my latest marlin code asap = 0.9.4.6 (2 more bugs fixed), low risk (few lines) if you agree.

(but don't change your branch name or would need to create a new PR, which doesn't seem worth it)

[bourgesl]

Thanks @kevinrushforth for instructions. The dpqs part and stroker changes were released in marlin 0.9.4.5 publicly on my github... so it passed the production to me. If you have any question, please ask.

Cheers, Laurent (covid+ since wednesday)

[bourgesl]

See https://bourgesl.github.io/github-release-stats/?username=bourgesl&repository=marlin-renderer

~ 1000 downloads on 0.9.4.5 releases...

[kevinrushforth]

At this point, due to time constraints, we will need to do this early in JavaFX 20 rather than late in JavaFX 19 (which is probably better anyway).

[bourgesl]

This PR corresponds to Marlin-FX 0.9.4.5 released in oct 2021, it is all good to go!

Allright, just tell me when you will have time to review this large patch, I will be ready (on vacation between 07.22 and 08.22, but online and working on new bug fixes as no hurry).

Bye, Laurent

[bourgesl]

@kevinrushforth could you tell me approximately when you will have free cycles to review this PR ? I plan to make minor updates by that time.

[kevinrushforth]

I plan to get to this next week.

[kevinrushforth]

@bourgesl One more thing: can you please merge the latest upstream master into your branch, since it is now several months out of date.