Comparison reversed in webrender::batch::BatchRects::add_rect
Categories
(Core :: Graphics: WebRender, defect, P4)
Tracking
()
| Tracking | Status | |
|---|---|---|
| firefox88 | --- | fixed |
People
(Reporter: jimb, Assigned: jimb)
Details
Attachments
(1 file)
The comparison that decides whether to store per-rectangle information about each item in a BatchRects uses the heuristic backwards, resulting in less detailed information being kept, and more primitives falsely being flagged as intersecting.
BatchRects accumulates a set of rectangles, and answers queries about whether a given rectangle might intersects any rectangle in the set. False positives are okay; false negatives are not.
A BatchRects maintains a bounding box for the entire set, but uses a heuristic to decide whether to also keep a list of the specific rectangles added to the set, for a more precise result. The heuristic compares the sums of the individual areas of the old BB and the new rectangle against the area of the new BB that will result from incorporating the new rectangle. If the first is larger, then a detailed list is started.
I think this is backwards. The detailed list is valuable when it would allow intersection queries to return false more often - that is, when the detailed list covers less area than the BB. For example, if the set contains two small, widely separated rectangles, then the list will win big. But the heuristic starts the list only if the area of the initial detailed list would be greater than the current BB. Or, In the opposite case, if we add a rectangle that encloses the existing BB - in which case the expanded BB would be exact - the heuristic does decide to start a detailed list, even though it will not help.
I collected some data from the pocket about:newtab, nytimes.com, and en.wikipedia.com about the distribution of detailed rectangle list sizes, and the percentage of intersection queries that return true:
With the current heuristic comparison:
batch list sizes:
< 2^0 < 2^1 < 2^2 < 2^3 : < 2^4 < 2^5 < 2^6 < 2^7 : < 2^8 < 2^9 < 2^10 < 2^11 : < 2^12 < 2^13 < 2^14 < 2^15
13390 0 2182 582 : 369 117 86 0 : 0 0 0 0 : 0 0 0 0
80.0% 0.0% 13.0% 3.5% : 2.2% 0.7% 0.5% 0.0% : 0.0% 0.0% 0.0% 0.0% : 0.0% 0.0% 0.0% 0.0%
intersection hit rate 38.75% (11555 of 29818)
With the comparison flipped:
batch list sizes:
< 2^0 < 2^1 < 2^2 < 2^3 : < 2^4 < 2^5 < 2^6 < 2^7 : < 2^8 < 2^9 < 2^10 < 2^11 : < 2^12 < 2^13 < 2^14 < 2^15
9866 0 2707 2203 : 1257 246 100 1 : 0 0 0 0 : 0 0 0 0
60.2% 0.0% 16.5% 13.4% : 7.7% 1.5% 0.6% 0.0% : 0.0% 0.0% 0.0% 0.0% : 0.0% 0.0% 0.0% 0.0%
intersection hit rate 26.32% (11000 of 41790)
(There are never any rectangle lists of length one, since rectangle lists are created with two elements initially.)
So flipping the comparison allocates more detailed rectangle list entries, as expected, and lowers the hit rate.
I assume this improves batching, but since draw counts per frame vary wildly based on many conditions, I wasn't able to easily measure the impact there.
|
Assignee | |
Updated•3 years ago
|
|
|
Assignee | |
Updated•3 years ago
|
|
|
Assignee | |
Comment 1•3 years ago
|
||
BatchRects would like to avoid allocating and iterating over detailed rectangle
lists when the bounding box is not much larger than the area of the detailed
rectangle lists, such that the approximation won't affect the accuracy of
intersection queries. But bounding boxes can badly overestimate intersections,
so sometimes a detailed list must be retained.
Thus, the heuristic in add_rect should start a detailed rectangle list when
the area of the old BB and the new rectangle is less than that of the new BB,
not more.
Pushed by jblandy@mozilla.com: https://hg.mozilla.org/integration/autoland/rev/d4b8277dc7e2 Fix heuristic comparison in webrender::batch::BatchRects. r=nical
|
||
Comment 3•3 years ago
|
||
| bugherder | ||
Description
•