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

[Sergey Bylokhov]

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

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.