1350770 - Quadratic behavior in nsGenConList::Insert

Status: RESOLVED FIXED

(Core :: Layout, defect)

Description

[(Away)]

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.

Comment 1

[(Away)]

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.)

Comment 2

[Xidorn Quan [:xidorn] UTC+10]

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.

Comment 3

[(Away)]

Attachment: 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 4

[Xidorn Quan [:xidorn] UTC+10]

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.

Comment 5

[(Away)]

Attachment: Remember the last insertion point

Good point!

Comment 6

[Xidorn Quan [:xidorn] UTC+10]

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?

Comment 7

[(Away)]

(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...

Comment 8

[Xidorn Quan [:xidorn] UTC+10]

(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 9

[Xidorn Quan [:xidorn] UTC+10]

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.

Comment 10

[Xidorn Quan [:xidorn] UTC+10]

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.

Comment 11

[(Away)]

Thanks!

Comment 12

[Pulsebot]

Pushed by [e-mail]:
https://hg.mozilla.org/integration/mozilla-inbound/rev/5544a84d59a4
Cache the most recent nsGenConNode to speed up future insertions. r=xidorn

Comment 13

[Carsten Book [:Tomcat]]

backed out for bustage like https://treeherder.mozilla.org/logviewer.html#?job_id=86970185&repo=mozilla-inbound

Comment 14

[Pulsebot]

Pushed by [e-mail]:
https://hg.mozilla.org/integration/mozilla-inbound/rev/ae69e36301a0
Cache the most recent nsGenConNode to speed up future insertions. r=xidorn

Comment 15

[Pulsebot]

Backout by [e-mail]:
https://hg.mozilla.org/integration/mozilla-inbound/rev/e0b2e9f5bc10
Backed out changeset 5544a84d59a4 for bustage

Comment 16

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

https://hg.mozilla.org/mozilla-central/rev/ae69e36301a0