1149235 - Handling of many async scripts in nsScriptLoader::ProcessPendingRequests is slow

Status: RESOLVED FIXED

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

Description

[Boris Zbarsky [:bzbarsky]]

The current setup in nsScriptLoader::ProcessPendingRequests does this:

  uint32_t i = 0;
  while (mEnabled && i < mAsyncRequests.Length()) {
    if (!mAsyncRequests[i]->mLoading) {
      request.swap(mAsyncRequests[i]);
      mAsyncRequests.RemoveElementAt(i);
      ProcessRequest(request);
      continue;
    }
    ++i;
  }

This is pretty bad when mAsyncRequests.Length() is large: we'll get one callback from necko for each one, and each callback will set mLoading on _one_ thing in the list and then call ProcessPendingRequests.  So we get O(N^2) behavior.

I'm going to switch to using separate lists for loading and loaded async requests, and doubly linked lists for nsScriptLoadRequest so we don't have to do this silliness and can remove things from the middle of the list quickly.  The other option would probably be to use a hashset or something for mLoading/LoadedAsyncRequests, I guess, but I think the general idea of linked lists makes a lot of sense for most of the stuff in scriptloader.

Comment 1

[Boris Zbarsky [:bzbarsky]]

Attachment: part 1. Move nsScriptLoadRequest into nsScriptLoader.h

Comment 2

[Boris Zbarsky [:bzbarsky]]

Attachment: part 2. Switch to using linked lists for nsScriptLoadRequest

Comment 3

[Boris Zbarsky [:bzbarsky]]

Attachment: part 3. Store async requests in the scriptloader in two lists, so we don't have to grovel about looking for loaded ones

Comment 4

[Boris Zbarsky [:bzbarsky]]

Attachment: part 2. Switch to using linked lists for nsScriptLoadRequest

Comment 5

[Boris Zbarsky [:bzbarsky]]

Attachment: part 2. Switch to using linked lists for nsScriptLoadRequest

Comment 6

[Jonas Sicking (:sicking) No longer reading bugmail consistently]

My queue is long enough that it'd probably be better to find someone else to review.

Comment 7

[Boris Zbarsky [:bzbarsky]]

Let's try Olli.

Comment 8

[Olli Pettay [:smaug][[e-mail]]]

Will do, Tuesday at latest.

Comment 9

[Olli Pettay [:smaug][[e-mail]]]

Comment on attachment 8586791 [details] [diff] [review]
part 2.  Switch to using linked lists for nsScriptLoadRequest


