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

[Laurent Bourgès]

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> 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
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://mail.openjdk.java.net/pipermail/2d-dev/attachments/20181023/6fbfcf99/attachment.html>