Limit to only 10 image requests per page in ResourceScheduler.

The pending requests are now kept in a net::PriorityQueue. Priority changes
affect the order of the queue. After painting or network idle, we'll load up to
10 images simultaneously in PriorityQueue order.

This is a 2% improvement in Speed Index, 4% in first paint, and 5% in
DOMContentLoaded. There is a 0.5% regression in onload.


BUG=None


Review URL: https://chromiumcodereview.appspot.com/12874003

git-svn-id: svn://svn.chromium.org/chrome/trunk/src@190201 0039d316-1c4b-4281-b951-d872f2087c98

1 files changed, 155 insertions, 51 deletions

diff --git a/content/browser/loader/resource_scheduler.cc b/content/browser/loader/resource_scheduler.cc
index f9a302e..4f377dc 100644
--- a/content/browser/loader/resource_scheduler.cc
+++ b/content/browser/loader/resource_scheduler.cc
@@ -8,6 +8,7 @@
 #include "content/common/resource_messages.h"
 #include "content/browser/loader/resource_message_delegate.h"
 #include "content/public/browser/resource_controller.h"
+#include "content/public/browser/resource_request_info.h"
 #include "content/public/browser/resource_throttle.h"
 #include "ipc/ipc_message_macros.h"
 #include "net/base/load_flags.h"
@@ -16,6 +17,54 @@
 
 namespace content {
 
+static const size_t kMaxNumDelayableRequestsPerClient = 10;
+
+// A thin wrapper around net::PriorityQueue that deals with
+// ScheduledResourceRequests instead of PriorityQueue::Pointers.
+class ResourceScheduler::RequestQueue {
+ public:
+  RequestQueue() : queue_(net::NUM_PRIORITIES) {}
+  ~RequestQueue() {}
+
+  // Adds |request| to the queue with given |priority|.
+  void Insert(ScheduledResourceRequest* request,
+              net::RequestPriority priority) {
+    DCHECK(!ContainsKey(pointers_, request));
+    NetQueue::Pointer pointer = queue_.Insert(request, priority);
+    pointers_[request] = pointer;
+  }
+
+  // Removes |request| from the queue.
+  void Erase(ScheduledResourceRequest* request) {
+    PointerMap::iterator it = pointers_.find(request);
+    DCHECK(it != pointers_.end());
+    queue_.Erase(it->second);
+    pointers_.erase(it);
+  }
+
+  // Returns the highest priority request that's queued, or NULL if none are.
+  ScheduledResourceRequest* FirstMax() {
+    return queue_.FirstMax().value();
+  }
+
+  // Returns true if |request| is queued.
+  bool IsQueued(ScheduledResourceRequest* request) const {
+    return ContainsKey(pointers_, request);
+  }
+
+  // Returns true if no requests are queued.
+  bool IsEmpty() const { return queue_.size() == 0; }
+
+ private:
+  typedef net::PriorityQueue<ScheduledResourceRequest*> NetQueue;
+  typedef std::map<ScheduledResourceRequest*, NetQueue::Pointer> PointerMap;
+
+  NetQueue queue_;
+  PointerMap pointers_;
+};
+
+// This is the handle we return to the ResourceDispatcherHostImpl so it can
+// interact with the request.
 class ResourceScheduler::ScheduledResourceRequest
     : public ResourceMessageDelegate,
       public ResourceThrottle {
@@ -44,7 +93,8 @@ class ResourceScheduler::ScheduledResourceRequest
   }
 
   const ClientId& client_id() const { return client_id_; }
-  const net::URLRequest& url_request() const { return *request_; }
+  net::URLRequest* url_request() { return request_; }
+  const net::URLRequest* url_request() const { return request_; }
 
  private:
   // ResourceMessageDelegate interface:
@@ -64,11 +114,7 @@ class ResourceScheduler::ScheduledResourceRequest
   }
 
   void DidChangePriority(int request_id, net::RequestPriority new_priority) {
-    net::RequestPriority old_priority = request_->priority();
-    request_->SetPriority(new_priority);
-    if (new_priority > old_priority) {
-      Start();
-    }
+    scheduler_->ReprioritizeRequest(this, new_priority);
   }
 
   ClientId client_id_;
