predictors: Use redirect data in prefetch.

chrome/browser/predictors/resource_prefetch_predictor.cc

Index: chrome/browser/predictors/resource_prefetch_predictor.cc
diff --git a/chrome/browser/predictors/resource_prefetch_predictor.cc b/chrome/browser/predictors/resource_prefetch_predictor.cc
index 03e9570a0b1cc020038315f01d97dc01a6468e85..2fdc9bb8293f15579290a993dd07f07b2f07609a 100644
--- a/chrome/browser/predictors/resource_prefetch_predictor.cc
+++ b/chrome/browser/predictors/resource_prefetch_predictor.cc
@@ -210,6 +210,47 @@ content::ResourceType ResourcePrefetchPredictor::GetResourceTypeFromMimeType(
   return fallback;
 }
 
+// static
+bool ResourcePrefetchPredictor::GetFinalRedirect(
+    const std::string& first_redirect,
+    RedirectDataMap* redirect_data_map,
+    std::string* final_redirect) {
+  DCHECK(final_redirect);
+
+  RedirectDataMap::const_iterator it = redirect_data_map->find(first_redirect);
+  if (it == redirect_data_map->end())
+    return false;
+
+  const RedirectData& redirect_data = it->second;
+  int best_redirect_i = -1;
+  float best_confidence = 0.0;
+  for (int i = 0; i < redirect_data.redirect_endpoints_size(); ++i) {
+    const RedirectStat& redirect = redirect_data.redirect_endpoints(i);
+    float confidence =
+        (redirect.number_of_hits() + 0.0) /
+        (redirect.number_of_hits() + redirect.number_of_misses());
+    if (confidence > best_confidence) {
+      best_redirect_i = i;
+      best_confidence = confidence;
+    }
+  }
+
+  if (best_redirect_i == -1)
+    return false;
+
+  const RedirectStat& best_redirect =

[pasko, 2016/10/07 13:44:27]

std::max_element?

[alexilin, 2016/10/07 14:29:05]

Well, it will lead to small overhead : we'll have to compute confidence for
current best element each time. WDYT?

[pasko, 2016/10/07 15:42:44]

Did you mean we would re-compute the confidence 2 times for the best element
(but only once for all other elements)?

I did not think about it, so let me think as I am writing this. I am a fan of
not doing premature optimization. We have numerous bigger inefficiencies
sprinkled densely around the code, each one of them would be 1000x slower than
these 3 floating point operations. So it seems unlikely that this optimization
would turn out to be user-visible.

The benefits of having 5 lines of straightforward code instead of ~20 lines look
attractive to me. We are also fans of boring code: even though it is less fun to
write, it is a lot easier to maintain.

So yeah, using std::max_element looks better.

[alexilin, 2016/10/07 16:33:44]

I meant that std::max_element accepts comparer as an argument so the confidence
will be computed for two arguments (for current element and current best) for
each element in list.

I've got your message, thanks.

Done.

[pasko, 2016/10/07 17:18:54]

Ah, sorry, you are right, this has a comparator, hence evaluating twice each
time. I did not realize that. Still not overly heavy.

[alexilin, 2016/10/11 13:14:41]

Done.

+      redirect_data.redirect_endpoints(best_redirect_i);
+  const float kMinRedirectConfidenceToTriggerPrefetch = 0.7f;
+  const int kMinRedirectHitsToTriggerPrefetch = 2;
+
+  if (best_confidence < kMinRedirectConfidenceToTriggerPrefetch ||
+      best_redirect.number_of_hits() < kMinRedirectHitsToTriggerPrefetch)
+    return false;
+
+  *final_redirect = best_redirect.url();
+  return true;
+}
+
 ////////////////////////////////////////////////////////////////////////////////
 // ResourcePrefetchPredictor nested types.
 
