<a class="header-button" href="https://bugzilla.mozilla.org/home" title="Go to home page"> Bugzilla

Olli Pettay [:smaug][bugs@pettay.fi]

Assignee

Comment 2

•

2 years ago

Bug 1872535 introduced reordering of ranges inside of a Selection. Ranges are expected to be sorted by their start point. With implementation of custom highlight API, Selections can now also contain Static Ranges. After a DOM mutation the static range may not be at the right position in this list anymore -- hence we need to to run through the sorting algorithm again. Sorting the ranges involves lots of DOM point comparisons. Comparing two points is very expensive. Hence the jank we can see in the profile.
Bug 1878504 was already attempting to fix this by reducing the criteria which trigger a reordering.

While I could not reproduce the exact issue in about:settings, I managed to write a test case which shows similar behavior (also attached) and used it to do a profiling case study to find optimization potential.

Test case

The test case triggers DOM mutation (triggering the "the DOM has changed" marker) and adds a new range (triggering the reorder algorithm since the "the DOM has changed" marker is active):

<!DOCTYPE html>
<body></body>
<script>
  const sel = document.getSelection();

  for (let i = 0; i < 10000; i++) {
    const newdiv = document.createElement("div");
    newdiv.textContent = "Hi there!";
    document.body.appendChild(newdiv);
    const r = document.createRange();
    r.selectNode(newdiv);
    sel.addRange(r);
  }
</script>

The following optimization measures was done on Ubuntu. The given timings show the DOM computation which is visible in the respective profiles. Each measure has been run only once and the timings were gathered from the profiler UI, so are far from accurate. However, they give a sufficient overview of the situation.

Current situation

Running the test case on a release build revealed that 9.6 seconds were spent in DOM computations, to a large extent (85%) in the ReorderRangesIfNecessary() function.

Baseline: Remove the function

Removing the calls to ReorderRangesIfNecessary() (or making it a noop) gives 1.4 seconds being spent in DOM computation. The goal will be coming as close as possible to this point.

Using the existing cache

The expensive part of comparing points is computing the index of a node inside of its parent, because this is essentially a O(n) operation over the number of children of parent each time it is called (children are stored as a list, not an array).

There exists a Cache that can be passed into nsContentUtils::ComparePoints(), which keeps pointers to the last parent/child/index combination. If the function happens to be called with the same combo, the expensive call to nsINode:::ComputeIndexOf() can be saved.

Adding this cache to the reordering algorithm unfortunately had no effect. This is not very surprising as the cache only considers the last used value, however we are iterating several values lots of times.

Implementing a different kind of cache

Since the code checks the same nodes over and over again, it may make sense to cache all of them. The first approach here uses a stack-allocated array of parent/child/index combos:

  struct ComparePointsCache2 {
    ComparePointsCache2() {
      for(size_t i = 0; i < 100; ++i) {
        mParents[i] = nullptr;
        mChildren[i] = nullptr;
        mIndices[i] = mozilla::Nothing();
      }
    }
    mozilla::Maybe<uint32_t> ComputeIndexOf(const nsINode* aParent, const nsINode* aChild) {
      for(size_t i = 0; i < mLength; ++i) {
        if(mParents[i] == aParent && mChildren[i] == aChild) {
          return mIndices[i];
        }
      }
      mozilla::Maybe<uint32_t> index = aParent->ComputeIndexOf(aChild);
      if(mLength < 100) {
        mParents[mLength] = aParent;
        mChildren[mLength] = aChild;
        mIndices[mLength] = index;
        ++mLength;
        return index;
      }
      mParents[mOldest] = aParent;
      mChildren[mOldest] = aChild;
      mIndices[mOldest] = index;
      ++mOldest;
      if(mOldest == 100) {
        mOldest = 0;
      }
      return index;
    }
   private:
    const nsINode* mParents[100]{};
    const nsINode* mChildren[100]{};
    mozilla::Maybe<uint32_t> mIndices[100];
    size_t mLength{0};
    size_t mOldest{0};
  };

