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

[Laurent Bourgès]

Sergey,

Le mer. 24 oct. 2018 à 23:50, Sergey Bylokhov <Sergey.Bylokhov at oracle.com>
a écrit :

> I have no comments about the current proposal(results is good), but is
> that really necessary to have this implementation in native code?
>

1. I read the academic papers "Sort Race", 2016 and I will experiment their
best merge6 sort in Marlin to optimize even better the sort of crossings
(x).

It reports that linux qsort() is instezd a mergesort (sedgewick), not
optimal for ordered/reversed runs, as java Timsort does: stdlib is up to 2
times slower (worst case).

See https://arxiv.org/abs/1609.04471

2. My goal consists in fixing the worst case here, as demonstrated by this
case. I may port my MergeSort to C if interested.

Later we could get rid of this native nln-AA pipeline if we switch to
Marlin NonAA renderer like OpenJFX.

I suppose a JEP or RFE is required, isnt it ?

Cheers,
Laurent


> On 23/10/2018 13:37, Laurent Bourgès wrote:
> > 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.
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://mail.openjdk.java.net/pipermail/2d-dev/attachments/20181026/e4a97bbd/attachment.html>