[OpenJDK 2D-Dev] Fwd: CubicCurve2D.solveCubic and containment/intersection bugs.

Fri Feb 4 01:59:39 UTC 2011

Hi Jim.

> The code changes look good to go.

Nice! Thanks.

> I'm guessing there is no regression test for this as it is entirely
> performance. If this fixes any quality or correctness bugs it would be
> nice to develop an automated test case to go back with it, but if it
> is
> just performance then they don't usually have tests...

This changeset would be entirely performance and I don't have a test
for it. I do however have a few regression tests that I would like to
push. They're already in icedtea:
http://icedtea.classpath.org/hg/icedtea6/file/12df222ab029/patches/rendering-engine-tests.patch
One of them doesn't have a sun bugid, so we should probably just skip it.
I'm not sure how we would include them, since they all test bugs that
have already been fixed.

Regards,
Denis.

----- Original Message -----
> Thanks Denis,
> 

> 

> 
> ...jim
> 
> On 2/3/2011 5:13 PM, Denis Lila wrote:
> > Hi Jim.
> >
> >> breakPtsAtTs - [whine]I sort of feel as if this method is trying to
> >> abstract something that is not really that bad to just do inline
> >> and
> >> in
> >> trying to apply the abstraction it might make the calling code
> >> slightly
> >> simpler, but it created a mess here by trying to shoehorn a natural
> >> inline process into an "Iterator" paradigm. :-( [/whine] Having
> >> said
> >> that, the new changes to this look good. ;-)
> >
> > I agree that the complexity of the abstraction is higher than what
> > it saves
> > in the calling code (but I also think it makes the calling code more
> > than
> > slightly simpler since it saves us one or two local variables in the
> > caller).
> > The reason I wrote this method was because I was hoping to perhaps
> > use it in
> > Dasher too (like I describe in the TODO), and I think I was using it
> > in some
> > other place at the time. Now the only calling function is in
> > Stroker, so I
> > could inline it if you want, but I'm not too eager to do that,
> > because what
> > we have works, and we wouldn't gain much from inlining.
> >
> >> LengthIterator comment - any reason to delete it? Too hard to keep
> >> it
> >> up to date?
> >
> > I reintroduced it. I don't even remember deleting it, or why I did
> > so :/
> >
> >> line 342 - 0/0 == NaN which fails all tests, but should be
> >> considered
> >> to
> >> have low acceleration, no? Also, what about the test:
> >> within(len1, len2, len2*err)
> >> would that have similar properties? The only advantage here is that
> >> multiplies are usually faster than divides.
> >
> > They are equivalent. I'm using your version now. This also fixes the
> > 0/0
> > problem.
> >
> >> line 176 and 183-186 - does Math.scalb() go faster for these?
> >
> > scalb is slightly slower on my machine (by about 5%).
> >
> >> line 190 - what happened to the adjustment that used to be at line
> >> 359
> >> (i.e. dx,dy greater than INC_BND)? Did it not save very many lines
> >> in
> >> the output?
> >
> > I eliminated it because of how the dx and ddx values change for
> > quadratic
> > curves. I don't remember exactly what was going on, but one of them
> > stays
> > constant so every test had the same outcome and was therefore a
> > waste.
> > A better explanation can be found in ProcesPath.c (which is one of
> > the
> > palces from where I got the algorithm).
> >
> >> line 80 - technically "ecur>= 0" would work as well and would
> >> probably
> >> be cheaper on most architectures if the condition codes are already
> >> set
> >> by the fetch - if not then comparing to 0 is usually cheaper than
> >> comparing to a number. Though, I prefer using 0 as the terminator
> >> since
> >> it doesn't require an Arrays.fill() (though it does require biasing
> >> the
> >> stored indices by +1 so that they aren't null which may offset some
> >> of
> >> the array fill savings).
> >
> > I didn't implement this because of your last point. I could, if you
> > think the benefits would definitely be worth it.
> >
> > I've implemented all your other suggestions.
> >
> > Thank you,
> > Denis.
> >
> > ----- Original Message -----
> >> Hi Denis,
> >>
> >> Curve.java
> >>
> >> line 242 - remove "both"
> >>
> >
> >>
> >> Dasher.java
> >>
> >>
> >
> >>
> >> line 385 - cache the "haveLowAccel" return value until the curve is
> >> redivided?
> >>
> >> caching flatLeafCoef - If you add cache[3] and save the value to
> >> muliply
> >> by t (either -z or -y) then you wouldn't need to recalculate x,y,z
> >> every
> >> time:
> >> if (cache[2]< 0) {
> >> float x = ..., y = ...;
> >> if (type == 8) {
> >> float z = ...;
> >> cache[0..2] = ...;
> >> cache[3] = -z;
> >> } else {
> >> cache[0..2] = ...;
> >> cache[3] = -y;
> >> }
> >> }
> >> float a=...;
> >> float b=...;
> >> float c=...;
> >> float d=t*...;
> >>
> >> Helpers.java
> >>
> >> line 147 {}
> >>
> >> PiscesRE.java
> >>
> >> lines 286,288 - (dog whimpers) I noticed that the two lines you've
> >> modified are the only 2 lines in the comment that have apostrophes
> >> that
> >> my gnuemacs is allergic to. Any chance you'd get rid of them for
> >> me?
> >> ;-)
> >>
> >> Renderer.java
> >>
> >
> >>
> >> line 87 - should this be commented out at some point?
> >>
> >> line 135 - "NEXT and OR" and "indices"
> >>
> >
> >>
> >> line 188 - it might look cleaner to just declare these inside the
> >> loop
> >> and add them from x0,y0 rather than +=. I'm not sure if it will
> >> make a
> >> difference in performance, though, given the vagaries of FPU
> >> scheduling.
> >>
> >
> >>
> >> line 286 - in my version I moved the calculation of slope up above
> >> here
> >> and just used the sign of the slope as the test for x ordering.
> >> Note
> >> that if the slope calculations immediately precedes the "if (slope<
> >> 0)"
> >> test then the condition codes are likely already set as a side
> >> effect
> >> of
> >> the previous operation. I also just put the "edgeMinMaxX" tests in
> >> the
> >> two halves of the "if" statement and avoided the need for the extra
> >> minX,maxX variables, though with a slight duplication of code.
> >>
> >> line 442 - the code actually adds "2"
> >>
> >> line 480 - interesting math trick which avoids a conditional:
> >> crorientation = ((curxo& 0x1)<< 1) - 1;
> >>
> >> ...jim
> >>
> >> On 2/1/2011 6:16 PM, Denis Lila wrote:
> >>> Ah, I'm sorry. I forgot to CC the list.
> >>>
> >>> ----- Forwarded Message -----
> >>> From: "Denis Lila"<dlila at redhat.com>
> >>> To: "Jim Graham"<james.graham at oracle.com>
> >>> Sent: Tuesday, February 1, 2011 6:04:09 PM
> >>> Subject: Re: [OpenJDK 2D-Dev] CubicCurve2D.solveCubic and
> >>> containment/intersection bugs.
> >>>
> >>> Hi Jim.
> >>>
> >>> The webrev for the performance improvement is here:
> >>> http://icedtea.classpath.org/~dlila/webrevs/perfWebrev/webrev/
> >>>
> >>> I have changed a few things since the last time you looked at it.
> >>> The largest change is in Curve.java in breakPtsAtTs. I changed its
> >>> return
> >>> from an Iterator<float[]> to an Iterator<Integer>, which allowed
> >>> me
> >>> to
> >>> change middle in Stroker from a float[2][8] to a float[16]. I also
> >>> eliminated the call to updateTs and the bouncing back and forth of
> >>> the
> >>> subdivided curves in breakPtsAtTs.
> >>>
> >>> The other major change is the implementation of the cubic solver
> >>> in
> >>> Helpers.java (which is used in Dasher.LengthIterator). It's almost
> >>> identical to what I just commited to awt.geom.CubicCurve2D. I'm
> >>> not
> >>> using the version in awt.geom because I want to avoid the array
> >>> creations
> >>> but most importantly because we don't need anything even close to
> >>> the
> >>> accuracy that CubicCurve2D provides. In fact, most of the time*,
> >>> LengthIterator's arguments to solveCubic are such that there is
> >>> only
> >>> one solution, so I considered removing the 2 root case altogether
> >>> just
> >>> to skip the within(D, 0, 1e-8) call (I haven't done this yet
> >>> because
> >>> I wanted to check with you first).
> >>>
> >>> * "most of the time" is a bit of an understatement. I've tested
> >>> this
> >>> with
> >>> tens of thousands of Dasher.curveTo calls, and I've never seen a
> >>> case
> >>> where there is more than one root.
> >>>
> >>> Regards,
> >>> Denis.
> >>>
> >>> ----- Original Message -----
> >>>> Actually, if you just want to type up a quick "description" I'll
> >>>> file
> >>>> the bug...
> >>>>
> >>>> ...jim
> >>>>
> >>>> On 1/27/2011 2:26 PM, Jim Graham wrote:
> >>>>> On 1/27/2011 2:03 PM, Denis Lila wrote:
> >>>>>> Well, it is pushed. Now all that's left on my end is the
> >>>>>> performance
> >>>>>> improvement for pisces (dashing in particular). Could you
> >>>>>> please
> >>>>>> file
> >>>>>> a performance regression bug for it?
> >>>>>
> >>>>> What are we regressing from? Is it slower than the previous
> >>>>> OpenJDK
> >>>>> rasterizer?