2066058 - Make nsDOMMutationObserver receiver lookup O(1)

Status: RESOLVED FIXED

(Core :: DOM: Core & HTML, enhancement)

Comment 1

[Mayank Bansal]

Attachment: Bug 2066058 - Make nsDOMMutationObserver receiver lookup O(1). r=jjaschke

GetReceiverFor linear-scanned mReceivers. It runs once per observe() and,
via GetAllSubtreeObserversFor, once per ancestor that has an observer on
every mutation, so a single MutationObserver watching N nodes was O(N^2) on
setup and paid O(N) per mutation. This is the more idiomatic usage than the
many-observers-on-one-node case in bug 1952616: frameworks share one
observer across many targets.

mReceivers stays the owning, ordered storage and mReceiverMap is added
purely as a lookup index. Replacing the array outright would be smaller, but
three loops over mReceivers - the CC unlink body, Disconnect, and
RemoveClones - call into receiver code that can run arbitrary destructors,
which is safe while indexing an array and is mutation-during-iteration on a
hashtable. The array also gives GetObservingInfo (ChromeOnly) a stable
order. So the array keeps its job and the map only answers "which receiver
watches this node".

Keys are raw nsINode*. They cannot dangle: a target that dies runs
nsMutationReceiver::NodeWillBeDestroyed, which calls Disconnect(true), which
removes the entry before the node is gone.

RemoveReceiver takes the target explicitly because Disconnect clears mTarget
before calling it. Its mReceivers.RemoveObject is still O(N) and is left
that way deliberately: it is only reached when one target dies, while the
bulk paths (Disconnect, CC unlink) drop every receiver at once and are O(N)
in total. Making it O(1) would need either unordered removal plus an index,
reintroducing the two-structures-in-sync problem this patch avoids, or
dropping the array, which the iteration hazard above rules out.

Unmeasured: no profile drove this, it fell out of reviewing the bug 1952616
patch. The complexity claim is from source, not from a benchmark.

Comment 2

[Mayank Bansal]

try: https://treeherder.mozilla.org/jobs?repo=try&revision=de6dedede31db3d890addb4711aed2cec10ffc29
sp3 perfcompare: https://perf.compare/compare-results?baseRev=7dd0e00d755920961bfd7bbf065d85820062a0bb&baseRepo=try&newRev=8c68bdf77915a31b466cd5acbd5ff24ff0a10fa1&newRepo=try&framework=13

Comment 3

[Pulsebot]

Pushed by [e-mail]:
https://github.com/mozilla-firefox/firefox/commit/d48e4cfbff4b
https://hg.mozilla.org/integration/autoland/rev/94c111d03325
Make nsDOMMutationObserver receiver lookup O(1). r=jjaschke

Comment 4

[Cristian Tuns]

https://hg.mozilla.org/mozilla-central/rev/94c111d03325