389814 - Make tile filter faster

Status: RESOLVED FIXED

(Core :: SVG, defect)

Description

[Robert Longson [:longsonr]]

Bug 373572 comment 4 suggests that the tile filter could be made faster by copying rows at a time rather than individual pixels.

Comment 1

[O S K Chaitanya]

Attachment: Copy rows instead of pixel-by-pixel copy.

I have made a patch to copy row-by-row and have minimal operations in the inner loops.

(Also, I re-formatted a couple of lines which were exceeding 80 columns).

I am marking longsonr for review on this since I see from bug#373572 that he has originally coded this filter.

Also I would like to submit three additional test cases for this filter. It would be kind if someone could point me the right way for it.

Comment 2

[O S K Chaitanya]

> Also I would like to submit three additional test cases for this filter. It
> would be kind if someone could point me the right way for it.

My bad! I found this page to help me out: 
https://developer.mozilla.org/en-US/docs/Creating_reftest-based_unit_tests

Comment 3

[Robert Longson [:longsonr]]

Comment on attachment 720271 [details] [diff] [review]
Copy rows instead of pixel-by-pixel copy.


>+void

static inline void

We want it inline as there's only one call to it so we might as well.

>+TilePixels(uint8_t *aTargetData,
>+           const uint8_t *aSourceData,
>+           const nsIntRect &aCopyRegionInTarget,
>+           const nsIntRect &aTile,
>+           uint32_t aStride)
>+{
>+  uint32_t tileRowCopyMemSize = aTile.width * 4;
>+  uint32_t numTimesToCopyTileRows = aCopyRegionInTarget.width / aTile.width;
>+
>+  for (int32_t targetY = aCopyRegionInTarget.y, tileYOffset = 0;
>+       targetY < aCopyRegionInTarget.YMost();
>+       ++targetY, tileYOffset = (tileYOffset + 1) % aTile.height) {

I don't really like the assign to tileYOffset in the for there, can you just make it a statement in the loop body.

>+    uint8_t *targetCopyStartPosition = aTargetData +
>+                                         4 * aCopyRegionInTarget.x +
>+                                         targetY * aStride;

Some of this calculation can move out of the loop e.g. aTargetData + 4 * aCopyRegionInTarget.x is constant within the loop.

>+    const uint8_t *tileCopyStartPosition = aSourceData +
>+                                             aStride * (aTile.y + tileYOffset) +
>+                                             4 * aTile.x;

ditto for aSourceData + 4 * aTile.x

> 
>+  // clip tile
>+  if (tile.x < 0) {
>+    tile.x = 0;
>+  }
>+
>+  if (tile.y < 0) {
>+    tile.y = 0;
>+  }
>+
>+  if (tile.XMost() > surfaceRect.XMost()) {
>+    tile.width -= tile.XMost() - surfaceRect.XMost();
>+  }
>+
>+  if (tile.YMost() > surfaceRect.YMost()) {
>+    tile.height -= tile.YMost() - surfaceRect.YMost();
>+  }
>+

Isn't this the same as intRect::Intersect?

    tile = tile.Intersect(surfaceRect);

See http://mxr.mozilla.org/mozilla-central/source/gfx/2d/BaseRect.h#89

>+  /*
>+   * priority: left before right before centre 
>+   *           and top before bottom before centre
>+   * eg: If we have a target area which is 1.5 times the width of a tile,
>+   *     then we a left and right or a left and centre (based on alignment)

then we a? Missing word somewhere I think.

>+   */
>+  int32_t leftPartialTileWidth;
>+  if (tile.x < rect.x) {
>+    leftPartialTileWidth = tile.width + tile.x - rect.x;

tile.width + tile.x can be written as tile.XMost()

>+  } else {
>+    leftPartialTileWidth = (tile.x - rect.x) % tile.width;
>+  }
>+
>+  int32_t rightPartialTileWidth;
>+  if (leftPartialTileWidth > rect.width) {
>+    leftPartialTileWidth = rect.width;
>+    rightPartialTileWidth = 0;
>+  } else if (tile.XMost() > rect.XMost()) {
>+      rightPartialTileWidth = tile.width + rect.XMost() - tile.XMost();

tile.XMost() is tile.x + tile.width so 

tile.width + rect.XMost() - tile.XMost()

is the same as

rect.XMost() - tile.x

>+  } else {
>+    rightPartialTileWidth = (rect.XMost() - tile.XMost()) % tile.width;
>+  }
>+
>+  if (leftPartialTileWidth + rightPartialTileWidth > rect.width) {
>+    rightPartialTileWidth = rect.width - leftPartialTileWidth;
>+  }
>+
>+  int32_t centreWidth;
>+  if (leftPartialTileWidth == rect.width || 
>+      leftPartialTileWidth + rightPartialTileWidth == rect.width) {
>+    centreWidth = 0;
>+  } else {
>+    centreWidth = rect.width - (leftPartialTileWidth + rightPartialTileWidth);
>+  }

I'm confused by the if test. Can the first be true if the second is false?
Aren't we just doing this?

    centreWidth = std::min(0, rect.width - (leftPartialTileWidth + rightPartialTileWidth));

Overall It might be easier if you worked with a nsIntRect or maybe nsIntPoint and nsIntSize above rather than separate width/height variables and tried to use where possible the methods they expose like nsIntRect::Intersect 

At any rate the width logic is the same as the height logic with width replaced by height so you should be able to use some common function rather than writing everything twice with height replaced by width.

>+
>+  /* We have nine regions of the target area which have to be tiled differetly:
>+   *
>+   * Top Left, Top Middle, Top Right,
>+   * Left Mid, Centre    , Right Mid,

Whole words in comments please. So Left Middle, Right Middle.

>+   * Bot Left, Bot Middle, Bot Right
>+   *
>+   * + Centre is tiled by repeating the tiled image in full.
>+   * + Top Left, Top Middle and Top Right:
>+   *     Some of the rows from the top of the tile will be clipped here.
>+   * + Bot Left, Bot Middle and Bot Right:
>+   *     Some of the rows from the bottom of the tile will be clipped here.
>+   * + Top Left, Left Mid and Bot left:
>+   *     Some of the columns from the left of the tile will be clipped here.
>+   * + Top Right, Right Mid and Bot Right:
>+   *     Some of the columns from the right of the tile will be clipped here.
>+   *
>+   * If the sizes and positions of the target and tile are such that the tile
>+   * aligns exactly on any (or all) of the edges, then some (or all) of the
>+   * regions above (except Centre) will be zero sized.
>+   */

I like the comment. :-)

>+
>+  nsIntRect targetRects[9] = {

Don't need the 9 here, I don't think. And this could be an array of references I think. i.e.

    nsIntRect& targetRects[] =

>+    // Top Left
>+    nsIntRect(rect.x, rect.y, leftPartialTileWidth, topPartialTileHeight),
>+    // Top Mid
>+    nsIntRect(rect.x + leftPartialTileWidth,
>+              rect.y,
>+              centreWidth,
>+              topPartialTileHeight),
>+    // Top Right
>+    nsIntRect(rect.XMost() - rightPartialTileWidth,
>+              rect.y,
>+              rightPartialTileWidth,
>+              topPartialTileHeight),
>+    // Left Mid
>+    nsIntRect(rect.x,
>+              rect.y + topPartialTileHeight,
>+              leftPartialTileWidth,
>+              centreHeight),
>+    // Centre
>+    nsIntRect(rect.x + leftPartialTileWidth,
>+              rect.y + topPartialTileHeight,
>+              centreWidth,
>+              centreHeight),
>+    // Right Mid
>+    nsIntRect(rect.XMost() - rightPartialTileWidth,
>+              rect.y + topPartialTileHeight,
>+              rightPartialTileWidth,
>+              centreHeight),
>+    // Bot Left
>+    nsIntRect(rect.x,
>+              rect.YMost() - bottomPartialTileHeight,
>+              leftPartialTileWidth,
>+              bottomPartialTileHeight),
>+    // Bot Mid
>+    nsIntRect(rect.x + leftPartialTileWidth,
>+              rect.YMost() - bottomPartialTileHeight,
>+              centreWidth,
>+              bottomPartialTileHeight),
>+    // Bot Right
>+    nsIntRect(rect.XMost() - rightPartialTileWidth,
>+              rect.YMost() - bottomPartialTileHeight,
>+              rightPartialTileWidth,
>+              bottomPartialTileHeight)
>+  };
>+
>+
>+  for (int i = 0; i < 9; ++i) {

ArrayLength(targetRects) rather than 9

>+    nsIntRect & targetAreaRect = targetRects[i];
>+    nsIntRect & tileRectForCopy = tileRects[i];

Don't really need these variables, just pass targetRects[i] to TilePixels etc.

>+
>+    if (targetAreaRect.width == 0 || targetAreaRect.height == 0) {
>+      continue;
>     }

Move this test inside TilePixels with an early return then it's easy to see that we're not dividing by zero in TilePixels.

Overall I really like it. :-)

You should apply for editbugs permission in bugzilla per

https://bugzilla.mozilla.org/page.cgi?id=get_permissions.html

Also if you want to obtain try server access I'd vouch for you. Just follow the steps below to get a level 1 account and cc me on the bugzilla bug.

https://wiki.mozilla.org/ReleaseEngineering/TryServer

or more succinctly

http://mschranz.wordpress.com/2012/02/09/getting-access-to-and-using-the-mozilla-try-server/

Much easier than running tests yourself.

Comment 4

[Robert Longson [:longsonr]]

(In reply to O S K Chaitanya from comment #2)
> > Also I would like to submit three additional test cases for this filter. It
> > would be kind if someone could point me the right way for it.
> 
> My bad! I found this page to help me out: 
> https://developer.mozilla.org/en-US/docs/Creating_reftest-based_unit_tests

Just include any additional reftests to the next version of the patch please.

Looks like you're interested in SVG so far, if so Jonathan, Daniel and I would all like to extend our warmest welcome to you.

Comment 5

[O S K Chaitanya]

I am uploading a new patch with the changes suggested by you.

> 
> Isn't this the same as intRect::Intersect?
> 
>     tile = tile.Intersect(surfaceRect);

This is the same. However, we have to ensure this is always done _before_ converting tile to surface-space (I have taken care of it).

> >+  int32_t centreWidth;
> >+  if (leftPartialTileWidth == rect.width || 
> >+      leftPartialTileWidth + rightPartialTileWidth == rect.width) {
> >+    centreWidth = 0;
> >+  } else {
> >+    centreWidth = rect.width - (leftPartialTileWidth + rightPartialTileWidth);
> >+  }
> 
> I'm confused by the if test. Can the first be true if the second is false?
> Aren't we just doing this?
> 
>     centreWidth = std::min(0, rect.width - (leftPartialTileWidth +
> rightPartialTileWidth));
> 

leftPartialTileWidth == rect.width only happens when the tile entirely overlaps with the target area in the X-axis and exceeds its bounds by at least one pixel on the lower X-Axis side.

leftPartialTileWidth + rightPartialTileWidth == rect.width only happens when the tile overlaps the target area in such a way that the edge of the tile on the higher X-Axis side cuts through the target area and there is no space for a complete tile in the X-Axis in the target area on either side of that edge. In this scenario, centre will be of zero width and the partial widths on left and right will add up to the width of the rect. In case the tile is bigger than the rect in the X-axis, it will get clipped and remain equal to rect.width.

Therefore, those two conditions are separate cases which lead to centre being of zero width.

> Overall It might be easier if you worked with a nsIntRect or maybe
> nsIntPoint and nsIntSize above rather than separate width/height variables
> and tried to use where possible the methods they expose like
> nsIntRect::Intersect

I have used it to clip tile to surface rect as per your suggestion. However, I could not see how I could do this for computing the partial widths and heights at all the edges of the rect. The final tiling is done using rects but for computing the bounds needed to create those rects, we need these dimensions.

> >+
> >+  nsIntRect targetRects[9] = {
> 
> Don't need the 9 here, I don't think. And this could be an array of
> references I think. i.e.
> 
>     nsIntRect& targetRects[] =
> 

Upon trying this, I came to know that C++ doesn't permit array of references (they are not objects with any memory assigned to them) but I did remove the '9'.

Also I have added three new test cases for the tile filter (in the updated patch)

Comment 6

[O S K Chaitanya]

Attachment: Updated patch with changes as per review feedback.

Comment 7

[O S K Chaitanya]

> Looks like you're interested in SVG so far, if so Jonathan, Daniel and I
> would all like to extend our warmest welcome to you.

Thank you! The friendly and helpful face of Mozilla that you guys have shown keeps me wanting to do more!

Also, I did apply for edit-bugs permissions and will soon apply for try server access too.

Comment 8

[O S K Chaitanya]

Attachment: removed two extra blank lines from the earlier patch

Comment 9

[O S K Chaitanya]

Comment on attachment 720339 [details] [diff] [review]
removed two extra blank lines from the earlier patch

Forgot to mark r? while submitting.

Comment 10

[Robert Longson [:longsonr]]

Comment on attachment 720339 [details] [diff] [review]
removed two extra blank lines from the earlier patch

A comment explaining what the arguments to ComputePartialTileExtents are would be helpful I feel. Particularly as reviewing this patch makes my head hurt which it totally not your fault - if we want it fast, which we do then we're going to have to accept more complicated code :-)

>+  int32_t centreSize;
>+  if (lesserSidePartialMatchSize == aTargetSize ||
>+        lesserSidePartialMatchSize + higherSidePartialMatchSize ==
>+        aTargetSize) {

Please add a comment with the explantion text from comment 5 prior to the if test here.

>+static inline void
>+TilePixels(uint8_t *aTargetData,
>+           const uint8_t *aSourceData,
>+           const nsIntRect &aCopyRegionInTarget,

Optional nit: A lot of variable names have "Copy" in them in this function, not sure that it adds much except extra typing.

>+           const nsIntRect &aTile,
>+           uint32_t aStride)
>+{
>+  if (aCopyRegionInTarget.width == 0 || aCopyRegionInTarget.height == 0) {

replace with aCopyRegionInTarget.IsEmpty()

>diff --git a/layout/reftests/svg/filters/feTile-3-ref.svg b/layout/reftests/svg/filters/feTile-3-ref.svg
>new file mode 100644
>index 0000000..495004f
>--- /dev/null
>+++ b/layout/reftests/svg/filters/feTile-3-ref.svg
>@@ -0,0 +1,15 @@

Would you mind adding 

<!--
     Any copyright is dedicated to the Public Domain.
     http://creativecommons.org/publicdomain/zero/1.0/
-->

to the top of each ref and test file (assuming you're happy with this licence). This is optional and we'll still accept the patch without the reftests having this licence - they'd get the standard MPL 2, GPL, LGPL tri-licence in that case.

>+<svg xmlns="http://www.w3.org/2000/svg">

I'd like to see a title element explaining the purpose of the testcase

    <title>Testcase for ...</title>

or (if it's a ref file)

    <title>Reference for ...</title>

>+<rect x="0" y="0" width="20" height="20" fill="#00ff00"/>

omit x="0"

>+<rect x="40" y="0" width="20" height="20" fill="#00ff00"/>
>+
>+<rect x="20" y="20" width="20" height="20" fill="#0000ff"/>
>+<rect x="60" y="20" width="10" height="20" fill="#0000ff"/>
>+
>+<rect x="00" y="40" width="20" height="20" fill="#00ff00"/>

omit x="00"

>diff --git a/layout/reftests/svg/filters/feTile-4-ref.svg b/layout/reftests/svg/filters/feTile-4-ref.svg
>new file mode 100644
>index 0000000..a7c9020
>--- /dev/null
>+++ b/layout/reftests/svg/filters/feTile-4-ref.svg
>@@ -0,0 +1,6 @@
>+<svg xmlns="http://www.w3.org/2000/svg">
>+<g>
>+  <rect x="0" y="0" width="100" height="100" fill="#ff0000"/>

Having a reference which shows any red is unfortunate. Red in testcases generally indicates failure of some sort.

The ideal in a testcase is to produce something that compares to pass.svg (totally #00ff00) and displays red on failure.

Otherwise, if that's not feasible just something that avoids red in both the test and reference.

>diff --git a/layout/reftests/svg/filters/feTile-4.svg b/layout/reftests/svg/filters/feTile-4.svg

>+<g filter="url(#f1)">
>+  <rect x="0" y="0" width="100" height="100" fill="#00ff00"/>
>+</g>
>+<g>
>+  <rect x="0" y="0" width="100" height="100" fill="#ff0000"/>
>+</g>

So here is it possible to make the rects width/height 100% and compare the test to pass.svg with colours adjusted appropriately.

And omit x and y values of 0 in the rects

>diff --git a/layout/reftests/svg/filters/reftest.list b/layout/reftests/svg/filters/reftest.list
>index d56f583..d254154 100644
>--- a/layout/reftests/svg/filters/reftest.list
>+++ b/layout/reftests/svg/filters/reftest.list
>@@ -40,16 +40,19 @@ skip-if(B2G) == dynamic-filtered-foreignObject-01.svg pass.svg # bug 773482
> 
> == feTile-1.svg feTile-1-ref.svg
> == feTile-2.svg feTile-2-ref.svg

-1 and -2 filters are special (as explained at the top of the reftest.list file)

>+== feTile-3.svg feTile-3-ref.svg
>+== feTile-4.svg feTile-4-ref.svg
>+== feTile-5.svg feTile-5-ref.svg

So these should go at the bottom, perhaps next to the 
== feTile-large-01.svg pass.svg
line and be numbered appropriately, using 01, 02, 03 rather than 1, 2, 3


Overall, this is very close. I almost gave it an "r+ with review comments applied", and if you had fixed 20 bugs rather than 2 I probably would have.

Comment 11

[O S K Chaitanya]

Attachment: Updated patch with changes as per review feedback.

I have made the changes that you have suggested and uploaded a new patch.

Also, I removed the x, y entries from the svg files where they were '0'. However, I felt that having them there made it more explicit. Nevertheless, I defer to your experience on the project and have followed what you have suggested.

Please let me know if this will serve.

Comment 12

[O S K Chaitanya]

Attachment: Had forgotten a period in one of the comments in the earlier patch

This patch is almost the same as attachment no. 720445 (the one right before this one). I only added a '.' at the end of a sentence in one of the comments.

Comment 13

[Jonathan Watt [:jwatt]]

(In reply to Robert Longson from comment #4)
> Looks like you're interested in SVG so far, if so Jonathan, Daniel and I
> would all like to extend our warmest welcome to you.

Most definitely. :) Thanks for your contributions!

Comment 14

[Robert Longson [:longsonr]]

We do have a crashtest http://mxr.mozilla.org/mozilla-central/source/content/svg/content/src/crashtests/414188-1.svg?raw=1 which tests for tiles with 0 width. 

That seems to be what testcase 3 is testing so I've removed it.

Sent the rest to try with some reftest renaming

https://tbpl.mozilla.org/?tree=Try&rev=474f5721fc08

Note to self: make sure it lands with the right contributor name

Comment 15

[O S K Chaitanya]

I did have in mind that I should rename the reftests. I came here to ask if it was okay to rename the tests in a separate patch.

Comment 16

[Robert Longson [:longsonr]]

Comment on attachment 720446 [details] [diff] [review]
Had forgotten a period in one of the comments in the earlier patch

Some of the reftest file names aren't quite right and one is a duplicate of a crashtest as far as I can tell. I'll fix that on check in for you.

Comment 17

[Robert Longson [:longsonr]]

https://hg.mozilla.org/integration/mozilla-inbound/rev/f3c321ce4980

Comment 18

[Robert Longson [:longsonr]]

(In reply to O S K Chaitanya from comment #15)
> I did have in mind that I should rename the reftests. I came here to ask if
> it was okay to rename the tests in a separate patch.

I did that as part of landing the patch for you. Thanks for your contribution.

Comment 19

[Ryan VanderMeulen [:RyanVM]]

https://hg.mozilla.org/mozilla-central/rev/f3c321ce4980