This cache will keep up to N parent/child/index combinations, while not requiring any allocation.
For N = 10 8.5 s are spent in DOM computations, for N = 100 it's 8.3 seconds.

This is still not acceptable.

Check if sorting is necessary

In the given example, it will never be necessary to reorder. And it can be expected that this will be the case in many real-world examples. Given that we have a cache that keeps most / all of the parent/child/index combos so that looking them up is cheap, we could invest num of ranges - 1 calls to ComparePoints() up front to check if we have to reorder. This is being done by changing the sort call to this:

    nsContentUtils::ComparePointsCache2 cache;
    bool reordering = false;
    AbstractRange* prev = nullptr;
    for (auto& range : mRanges) {
      if (!prev) {
        prev = range.mRange;
        continue;
      }
      if (CompareToRangeStart2(*range.mRange->GetStartContainer(),
                               range.mRange->StartOffset(), *prev,
                               &cache) != 1) {
        reordering = true;
        break;
      }
    }
    if (reordering) {
      mRanges.Sort([&cache](const StyledRange& a, const StyledRange& b) -> int {
        return CompareToRangeStart2(*a.mRange->GetStartContainer(),
                                    a.mRange->StartOffset(), *b.mRange, &cache);
      });
    }

This drops the amount of time spent in the DOM computations to 1.9 s, which should be good enough for now.

However, I am still not sure if the reordering is necessary at all if there are only live ranges. It seems that things have worked before, so it might be okay to only call this if there are static ranges present. This would reduce the computation effort for the given test case to 1.4 s (see Baseline) while keeping the perhaps-broken status quo (so it wouldn't break anything new).

Flags: needinfo?(jjaschke) → needinfo?(smaug)

Comment 3

•

2 years ago

But things have not really worked with live ranges. And don't we need fast sorting anyhow for highlight API?
Are there any drawbacks to use that last approach?

Flags: needinfo?(smaug)

Assignee

Comment 4

•

2 years ago

I currently don’t see drawbacks to the last approach (new cache and check if sorting is needed).
We need this fast approach definitely for custom highlight. However, we could opt to only use it if static ranges are present, since it will introduce a performance regression (even though a much smaller one when this is important).

I would make the implementation sound now and put it up for review, thanks! :)

Assignee

Comment 5

•

2 years ago

Attached file Bug 1881695: Implemented a new Cache to store the index of a node in a parent. r=smaug!,#dom-core — Details

This new cache implementation keeps the last N node/index combos in a stack-allocated array, which will be queried before calling nsINode::ComputeIndexOf().

Updated

•

2 years ago

Assignee: nobody → jjaschke

Status: NEW → ASSIGNED

Narcis Beleuzu [:NarcisB]

Comment 6

•

2 years ago

Pushed by jjaschke@mozilla.com: https://hg.mozilla.org/integration/autoland/rev/cc11e54ef4b1 Implemented a new Cache to store the index of a node in a parent. r=smaug

Comment 7

•

2 years ago

Backed out for bustages on nsContentUtils.h

Backout link: https://hg.mozilla.org/integration/autoland/rev/aacf5bfc85b147b82cfe590a4451d0792aebdd2e
Log link: https://treeherder.mozilla.org/logviewer?job_id=449936941&repo=autoland&lineNumber=19806

Flags: needinfo?(jjaschke)

Assignee

Comment 8

•

2 years ago

My bad, sorry. Should be fixed now.

Flags: needinfo?(jjaschke)

Comment 9

•

2 years ago

Pushed by jjaschke@mozilla.com: https://hg.mozilla.org/integration/autoland/rev/e72815765675 Implemented a new Cache to store the index of a node in a parent. r=smaug

Assignee

Comment 10

•

2 years ago

Attached file Bug 1881695: Implemented a new Cache to store the index of a node in a parent. r=smaug!,#dom-core (obsolete) — Details

This new cache implementation keeps the last N node/index combos in a stack-allocated array, which will be queried before calling nsINode::ComputeIndexOf().

Original Revision: https://phabricator.services.mozilla.com/D203900

Updated

•

2 years ago

Attachment #9390006 - Flags: approval-mozilla-beta?

Cristina Horotan [:chorotan]

Comment 11

•

2 years ago

Uplift Approval Request

Fix verified in Nightly: yes
Is Android affected?: yes
String changes made/needed: -
User impact if declined: Searching in about:settings might be slow and lead to a bad user experience
Steps to reproduce for manual QE testing: Search und delete text in search field for about:settings (see description in comment 0)..
Risk associated with taking this patch: low
Code covered by automated testing: no
Explanation of risk level: This code touches relatively hot paths in Selection. However the new cache approach should not lead to perf regressions.
Needs manual QE test: yes

Flags: qe-verify+

Comment 12

•

2 years ago

Backed out changeset e72815765675 (bug 1881695) for causing Hazard failure at nsContentUtils.h

Backout; https://hg.mozilla.org/integration/autoland/rev/6efffffd0dc4ba0005af868fa59f9e9a494a9078

Failure push: https://treeherder.mozilla.org/jobs?repo=autoland&group_state=expanded&resultStatus=testfailed%2Cbusted%2Cexception%2Cretry%2Cusercancel&revision=e7281576567562c045eba058013864843a68d5f0

Failure log: https://treeherder.mozilla.org/logviewer?job_id=449966231&repo=autoland&lineNumber=92902

Flags: needinfo?(jjaschke)

Comment 13

•

2 years ago

Pushed by jjaschke@mozilla.com: https://hg.mozilla.org/integration/autoland/rev/37af5c6d011a Implemented a new Cache to store the index of a node in a parent. r=smaug

Narcis Beleuzu [:NarcisB]

Assignee

Updated

•

2 years ago

Flags: needinfo?(jjaschke)

Comment 14

•

2 years ago

bugherder

https://hg.mozilla.org/mozilla-central/rev/37af5c6d011a

Status: ASSIGNED → RESOLVED

Closed: 2 years ago

status-firefox125: affected → fixed

Resolution: --- → FIXED

Target Milestone: --- → 125 Branch

Dianna Smith [:diannaS]

Updated

•

2 years ago

Updated

•

2 years ago

Comment 15

•

2 years ago

•

Edited

Going to hold off on uplift until the above two crashes are investigated

Natalia Csoregi [:nataliaCs]

Assignee

Comment 16

•

2 years ago

They are definitely regressions. I don’t understand the cause yet, the change seems riskier than anticipated. I think it’s better not to uplift the patch to beta.

Comment 17

•

2 years ago

Backed out for causing Bug 1884602 and Bug 1884601

backout: https://hg.mozilla.org/integration/autoland/rev/f64e162799d9bd2165756c4d7690068eb14545af

Status: RESOLVED → REOPENED

status-firefox125: fixed → ---

Flags: needinfo?(jjaschke)

Resolution: FIXED → ---

Target Milestone: 125 Branch → ---

Brindusa Tot, DTE

Updated

•

2 years ago

QA Whiteboard: [qa-triaged]

Sebastian Hengst [:aryx] (needinfo me if it's about an intermittent or backout)

Updated

•

2 years ago

Regressions: 1884601

BugBot [:suhaib / :marco/ :calixte]

Comment 18

•

2 years ago

Set release status flags based on info from the regressing bug 1872535

status-firefox125: --- → affected

Dianna Smith [:diannaS]

Updated

•

2 years ago

status-firefox124: affected → wontfix

Updated

•

2 years ago

Attachment #9390006 - Attachment is obsolete: true

Attachment #9390006 - Flags: approval-mozilla-beta?

Dianna Smith [:diannaS]

Updated

•

2 years ago

Regressions: 1884602

Assignee

Comment 19

•

2 years ago

Four time's a charm...

Flags: needinfo?(jjaschke)