1931789 - avoid quadratic case when appending style sheets

Status: RESOLVED FIXED

(Core :: CSS Parsing and Computation, defect)

Comment 1

[Timothy Nikkel (:tnikkel)]

Attachment: Bug 1931789. Change DocumentOrShadowRoot::StyleOrderIndexOfSheet to return size_t. r?smaug,#dom-core

size_t is the return type of nsTArray::IndexOf. NoIndex is defined as (size_t)-1. Implicitly converting this to int32_t which is signed and might be a different bit width seems sketchy to me. This makes this clear and explicit.

Comment 2

[Timothy Nikkel (:tnikkel)]

Attachment: Bug 1931789 - Avoid quadratic behaviour of FindDocStyleSheetInsertionPoint in the common append case. r?smaug,#dom-core,#style

FillStyleSetDocumentSheets specifically iterates the existing sheets in reverse order when calling AddDocStyleSheet in order to avoid this problem (because FindDocStyleSheetInsertionPoint iterates from the start of existing sheets).

FindDocStyleSheetInsertionPoint has to deal with some other types of sheets, so just flipping the order it iterates seems a bit more complex.

The slow case that we want to avoid here is the other caller of AddDocStyleSheet: AddStyleSheetToStyleSets. When the sheets are appended at the end one by one using this function we hit the quadratic worst case.

This is about 0.75% of the full sp3 suite.

Comment 4

[Emilio Cobos Álvarez (:emilio)]

I had a totally busted wip that I plan to clean up and land.

Comment 5

[Emilio Cobos Álvarez (:emilio)]

It was of course a silly off-by-one.

Comment 6

[Emilio Cobos Álvarez (:emilio)]

https://perf.compare/subtests-compare-results?baseRev=623c1b15f0513cc362f6216838d4eeb517adaf95&baseRepo=try&newRev=1607f0751f0b79495a253d0841edc771747d43c4&newRepo=try&framework=13&baseParentSignature=4569240&newParentSignature=4569240

Comment 7

[Emilio Cobos Álvarez (:emilio)]

https://treeherder.mozilla.org/jobs?repo=try&revision=1b1ba53ede6e0815b0e09afe1c6f019903820f87

Comment 8

[Olli Pettay [:smaug][[e-mail]]]

(In reply to Emilio Cobos Álvarez (:emilio) from comment #6)

https://perf.compare/subtests-compare-results?baseRev=623c1b15f0513cc362f6216838d4eeb517adaf95&baseRepo=try&newRev=1607f0751f0b79495a253d0841edc771747d43c4&newRepo=try&framework=13&baseParentSignature=4569240&newParentSignature=4569240

So basically no changes to sp3? I was looking also at the other platforms.

Comment 9

[Olli Pettay [:smaug][[e-mail]]]

I wonder, was 0.75% covering also the time outside the time which sp3 runner uses for the results?

Comment 10

[Timothy Nikkel (:tnikkel)]

(In reply to Olli Pettay [:smaug][[e-mail]] from comment #9)

I wonder, was 0.75% covering also the time outside the time which sp3 runner uses for the results?

Yes. We figured out that was the case on matrix, I never updated this bug with that information. (Which is why I haven't had time to come back to fix the review comments here.)

Comment 11

[Emilio Cobos Álvarez (:emilio)]

This has come up in other places tho, so would be nice to fix regardless

Comment 12

[Olli Pettay [:smaug][[e-mail]]]

Oh sure, I wasn't saying this isn't good :) This stuff does indeed show up in the profiles when not filtering out the not-measured parts of sp3.

Comment 13

[Timothy Nikkel (:tnikkel)]

Yeah, still worth it to do, just not as important as if it were on some critical paths for common interactive web operations.

Comment 15

[Pulsebot]

Pushed by [e-mail]:
https://hg.mozilla.org/integration/autoland/rev/a1695c424bbd
Change DocumentOrShadowRoot::StyleOrderIndexOfSheet to return size_t. r=emilio
https://hg.mozilla.org/integration/autoland/rev/8a1c41b85d1c
Avoid quadratic behaviour of FindDocStyleSheetInsertionPoint in the common append case. r=smaug

Comment 16

[Pulsebot]

Pushed by [e-mail]:
https://hg.mozilla.org/integration/autoland/rev/923fc29a2667
Fix an assert triggering in some devtools tests.

Comment 17

[Norisz Fay [:noriszfay]]

https://hg.mozilla.org/mozilla-central/rev/a1695c424bbd
https://hg.mozilla.org/mozilla-central/rev/8a1c41b85d1c
https://hg.mozilla.org/mozilla-central/rev/923fc29a2667

Comment 18

[Florin Bilt]

(In reply to Norisz Fay [:noriszfay] from comment #17)

https://hg.mozilla.org/mozilla-central/rev/a1695c424bbd
https://hg.mozilla.org/mozilla-central/rev/8a1c41b85d1c
https://hg.mozilla.org/mozilla-central/rev/923fc29a2667

Perfherder has detected a browsertime performance change from push 8a1c41b85d1ce6a77c2abc7c0df2af5ea4f3557a.

Improvements:

Ratio	Test	Platform	Options	Absolute values (old vs new)	Performance Profiles
8%	speedometer3 cpuTime	macosx1400-64-shippable-qr	fission webrender	48,010.34 -> 43,978.17	Before/After
3%	speedometer3 TodoMVC-Lit-Complex-DOM/DeletingAllItems/Async	macosx1400-64-shippable-qr	fission webrender	1.87 -> 1.82	Before/After

Details of the alert can be found in the alert summary, including links to graphs and comparisons for each of the affected tests.

If you need the profiling jobs you can trigger them yourself from treeherder job view or ask a sheriff to do that for you.

You can run these tests on try with ./mach try perf --alert 44206

For more information on performance sheriffing please see our FAQ.