Add an accumulating region type

RESOLVED FIXED in Firefox 48

Status

()

defect
RESOLVED FIXED
4 years ago
3 years ago

People

(Reporter: jrmuizel, Assigned: jrmuizel)

Tracking

(Blocks 2 bugs)

unspecified
mozilla48
Points:
---
Dependency tree / graph

Firefox Tracking Flags

(firefox48 fixed)

Details

Attachments

(2 attachments, 1 obsolete attachment)

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.
Posted patch Add AccumRegion (obsolete) — Splinter Review
Assignee: nobody → jmuizelaar
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?
Flags: needinfo?(jmuizelaar)
Blocks: 1256373
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.
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 =\.
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+
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)
https://hg.mozilla.org/mozilla-central/rev/394c9900b838
Status: NEW → RESOLVED
Closed: 3 years ago
Resolution: --- → FIXED
Target Milestone: --- → mozilla48
Flags: needinfo?(bgirard)
You need to log in before you can comment on or make changes to this bug.