Get rid of quadratic behavior in ResourceScheduler

content/browser/loader/resource_scheduler.cc

Index: content/browser/loader/resource_scheduler.cc
diff --git a/content/browser/loader/resource_scheduler.cc b/content/browser/loader/resource_scheduler.cc
index 6973687cb719a615ca3675eec90e37d80ff89714..6d68cf1c438dd7b22621500e2dcc70af6fa917b0 100644
--- a/content/browser/loader/resource_scheduler.cc
+++ b/content/browser/loader/resource_scheduler.cc
@@ -354,7 +354,9 @@ class ResourceScheduler::Client {
         using_spdy_proxy_(false),
         in_flight_delayable_count_(0),
         total_layout_blocking_count_(0),
-        priority_requests_delayable_(priority_requests_delayable) {}
+        priority_requests_delayable_(priority_requests_delayable),
+        has_pending_start_task_(false),
+        weak_ptr_factory_(this) {}
 
   ~Client() {}
 
@@ -377,10 +379,9 @@ class ResourceScheduler::Client {
       EraseInFlightRequest(request);
 
       // Removing this request may have freed up another to load.
-      LoadAnyStartablePendingRequests(
-          has_html_body_
-          ? RequestStartTrigger::COMPLETION_POST_BODY
-          : RequestStartTrigger::COMPLETION_PRE_BODY);
+      ScheduleLoadAnyStartablePendingRequests(
+          has_html_body_ ? RequestStartTrigger::COMPLETION_POST_BODY
+                         : RequestStartTrigger::COMPLETION_PRE_BODY);
     }
   }
 
@@ -453,7 +454,7 @@ class ResourceScheduler::Client {
 
     if (new_priority_params.priority > old_priority_params.priority) {
       // Check if this request is now able to load at its new priority.
-      LoadAnyStartablePendingRequests(
+      ScheduleLoadAnyStartablePendingRequests(
           RequestStartTrigger::REQUEST_REPRIORITIZED);
     }
   }
@@ -719,6 +720,24 @@ class ResourceScheduler::Client {
     return START_REQUEST;
   }
 
+  // It is common for a burst of messages to come from the renderer which
+  // trigger starting pending requests. Naively, this would result in O(n*m)
+  // behavior for n pending requests and m <= n messages, as
+  // LoadAnyStartablePendingRequest is O(n) for n pending requests. To solve
+  // this, just post a task to the end of the queue to call the method,
+  // coalescing the m messages into a single call to
+  // LoadAnyStartablePendingRequests.
+  // TODO(csharrison): Reconsider this if IPC batching becomes an easy to use
+  // pattern.
+  void ScheduleLoadAnyStartablePendingRequests(RequestStartTrigger trigger) {
+    if (has_pending_start_task_)
+      return;
+    has_pending_start_task_ = true;
+    base::ThreadTaskRunnerHandle::Get()->PostTask(
+        FROM_HERE, base::Bind(&Client::LoadAnyStartablePendingRequests,
+                              weak_ptr_factory_.GetWeakPtr(), trigger));

[kinuko, 2017/02/06 20:57:14]

This changes when we actually triggers startable requests esp. if we already
have lots of inflight tasks already in the queue (and during contentious loading
it looks it's often the case).  Do you think it could affect performance?

[Charlie Harrison, 2017/02/06 21:24:29]

This is a valid concern. We currently "schedule" these start tasks on two
conditions.
1. Reprioritization (which often comes in batches for image priorities)
2. Request tear down (~ResourceThrottle). I think this will only come from
batches from callers of ResourceFetcher::stopFetching (e.g. stopAllLoaders). 

In my mind, if we have a bloated queue during these times it feels better to
delay here than delaying the current work on the queue with lots of CPU bound
work. A single extra post task during request finish / reprioritization seems
not too bad to me.

If you'd like, I can add a histogram of the wait time for the scheduled task?

+  }
+
   void LoadAnyStartablePendingRequests(RequestStartTrigger trigger) {
     // We iterate through all the pending requests, starting with the highest
     // priority one. For each entry, one of three things can happen:
@@ -728,6 +747,7 @@ class ResourceScheduler::Client {
     //     the previous request still in the list.
     // 3) We do not start the request, same as above, but StartRequest() tells
     //     us there's no point in checking any further requests.
+    has_pending_start_task_ = false;
     RequestQueue::NetQueue::iterator request_iter =
         pending_requests_.GetNextHighestIterator();
 
@@ -771,6 +791,10 @@ class ResourceScheduler::Client {
   // True if requests to servers that support priorities (e.g., H2/QUIC) can
   // be delayed.
   bool priority_requests_delayable_;
+
+  bool has_pending_start_task_;
+
+  base::WeakPtrFactory<ResourceScheduler::Client> weak_ptr_factory_;
 };
 
 ResourceScheduler::ResourceScheduler()