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

[Sergey Bylokhov]

On 26/10/2018 00:41, Laurent Bourgès wrote:
> I suppose a JEP or RFE is required, isnt it ?

It depends from the changes, but such contributions are welcome!

> 
> 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> <mailto: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.
> 


-- 
Best regards, Sergey.