Closed Bug 1285874 Opened 8 years ago Closed 7 years ago

removeChild is slow in a React-based testcase with large table

Categories

(Core :: Layout: Tables, defect, P3)

defect

Tracking

()

RESOLVED FIXED
mozilla54
Tracking Status
firefox54 --- fixed

People

(Reporter: julienw, Assigned: neerja)

References

Details

Attachments

(4 files, 12 obsolete files)

2.05 KB, patch
Details | Diff | Splinter Review
2.04 KB, patch
Details | Diff | Splinter Review
2.17 KB, text/html
Details
14.93 KB, patch
neerja
: review+
Details | Diff | Splinter Review
This comes from https://github.com/facebook/react/issues/7227

STR:
1. open http://stefankrause.net/js-frameworks-benchmark2/react-v0.14.8/index.html
2. click on "create 10000 rows"
3. click on "clear"
4. open the console to see the logs.

On the same computer, Firefox (tested nightly 50 from July 10) is ~3 times slower than Chromium (tested Debian's version 51.0.2704.79). It's not only the measurements, we can also definitely see it.

According to https://github.com/facebook/react/issues/7227#issuecomment-231541916, it may be because of removeChild being slow.
Hmm, is this part of bug 1282939?

I'll profile this shortly.
(In reply to Julien Wajsberg [:julienw] from comment #0)
> This comes from https://github.com/facebook/react/issues/7227
> 
> STR:
> 1. open
> http://stefankrause.net/js-frameworks-benchmark2/react-v0.14.8/index.html
> 2. click on "create 10000 rows"
> 3. click on "clear"
> 4. open the console to see the logs.
> 
> On the same computer, Firefox (tested nightly 50 from July 10) is ~3 times
> slower than Chromium (tested Debian's version 51.0.2704.79). It's not only
> the measurements, we can also definitely see it.


BTW, I'm refering to the "3. clear" part only here. Creating rows takes roughly the same time.
Of the time under in and under nsINode::RemoveChild, PresShell::ContentRemoved takes 98%.
->Layout.

nsTableFrame::AdjustRowIndices takes %75 (self time ~13%)
Self time of nsIFrame::StyleDisplay() is really high. ~65% in the profile I'm looking at (of that 100% nsINode::RemoveChild).
Component: DOM → Layout
Flags: needinfo?(dholbert)
Flags: needinfo?(dbaron)
So the basic problem is that nsTableRowFrame stores its index in the table.  This means when you remove a row you have to walk all the later ones and update the index in them.  Which means that if keep removing the _first_ row until all the rows are gone you'll take O(N^2) time.

I wonder whether it makes sense to just set a "row indices dirty" flag on the table, add checks for the flag in GetRowIndex, and update the row indices lazily...  It looks like we use the row index thing all over, so just getting rid of it would not be trivial.
Removing the firstChild while there are some children is actually a common idiom (even if it's not very efficient), see http://stackoverflow.com/questions/3955229/remove-all-child-elements-of-a-dom-node-in-javascript for example.
Yeah, it definitely is.  The fact that for table sections it has this layout-related problem in Gecko is really unfortunate.
[not sure I can add anything beyond what bz already said in comment 4 here; clearing needinfo.]
Flags: needinfo?(dholbert)
Summary: removeChild is slow in a React-based testcase → removeChild is slow in a React-based testcase with large table
Component: Layout → Layout: Tables
OS: Unspecified → All
Hardware: Unspecified → All
Version: unspecified → Trunk
(In reply to Boris Zbarsky [:bz] from comment #4)
> So the basic problem is that nsTableRowFrame stores its index in the table. 
> This means when you remove a row you have to walk all the later ones and
> update the index in them.  Which means that if keep removing the _first_ row
> until all the rows are gone you'll take O(N^2) time.
> 
> I wonder whether it makes sense to just set a "row indices dirty" flag on
> the table, add checks for the flag in GetRowIndex, and update the row
> indices lazily...  It looks like we use the row index thing all over, so
> just getting rid of it would not be trivial.

An alternative that would be faster in some cases, I think:
 * have a value of the row-index that means "dirty"
 * maintain the invariant that if a row's index is "dirty", all *later* rows are also dirty
 * replace callers to AdjustRowIndices with code to dirty the row indices starting at that row and all later rows (this is potentially more expensive, in a way that only calls OrderRowGroups if the dirtying needs to cross row groups
 * replace callers that use the row index with a getter that resolves dirtiness if needed (perhaps only in the current row group, up to the index needed, if that row group's first cell is not dirty, and globally if the first cell of the current row group is dirty)

Then again, we should look at the uses of the indices more carefully before deciding.


Jet, maybe you could assign this to somebody?  It might even be a decent second or third bug.
Needinfo'ing Jet for dbaron.
Flags: needinfo?(bugs)
Another reason why developers are still using the for loop instead of using textContent: in Chrome it's much faster.

See https://twitter.com/kdzwinel/status/756957360875249664
(In reply to Andrew McCreight [:mccr8] from comment #9)
> Needinfo'ing Jet for dbaron.

Neerja is looking into this bug for us.
Flags: needinfo?(npancholi)
Flags: needinfo?(dbaron)
Flags: needinfo?(bugs)
Priority: -- → P3
Assignee: nobody → npancholi
Flags: needinfo?(npancholi)
(In reply to David Baron :dbaron: ⌚️UTC+9 (busy until November 7) from comment #8)
> (In reply to Boris Zbarsky [:bz] from comment #4)
> > So the basic problem is that nsTableRowFrame stores its index in the table. 
> > This means when you remove a row you have to walk all the later ones and
> > update the index in them.  Which means that if keep removing the _first_ row
> > until all the rows are gone you'll take O(N^2) time.
> > 
> > I wonder whether it makes sense to just set a "row indices dirty" flag on
> > the table, add checks for the flag in GetRowIndex, and update the row
> > indices lazily...  It looks like we use the row index thing all over, so
> > just getting rid of it would not be trivial.
> 
> An alternative that would be faster in some cases, I think:
>  * have a value of the row-index that means "dirty"
>  * maintain the invariant that if a row's index is "dirty", all *later* rows
> are also dirty
>  * replace callers to AdjustRowIndices with code to dirty the row indices
> starting at that row and all later rows (this is potentially more expensive,
> in a way that only calls OrderRowGroups if the dirtying needs to cross row
> groups
>  * replace callers that use the row index with a getter that resolves
> dirtiness if needed (perhaps only in the current row group, up to the index
> needed, if that row group's first cell is not dirty, and globally if the
> first cell of the current row group is dirty)
> 
> Then again, we should look at the uses of the indices more carefully before
> deciding.
> 
> 
> Jet, maybe you could assign this to somebody?  It might even be a decent
> second or third bug.

I tried marking the row immediately following the deleted row as dirty and then resolving the dirty indices in the GetRowIndex method but realized that we need to resolve the dirty row indices during removal because we need to get the row-index to delete from the ordered row groups. So we don't actually end up making the delete row method efficient. 
See https://dxr.mozilla.org/mozilla-central/source/layout/tables/nsTableFrame.cpp#966 for an example of how removing rows requires calculating the resolved index.

To get around this, I modified the approach a bit by storing the deleted row indices (same as dirty row indices) in a balanced BST. So, given a dirty row index, we can cleanse it by simply subtracting the number of dirty row indices in the BST which are smaller than the index to cleanse. If the number of deleted row-indexes is r, we get
1. Remove row index time complexity of O(log r)
2. GetRowIndex time complexity of O(r)

To minimize the value of “r”, I represent consecutive deleted row indices in a single node (as a range). This makes the case where we remove consecutive rows (e.g. from the start or end of the table) almost O(1). In the average case this should still be good because r can never be more than n/2.

There is an added cost to the add row method. Essentially the first add row call has to be O(n log(r)) to cleanse all indices. But this is not much worse than the current O(n) and subsequent calls to add row are not impacted.

Would really appreciate your opinion on this approach :)

[More to come: Test showing a quantifiable improvement in the performance]
Flags: needinfo?(dbaron)
Attachment #8806597 - Attachment is obsolete: true
Just want to say that this is not necessarily ready for final review but I really want feedback on this. Thanks!
Comment on attachment 8808759 [details]
Bug 1285874 - Maintain a map of removed table-rows and use it to lazily recalculate row indices

https://reviewboard.mozilla.org/r/89184/#review91420

A few drive-by commit notes:

First, the commit message needs to explain at a high level what the patch actually *does*, rather than the problem that it fixes. Perhaps something like: "Maintain a map of removed table-rows, and use it to lazily recalculate row indices"

::: layout/tables/nsTableFrame.cpp:954
(Diff revision 2)
> +  for (uint32_t rgIdx = 0; rgIdx < rowGroups.Length(); rgIdx++) {
> +    rowGroups[rgIdx]->RecalculateRowIndices();

I think you can (& should) simplify to use a range-based for loop here.  This should work:

for (rowGroup : rowGroups) {
  rowGroup->RecalculateRowIndices();
}

::: layout/tables/nsTableFrame.cpp:969
(Diff revision 2)
> +  //Find the position of the current deleted row index among the previous deleted row indices
> +  //Call to mDeletedRowIndexRanges.upper_bound is O(log(mDeletedRowIndexRanges.size()))
> +  std::map<int32_t, int32_t>::iterator nextItr = mDeletedRowIndexRanges.upper_bound(aDeletedRowIndex);

There should be a space after "//" here (and after all of your added "//"-style comments).

Also, these lines should be wrapped to be a maximum of 80 characters long.
(In reply to Daniel Holbert [:dholbert] from comment #17)
> Comment on attachment 8808759 [details]
> Bug 1285874 - Maintain a map of removed table-rows and use it to lazily
> recalculate row indices
> 
> https://reviewboard.mozilla.org/r/89184/#review91420
> 
> A few drive-by commit notes:
> 
> First, the commit message needs to explain at a high level what the patch
> actually *does*, rather than the problem that it fixes. Perhaps something
> like: "Maintain a map of removed table-rows, and use it to lazily
> recalculate row indices"
> 
> ::: layout/tables/nsTableFrame.cpp:954
> (Diff revision 2)
> > +  for (uint32_t rgIdx = 0; rgIdx < rowGroups.Length(); rgIdx++) {
> > +    rowGroups[rgIdx]->RecalculateRowIndices();
> 
> I think you can (& should) simplify to use a range-based for loop here. 
> This should work:
> 
> for (rowGroup : rowGroups) {
>   rowGroup->RecalculateRowIndices();
> }
> 
> ::: layout/tables/nsTableFrame.cpp:969
> (Diff revision 2)
> > +  //Find the position of the current deleted row index among the previous deleted row indices
> > +  //Call to mDeletedRowIndexRanges.upper_bound is O(log(mDeletedRowIndexRanges.size()))
> > +  std::map<int32_t, int32_t>::iterator nextItr = mDeletedRowIndexRanges.upper_bound(aDeletedRowIndex);
> 
> There should be a space after "//" here (and after all of your added
> "//"-style comments).
> 
> Also, these lines should be wrapped to be a maximum of 80 characters long.

I just updated the patch with all the changes you pointed out in the comment. I also removed all cases of extra spacing between parentheses like if ( (..) ). Let me know if this looks good. Thanks! :)
Comment on attachment 8808759 [details]
Bug 1285874 - Maintain a map of removed table-rows and use it to lazily recalculate row indices

Due to the combination of bug 1224733, bug 1251455, and MozReview's
inability to inspect old patch state in a usable way (some combination
of bugs like bug 1234279, bug 1249468, bug 1296135), I'm no longer
accepting review requests in MozReview.   If you'd like me to review
patches, please submit those review requests as attached patch files.
Attachment #8808759 - Flags: review?(dbaron)
Attachment #8808759 - Attachment is obsolete: false
Attachment #8808759 - Attachment is obsolete: true
(In reply to David Baron :dbaron: ⌚️UTC+8 from comment #20)
> Comment on attachment 8808759 [details]
> Bug 1285874 - Maintain a map of removed table-rows and use it to lazily
> recalculate row indices
> 
> Due to the combination of bug 1224733, bug 1251455, and MozReview's
> inability to inspect old patch state in a usable way (some combination
> of bugs like bug 1234279, bug 1249468, bug 1296135), I'm no longer
> accepting review requests in MozReview.   If you'd like me to review
> patches, please submit those review requests as attached patch files.

I've attached a patch and marked the previous from MozReview one as obsolete. Thanks!
So in general an attached patch should include the commit message
and author (i.e., be generated by hg export or part of an mq series).
But in this case I can see that in the old MozReview request.

A few questions before I review in detail:

It looks like RemoveRows calls AddDeletedRowIndex, but RemoveRows
seems like it can handle removal of *multiple* rows, whereas the call
seems to only add a single row index to the list of deleted indices.
That seems wrong to me, but I might be missing something.  Am I?

This approach also seems less than ideal in that it doesn't make similar
optimizations for row insertion.  Did you consider approaches that would
handle insertion quickly as well?  It seems that, say, maintaining
indices using a balanced binary tree rather than storing them on the
rows might make insertion/removal of a row be roughly O(log(rowcount)).
(I also wonder if we have a space-efficient implementation of a binary
tree that stores the tree in a single array, with a node's at index I's
parent at floor((I-1)/2), or something like that?)  Maybe that's more
than is really needed here, though; I think changing to lazy
recomputation ought to be sufficient and perhaps even more effective.  I
also haven't thought any of this through in detail.

That said, I don't fully understand the usage pattern here.  Did you
look at who *uses* the row indices and what they're used for?  If so,
could you summarize that?  In particular, it seems interesting whether
there are callers that happen during frame construction (definitely
destruction, and maybe parts of construction that would happen
synchronously, although I'm not sure how much of frame construction
happens synchronously these days), or whether they're all in layout.
Since if they're all in layout, doing something involving laziness seems
like it should be effective since it will still allow a large sequence
of DOM manipulations (including frame destruction and maybe construction
that happens synchronously) without a huge amount of work (in
particular, the dirtying for all of the manipulations together should be
at worst O(rowcount), and you should only need to call OrderRowGroups if
the last row in removed/added row's rowgroup is not already dirty)

from comment 13:
> resolve the dirty row indices during removal because we need to get
> the row-index to delete from the ordered row groups

I don't see why this is actually necessary.  If you change to a
different strategy for dirtying the row indices, you can avoid this call
to GetRowIndex.

also from comment 13:
>I tried marking the row immediately following the deleted row as dirty
>and then resolving the dirty indices in the GetRowIndex method

You'd need to mark *all* the rows after the deleted row as dirty, but
you could stop when you find a row that's already marked dirty.
Flags: needinfo?(dbaron) → needinfo?(npancholi)
Comment on attachment 8809514 [details] [diff] [review]
Bug 1285874 - Maintain a map of removed table-rows and use it to lazily recalculate row indices

Cancelling the review request for now. 
I am in the process of making some changes according to what Dbaron mentioned in comment 23. I will be talking with him over IRC about some of the details and re-post for review soon.
Attachment #8809514 - Attachment is obsolete: true
Flags: needinfo?(npancholi)
Attachment #8809514 - Flags: review?(dbaron)
(In reply to David Baron :dbaron: ⌚️UTC-8 from comment #23)
> from comment 13:
> > resolve the dirty row indices during removal because we need to get
> > the row-index to delete from the ordered row groups
> 
> I don't see why this is actually necessary.  If you change to a
> different strategy for dirtying the row indices, you can avoid this call
> to GetRowIndex.

OK, I think I was wrong about this, since it is needed for the call nsTableFrame::RemoveRows makes to cellMap->RemoveRows.




But what about a strategy where we store on the table a value that says "row indices greater than this value are invalid and need to be recomputed"?  Would that help with sequential removal of rows?
(In reply to David Baron :dbaron: ⌚️UTC-8 from comment #25)
> (In reply to David Baron :dbaron: ⌚️UTC-8 from comment #23)
> > from comment 13:
> > > resolve the dirty row indices during removal because we need to get
> > > the row-index to delete from the ordered row groups
> > 
> > I don't see why this is actually necessary.  If you change to a
> > different strategy for dirtying the row indices, you can avoid this call
> > to GetRowIndex.
> 
> OK, I think I was wrong about this, since it is needed for the call
> nsTableFrame::RemoveRows makes to cellMap->RemoveRows.
> 
> 
> 
> 
> But what about a strategy where we store on the table a value that says "row
> indices greater than this value are invalid and need to be recomputed"? 
> Would that help with sequential removal of rows?


Sorry for the late reply. I was trying to work out that approach but while doing it I realized something else. I tried using Cleopatra to profile the performance of nsTableFrame::RemoveRows with and without the fix but I couldn't get a definitive answer so I just wrote a log with the runtime for this function. This is what I see for deleting 10,000 rows on my machine. 
Total time is 2258683358 nanoseconds ~2.25 seconds <-Without patch
Total time is 114050534 nanoseconds ~0.11 seconds <-With patch

This shows a 20x improvement but when you look at the react log: 
(There is a huge variability when running react but I'm mentioning just one reading and the 9 second improvement may not be consistent)
With patch:
runLots took 54863.13 ms
clear took 16455.515 ms

Without patch:
runLots took 66431.66000000003 ms
clear took 25077.099999999977 ms

So, you can see that there is a lot of overhead which is the source of most of the inefficiency. To know what this is exactly, I need to figure out how to use Cleopatra better but this proves that the nsTableFrame::RemoveRows function is not the source of the bottleneck. Even if we fix this, we get a max ~2 seconds improvement and there is still ~16 seconds of something else going on which is masking any gain in performance. So whichever approach we take will have this problem. 
I thought this is important to mention since the last time we spoke you said that any complexity introduced by fixing this bug has to be justified by significant gains in performance and looking at this I'm afraid we might never get to it without looking elsewhere for the fix. What do you think?
What do the Cleopatra profiles with and without the patch look like?
Cleopatra doesn't always give very low level information, so using other profilers can be useful too.
(In reply to Boris Zbarsky [:bz] (still a bit busy) from comment #27)
> What do the Cleopatra profiles with and without the patch look like?

Here are the profiles I was looking at yesterday. Both of them profile the 'Clear' operation for 10,000 rows:

Profile1 - Does not use my patch.
https://clptr.io/2hN9TSo

Function names I was looking for:
nsTableFrame::RemoveRows
nsTableFrame::AdjustRowIndices
nsTableRowFrame::GetRowIndex

Profile2 - Uses my patch.
https://clptr.io/2hN9TSo

Function names I was looking for:
nsTableFrame::RemoveRows
nsTableRowFrame::GetRowIndex
(function nsTableFrame::AdjustRowIndices is no longer being used)
Those are the same exact link, right?  That said, I have one more question.  The times you cite without your patch are:

  runLots took 66431.66000000003 ms
  clear took 25077.099999999977 ms

and I assume that's following the steps in comment 0.  I just tried those in today's nightly, and I get:

  runLots took 2595.869999999999
  clear took 1286.2249999999985

I really hope my hardware is not 20x faster than your!.  Is it possible you were measuring in a debug build, not an opt one?  If so, it's worth remeasuring in an opt build.
(In reply to Boris Zbarsky [:bz] (still a bit busy) from comment #30)
> Those are the same exact link, right?  That said, I have one more question. 
> The times you cite without your patch are:
> 
>   runLots took 66431.66000000003 ms
>   clear took 25077.099999999977 ms
> 
> and I assume that's following the steps in comment 0.  I just tried those in
> today's nightly, and I get:
> 
>   runLots took 2595.869999999999
>   clear took 1286.2249999999985
> 
> I really hope my hardware is not 20x faster than your!.  Is it possible you
> were measuring in a debug build, not an opt one?  If so, it's worth
> remeasuring in an opt build.

I was using a debug build to look at react but I assumed it would affect the function timing evenly but I realize that might not be the case so I'm going to try this again on an opt build. (Sorry about the duplicate link, let me regenerate this)
> I assumed it would affect the function timing evenly

Not at all.  For one thing, the JS engine does a _huge_ amount more work in debug builds verifying various invariants hold.  So a debug build will very much skew where the bottlenecks are just for that reason.  It also used to be that we had some layout algorithms that had different big-O behavior in opt and debug builds, though we've tried to get rid of that....
(In reply to Boris Zbarsky [:bz] (still a bit busy) from comment #32)
> > I assumed it would affect the function timing evenly
> 
> Not at all.  For one thing, the JS engine does a _huge_ amount more work in
> debug builds verifying various invariants hold.  So a debug build will very
> much skew where the bottlenecks are just for that reason.  It also used to
> be that we had some layout algorithms that had different big-O behavior in
> opt and debug builds, though we've tried to get rid of that....

Thanks for pointing this out :). It was the debug that was causing the extra ~16 seconds from the react point of view. The good news is that without debug mode my patch does cut the time in half :) Here are some timings I get along with the Cleopatra profiles -

Without patch: https://clptr.io/2hQTjRk
[Main Thread]: I/example_logger Total time is 864729232 nanoseconds ~0.8 seconds

runLots took 2630.0399999999936 ms
clear took 1645.6549999999988 ms

With patch:  https://clptr.io/2ioBd6a
[Main Thread]: I/example_logger Total time is 35283144 nanoseconds ~0.03 seconds

runLots took 3022.115 ms
clear took 955.9850000000006 ms

Sorry for the confusion! But thankfully this approach does help the performance so I'm going to continue looking at dbaron's suggestion and try to make this simpler.
That looks more like it.  ;)  removeChild is going from 61% of the time to 33%.  And a quarter of that is the log_print you have there, looks like (presumably the timing logging you mention in comment 12), so just taking it out will give an ~60ms easy win.

The other thing you may want to do to get numbers more comparable to release is to set your "javascript.options.asyncstack" preference to false in whatever profile you use for performance testing.  Async stack capture is certainly showing up on the non-removeChild bits of that profile and hence reducing the relative importance of removeChild.  ;)
Attachment #8834684 - Attachment description: TableCreateAndRemoveRowsRuntimeTest.html → TableCreateAndRemoveRowsRuntimeTest.html [warning: may hang your browser for a little while when loaded]
Thanks a lot bz for taking a look at this!

I have added an updated patch with fixes and a test case for this. 
Clean try run for this patch is at:
https://treeherder.mozilla.org/#/jobs?repo=try&revision=828cac92ceaa44e110d3d5777ae834e89bdadc52

Looking at the terminal log for total runtime of nsTableFrame::RemoveRows(below) produced with my test case and the Cleopatra profiles that bz looked at (here: Comment 34), this patch definitely works to really speed up the running time for nsTableFrame::RemoveRows and so I am marking it for review. 

Runtimes with opt build for deleting 10,000 rows with my test case-

With Patch:
2017-02-07 21:22:07.073240 UTC - [Main Thread]: I/example_logger Total runtime is 66400414 nanoseconds ~0.06 seconds

Without Patch:
2017-02-07 21:13:50.932791 UTC - [Main Thread]: I/example_logger Total runtime is 1045297430 nanoseconds ~1.05 seconds

This speedup is not completely apparent when looking at the numbers printed directly on the console via the react test case or my test case, possibly because we are not running it enough number of times or there might be inefficiency somewhere else. But, I think this is ok since the patch clearly works for speeding up nsTableFrame::RemoveRows and so I think this is good for review.
Flags: needinfo?(dbaron)
One example run of my test case with and without the patch prints the following on the console -
**I have javascript.options.asyncstack turned off as pointed out by bz.

With fix -
Time to create 10000 rows = 421 ms 
Time to remove 10000 rows = 55 ms

Without fix -
Time to create 10000 rows = 409 ms  
Time to remove 10000 rows = 622 ms
Attachment #8834610 - Flags: review?(dbaron)
Clearing needinfo flag for dbaron and setting the review flag instead.
Flags: needinfo?(dbaron)
Comment on attachment 8834610 [details] [diff] [review]
Bug 1285874 - Maintain a map of removed table-rows and use it to lazily recalculate row indices

Throughout, please use "iter" or "...Iter" for iterator variable
names rather than "itr" or "...Itr".

I'd also suggest changing the terminology from "original index"
to "stored index" throughout, since the "original index" can get
rewritten by RecalculateRowIndices.


In nsTableRowGroupFrame::RecalculateRowIndices, please use static_cast
rather than C-style casts, and use a variable rather than casting twice.
(Perhaps rename rowFrame to child, and make the new variable rowFrame?)

Also, RecalculateRowIndices looks like it recalculates the row indices
for the entire table using the adjustment, which as a whole is
O(N * log(N)) in the number of rows (assuming
GetAdjustmentForOriginalIndex is O(log N) as the comment says).
That seems entirely unnecessary.  It would be faster to recalculate them
from scratch (O(N)).  It would also be less risky for future
maintenance of the code, since somebody in the future might assume that
RecalculateRowIndices actually recalculates them, and might decide to
use the function to recalculate them after making changes that aren't
reflected in mDeletedRowIndexRanges (especially since it's not clearly
documented that it depends on that).  So I think you should just rewrite
RecalculateRowIndices to renumber from start to end.


In nsTableRowGroupFrame::MarkRowsAsDeleted:

 * put spaces around the <.

 * add a FIXME comment suggesting that the separate AddDeletedRowIndex
   calls could be optimized.

 * eliminate the numOfDeletedRows variable by just decrementing
   aNumRowsToDelete as you go.

 * the assertion isn't particularly useful, since it's asserting
   *after* null-checking that the frame could be queried to
   nsTableRowFrame.  Instead, move the assertion to the end of the loop,
   and assert that either aNumRowsToDelete is 0, or that you have a
   non-null sibling.  Or, perhaps better, restructure the loop a bit:

   for (;;) {
     currentRowFrame->AddDeletedRowIndex();
     if (--aNumRowsToDelete == 0) {
       break;
     }
     currentRowFrame = do_QueryFrame(currentRowFrame->GetNextSibling());
     if (!currentRowFrame) {
       MOZ_ASSERT_UNREACHABLE("expected another row frame");
       break;
     }
   }

In nsTableFrame::AddDeletedRowIndex:

>+  if (smallerItr != mDeletedRowIndexRanges.begin())
>+    smallerItr--;

Put {} around the if-body.

Also:

>+  if ((smallerItr->second == aDeletedRowOriginalIndex - 1) &&
>+      (greaterItr != mDeletedRowIndexRanges.end()) &&
>+      (greaterItr->first == aDeletedRowOriginalIndex + 1)) {
>+    // merge current index with smaller and greater range as they are consecutive
>+    smallerItr->second = greaterItr->second;
>+    mDeletedRowIndexRanges.erase(greaterItr);
>+  } else if (smallerItr->second == aDeletedRowOriginalIndex - 1) {
>+    // add aDeletedRowOriginalIndex in the smaller range as it is consecutive
>+    smallerItr->second = aDeletedRowOriginalIndex;

The first condition is the same between these, so please merge the two
into:

  if (smallerItr->second == aDeletedRowOriginalIndex - 1) {
    if (greaterItr != mDeletedRowIndexRanges.end() &&
        greaterItr->first == aDeletedRowOriginalIndex + 1) {
      ...
    } else {
      ...
    }
which also removes the over-parenthesization.

And also please don't over-parenthesize in the following condition, i.e.,
write it as:

>  } else if (greaterItr != mDeletedRowIndexRanges.end() &&
>             greaterItr->first == aDeletedRowOriginalIndex + 1) {


In GetAdjustmentForOriginalIndex, this code:

>+  auto itr = mDeletedRowIndexRanges.upper_bound(aOriginalIndex);
>+
>+  if (itr != mDeletedRowIndexRanges.begin())
>+    itr--;
>+  else
>+    return 0; // No rows above this have been deleted, therefore '0' adjustment.
>+
>+  while (itr != mDeletedRowIndexRanges.begin()) {
>+    adjustment += (itr->second - itr->first + 1);
>+    itr--;
>+  }
>+
>+  adjustment += (itr->second - itr->first + 1);

can be simplified to just this:

>  auto endIter = mDeletedRowIndexRanges.upper_bound(aOriginalIndex);
>  for (auto iter = mDeletedRowIndexRanges.begin(); iter != endIter; ++iter) {
>    adjustment += (iter->second - iter->first + 1);
>  }


If you're going to fix the indentation here:

> nsTableFrame::RemoveRows(nsTableRowFrame& aFirstRowFrame,
>-                              int32_t          aNumRowsToRemove,
>-                              bool             aConsiderSpans)
>+                              int32_t     aNumRowsToRemove,
>+                              bool        aConsiderSpans)

Please instead fix it to be:

>nsTableFrame::RemoveRows(nsTableRowFrame& aFirstRowFrame,
>                         int32_t          aNumRowsToRemove,
>                         bool             aConsiderSpans)


In nsTableFrame.h:

>+  /** Add the originalIndex of the current row to the existing ranges of

"originalIndex of the current row" -> "given index"

>+   *  Note - 'original' here refers to the index that was assigned to
>+   *  the row before any remove row operations were performed.

This comment should also explain that this means it's the mRowIndex
member variable, not the result of GetRowIndex.



In nsTableRowFrame::SetRowIndex, please assert that the table does
not have any adjustments.  (This is more practical given my comment
above about rewriting RecalculateRowIndices, but it's important to
ensure that the invariants set up here aren't violated by adding new
rows once we already have adjustments.)


In nsTableRowGroupFrame.h, I'd suggest making most of the comments say
"see nsTableFrame.h" rather than trying to repeat some of the material.
Possibly the same for nsTableRowFrame.h.  (Although maybe some of the
comments belong in nsTableRowFrame.h... but it's best to have them in
one place, with the others pointing to it.)



Could you also please file a followup bug on removing all the null-checks
on the results of nsTableFrame::GetCellMap()?  I don't believe it's
possible for an initialized frame to have GetCellMap() return null,
so all of those checks are useless.  (I say this because I had to figure
out when GetCellMap() returns null to figure out whether your change
to nsTableFrame::RemoveRows was valid... and the answer is that it should
never be null, so it's not an issue.)


Marking review- since I'd like to see a revised patch with these issues
addressed.

Note that I didn't go through the previous review comments this time; I'm
assuming you've addressed those right now, but I do intend to go through
them for the final review, along with double-checking that all the removal
callers are handled (which I believe we reviewed before).
Attachment #8834610 - Flags: review?(dbaron) → review-
(In reply to David Baron :dbaron: ⌚️UTC-8 from comment #45)
> can be simplified to just this:
> 
> >  auto endIter = mDeletedRowIndexRanges.upper_bound(aOriginalIndex);
> >  for (auto iter = mDeletedRowIndexRanges.begin(); iter != endIter; ++iter) {
> >    adjustment += (iter->second - iter->first + 1);
> >  }

Actually, without overparenthesization, this should be:

>  auto endIter = mDeletedRowIndexRanges.upper_bound(aOriginalIndex);
>  for (auto iter = mDeletedRowIndexRanges.begin(); iter != endIter; ++iter) {
>    adjustment += iter->second - iter->first + 1;
>  }
Adding this comment as a checklist to make sure I addressed everything - 

(In reply to David Baron :dbaron: ⌚️UTC-8 from comment #45)
> Comment on attachment 8834610 [details] [diff] [review]
> Bug 1285874 - Maintain a map of removed table-rows and use it to lazily
> recalculate row indices
> 
> Throughout, please use "iter" or "...Iter" for iterator variable
> names rather than "itr" or "...Itr".
RESOLVED

> I'd also suggest changing the terminology from "original index"
> to "stored index" throughout, since the "original index" can get
> rewritten by RecalculateRowIndices.
RESOLVED

> 
> In nsTableRowGroupFrame::RecalculateRowIndices, please use static_cast
> rather than C-style casts, and use a variable rather than casting twice.
> (Perhaps rename rowFrame to child, and make the new variable rowFrame?)
RESOLVED

> Also, RecalculateRowIndices looks like it recalculates the row indices
> for the entire table using the adjustment, which as a whole is
> O(N * log(N)) in the number of rows (assuming
> GetAdjustmentForOriginalIndex is O(log N) as the comment says).
> That seems entirely unnecessary.  It would be faster to recalculate them
> from scratch (O(N)).  It would also be less risky for future
> maintenance of the code, since somebody in the future might assume that
> RecalculateRowIndices actually recalculates them, and might decide to
> use the function to recalculate them after making changes that aren't
> reflected in mDeletedRowIndexRanges (especially since it's not clearly
> documented that it depends on that).  So I think you should just rewrite
> RecalculateRowIndices to renumber from start to end.
RESOLVED

> 
> In nsTableRowGroupFrame::MarkRowsAsDeleted:
> 
>  * put spaces around the <.
RESOLVED

>  * add a FIXME comment suggesting that the separate AddDeletedRowIndex
>    calls could be optimized.
RESOLVED

>  * eliminate the numOfDeletedRows variable by just decrementing
>    aNumRowsToDelete as you go.
RESOLVED

>  * the assertion isn't particularly useful, since it's asserting
>    *after* null-checking that the frame could be queried to
>    nsTableRowFrame.  Instead, move the assertion to the end of the loop,
>    and assert that either aNumRowsToDelete is 0, or that you have a
>    non-null sibling.  Or, perhaps better, restructure the loop a bit:
> 
>    for (;;) {
>      currentRowFrame->AddDeletedRowIndex();
>      if (--aNumRowsToDelete == 0) {
>        break;
>      }
>      currentRowFrame = do_QueryFrame(currentRowFrame->GetNextSibling());
>      if (!currentRowFrame) {
>        MOZ_ASSERT_UNREACHABLE("expected another row frame");
>        break;
>      }
>    }
RESOLVED

> In nsTableFrame::AddDeletedRowIndex:
> 
> >+  if (smallerItr != mDeletedRowIndexRanges.begin())
> >+    smallerItr--;
> 
> Put {} around the if-body.
RESOLVED

> Also:
> 
> >+  if ((smallerItr->second == aDeletedRowOriginalIndex - 1) &&
> >+      (greaterItr != mDeletedRowIndexRanges.end()) &&
> >+      (greaterItr->first == aDeletedRowOriginalIndex + 1)) {
> >+    // merge current index with smaller and greater range as they are consecutive
> >+    smallerItr->second = greaterItr->second;
> >+    mDeletedRowIndexRanges.erase(greaterItr);
> >+  } else if (smallerItr->second == aDeletedRowOriginalIndex - 1) {
> >+    // add aDeletedRowOriginalIndex in the smaller range as it is consecutive
> >+    smallerItr->second = aDeletedRowOriginalIndex;
> 
> The first condition is the same between these, so please merge the two
> into:
> 
>   if (smallerItr->second == aDeletedRowOriginalIndex - 1) {
>     if (greaterItr != mDeletedRowIndexRanges.end() &&
>         greaterItr->first == aDeletedRowOriginalIndex + 1) {
>       ...
>     } else {
>       ...
>     }
> which also removes the over-parenthesization.
RESOLVED

> And also please don't over-parenthesize in the following condition, i.e.,
> write it as:
> 
> >  } else if (greaterItr != mDeletedRowIndexRanges.end() &&
> >             greaterItr->first == aDeletedRowOriginalIndex + 1) {
RESOLVED

> 
> In GetAdjustmentForOriginalIndex, this code:
> 
> >+  auto itr = mDeletedRowIndexRanges.upper_bound(aOriginalIndex);
> >+
> >+  if (itr != mDeletedRowIndexRanges.begin())
> >+    itr--;
> >+  else
> >+    return 0; // No rows above this have been deleted, therefore '0' adjustment.
> >+
> >+  while (itr != mDeletedRowIndexRanges.begin()) {
> >+    adjustment += (itr->second - itr->first + 1);
> >+    itr--;
> >+  }
> >+
> >+  adjustment += (itr->second - itr->first + 1);
> 
> can be simplified to just this:
> 
> >  auto endIter = mDeletedRowIndexRanges.upper_bound(aOriginalIndex);
> >  for (auto iter = mDeletedRowIndexRanges.begin(); iter != endIter; ++iter) {
> >    adjustment += (iter->second - iter->first + 1);
> >  }
RESOLVED

> If you're going to fix the indentation here:
> 
> > nsTableFrame::RemoveRows(nsTableRowFrame& aFirstRowFrame,
> >-                              int32_t          aNumRowsToRemove,
> >-                              bool             aConsiderSpans)
> >+                              int32_t     aNumRowsToRemove,
> >+                              bool        aConsiderSpans)
> 
> Please instead fix it to be:
> 
> >nsTableFrame::RemoveRows(nsTableRowFrame& aFirstRowFrame,
> >                         int32_t          aNumRowsToRemove,
> >                         bool             aConsiderSpans)
RESOLVED

> 
> In nsTableFrame.h:
> 
> >+  /** Add the originalIndex of the current row to the existing ranges of
> 
> "originalIndex of the current row" -> "given index"
RESOLVED

> >+   *  Note - 'original' here refers to the index that was assigned to
> >+   *  the row before any remove row operations were performed.
> 
> This comment should also explain that this means it's the mRowIndex
> member variable, not the result of GetRowIndex.
RESOLVED


> In nsTableRowFrame::SetRowIndex, please assert that the table does
> not have any adjustments.  (This is more practical given my comment
> above about rewriting RecalculateRowIndices, but it's important to
> ensure that the invariants set up here aren't violated by adding new
> rows once we already have adjustments.)
RESOLVED
 
> In nsTableRowGroupFrame.h, I'd suggest making most of the comments say
> "see nsTableFrame.h" rather than trying to repeat some of the material.
> Possibly the same for nsTableRowFrame.h.  (Although maybe some of the
> comments belong in nsTableRowFrame.h... but it's best to have them in
> one place, with the others pointing to it.)
RESOLVED

> Could you also please file a followup bug on removing all the null-checks
> on the results of nsTableFrame::GetCellMap()?  I don't believe it's
> possible for an initialized frame to have GetCellMap() return null,
> so all of those checks are useless.  (I say this because I had to figure
> out when GetCellMap() returns null to figure out whether your change
> to nsTableFrame::RemoveRows was valid... and the answer is that it should
> never be null, so it's not an issue.)
RESOLVED - Bug 1341940


> Marking review- since I'd like to see a revised patch with these issues
> addressed.
> 
> Note that I didn't go through the previous review comments this time; I'm
> assuming you've addressed those right now, but I do intend to go through
> them for the final review, along with double-checking that all the removal
> callers are handled (which I believe we reviewed before).
Addressed as part of the next comment
Checklist to make sure that I addressed all of these issues pointed by dbaron - 

(In reply to David Baron :dbaron: ⌚️UTC-8 from comment #23)
> So in general an attached patch should include the commit message
> and author (i.e., be generated by hg export or part of an mq series).
> But in this case I can see that in the old MozReview request.
> 
> A few questions before I review in detail:
> 
> It looks like RemoveRows calls AddDeletedRowIndex, but RemoveRows
> seems like it can handle removal of *multiple* rows, whereas the call
> seems to only add a single row index to the list of deleted indices.
> That seems wrong to me, but I might be missing something.  Am I?
Yes, this was a bug. AddDeletedRowIndex was not handling the case for 
deleting multiple rows at a time. I fixed this.
RESOLVED.

> This approach also seems less than ideal in that it doesn't make similar
> optimizations for row insertion.  Did you consider approaches that would
> handle insertion quickly as well?  It seems that, say, maintaining
> indices using a balanced binary tree rather than storing them on the
> rows might make insertion/removal of a row be roughly O(log(rowcount)).
> (I also wonder if we have a space-efficient implementation of a binary
> tree that stores the tree in a single array, with a node's at index I's
> parent at floor((I-1)/2), or something like that?)  Maybe that's more
> than is really needed here, though; I think changing to lazy
> recomputation ought to be sufficient and perhaps even more effective.  I
> also haven't thought any of this through in detail.
Had a discussion with dbaron about this and he mentioned that this is not a
concern for now so marking this resolved.
RESOLVED.

> That said, I don't fully understand the usage pattern here.  Did you
> look at who *uses* the row indices and what they're used for?  If so,
> could you summarize that?  In particular, it seems interesting whether
> there are callers that happen during frame construction (definitely
> destruction, and maybe parts of construction that would happen
> synchronously, although I'm not sure how much of frame construction
> happens synchronously these days), or whether they're all in layout.
> Since if they're all in layout, doing something involving laziness seems
> like it should be effective since it will still allow a large sequence
> of DOM manipulations (including frame destruction and maybe construction
> that happens synchronously) without a huge amount of work (in
> particular, the dirtying for all of the manipulations together should be
> at worst O(rowcount), and you should only need to call OrderRowGroups if
> the last row in removed/added row's rowgroup is not already dirty)
Had a discussion with dbaron about this. Originally I thought "synchronously"
meant handling concurrency but dbaron explained to me that this was more
about batching operations together to prevent unnecessary reflow. 
In the end dbaron suggested that this case no longer applies so marking as resolved.
RESOLVED.

> from comment 13:
> > resolve the dirty row indices during removal because we need to get
> > the row-index to delete from the ordered row groups
> 
> I don't see why this is actually necessary.  If you change to a
> different strategy for dirtying the row indices, you can avoid this call
> to GetRowIndex.
> 
> also from comment 13:
> >I tried marking the row immediately following the deleted row as dirty
> >and then resolving the dirty indices in the GetRowIndex method
> 
> You'd need to mark *all* the rows after the deleted row as dirty, but
> you could stop when you find a row that's already marked dirty.
This was addressed by dbaron as part of Comment 25.
RESOLVED.
Comment on attachment 8840230 [details] [diff] [review]
Bug 1285874 - Maintain a map of removed table-rows and use it to lazily recalculate row indices

In nsTableFrame::RecalculateRowIndices:
>+  RowGroupArray rowGroups;
>+  OrderRowGroups(rowGroups);
>+  mDeletedRowIndexRanges.clear();

Probably clearer to put the mDeletedRowIndexRanges.clear() before
the other two lines, and with a blank line separating them.

In nsTableFrame::IsDeletedRowIndexRangesEmpty:
>+  return mDeletedRowIndexRanges.size() == 0 ? true:false;

drop the " ? true:false".

And also use .empty() instead of .size() == 0.

Also, the method should probably be inlined in the header, so that
it will be inlined into the caller.

In the comment in the header:

>++  /** Returns true if size of mDeletedRowIndexRanges is zero else false

Should just be "Returns whether mDeletedRowIndexRanges is empty".

In nsTableRowFrame::SetRowIndex:
>+  MOZ_ASSERT(GetTableRowGroupFrame()->
>+             GetTableFrame()->IsDeletedRowIndexRangesEmpty(),
>+             "mDeletedRowIndexRanges should be empty here!");

Please indent the *middle* of these 3 lines by 2 more spaces.

r=dbaron with those changes
Attachment #8840230 - Flags: review?(dbaron) → review+
Attachment #8840564 - Flags: review+
Attachment #8840564 - Attachment is obsolete: true
Attachment #8840230 - Attachment is obsolete: false
Attachment #8840588 - Attachment is obsolete: true
Attachment #8840588 - Attachment description: Bug 1285874 - Maintain a map of removed table-rows and use it to lazily recalculate row indices → Bug 1285874 - Maintain a map of removed table-rows and use it to lazily recalculate row indices r=dbaron
Attachment #8840588 - Attachment is obsolete: false
Attachment #8840588 - Attachment description: Bug 1285874 - Maintain a map of removed table-rows and use it to lazily recalculate row indices r=dbaron → Bug 1285874 - Maintain a map of removed table-rows and use it to lazily recalculate row indices. r=dbaron
Added a new patch with these changes.

CHECKLIST - 

(In reply to David Baron :dbaron: ⌚️UTC-8 from comment #50)
> Comment on attachment 8840230 [details] [diff] [review]
> Bug 1285874 - Maintain a map of removed table-rows and use it to lazily
> recalculate row indices
> 
> In nsTableFrame::RecalculateRowIndices:
> >+  RowGroupArray rowGroups;
> >+  OrderRowGroups(rowGroups);
> >+  mDeletedRowIndexRanges.clear();
> 
> Probably clearer to put the mDeletedRowIndexRanges.clear() before
> the other two lines, and with a blank line separating them.
RESOLVED

> In nsTableFrame::IsDeletedRowIndexRangesEmpty:
> >+  return mDeletedRowIndexRanges.size() == 0 ? true:false;
>
> drop the " ? true:false".
> 
> And also use .empty() instead of .size() == 0.
RESOLVED

> Also, the method should probably be inlined in the header, so that
> it will be inlined into the caller.
RESOLVED

> In the comment in the header:
> 
> >++  /** Returns true if size of mDeletedRowIndexRanges is zero else false
> 
> Should just be "Returns whether mDeletedRowIndexRanges is empty".
RESOLVED

> In nsTableRowFrame::SetRowIndex:
> >+  MOZ_ASSERT(GetTableRowGroupFrame()->
> >+             GetTableFrame()->IsDeletedRowIndexRangesEmpty(),
> >+             "mDeletedRowIndexRanges should be empty here!");
> 
> Please indent the *middle* of these 3 lines by 2 more spaces.
RESOLVED

> r=dbaron with those changes
Try run with this patch doesn't show any related failures:
https://treeherder.mozilla.org/#/jobs?repo=try&revision=c1c7546c86a2c2ebb204e97facc61b8b07ffaef4&selectedJob=81027411

(**The Android reftest failure initially looked related to me but it seems to happen even without this patch -> https://treeherder.mozilla.org/#/jobs?repo=try&revision=9bf03e655be34fc2494755909b1301988e6de484&selectedJob=81254663)
Attachment #8840590 - Attachment is obsolete: true
Flags: needinfo?(dbaron)
Comment on attachment 8843079 [details] [diff] [review]
Bug 1285874 - Maintain a map of removed table-rows and use it to lazily recalculate row indices. r?dbaron

>+inline bool nsTableFrame::IsDeletedRowIndexRangesEmpty() const
>+{
>+  return mDeletedRowIndexRanges.empty();
>+}
>+

There's no need for this to be outside of the class definition.  Move it inside, like most inline methods, e.g., http://searchfox.org/mozilla-central/rev/546a05fec017cb785fca62a5199d42812a6a1fd3/layout/style/nsRuleNode.h#829

r=dbaron with that
Flags: needinfo?(dbaron)
Attachment #8843079 - Flags: review+
Attachment #8843079 - Attachment is obsolete: true
(In reply to David Baron :dbaron: ⌚️UTC-8 from comment #56)
> Comment on attachment 8843079 [details] [diff] [review]
> Bug 1285874 - Maintain a map of removed table-rows and use it to lazily
> recalculate row indices. r?dbaron
> 
> >+inline bool nsTableFrame::IsDeletedRowIndexRangesEmpty() const
> >+{
> >+  return mDeletedRowIndexRanges.empty();
> >+}
> >+
> 
> There's no need for this to be outside of the class definition.  Move it
> inside, like most inline methods, e.g.,
> http://searchfox.org/mozilla-central/rev/
> 546a05fec017cb785fca62a5199d42812a6a1fd3/layout/style/nsRuleNode.h#829
> 
> r=dbaron with that

Done. Thanks Dbaron!
Pushed by dholbert@mozilla.com:
https://hg.mozilla.org/integration/mozilla-inbound/rev/85613fa0c5fe
Maintain a map of removed table-rows and use it to lazily recalculate row indices. r=dbaron
https://hg.mozilla.org/mozilla-central/rev/85613fa0c5fe
Status: NEW → RESOLVED
Closed: 7 years ago
Resolution: --- → FIXED
Target Milestone: --- → mozilla54
Depends on: 1344542
Depends on: 1344628
Depends on: 1345352
It's possible that bug 560613 was this exact same problem, filed 7 years ago...
Blocks: 560613
Blocks: 559396
You need to log in before you can comment on or make changes to this bug.