@@ -80,15 +126,20 @@ class ResourceScheduler::ScheduledResourceRequest
   DISALLOW_COPY_AND_ASSIGN(ScheduledResourceRequest);
 };
 
+// Each client represents a tab.
+struct ResourceScheduler::Client {
+  Client() : has_body(false) {}
+  ~Client() {}
+
+  bool has_body;
+  RequestQueue pending_requests;
+  RequestSet in_flight_requests;
+};
+
 ResourceScheduler::ResourceScheduler() {
 }
 
 ResourceScheduler::~ResourceScheduler() {
-  for (ClientMap::iterator it ALLOW_UNUSED = client_map_.begin();
-       it != client_map_.end(); ++it) {
-    DCHECK(it->second->pending_requests.empty());
-    DCHECK(it->second->in_flight_requests.empty());
-  }
   DCHECK(unowned_requests_.empty());
   DCHECK(client_map_.empty());
 }
@@ -114,17 +165,10 @@ scoped_ptr<ResourceThrottle> ResourceScheduler::ScheduleRequest(
   }
 
   Client* client = it->second;
-
-  bool is_synchronous = (url_request->load_flags() & net::LOAD_IGNORE_LIMITS) ==
-      net::LOAD_IGNORE_LIMITS;
-  bool is_low_priority =
-      url_request->priority() < net::LOW && !is_synchronous;
-
-  if (is_low_priority && !client->in_flight_requests.empty() &&
-      !client->has_body) {
-    client->pending_requests.push_back(request.get());
-  } else {
+  if (ShouldStartRequest(request.get(), client)) {
     StartRequest(request.get(), client);
+  } else {
+    client->pending_requests.Insert(request.get(), url_request->priority());
   }
   return request.PassAs<ResourceThrottle>();
 }
@@ -142,29 +186,16 @@ void ResourceScheduler::RemoveRequest(ScheduledResourceRequest* request) {
   }
 
   Client* client = client_it->second;
-  RequestSet::iterator request_it = client->in_flight_requests.find(request);
-  if (request_it == client->in_flight_requests.end()) {
-    bool removed = false;
-    RequestQueue::iterator queue_it;
-    for (queue_it = client->pending_requests.begin();
-         queue_it != client->pending_requests.end(); ++queue_it) {
-      if (*queue_it == request) {
-        client->pending_requests.erase(queue_it);
-        removed = true;
-        break;
-      }
-    }
-    DCHECK(removed);
+
+  if (client->pending_requests.IsQueued(request)) {
+    client->pending_requests.Erase(request);
     DCHECK(!ContainsKey(client->in_flight_requests, request));
   } else {
     size_t erased = client->in_flight_requests.erase(request);
     DCHECK(erased);
-  }
 
-  if (client->in_flight_requests.empty()) {
-    // Since the network is now idle, we may as well load some of the low
-    // priority requests.
-    LoadPendingRequests(client);
+    // Removing this request may have freed up another to load.
+    LoadAnyStartablePendingRequests(client);
   }
 }
 
@@ -224,7 +255,7 @@ void ResourceScheduler::OnWillInsertBody(int child_id, int route_id) {
   client->has_body = false;
   if (!client->has_body) {
     client->has_body = true;
-    LoadPendingRequests(client);
+    LoadAnyStartablePendingRequests(client);
   }
 }
 
@@ -234,24 +265,97 @@ void ResourceScheduler::StartRequest(ScheduledResourceRequest* request,
   request->Start();
 }
 
