Get rid of quadratic behavior in ResourceScheduler

content/browser/loader/resource_scheduler.cc

 // Copyright (c) 2012 The Chromium Authors. All rights reserved.
 // Use of this source code is governed by a BSD-style license that can be
 // found in the LICENSE file.
 
 #include "content/browser/loader/resource_scheduler.h"
 
 #include <stdint.h>
 #include <set>
 #include <string>
 #include <utility>
@@ skipping 336 matching lines @@
 
 // Each client represents a tab.
 class ResourceScheduler::Client {
  public:
   explicit Client(bool priority_requests_delayable)
       : is_loaded_(false),
         has_html_body_(false),
         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() {}
 
   void ScheduleRequest(net::URLRequest* url_request,
                        ScheduledResourceRequest* request) {
     SetRequestAttributes(request, DetermineRequestAttributes(request));
     if (ShouldStartRequest(request) == START_REQUEST) {
       // New requests can be started synchronously without issue.
       StartRequest(request, START_SYNC, RequestStartTrigger::NONE);
     } else {
       pending_requests_.Insert(request);
     }
   }
 
   void RemoveRequest(ScheduledResourceRequest* request) {
     if (pending_requests_.IsQueued(request)) {
       pending_requests_.Erase(request);
       DCHECK(!base::ContainsKey(in_flight_requests_, request));
     } else {
       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);
     }
   }
 
   RequestSet StartAndRemoveAllRequests() {
     // First start any pending requests so that they will be moved into
     // in_flight_requests_. This may exceed the limits
     // kDefaultMaxNumDelayableRequestsPerClient and
     // kMaxNumDelayableRequestsPerHostPerClient, so this method must not do
     // anything that depends on those limits before calling
     // ClearInFlightRequests() below.
@@ skipping 52 matching lines @@
       DCHECK(base::ContainsKey(in_flight_requests_, request));
       // Request has already started.
       return;
     }
 
     pending_requests_.Erase(request);
     pending_requests_.Insert(request);
 
     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);
     }
   }
 
  private:
   enum ShouldStartReqResult {
     DO_NOT_START_REQUEST_AND_STOP_SEARCHING,
     DO_NOT_START_REQUEST_AND_KEEP_SEARCHING,
     START_REQUEST,
   };
@@ skipping 245 matching lines @@
         // Block the request if at least one request is in flight and the
         // number of in-flight delayable requests has hit the configured
         // limit.
         return DO_NOT_START_REQUEST_AND_STOP_SEARCHING;
       }
     }
 
     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:
     // 1) We start the request, remove it from the list, and keep checking.
     // 2) We do NOT start the request, but ShouldStartRequest() signals us that
     //     there may be room for other requests, so we keep checking and leave
     //     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();
 
     while (request_iter != pending_requests_.End()) {
       ScheduledResourceRequest* request = *request_iter;
       ShouldStartReqResult query_result = ShouldStartRequest(request);
 
       if (query_result == START_REQUEST) {
         pending_requests_.Erase(request);
         StartRequest(request, START_ASYNC, trigger);
@@ skipping 23 matching lines @@
   RequestQueue pending_requests_;
   RequestSet in_flight_requests_;
   // The number of delayable in-flight requests.
   size_t in_flight_delayable_count_;
   // The number of layout-blocking in-flight requests.
   size_t total_layout_blocking_count_;
 
   // 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()
     : priority_requests_delayable_(
           base::FeatureList::IsEnabled(kPrioritySupportedRequestsDelayable)) {}
 
 ResourceScheduler::~ResourceScheduler() {
   DCHECK(unowned_requests_.empty());
   DCHECK(client_map_.empty());
 }
@@ skipping 180 matching lines @@
   client->ReprioritizeRequest(scheduled_resource_request, old_priority_params,
                               new_priority_params);
 }
 
 ResourceScheduler::ClientId ResourceScheduler::MakeClientId(
     int child_id, int route_id) {
   return (static_cast<ResourceScheduler::ClientId>(child_id) << 32) | route_id;
 }
 
 }  // namespace content