Quadratic behavior in nsGenConList::Insert

RESOLVED FIXED in Firefox 55

Status

()

Core
Layout
RESOLVED FIXED
3 months ago
3 months ago

People

(Reporter: dmajor, Assigned: dmajor)

Tracking

(Blocks: 1 bug)

unspecified
mozilla55
Points:
---

Firefox Tracking Flags

(firefox55 fixed)

Details

(Whiteboard: [qf])

Attachments

(1 attachment, 1 obsolete attachment)

(Assignee)

Description

3 months ago
STR: load https://hg.mozilla.org/try/rev/0bb59a9f8a6e which is a page with a lot of  generated content for the line counters.

nsGenConList::Insert claims to do a binary search, but this is only with respect to the number of times it calls NodeAfter. Moving the start and end markers still happens linearly: https://dxr.mozilla.org/mozilla-central/rev/e03e0c60462c775c7558a1dc9d5cf2076c3cd1f9/layout/base/nsGenConList.cpp#125,128

Those two for loops run 170 million iterations on the repro link.
(Assignee)

Updated

3 months ago
Whiteboard: [qf]
(Assignee)

Comment 1

3 months ago
We're inserting a bunch of consecutive nodes into some random point of the list. We could probably avoid most of the traversals just by remembering the last insertion point.

