1123019 - Long dotted / dashed borders paint extremely slowly on Mac, even if only a screenful of them is visible

Status: RESOLVED FIXED

(Core :: Graphics, defect)

Description

[Markus Stange [:mstange]]

Attachment: slow scrolling testcase

Mozilla/5.0 (Macintosh; Intel Mac OS X 10.10; rv:38.0) Gecko/20100101 Firefox/38.0

I noticed this on a long reddit thread. It looks like CoreGraphics iterates over all line segments of the border and is very bad at ignoring those outside the visible bounds.

I think this is a regression. At least I don't remember it being this bad before. Tiling will have made this worse, but it might also be a regression in CG from 10.9 to 10.10.

Almost all the time is spent in this stack:

> nsCSSBorderRenderer::DrawDashedSide(mozilla::Side)
> mozilla::gfx::DrawTargetTiled::StrokeLine
> mozilla::gfx::DrawTargetCG::StrokeLine
> ripc_DrawPathCGContextDrawPath
> CGPathApplyRIPRenderPath
> CG::Path::Sequence::apply
> CG::Path::Subpath::apply
> CG::Chunk::apply
> path_iterator_add_line_to_point

Comment 1

[Markus Stange [:mstange]]

Builds before tiling are fast, builds after tiling are slow, blaming bug 982338.

Comment 2

[Markus Stange [:mstange]]

mozregression gave me the ranges
https://hg.mozilla.org/mozilla-central/pushloghtml?fromchange=5e9826980be5&tochange=776fa9cf70cd and
https://hg.mozilla.org/integration/mozilla-inbound/pushloghtml?fromchange=7753c52d5976&tochange=776fa9cf70cd

Comment 3

[Matt Woodrow (:mattwoodrow)]

DrawTargetTiled attempts to avoid sending draw calls to tiles that won't be affected, but it doesn't yet do this for StrokeLine (or StrokeRect).

Implementing that should be easy and would fix the regression.

Comment 4

[Milan Sreckovic [:milan] (needinfo for best results)]

Markus, is this something you can take?  Based on the time honoured "you find it, you fix it" approach :)

Comment 5

[Markus Stange [:mstange]]

Sure.

