predictors: Several improvements for redirects database.

chrome/browser/predictors/resource_prefetch_predictor.cc

 // Copyright 2014 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 "chrome/browser/predictors/resource_prefetch_predictor.h"
 
 #include <map>
 #include <set>
 #include <utility>
 
@@ skipping 380 matching lines @@
         std::any_of(std::begin(kFontMimeTypes), std::end(kFontMimeTypes),
                     [&mime_type](const std::string& mime) {
                       return net::MatchesMimeType(mime, mime_type);
                     });
     if (found)
       return content::RESOURCE_TYPE_FONT_RESOURCE;
   }
   return fallback;
 }
 
-// static
 bool ResourcePrefetchPredictor::GetRedirectEndpoint(
-    const std::string& first_redirect,
+    const std::string& entry_point,
     const RedirectDataMap& redirect_data_map,
-    std::string* final_redirect) {
-  DCHECK(final_redirect);
+    std::string* redirect_endpoint) const {
+  DCHECK(redirect_endpoint);
 
-  RedirectDataMap::const_iterator it = redirect_data_map.find(first_redirect);
-  if (it == redirect_data_map.end())
-    return false;
+  RedirectDataMap::const_iterator it = redirect_data_map.find(entry_point);
+  if (it == redirect_data_map.end()) {
+    // Fallback to fetching URLs based on the incoming URL/host. By default
+    // the predictor is confident that there is no redirect.
+    *redirect_endpoint = entry_point;
+    return true;
+  }
 
   const RedirectData& redirect_data = it->second;
-  auto best_redirect = std::max_element(
-      redirect_data.redirect_endpoints().begin(),
-      redirect_data.redirect_endpoints().end(),
-      [](const RedirectStat& x, const RedirectStat& y) {
-        return ComputeRedirectConfidence(x) < ComputeRedirectConfidence(y);
-      });
+  DCHECK_GT(redirect_data.redirect_endpoints_size(), 0);
+  if (redirect_data.redirect_endpoints_size() > 1) {
+    // The predictor observed multiple redirect destinations recently. Redirect
+    // endpoint is ambiguous. The predictor predicts a redirect only if it
+    // believes that the redirect is "permanent", i.e. subsequent navigations
+    // will lead to the same destination.
+    return false;
+  }
 
-  const float kMinRedirectConfidenceToTriggerPrefetch = 0.7f;
+  // The threshold is higher than the threshold for resources because the
+  // redirect misprediction causes the waste of whole prefetch.
+  const float kMinRedirectConfidenceToTriggerPrefetch = 0.9f;
   const int kMinRedirectHitsToTriggerPrefetch = 2;
 
-  if (best_redirect == redirect_data.redirect_endpoints().end() ||
-      ComputeRedirectConfidence(*best_redirect) <
+  // The predictor doesn't apply a minimum-number-of-hits threshold to
+  // the no-redirect case because the no-redirect is a default assumption.
+  const RedirectStat& redirect = redirect_data.redirect_endpoints(0);
+  if (ComputeRedirectConfidence(redirect) <
           kMinRedirectConfidenceToTriggerPrefetch ||
-      best_redirect->number_of_hits() < kMinRedirectHitsToTriggerPrefetch)
+      (redirect.number_of_hits() < kMinRedirectHitsToTriggerPrefetch &&
+       redirect.url() != entry_point)) {
     return false;
+  }
 
-  *final_redirect = best_redirect->url();
+  *redirect_endpoint = redirect.url();
   return true;
 }
 
 // static
 void ResourcePrefetchPredictor::SetAllowPortInUrlsForTesting(bool state) {
   g_allow_port_in_urls = state;
 }
 
 ////////////////////////////////////////////////////////////////////////////////
 // ResourcePrefetchPredictor nested types.
