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

[Jim Graham]

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