[OpenJDK 2D-Dev] X11 uniform scaled wide lines and dashed lines; STROKE_CONTROL in Pisces

[Denis Lila]

Hi Jim.

I implemented a middle ground between what I sent yesterday and
what we have now: using the array of linked lists only to replace
the quicksort (I think this was your original suggestion).

Unfortunately, this didn't work out (at least according to the
benchmarks). Curves were no different than what we used to have,
while the performance on lines (especially horizontal ones) decreased
significantly.

It's not obvious to me why this happened, so I think now I will put
this type of optimization aside and convert to JNI, where profiling
will be easier (for me - I haven't been able to make OProfile work
for java yet).

Regards,
Denis.

----- "Jim Graham" <james.graham at oracle.com> wrote:

> Hi Denis,
> 
> A generic suggestion - make all of your classes final - that gives the
> 
> compiler the maximum flexibility to inline any methods you write.
> 
> With respect to the algorithm choices:
> 
> I think they key is that the X sorting rarely has any work to do.  The
> 
> first test of "does this edge need to be swapped with the next lower 
> edge" is probably 99.999% guaranteed to be false.  Thus, trying to 
> optimize anything else to simplify swapping is likely a step in the 
> wrong direction.
> 
> The casting may be hurting a bit more, and it is hurting on every
> access 
> to an edge.
> 
> I'm guessing the best model to use would be to write the code to
> assume 
> no swapping is necessary at all.  Get that code as simple and as fast
> as 
> can be.  Then add as little perturbation of that code to manage
> swapping 
> when it is necessary, and that will likely be the optimal 
> implementation.  I think you could probably even do some benchmarking
> on 
> a path that is carefully tested to process lots of edges without any X
> 
> sorting and get that as fast as you can without any swap code, and
> then 
> add the swap code that impacts the performance of that operation as 
> little as possible.  The key is that the swap code have as little
> impact 
> on the performance of the case that never needs any swapping at all 
> first and foremost - then make swapping faster within that
> constraint...
> 
> 			...jim
> 
> On 11/1/10 3:13 PM, Denis Lila wrote:
> > Hi Jim.
> >
> > I implemented your bucket sort idea. I'm not just using the buckets
> > to remove the y-sort. I use them in the iteration through the
> scanlines
> > too. What happens is that on any iteration, the active list is the
> > doubly linked list buckets[nextY-boundsMinY]. I did this because I
> thought
> > less memory would need to be moved around compared to when we just
> kept
> > the active list "pointers" in an array. For example, with doubly
> linked
> > lists we can implement insertion sort with O(1) writes. With arrays
> we
> > have to use O(n) writes. This also allows us to get rid of the the
> edgePtrs
> > array.
> >
> > I ran some benchmarks, and unfortunately I was wrong, somehwere. All
> the tests
> > are at least 10% slower than the insertion sort version of what we
> have now.
> > I can't immediately see why this is. The only thing I can think of
> is that
> > there are a lot of float ->  int casts, but then again, I don't know
> how
> > slow this operation is. It would be good if it's because of the
> casts because
> > it would no longer be an issue when we convert to native.
> >
> > I alo made an unrelated change: I now find the orientation and
> update x0,y0
> > much earlier than we used to. The way I was doing it before was
> silly.
> >
> > Regards,
> > Denis.
> >
> > ----- "Jim Graham"<james.graham at oracle.com>  wrote:
> >
> >> Hi Denis,
> >>
> >> Good news!
> >>
> >> On 10/28/2010 3:27 PM, Denis Lila wrote:
> >>>> If we moved to a Curve class or some other way to
> >>>> consolidate the 3 lists (may be easier in native code), this
> might
> >> win
> >>>> in more cases...
> >>>
> >>> Does that mean you no longer think we should flatten every curve
> as
> >> soon
> >>> as we get it?
> >>
> >> No, I was just discussion the feasibility of that one suggestion
> in
> >> the
> >> context of all of the possibilities of whether or not we took the
> >> other
> >> choices.  If you think that flattening will pay off then we don't
> have
> >>
> >> to worry about the 3 lists.  It was just that when I hacked it in,
> I
> >> still had your 3 lists and so the pros and cons of horizontal edge
> >> sorting were relative to that version of the renderer...
> >>
> >> 			...jim