@@ skipping 422 matching lines @@
   }
 }
 
 bool ResourcePrefetchPredictor::GetPrefetchData(
     const GURL& main_frame_url,
     ResourcePrefetchPredictor::Prediction* prediction) const {
   std::vector<GURL>* urls =
       prediction ? &prediction->subresource_urls : nullptr;
   DCHECK(!urls || urls->empty());
 
-  // Fetch URLs based on a redirect endpoint for URL/host first.
+  // Fetch resources using URL-keyed data first.
   std::string redirect_endpoint;
+  const std::string& main_frame_url_spec = main_frame_url.spec();
   if (config_.is_url_learning_enabled &&
-      GetRedirectEndpoint(main_frame_url.spec(), *url_redirect_table_cache_,
+      GetRedirectEndpoint(main_frame_url_spec, *url_redirect_table_cache_,
                           &redirect_endpoint) &&
       PopulatePrefetcherRequest(redirect_endpoint, *url_table_cache_, urls)) {
     if (prediction) {
       prediction->is_host = false;
-      prediction->is_redirected = true;
       prediction->main_frame_key = redirect_endpoint;
+      prediction->is_redirected = (redirect_endpoint != main_frame_url_spec);
     }
     return true;
   }
 
-  if (GetRedirectEndpoint(main_frame_url.host(), *host_redirect_table_cache_,
+  // Use host data if the URL-based prediction isn't available.
+  std::string main_frame_url_host = main_frame_url.host();
+  if (GetRedirectEndpoint(main_frame_url_host, *host_redirect_table_cache_,
                           &redirect_endpoint) &&
       PopulatePrefetcherRequest(redirect_endpoint, *host_table_cache_, urls)) {
     if (prediction) {
       prediction->is_host = true;
-      prediction->is_redirected = true;
       prediction->main_frame_key = redirect_endpoint;
+      prediction->is_redirected = (redirect_endpoint != main_frame_url_host);
     }
     return true;
   }
-
-  // Fallback to fetching URLs based on the incoming URL/host.
-  if (config_.is_url_learning_enabled &&
-      PopulatePrefetcherRequest(main_frame_url.spec(), *url_table_cache_,
-                                urls)) {
-    if (prediction) {
-      prediction->is_host = false;
-      prediction->is_redirected = false;
-      prediction->main_frame_key = main_frame_url.spec();
-    }
-    return true;
-  }
-
-  if (PopulatePrefetcherRequest(main_frame_url.host(), *host_table_cache_,
-                                urls)) {
-    if (prediction) {
-      prediction->is_host = true;
-      prediction->is_redirected = false;
-      prediction->main_frame_key = main_frame_url.host();
-    }
-    return true;
-  }
 
   return false;
 }
 
 bool ResourcePrefetchPredictor::PopulatePrefetcherRequest(
     const std::string& main_frame_key,
     const PrefetchDataMap& data_map,
     std::vector<GURL>* urls) const {
   PrefetchDataMap::const_iterator it = data_map.find(main_frame_key);
   if (it == data_map.end())
@@ skipping 472 matching lines @@
     bool is_host = key_type == PREFETCH_KEY_TYPE_HOST;
     const PrefetchData& host_data = is_host ? data : empty_data;
     const PrefetchData& url_data = is_host ? empty_data : data;
     BrowserThread::PostTask(
         BrowserThread::DB, FROM_HERE,
         base::Bind(&ResourcePrefetchPredictorTables::UpdateData, tables_,
                    url_data, host_data, empty_redirect_data,
                    empty_redirect_data));
   }
 
-  if (key != key_before_redirects) {
-    LearnRedirect(key_before_redirects, key_type, key, max_data_map_size,
-                  redirect_map);
-  }
+  // Predictor learns about both redirected and non-redirected destinations to
+  // estimate whether the endpoint is permanent.
+  LearnRedirect(key_before_redirects, key_type, key, max_data_map_size,
+                redirect_map);
 }
 
 void ResourcePrefetchPredictor::LearnRedirect(const std::string& key,
                                               PrefetchKeyType key_type,
                                               const std::string& final_redirect,
                                               size_t max_redirect_map_size,
                                               RedirectDataMap* redirect_map) {
   DCHECK_CURRENTLY_ON(BrowserThread::UI);
   // If the primary key is too long reject it.
   if (key.length() > ResourcePrefetchPredictorTables::kMaxStringLength)
@@ skipping 31 matching lines @@
     if (need_to_add) {
       RedirectStat* redirect_to_add = data.add_redirect_endpoints();
       redirect_to_add->set_url(final_redirect);
       redirect_to_add->set_number_of_hits(1);
     }
   }
 
   RedirectData& data = cache_entry->second;
   // Trim the redirects after the update.
   ResourcePrefetchPredictorTables::TrimRedirects(
-      &data, config_.max_consecutive_misses);
+      &data, config_.max_redirect_consecutive_misses);
 
   if (data.redirect_endpoints_size() == 0) {
     redirect_map->erase(cache_entry);
     BrowserThread::PostTask(
         BrowserThread::DB, FROM_HERE,
         base::Bind(
             &ResourcePrefetchPredictorTables::DeleteSingleRedirectDataPoint,
             tables_, key, key_type));
   } else {
     RedirectData empty_redirect_data;
@@ skipping 230 matching lines @@
 TestObserver::~TestObserver() {
   predictor_->SetObserverForTesting(nullptr);
 }
 
 TestObserver::TestObserver(ResourcePrefetchPredictor* predictor)
     : predictor_(predictor) {
   predictor_->SetObserverForTesting(this);
 }
 
 }  // namespace predictors