Sergey, Le mer. 24 oct. 2018 à 23:50, Sergey Bylokhov <sergey.bylok...@oracle.com> a écrit :
> I have no comments about the current proposal(results is good), but is > that really necessary to have this implementation in native code? > 1. I read the academic papers "Sort Race", 2016 and I will experiment their best merge6 sort in Marlin to optimize even better the sort of crossings (x). It reports that linux qsort() is instezd a mergesort (sedgewick), not optimal for ordered/reversed runs, as java Timsort does: stdlib is up to 2 times slower (worst case). See https://arxiv.org/abs/1609.04471 2. My goal consists in fixing the worst case here, as demonstrated by this case. I may port my MergeSort to C if interested. Later we could get rid of this native nln-AA pipeline if we switch to Marlin NonAA renderer like OpenJFX. I suppose a JEP or RFE is required, isnt it ? 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.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. >