@@ -419,9 +460,6 @@ void ResourcePrefetchPredictor::OnMainFrameRedirect(
     const URLRequestSummary& response) {
   DCHECK_CURRENTLY_ON(BrowserThread::UI);
 
-  // Stop any inflight prefetching. Remove the older navigation.
-  StopPrefetching(response.navigation_id.main_frame_url);
-
   std::unique_ptr<PageRequestSummary> summary;
   NavigationMap::iterator nav_it =
       inflight_navigations_.find(response.navigation_id);
@@ -492,47 +530,68 @@ void ResourcePrefetchPredictor::OnNavigationComplete(
 bool ResourcePrefetchPredictor::GetPrefetchData(const GURL& main_frame_url,
                                                 std::vector<GURL>* urls) {
   DCHECK(urls);
-
+  DCHECK(urls->empty());
   bool use_url_data = config_.IsPrefetchingEnabled(profile_) ?
       config_.IsURLPrefetchingEnabled(profile_) :
       config_.IsURLLearningEnabled();
-  if (use_url_data) {
-    PrefetchDataMap::const_iterator iterator =
-        url_table_cache_->find(main_frame_url.spec());
-    if (iterator != url_table_cache_->end())
-      PopulatePrefetcherRequest(iterator->second, urls);
-  }
-  if (!urls->empty())
-    return true;
-
   bool use_host_data = config_.IsPrefetchingEnabled(profile_) ?
       config_.IsHostPrefetchingEnabled(profile_) :
       config_.IsHostLearningEnabled();
-  if (use_host_data) {
-    PrefetchDataMap::const_iterator iterator =
-        host_table_cache_->find(main_frame_url.host());
-    if (iterator != host_table_cache_->end())
-      PopulatePrefetcherRequest(iterator->second, urls);
+
+  if (use_url_data && PopulatePrefetcherRequest(main_frame_url.spec(),
+                                                url_table_cache_.get(), urls))
+    return true;
+
+  if (use_host_data && PopulatePrefetcherRequest(main_frame_url.host(),
+                                                 host_table_cache_.get(), urls))
+    return true;
+
+  std::string final_redirect;
+  if (GetFinalRedirect(main_frame_url.spec(), url_redirect_table_cache_.get(),
+                       &final_redirect)) {
+    GURL redirect_url(final_redirect);
+
+    if (use_url_data && PopulatePrefetcherRequest(redirect_url.spec(),
+                                                  url_table_cache_.get(), urls))
+      return true;
+
+    if (use_host_data &&
+        PopulatePrefetcherRequest(redirect_url.host(), host_table_cache_.get(),
+                                  urls))
+      return true;
   }
 
-  return !urls->empty();
+  return use_host_data &&
+         GetFinalRedirect(main_frame_url.host(),
+                          host_redirect_table_cache_.get(), &final_redirect) &&
+         PopulatePrefetcherRequest(final_redirect, host_table_cache_.get(),
+                                   urls);
 }
 
-void ResourcePrefetchPredictor::PopulatePrefetcherRequest(
-    const PrefetchData& data,
+bool ResourcePrefetchPredictor::PopulatePrefetcherRequest(
+    const std::string& main_frame_key,
+    PrefetchDataMap* data_map,
     std::vector<GURL>* urls) {
-  for (const ResourceData& resource : data.resources()) {
+  DCHECK(data_map);
+  DCHECK(urls);
+  PrefetchDataMap::const_iterator it = data_map->find(main_frame_key);
+  if (it == data_map->end())
+    return false;
+
+  size_t initial_size = urls->size();
+  for (const ResourceData& resource : it->second.resources()) {
     float confidence =
         static_cast<float>(resource.number_of_hits()) /
         (resource.number_of_hits() + resource.number_of_misses());
     if (confidence < config_.min_resource_confidence_to_trigger_prefetch ||
         resource.number_of_hits() <
-            config_.min_resource_hits_to_trigger_prefetch) {
+            config_.min_resource_hits_to_trigger_prefetch)
       continue;
-    }
 
     urls->push_back(GURL(resource.resource_url()));
   }
+
+  return urls->size() > initial_size;
 }
 
 void ResourcePrefetchPredictor::StartPrefetching(const GURL& url) {
@@ -1000,10 +1059,9 @@ void ResourcePrefetchPredictor::LearnRedirect(const std::string& key,
   }
 
   RedirectData& data = cache_entry->second;
-  // Trim and sort the redirects after the update.
+  // Trim the redirects after the update.
   ResourcePrefetchPredictorTables::TrimRedirects(
       &data, config_.max_consecutive_misses);
-  ResourcePrefetchPredictorTables::SortRedirects(&data);
 
   if (data.redirect_endpoints_size() == 0) {
     redirect_map->erase(cache_entry);