(This is assuming that the "obvious" approach of switching data structures can't be done for some reason.)
We can improve the algorithm there by collecting all nodes into an vector, and doing binary search in the vector rather than linked-list. That should improve the time complexity to O(n + NodeAfter * lg n) which should be much better than it is now.
(Assignee)

Comment 3

3 months ago
Created attachment 8851461 [details] [diff] [review]
Remember the last insertion point

Would something like this work? I don't know if it's safe to hold on to a pointer like this -- I hope nobody mutates the links outside of Insert/Destroy.
Comment on attachment 8851461 [details] [diff] [review]
Remember the last insertion point

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

::: layout/base/nsGenConList.cpp
@@ +113,5 @@
>    if (mList.isEmpty() || NodeAfter(aNode, mList.getLast())) {
>      mList.insertBack(aNode);
> +  } else if (mLastInserted && NodeAfter(aNode, mLastInserted)) {
> +    // Fast path for inserting many consecutive nodes in one place
> +    mLastInserted->setNext(aNode);

You at least need to also check that NodeAfter(Next(mLastInserted), aNode) is also true, otherwise you may break the order.
(Assignee)

Comment 5

3 months ago
Created attachment 8851837 [details] [diff] [review]
Remember the last insertion point

Good point!
Assignee: nobody → dmajor
Attachment #8851461 - Attachment is obsolete: true
Attachment #8851837 - Flags: review?(xidorn+moz)
You also need to reset mLastInserted in nsGenConList::Destroy.

But before we proceed with this approach, could you confirm whether it really resolves this issue?

Also would this issue be resolved if we just optimize the general branch with the approach I mentioned in comment 2?
Flags: needinfo?(dmajor)
(Assignee)

Comment 7

3 months ago
(In reply to Xidorn Quan [:xidorn] (UTC+10) from comment #6)
> You also need to reset mLastInserted in nsGenConList::Destroy.

Thanks. I'll move the line from DestroyNodesFor() because it calls Destroy().

> But before we proceed with this approach, could you confirm whether it
> really resolves this issue?

For the usage patterns on this repro page, yes. 6051 out of 6056 searches are eliminated.

Total calls to Insert(): 150175
- insertBack fast path: 144119
- mLastInserted fast path: 6051
- remaining searches: 5

> Also would this issue be resolved if we just optimize the general branch
> with the approach I mentioned in comment 2?

Are you suggesting to create a temporary vector within Insert()? It would still be a linear operation to populate the vector, and multiplied by N calls to Insert(), the product is still N^2. Plus then you have a bunch of transient allocations. Unless I'm misunderstanding and you're suggesting something else...
Flags: needinfo?(dmajor)
(In reply to David Major [:dmajor] from comment #7)
> (In reply to Xidorn Quan [:xidorn] (UTC+10) from comment #6)
> > But before we proceed with this approach, could you confirm whether it
> > really resolves this issue?
> 
> For the usage patterns on this repro page, yes. 6051 out of 6056 searches
> are eliminated.
> 
> Total calls to Insert(): 150175
> - insertBack fast path: 144119
> - mLastInserted fast path: 6051
> - remaining searches: 5

Sounds good. OK.

> > Also would this issue be resolved if we just optimize the general branch
> > with the approach I mentioned in comment 2?
> 
> Are you suggesting to create a temporary vector within Insert()? It would
> still be a linear operation to populate the vector, and multiplied by N
> calls to Insert(), the product is still N^2. Plus then you have a bunch of
> transient allocations. Unless I'm misunderstanding and you're suggesting
> something else...

OK. We do want to avoid N^2 here. The current algorithm is something O((n + NodeAfter) * lg n), so it is probably still an improvement, but probably not enough for this case.
Comment on attachment 8851837 [details] [diff] [review]
Remember the last insertion point

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

I think this is fine.

And I think I was wrong that you should reset mLastInserted in nsGenConList::Destroy. I now think doing it in DestroyNodesFor is actually better, since it is the only callsite of nsGenConList::Destroy, and nsGenConList::Destroy is in a loop.

There is one further optimization we may be able to do on top of this change that, we can make use of the compare result of mLastInserted to reduce the range of binary search. It doesn't seem to be helpful for this case, but it might be something we can consider in the future. If we want to do that, probably we may not want to ever set mLastInserted to the last element.

::: layout/base/nsGenConList.cpp
@@ +111,5 @@
>  {
>    // Check for append.
>    if (mList.isEmpty() || NodeAfter(aNode, mList.getLast())) {
>      mList.insertBack(aNode);
> +  } else if (mLastInserted && NodeAfter(aNode, mLastInserted) &&

Probably add a condition that `mLastInserted != mList.getLast()` because it seems in majority of cases they would just be equal, and comparing aNode with the same node twice doesn't seem to be useful.
Attachment #8851837 - Flags: review?(xidorn+moz) → review+
Comment on attachment 8851837 [details] [diff] [review]
Remember the last insertion point

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

::: layout/base/nsGenConList.h
@@ +84,5 @@
>  protected:
>    mozilla::LinkedList<nsGenConNode> mList;
> +  // A weak pointer to the node most recently inserted, used to avoid repeated
> +  // list traversals in Insert().
> +  nsGenConNode* mLastInserted;

Also please move this to the `private` section at the end of this class. I don't think we want subclasses of it to access this field.
(Assignee)

Comment 11

3 months ago
Thanks!

Comment 12

3 months ago
Pushed by dmajor@mozilla.com:
https://hg.mozilla.org/integration/mozilla-inbound/rev/5544a84d59a4
Cache the most recent nsGenConNode to speed up future insertions. r=xidorn
backed out for bustage like https://treeherder.mozilla.org/logviewer.html#?job_id=86970185&repo=mozilla-inbound
Flags: needinfo?(dmajor)

Comment 14

3 months ago
Pushed by dmajor@mozilla.com:
https://hg.mozilla.org/integration/mozilla-inbound/rev/ae69e36301a0
Cache the most recent nsGenConNode to speed up future insertions. r=xidorn

Comment 15

3 months ago
Backout by cbook@mozilla.com:
https://hg.mozilla.org/integration/mozilla-inbound/rev/e0b2e9f5bc10
Backed out changeset 5544a84d59a4 for bustage

Comment 16

3 months ago
bugherder
https://hg.mozilla.org/mozilla-central/rev/ae69e36301a0
Status: NEW → RESOLVED
Last Resolved: 3 months ago
status-firefox55: --- → fixed
Resolution: --- → FIXED
Target Milestone: --- → mozilla55
(Assignee)

Updated

3 months ago
Flags: needinfo?(dmajor)
(Assignee)

Updated

3 months ago
Blocks: 827937
You need to log in before you can comment on or make changes to this bug.