Bug 1493420 - Use a RwLock'd HashMap instead of a lock-free linked list for rule node children. r=heycam
ClosedPublic
Actions

Authored by emilio on Sep 25 2018, 4:21 PM.

Details

Reviewers

heycam
xidorn

Commits

rMOZILLACENTRAL2428766459c6: Bug 1493420 - Use a RwLock'd HashMap instead of a lock-free linked list for…

Bugzilla Bug ID

1493420

Summary

I need to profile this a bit more, but talos was pretty happy about this, and it
solves the known performance issues here such as the test-case from bug 1483963
for example. This also gets rid of a bunch of unsafe code which is nice.

This still keeps the same GC scheme, removing the key from the hashmap when
needed. I kept those as release assertions, but should probably be turned into
debug-only assertions.

Test Plan

No behavior change, so no new tests, though we should probably
consider landing a perf_reftest based on the testcase from bug 1483963...

Diff Detail

Repository

rMOZILLACENTRAL mozilla-central

Lint

Automatic diff as part of commit; lint not applicable.

Unit

Automatic diff as part of commit; unit tests not applicable.

Event Timeline

emilio created this revision.Sep 25 2018, 4:21 PM

Herald added a project: Restricted Project. · View Herald TranscriptSep 25 2018, 4:21 PM

phab-bot changed the visibility from "Custom Policy" to "Public (No Login Required)".Sep 25 2018, 4:21 PM

phab-bot changed the edit policy from "Custom Policy" to "Restricted Project (Project)".

phab-bot removed a project: Restricted Project.

Harbormaster completed remote builds in B11595: Diff 18514.Sep 25 2018, 4:21 PM

emilio requested review of this revision.Sep 25 2018, 4:21 PM

Not feel confident enough to review rule tree changes.

Minor bits that benchmarking and profiling brought up.

Harbormaster completed remote builds in B11781: Diff 18871.Sep 26 2018, 1:30 PM

Per discussion in the bug, I'd like to try the hybrid approach, or see strong evidence + explanation that the results in the microbenchmark don't translate to real sites.

This revision now requires changes to proceed.Sep 28 2018, 4:53 PM

bholley removed a reviewer: bholley.Mar 9 2019, 12:10 AM

This revision now requires review to proceed.Mar 9 2019, 12:10 AM

I did some analysis a few months ago with three different options -- the current lock free linked lists, a hybrid approach, and the locked HashMap. I don't have the details any more unfortunately (I meant to write them up at the time but didn't get around to it), but my conclusion was that the hybrid approach didn't buy us anything, and it would be fine to just go with the locked HashMap.

As mentioned in IRC, the only other thing I wondered was whether it was worth using a Vec for the children below some limit, before upgrading it to a HashMap, since I've noticed recently other places where hash table lookup overhead showing up in profiles. But since rule tree manipulation is a small proportion of overall styling time that complexity may not be worth it.

servo/components/style/rule_tree/mod.rs
845–846	This no longer applies, and I guess the function can be safe now.
919–938	These changes seem logically separate from the child list data structure changes, so would have been better in a separate patch.

This revision is now accepted and ready to land.May 29 2019, 10:54 PM

emilio marked 2 inline comments as done.May 29 2019, 11:40 PM

Rebase

Harbormaster completed remote builds in B78049: Diff 111969.May 29 2019, 11:40 PM

emilio retitled this revision from Bug 1493420 - Use a RwLock'd HashMap instead of a lock-free linked list for rule node children. to Bug 1493420 - Use a RwLock'd HashMap instead of a lock-free linked list for rule node children. r=heycam.May 29 2019, 11:40 PM

emilio edited the summary of this revision. (Show Details)

Closed by commit rMOZILLACENTRAL2428766459c6: Bug 1493420 - Use a RwLock'd HashMap instead of a lock-free linked list for… (authored by emilio). · Explain WhyMay 29 2019, 11:44 PM

This revision was automatically updated to reflect the committed changes.