Add an accumulating region type

RESOLVED FIXED in Firefox 48

Status

()

Core
Graphics
RESOLVED FIXED
3 years ago
2 years ago

People

(Reporter: jrmuizel, Assigned: jrmuizel)

Tracking

(Blocks: 2 bugs)

unspecified
mozilla48
Points:
---
Dependency tree / graph

Firefox Tracking Flags

(firefox48 fixed)

Details

MozReview Requests

()

Submitter Diff Changes Open Issues Last Updated
Loading...
Error loading review requests:

Attachments

(2 attachments, 1 obsolete attachment)

(Assignee)

Description

3 years ago
In place modification of a region causes an new heap allocation. We can avoid that with accumulating regions that ping-pong two regions to avoid self modification.
(Assignee)

Comment 1

3 years ago
Created attachment 8718991 [details] [diff] [review]
Add AccumRegion
Assignee: nobody → jmuizelaar
^ Patch is empty, btw
(Assignee)

Comment 3

2 years ago
Created attachment 8719873 [details] [diff] [review]
Add AccumRegion

This time with content.
Attachment #8718991 - Attachment is obsolete: true
From the description 'Add an accumulating region type.' I expected a structure similar to a StringBuilder to avoid doing n*m operations while doing a lot of appends. This will help a bit with heap allocation but don't we still have problems with algorithm complexity of a lot of OR/AND operation in layout/layers that wont be solved by this?
(Assignee)

Updated

2 years ago
Flags: needinfo?(jmuizelaar)

Updated

2 years ago
Blocks: 1256373
Created attachment 8730329 [details]
MozReview Request: Bug 1248044 - Add PingPongRegion for faster region operations for 2x memory usage. r=jrmuizel

Review commit: https://reviewboard.mozilla.org/r/39807/diff/#index_header
See other reviews: https://reviewboard.mozilla.org/r/39807/
Here's a stub of what I had in mind. I think this would help with bug 1256373. This would be using |pixman_region32_init_rects| which we currently don't use in this way. I just noticed I'm missing the _fini call.
(Assignee)

Comment 7

2 years ago
It's true that this doesn't solve the algorithmic complexity issue. However, I've not seen evidence that the algorithmic complexity is actually a problem. From the profiles I've seen, the constant factor seems to dominate.
Flags: needinfo?(jmuizelaar)
What about the patch suggesting? IMO it's simpler to understand than your approach and the union code does show up in my profile in bug 1256373 alongside with allocation. I have seen the algorithm in some rare extreme cases but it's also cases where Chrome handles it no problem.

The only upside I see with your solution is that it supports subtraction.
A quick test of my patch shows a 10x to 200x performance improvement when doing 500 Or()s. Between 1-20ms vs 200ms.
We discussed this in person. Here's the conclusion:
1) We want both implementation
2) We're going to land the code to make it accessible for others to use when they hit performance problems. But we wont start replacing code until we see them in profiles.

I'm splitting off RegionBuilder into a different bug. This will make regression tracking easier.
Comment on attachment 8730329 [details]
MozReview Request: Bug 1248044 - Add PingPongRegion for faster region operations for 2x memory usage. r=jrmuizel

Move to a separate bug.
Attachment #8730329 - Attachment is obsolete: true
See bug 1258481 for RegionBuilder.
Need bug 1258558 for the tests to pass.
Depends on: 1258558
Comment on attachment 8730329 [details]
MozReview Request: Bug 1248044 - Add PingPongRegion for faster region operations for 2x memory usage. r=jrmuizel

Review request updated; see interdiff: https://reviewboard.mozilla.org/r/39807/diff/1-2/
Attachment #8730329 - Attachment description: MozReview Request: Bug 1248044 - Add nsRegionBuilder. → MozReview Request: Bug 1248044 - Add an accumulating region type. r?
Attachment #8730329 - Attachment is obsolete: false
This patch fixes a bug in your implementation and has a microbench. On this test AccumRegion is only 10% faster =\.
(Assignee)

Comment 16

2 years ago
Comment on attachment 8730329 [details]
MozReview Request: Bug 1248044 - Add PingPongRegion for faster region operations for 2x memory usage. r=jrmuizel

https://reviewboard.mozilla.org/r/39807/#review38509

This looks good. I'm surprised by only getting 10% improvement, but let's check it into the tree for now.
Attachment #8730329 - Flags: review+

Updated

2 years ago
Attachment #8730329 - Attachment description: MozReview Request: Bug 1248044 - Add an accumulating region type. r? → MozReview Request: Bug 1248044 - Add PingPongRegion for faster region operations for 2x memory usage. r=jrmuizel
Comment on attachment 8730329 [details]
MozReview Request: Bug 1248044 - Add PingPongRegion for faster region operations for 2x memory usage. r=jrmuizel

Review request updated; see interdiff: https://reviewboard.mozilla.org/r/39807/diff/2-3/
Renamed to PingPongRegion per our discussion since RegionBuilder does a better job at accumulating and this naming would of been misleading. ni? for try&landing.
Flags: needinfo?(bgirard)

Comment 20

2 years ago
bugherder
https://hg.mozilla.org/mozilla-central/rev/394c9900b838
Status: NEW → RESOLVED
Last Resolved: 2 years ago
status-firefox48: --- → fixed
Resolution: --- → FIXED
Target Milestone: --- → mozilla48

Updated

2 years ago
Flags: needinfo?(bgirard)
You need to log in before you can comment on or make changes to this bug.