-void ResourceScheduler::LoadPendingRequests(Client* client) {
-  while (!client->pending_requests.empty()) {
-    ScheduledResourceRequest* request = client->pending_requests.front();
-    client->pending_requests.erase(client->pending_requests.begin());
-    StartRequest(request, client);
+void ResourceScheduler::ReprioritizeRequest(ScheduledResourceRequest* request,
+                                            net::RequestPriority new_priority) {
+  net::RequestPriority old_priority = request->url_request()->priority();
+  DCHECK_NE(new_priority, old_priority);
+  request->url_request()->SetPriority(new_priority);
+  ClientMap::iterator client_it = client_map_.find(request->client_id());
+  if (client_it == client_map_.end()) {
+    // The client was likely deleted shortly before we received this IPC.
+    return;
+  }
+
+  Client *client = client_it->second;
+  if (!client->pending_requests.IsQueued(request)) {
+    DCHECK(ContainsKey(client->in_flight_requests, request));
+    // Request has already started.
+    return;
+  }
+
+  client->pending_requests.Erase(request);
+  client->pending_requests.Insert(request, request->url_request()->priority());
+
+  if (new_priority > old_priority) {
+    // Check if this request is now able to load at its new priority.
+    LoadAnyStartablePendingRequests(client);
   }
 }
 
-ResourceScheduler::ClientId ResourceScheduler::MakeClientId(
-    int child_id, int route_id) {
-  return (static_cast<ResourceScheduler::ClientId>(child_id) << 32) | route_id;
+void ResourceScheduler::LoadAnyStartablePendingRequests(Client* client) {
+  while (!client->pending_requests.IsEmpty()) {
+    ScheduledResourceRequest* request = client->pending_requests.FirstMax();
+    if (ShouldStartRequest(request, client)) {
+      client->pending_requests.Erase(request);
+      StartRequest(request, client);
+    } else {
+      break;
+    }
+  }
+}
+
+size_t ResourceScheduler::GetNumDelayableRequestsInFlight(
+    Client* client) const {
+  size_t count = 0;
+  for (RequestSet::iterator it = client->in_flight_requests.begin();
+       it != client->in_flight_requests.end(); ++it) {
+    if ((*it)->url_request()->priority() < net::LOW) {
+      ++count;
+    }
+  }
+  return count;
 }
 
-ResourceScheduler::Client::Client()
-    : has_body(false) {
+// ShouldStartRequest is the main scheduling algorithm.
+//
+// Requests are categorized into two categories:
+//
+// 1. Immediately issued requests, which are:
+//
+//   * Higher priority requests (>= net::LOW).
+//   * Synchronous requests.
+//
+// 2. The remainder are delayable requests, which follow these rules:
+//
+//   * If no high priority requests are in flight, start loading low priority
+//     requests.
+//   * Once the renderer has a <body>, start loading delayable requests.
+//   * Never exceed 10 delayable requests in flight per client.
+bool ResourceScheduler::ShouldStartRequest(ScheduledResourceRequest* request,
+                                           Client* client) const {
+  if (request->url_request()->priority() >= net::LOW ||
+      !ResourceRequestInfo::ForRequest(request->url_request())->IsAsync()) {
+    return true;
+  }
+
+  size_t num_delayable_requests_in_flight =
+      GetNumDelayableRequestsInFlight(client);
+  if (num_delayable_requests_in_flight >= kMaxNumDelayableRequestsPerClient) {
+    return false;
+  }
+
+  bool have_immediate_requests_in_flight =
+      client->in_flight_requests.size() > num_delayable_requests_in_flight;
+  if (have_immediate_requests_in_flight && !client->has_body) {
+    return false;
+  }
+
+  return true;
 }
 
-ResourceScheduler::Client::~Client() {
+ResourceScheduler::ClientId ResourceScheduler::MakeClientId(
+    int child_id, int route_id) {
+  return (static_cast<ResourceScheduler::ClientId>(child_id) << 32) | route_id;
 }
 
 }  // namespace content