[OpenJDK 2D-Dev] Speed of drawPolyline on JDK11

[Sergey Bylokhov]

Hi, Laurent.

I do not think that we should postpone it to the next version.
Just send the changes when they are ready, if the review fails
to take place at the right time, then the fix will be
moved to the jdk13.

On 20/11/2018 00:28, Laurent Bourgès wrote:
> As OpenJDK12 RDP1 is coming soon, I propose this plan:
> - integrate this basic fix in ShapeSpanIterator.c code to use stdlib sort (mergesort on linux)
> - integrate a very simple patch in Marlin renderer to disable insertion sort for large arrays: 0.5s to 0.25s, few LOC
> - postpone my changes to Marlin sort & Marlin nonAA renderer integration in OpenJDK 13
> 
> Will you have time to review 2 small patchs on time ?


> 
> Cheers,
> Laurent
> 
> Le mar. 23 oct. 2018 à 22:37, Laurent Bourgès <bourges.laurent at gmail.com <mailto:bourges.laurent at gmail.com>> a écrit :
> 
>     Phil,
>     I quickly modified the final update & sort loop to:
>     - move sort in another block
>     - use qsort() using a new comparator sortSegmentsByCurX
> 
>     This improves performance in PolyLineTest by 3 times: ~1s vs 3.5s !
>     Apparently qsort() is not optimal (comparator can not be inlined by c) so it may explain why Marlin (0x0 sampling) is still 2 times faster with its custom merge-sort (in-place).
> 
>     Any idea to improve C sort ?
>     Is it good enough ?
> 
>     - USE_QSORT_X: 1
>     oct. 23, 2018 10:15:29 PM polylinetest.Canvas paintComponent
>     INFOS: Paint Time: 1,081s
>     INFOS: Paint Time: 1,058s
>     INFOS: Paint Time: 1,067s
> 
>     - USE_QSORT_X: 0
>     oct. 23, 2018 10:18:50 PM polylinetest.Canvas paintComponent
>     INFOS: Paint Time: 3,318s
>     INFOS: Paint Time: 3,258s
>     INFOS: Paint Time: 3,273s
> 
>     Patch:
>     diff -r 297450fcab26 src/java.desktop/share/native/libawt/java2d/pipe/ShapeSpanIterator.c
>     --- a/src/java.desktop/share/native/libawt/java2d/pipe/ShapeSpanIterator.c    Tue Oct 16 23:21:05 2018 +0530
>     +++ b/src/java.desktop/share/native/libawt/java2d/pipe/ShapeSpanIterator.c    Tue Oct 23 22:31:00 2018 +0200
>     @@ -1243,6 +1243,18 @@
>           }
>       }
> 
>     +/* LBO: enable (1) / disable (0) qsort on curx */
>     +#define USE_QSORT_X (0)
>     +
>     +static int CDECL
>     +sortSegmentsByCurX(const void *elem1, const void *elem2)
>     +{
>     +    jint x1 = (*(segmentData **)elem1)->curx;
>     +    jint x2 = (*(segmentData **)elem2)->curx;
>     +
>     +    return (x1 - x2);
>     +}
>     +
>       static jboolean
>       ShapeSINextSpan(void *state, jint spanbox[])
>       {
>     @@ -1378,16 +1390,28 @@
>                   seg->curx = x0;
>                   seg->cury = y0;
>                   seg->error = err;
>     +        }
> 
>     -            /* Then make sure the segment is sorted by x0 */
>     -            for (new = cur; new > lo; new--) {
>     -                segmentData *seg2 = segmentTable[new - 1];
>     -                if (seg2->curx <= x0) {
>     -                    break;
>     +        if (USE_QSORT_X && (hi - lo) > 100)
>     +        {
>     +            /* use quick sort on [lo - hi] range */
>     +            qsort(&(segmentTable[lo]), (hi - lo), sizeof(segmentData *),
>     +                    sortSegmentsByCurX);
>     +        } else {
>     +            for (cur = lo; cur < hi; cur++) {
>     +                seg = segmentTable[cur];
>     +                x0 = seg->curx;
>     +
>     +                /* Then make sure the segment is sorted by x0 */
>     +                for (new = cur; new > lo; new--) {
>     +                    segmentData *seg2 = segmentTable[new - 1];
>     +                    if (seg2->curx <= x0) {
>     +                        break;
>     +                    }
>     +                    segmentTable[new] = seg2;
>                       }
>     -                segmentTable[new] = seg2;
>     +                segmentTable[new] = seg;
>                   }
>     -            segmentTable[new] = seg;
>               }
>               cur = lo;
>           }
> 
>     Cheers,
>     Laurent
> 
>     Le mar. 23 oct. 2018 à 08:30, Laurent Bourgès <bourges.laurent at gmail.com <mailto:bourges.laurent at gmail.com>> a écrit :
> 
>         Phil,
>         Yesterday I started hacking ShapeSpanIterator.c to add stats: the last stage (sort by x0) is the bottleneck.
>         In this case every sort takes up to 15ms per pixel row !
> 
>         I will see if I can adapt Marlin's MergeSort.java to C to have an efficient sort in-place.
>         Do you know if libawt has already an efficient sort instead of porting mine ?
> 
>         PS: "To save the planet, make software more efficient" is my quote of the day !
> 
>         Cheers,
>         Laurent
> 


-- 
Best regards, Sergey.