>-  for (uint32_t i = 0; i < mXSLTRequests.Length(); i++) {
>-    mXSLTRequests[i]->FireScriptAvailable(NS_ERROR_ABORT);
>+  for (nsScriptLoadRequest* req = mXSLTRequests.getFirst(); req;
>+       req = req->getNext()) {
>+    req->FireScriptAvailable(NS_ERROR_ABORT);
>   }
> 
>-  for (uint32_t i = 0; i < mDeferRequests.Length(); i++) {
>-    mDeferRequests[i]->FireScriptAvailable(NS_ERROR_ABORT);
>+  for (nsScriptLoadRequest* req = mDeferRequests.getFirst(); req;
>+       req = req->getNext()) {
>+    req->FireScriptAvailable(NS_ERROR_ABORT);
>   }
> 
>-  for (uint32_t i = 0; i < mAsyncRequests.Length(); i++) {
>-    mAsyncRequests[i]->FireScriptAvailable(NS_ERROR_ABORT);
>+  for (nsScriptLoadRequest* req = mAsyncRequests.getFirst(); req;
>+       req = req->getNext()) {
>+    req->FireScriptAvailable(NS_ERROR_ABORT);
>   }
> 
>-  for (uint32_t i = 0; i < mNonAsyncExternalScriptInsertedRequests.Length(); i++) {
>-    mNonAsyncExternalScriptInsertedRequests[i]->FireScriptAvailable(NS_ERROR_ABORT);
>+  for(nsScriptLoadRequest* req = mNonAsyncExternalScriptInsertedRequests.getFirst();
>+      req;
>+      req = req->getNext()) {
>+    req->FireScriptAvailable(NS_ERROR_ABORT);
>   }


Is this setup really safe?
I'd do something like
for (nsScriptLoadRequest* req = mFoo.getFirst(); req; req = mFoo.getFirst())
I'm worried that req->getNext() uses dead req


>+void
>+nsScriptLoadRequestList::Clear()
>+{
>+  nsScriptLoadRequest* req = getFirst();
>+  while (req) {
>+    nsScriptLoadRequest* next = req->getNext();
>+    req->remove();
>+    NS_RELEASE(req);
>+    req = next;
>+  }
>+}
this is similar. Just in case Release() has some side effects, would be better to always just take the
first item in the list, I think



>+  void AppendElement(nsScriptLoadRequest* aElem) {
{ goes to the next line

Comment 10

[Olli Pettay [:smaug][[e-mail]]]

er, wait

Comment 11

[Olli Pettay [:smaug][[e-mail]]]

(In reply to Olli Pettay [:smaug] from comment #9)

> 
> Is this setup really safe?
> I'd do something like
> for (nsScriptLoadRequest* req = mFoo.getFirst(); req; req = mFoo.getFirst())
> I'm worried that req->getNext() uses dead req
we don't actually remove the items from the list here, and this is happening in dtor, so no one should be
able to access to lists here. So fine.


> 
> 
> >+void
> >+nsScriptLoadRequestList::Clear()
> >+{
> >+  nsScriptLoadRequest* req = getFirst();
> >+  while (req) {
> >+    nsScriptLoadRequest* next = req->getNext();
> >+    req->remove();
> >+    NS_RELEASE(req);
> >+    req = next;
> >+  }
> >+}
So this could actually use StealFirst();
nsScriptLoadRequestList::Clear()
{
  while (!IsEmpty()) {
    nsRefPtr<nsScriptLoadRequest> first = StealFirst();
    first->remove();
  }
}

Comment 12

[Olli Pettay [:smaug][[e-mail]]]

Comment on attachment 8586791 [details] [diff] [review]
part 2.  Switch to using linked lists for nsScriptLoadRequest

So with that Clear() simplified and { placement fixed, r+.

Comment 13

[Olli Pettay [:smaug][[e-mail]]]

Comment on attachment 8585654 [details] [diff] [review]
part 3.  Store async requests in the scriptloader in two lists, so we don't have to grovel about looking for loaded ones

>     if (aElement->GetScriptAsync()) {
>       request->mIsAsync = true;
>-      mAsyncRequests.AppendElement(request);
>       if (!request->mLoading) {
>+        mLoadedAsyncRequests.AppendElement(request);
>         // The script is available already. Run it ASAP when the event
>         // loop gets a chance to spin.
>         ProcessPendingRequestsAsync();
>+      } else {
>+        mLoadingAsyncRequests.AppendElement(request);
>       }
I guess it might be good to assert in AppendElement that request isn't in any list

Comment 14

[Boris Zbarsky [:bzbarsky]]

> So this could actually use StealFirst();

Good catch, though it doesn't need the remove() call: StealFirst did that already.

> I guess it might be good to assert in AppendElement that request isn't in any list

Will do, though note that the LinkedListNode stuff ends up asserting that anyway.

Comment 15

[Boris Zbarsky [:bzbarsky]]

https://hg.mozilla.org/integration/mozilla-inbound/rev/50cb8f889d23
https://hg.mozilla.org/integration/mozilla-inbound/rev/c15e0ee2ee9f
https://hg.mozilla.org/integration/mozilla-inbound/rev/6607b7fca4f4

Comment 16

[Ryan VanderMeulen [:RyanVM]]

https://hg.mozilla.org/mozilla-central/rev/50cb8f889d23
https://hg.mozilla.org/mozilla-central/rev/c15e0ee2ee9f
https://hg.mozilla.org/mozilla-central/rev/6607b7fca4f4