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.laur...@gmail.com
<mailto:bourges.laur...@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.
