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