(In reply to Matt Woodrow (:mattwoodrow) from comment #3)
> DrawTargetTiled attempts to avoid sending draw calls to tiles that won't be
> affected, but it doesn't yet do this for StrokeLine (or StrokeRect).
> 
> Implementing that should be easy and would fix the regression.

It feels like the slowdown factor here is higher than the number of tiles, though. But I'll try that anyway.

Comment 6

[Markus Stange [:mstange]]

Attachment: part 1: skip unaffected tiles

This didn't make it any faster.

Comment 7

[Markus Stange [:mstange]]

Attachment: part 2: shorten lines

This made all the difference. But it's a good chunk of code, probably way over-engineered, and needs lots of comments. Before I sit down and add those comments, do you think this is something we should do or do you have a different idea?

Comment 8

[Jeff Muizelaar [:jrmuizel]]

(In reply to Markus Stange [:mstange] from comment #7)
> Created attachment 8563151 [details] [diff] [review]
> part 2: shorten lines
> 
> This made all the difference. But it's a good chunk of code, probably way
> over-engineered, and needs lots of comments. Before I sit down and add those
> comments, do you think this is something we should do or do you have a
> different idea?

Can you summarize what it does?

Comment 9

[Markus Stange [:mstange]]

It wraps a PathBuilder, and replaces LineTo calls with MoveTo, LineTo, MoveTo calls when a encountering a line that isn't completely inside the clip rect, so that only the visible part of the line (+ a little error margin) gets drawn, all the time ensuring that the dash pattern looks the same as if the line were drawn unshortened.

Comment 10

[Markus Stange [:mstange]]

This helps because the perf problem is that CG spends ages iterating over dashes that are outside the clip.

Comment 11

[Markus Stange [:mstange]]

Attachment: part 1: skip unaffected tiles

Fixes <cmath> build failure and also implements the culling for StrokeLine.

Comment 12

[Markus Stange [:mstange]]

Attachment: part 2: factor out stroking in DrawTargetCG

Comment 13

[Markus Stange [:mstange]]

Attachment: part 3: shrink clipped stroked rectangles and lines in DrawTargetCG

The previous approach wasn't working because you can't close a path that has been chopped up, and you need it to work for the top left corner of stroked rectangles.

Comment 14

[Markus Stange [:mstange]]

https://treeherder.mozilla.org/#/jobs?repo=try&revision=d1db90110790

Comment 15

[Markus Stange [:mstange]]

Attachment: part 1: skip unaffected tiles

I hope I've really fixed the build failure this time.

https://treeherder.mozilla.org/#/jobs?repo=try&revision=9eae58a04314

Comment 16

[Jeff Muizelaar [:jrmuizel]]

Comment on attachment 8566844 [details] [diff] [review]
part 2: factor out stroking in DrawTargetCG

Review of attachment 8566844 [details] [diff] [review]:
-----------------------------------------------------------------

Lets not. This adds some overhead that we're not particularly in need of.

Comment 17

[Jeff Muizelaar [:jrmuizel]]

Comment on attachment 8566845 [details] [diff] [review]
part 3: shrink clipped stroked rectangles and lines in DrawTargetCG

Review of attachment 8566845 [details] [diff] [review]:
-----------------------------------------------------------------

::: gfx/2d/DrawTargetCG.cpp
@@ +998,5 @@
> +  for (size_t i = 0; i < aStrokeOptions.mDashLength; i++) {
> +    length += aStrokeOptions.mDashPattern[i];
> +  }
> +  if (aStrokeOptions.mDashLength == 1) {
> +    // 1-element dash arrays are interpreted as a symmetric 2-element dash array.

The should be all odd dash arrays. i.e.
if (aStrokeOptions.mDashLength & 1)

https://developer.mozilla.org/en-US/docs/Web/SVG/Attribute/stroke-dasharray

@@ +1053,5 @@
> +}
> +
> +// Liang-Barsky
> +// Sets aStart and aEnd to floats between 0 and the line length, or returns
> +// false if the line is completely outside the rect.

You should add a note as to why you chose Liang-Barsky over other options.

Does this include the improvements suggested here?
"Some Improvements to a Parametric Line Clipping Algorithm"

Comment 18

[Markus Stange [:mstange]]

Attachment: part 2: shrink clipped stroked rectangles and lines in DrawTargetCG

(In reply to Jeff Muizelaar [:jrmuizel] from comment #17)
> Comment on attachment 8566845 [details] [diff] [review]
> part 3: shrink clipped stroked rectangles and lines in DrawTargetCG
> 
> Review of attachment 8566845 [details] [diff] [review]:
> -----------------------------------------------------------------
> 
> ::: gfx/2d/DrawTargetCG.cpp
> @@ +998,5 @@
> > +  for (size_t i = 0; i < aStrokeOptions.mDashLength; i++) {
> > +    length += aStrokeOptions.mDashPattern[i];
> > +  }
> > +  if (aStrokeOptions.mDashLength == 1) {
> > +    // 1-element dash arrays are interpreted as a symmetric 2-element dash array.
> 
> The should be all odd dash arrays. i.e.
> if (aStrokeOptions.mDashLength & 1)
> 
> https://developer.mozilla.org/en-US/docs/Web/SVG/Attribute/stroke-dasharray

Thanks, that makes a lot more sense.

> 
> @@ +1053,5 @@
> > +}
> > +
> > +// Liang-Barsky
> > +// Sets aStart and aEnd to floats between 0 and the line length, or returns
> > +// false if the line is completely outside the rect.
> 
> You should add a note as to why you chose Liang-Barsky over other options.

Added a comment:
// This algorithm was chosen for its code brevity, with the hope that its
// performance is good enough.

> Does this include the improvements suggested here?
> "Some Improvements to a Parametric Line Clipping Algorithm"

Doesn't look like it. I actually think the original code I was looking at had the improvement, and I removed it because I wanted to have extra ifs tainting the std::min/max lines.
I have this check at the very end:
  if (t0 > t1) {
    return false;
  }
The improvement suggested in that document is basically "move that check into the loop, so you can skip checking the remaining edges", if I understood correctly.
I have a hard time believing that at most three additional float divisions per line are going to hurt much.

Comment 19

[Jeff Muizelaar [:jrmuizel]]

(In reply to Markus Stange [:mstange] from comment #18)

> 
> > Does this include the improvements suggested here?
> > "Some Improvements to a Parametric Line Clipping Algorithm"
> 
> Doesn't look like it. I actually think the original code I was looking at
> had the improvement, and I removed it because I wanted to have extra ifs
> tainting the std::min/max lines.
> I have this check at the very end:
>   if (t0 > t1) {
>     return false;
>   }
> The improvement suggested in that document is basically "move that check
> into the loop, so you can skip checking the remaining edges", if I
> understood correctly.
> I have a hard time believing that at most three additional float divisions
> per line are going to hurt much.

Might as well add something about this to the comment too.

Comment 20

[Markus Stange [:mstange]]

Actually, let me just move that if up into the loop body. That way, the number of lines of code stays the same, we get the behavior we want, and we don't need the comment.

Comment 21

[Markus Stange [:mstange]]

https://hg.mozilla.org/integration/mozilla-inbound/rev/4558317a4a9c
https://hg.mozilla.org/integration/mozilla-inbound/rev/d472aa32cecf

Comment 22

[Carsten Book [:Tomcat]]

https://hg.mozilla.org/mozilla-central/rev/4558317a4a9c
https://hg.mozilla.org/mozilla-central/rev/d472aa32cecf

Comment 23

[Markus Stange [:mstange]]

Attachment: part 2*: don't just create a variable with the reduced rect, but actually use that variable

Well that was just stupid.

Comment 24

[Markus Stange [:mstange]]

https://hg.mozilla.org/integration/mozilla-inbound/rev/10cad47c3d33

Comment 25

[Phil Ringnalda (:philor)]

https://hg.mozilla.org/mozilla-central/rev/10cad47c3d33

Comment 26

[Milan Sreckovic [:milan] (needinfo for best results)]

Release Note Request (optional, but appreciated)
[Why is this notable]: Fixes a regression from Firefox 35.
[Suggested wording]: Performance of displaying dashed lines on OS X is improved.
[Links (documentation, blog post, etc)]: