1378201 - TableRowsCollection uses live node lists quite eagerly

Status: RESOLVED FIXED

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

Description

[(no longer active)]

I noticed this while profiling jandem's profileviewer tool on a Speedometer profile, which creates a very large table with tons of rows.  See this profile where 1.7 seconds is spent in nsContentList::PopulateSelf().  https://perfht.ml/2snkZQv

The tab was completely hung at this point and this profile only captures a very brief portion of the hang.

The JS code triggering the hang is as follows:

function clearFramesTable() {
    var framesTable = document.getElementById("frames");
    framesTable.style.display = "none";
    for (var i = framesTable.rows.length - 1; i > 0; i--)
        framesTable.deleteRow(i);
}

Note the |rows.length| getter.  Here is how we implement it:

https://searchfox.org/mozilla-central/rev/a3a739de04ee6134c11546568a33dbb6a6a29907/dom/html/HTMLTableElement.cpp#168

The DO_FOR_EACH_BY_ORDER macro *creates* new nsContentList objects as it iterates over nodes!  See for example <https://searchfox.org/mozilla-central/rev/a3a739de04ee6134c11546568a33dbb6a6a29907/dom/html/HTMLTableElement.cpp#117> which gets to <https://searchfox.org/mozilla-central/rev/a3a739de04ee6134c11546568a33dbb6a6a29907/dom/html/HTMLTableSectionElement.cpp#50>  This is very inefficient, as these nodes need to scan all of their subtree in the PopulateSelf() call seen in the profile before they can answer queries like GetLength() and they will receive mutation events etc.  It would be nice to see if we can rework these algorithms to not require live nsContentLists.

Comment 1

[Jan de Mooij [:jandem]]

(In reply to :Ehsan Akhgari (needinfo please, extremely long backlog) from comment #0)
> I noticed this while profiling jandem's profileviewer tool on a Speedometer
> profile, which creates a very large table with tons of rows.

In case somebody tries to reproduce this, I changed the page to get rid of the rows.length getter. It also (by default) limits the number of rows to 3000 now.

It should be easy to come up with a micro-benchmark for this, of course (create a table with many rows, then use table.rows.length).

Comment 2

[Nika Layzell [:nika] (ni? for response)]

Attachment: Improve the performance of TableRowsCollection

This patch improves the performance of my local microbenchmarks a lot. Here are some numbers (look at my attached microbenchmark for what these mean - smaller is better):

nightly:
 - remove: 828ms
 - append: 1702ms
 - iterate: 4233ms
 - before: 10124ms

patch:
 - remove: 33ms
 - append: 28ms
 - iterate: 28ms
 - before: 63ms

I did this by making the TableRowsCollection register a mutation observer and
perform minimal changes to its internal mRows object every time that a mutation
occurs, rather than re-computing the list of rows every time a question about
them is asked.

The unfortunate part about this is that if a rows object is created and used on
a table, all mutations of the table now cause the rows object to be updated in
the mutation observer, which means that the operations may be more expensive if
the rows object is never used again. I'm not sure if it would be possible or
desirable to improve this situation at all, for example, by only recording the
mutation events which are recieved and then flushing when data is actually
requested. This is only a concern because the mutation observer performs a bit
of pointer chasing to determine where to insert the newly added row.

Currently doing a try push to make sure that this actually passes all of our
tests.

MozReview-Commit-ID: 4joB73SXNGA

Comment 3

[Nika Layzell [:nika] (ni? for response)]

Attachment: small benchmark

Comment 4

[Nika Layzell [:nika] (ni? for response)]

Comment on attachment 8884069 [details] [diff] [review]
Improve the performance of TableRowsCollection

Oops, I accidentally didn't delete some of the methods from earlier versions of the patch while rebasing. clearing review, and I'll fix it up tomorrow.

Comment 5

[Nika Layzell [:nika] (ni? for response)]

Attachment: Improve the performance of TableRowsCollection

Fixed some test failures from my try push, improved the optimization a bit, and removed some unused methods.

I think this is ready for a review now. I tried to make sure that the mutation observer wouldn't add too significant overhead to table mutations once they are set up.

All in all I think that this should be faster than the original TableRowsCollection, with the sole exception of the case where JS creates and then never calls any methods on the TableRowsCollection object, which doesn't seem worth optimizing for.

Benchmark times look about the same, and this code doesn't really appear in the profiles for any of my benchmarks, making me think that this is now almost completely dwarfed by other DOM mutation overhead.

MozReview-Commit-ID: 4joB73SXNGA

Comment 6

[Nika Layzell [:nika] (ni? for response)]

(In reply to Michael Layzell [:mystor] from comment #5)
> Benchmark times look about the same, and this code doesn't really appear in
> the profiles for any of my benchmarks, making me think that this is now
> almost completely dwarfed by other DOM mutation overhead.

OK - so that's not completely true. Looking at a profile I just took, I got 18 samples in `HandleInsert` in the `before` test, which is a pretty bad case for any TableRowsCollection algorithm (it used to take 10 seconds!). I don't know how to make that any faster though, as I need to do that work at some point.

Comment 7

[(no longer active)]

Comment on attachment 8884326 [details] [diff] [review]
Improve the performance of TableRowsCollection

Review of attachment 8884326 [details] [diff] [review]:
-----------------------------------------------------------------

Looks great overall, thanks a lot.  I have a few small comments below.

::: dom/html/HTMLTableElement.cpp
@@ +118,5 @@
> +
> +  // Initialize mRows as the TableRowsCollection is created. The mutation
> +  // observer should keep it up to date.
> +  //
> +  // It should be extremely unlikely that anyone creates a TableRowsCollection

I actually don't think this assumption is necessarily true.  This code can basically run if a page runs the .rows getter on a table object.  There are two bad implications of running this code eagerly:

1. The work that it does may be out of date by the time that one of its other methods are invoked, for example, if the page does something like |var rows = table.rows;| and use the rows variable later.
2. Even more importantly, it registers a mutation observer eagerly, and mutation observers are expensive.  Especially given this code: <https://searchfox.org/mozilla-central/rev/f1472e5b57fea8d4a7bbdd81c44e46958fe3c1ce/dom/html/HTMLTableElement.cpp#383> once this object is initialized, the mutation observer is basically not going to get cleared.  (I filed bug 1379216 for that.)

So I think it's better to have a mInitialized boolean member and move this code to an EnsureInitialized() member and call it from the getters that need it instead.

@@ +132,5 @@
> +           inner; inner = inner->GetNextSibling()) {
> +        if (inner->IsHTMLElement(nsGkAtoms::tr)) {
> +          mRows.AppendElement(inner);
> +        }
> +      }

Nit: if it's easy, please consider refactoring this inner loop inside a helper lambda and call it three times instead of copying it?

@@ +168,5 @@
>    // instantiator who provided mParent is responsible for managing our
>    // reference for us.
> +  if (mParent) {
> +    mParent->RemoveMutationObserver(this);
> +  }

I think you also want to give this a LastRelease() function and remove the mutation observer when the refcount drops to 0, similar to bug 1376936.  And please put the cleanup code in a helper and call it from both places.

@@ +303,5 @@
> +    (aContainer == mParent ||
> +     (aContainer->GetParent() == mParent &&
> +      (aContainer->IsHTMLElement(nsGkAtoms::thead) ||
> +       aContainer->IsHTMLElement(nsGkAtoms::tbody) ||
> +       aContainer->IsHTMLElement(nsGkAtoms::tfoot))));

Nit: please use IsAnyOfHTMLElements() instead.

@@ +364,5 @@
> +  // individually.
> +  if (aContainer == mParent &&
> +      (aChild->IsHTMLElement(nsGkAtoms::thead) ||
> +       aChild->IsHTMLElement(nsGkAtoms::tbody) ||
> +       aChild->IsHTMLElement(nsGkAtoms::tfoot))) {

Ditto.

@@ +515,5 @@
> +  // remove any `tr`s in our list which have that element as its parent node. In
> +  // any other situation, the removal won't affect us, so we can ignore it.
> +  if (!aChild->IsHTMLElement(nsGkAtoms::thead) &&
> +      !aChild->IsHTMLElement(nsGkAtoms::tbody) &&
> +      !aChild->IsHTMLElement(nsGkAtoms::tfoot)) {

Ditto.

Comment 8

[(no longer active)]

(In reply to Michael Layzell [:mystor] from comment #6)
> (In reply to Michael Layzell [:mystor] from comment #5)
> > Benchmark times look about the same, and this code doesn't really appear in
> > the profiles for any of my benchmarks, making me think that this is now
> > almost completely dwarfed by other DOM mutation overhead.
> 
> OK - so that's not completely true. Looking at a profile I just took, I got
> 18 samples in `HandleInsert` in the `before` test, which is a pretty bad
> case for any TableRowsCollection algorithm (it used to take 10 seconds!). I
> don't know how to make that any faster though, as I need to do that work at
> some point.

Try to use a native profiler to see how the time is spent in that function.  That may give you a hint on how to optimize it further?

(But I suggest that we can also do further optimizations in follow-up bugs!)

Comment 9

[Nika Layzell [:nika] (ni? for response)]

Attachment: Improve the performance of TableRowsCollection

MozReview-Commit-ID: 4joB73SXNGA

Comment 10

[(no longer active)]

Comment on attachment 8884406 [details] [diff] [review]
Improve the performance of TableRowsCollection

Review of attachment 8884406 [details] [diff] [review]:
-----------------------------------------------------------------

Very nice, thanks a lot!

::: dom/html/HTMLTableElement.cpp
@@ +63,5 @@
> +  void LastRelease()
> +  {
> +    CleanUp();
> +  }
> +  virtual ~TableRowsCollection()

This doesn't need to be virtual BTW.

@@ +196,5 @@
> +  // at us.
> +  mRows.Clear();
> +  mBodyStart = 0;
> +  mFootStart = 0;
> +  mInitialized = true;

Why this?

@@ +564,5 @@
> +
> +void
> +TableRowsCollection::NodeWillBeDestroyed(const nsINode* aNode)
> +{
> +  mInitialized = false; // Don't bother cleaning up our mutation observer, as it's going away.

Why this?  I mean, EnsureInitialized() shouldn't get called after this point so it should be no-op but it seems unnecessary to pretend we support bringing this object back to life.

Comment 11

[Pulsebot]

Pushed by [e-mail]:
https://hg.mozilla.org/integration/mozilla-inbound/rev/1f83acf33534
Improve the performance of TableRowsCollection, r=ehsan

Comment 12

[Wes Kocher (:KWierso) (Not reading bugmail; email directly if needed)]

https://hg.mozilla.org/mozilla-central/rev/1f83acf33534