predictors: Use redirect data in prefetch.

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 192 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::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.
 
 ResourcePrefetchPredictor::URLRequestSummary::URLRequestSummary()
     : resource_type(content::RESOURCE_TYPE_LAST_TYPE),
       priority(net::IDLE),
       was_cached(false),
       has_validators(false),
       always_revalidate(false) {}
 
@@ skipping 189 matching lines @@
   if (initialization_state_ != INITIALIZED)
     return;
 
   StopPrefetching(response.navigation_id.main_frame_url);
 }
 
 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);
   if (nav_it != inflight_navigations_.end()) {
     summary.reset(nav_it->second.release());
     inflight_navigations_.erase(nav_it);
   }
 
   // The redirect url may be empty if the URL was invalid.
   if (response.redirect_url.is_empty())
@@ skipping 50 matching lines @@
       std::unique_ptr<history::HistoryDBTask>(new GetUrlVisitCountTask(
           navigation_id, std::move(summary),
           base::Bind(&ResourcePrefetchPredictor::OnVisitCountLookup,
                      AsWeakPtr()))),
       &history_lookup_consumer_);
 }
 
 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) {
   if (!prefetch_manager_.get())  // Prefetching not enabled.
     return;
 
   std::vector<GURL> subresource_urls;
   if (!GetPrefetchData(url, &subresource_urls)) {
     // No prefetching data at host or URL level.
     return;
@@ skipping 447 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 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);
     BrowserThread::PostTask(
         BrowserThread::DB, FROM_HERE,
         base::Bind(
             &ResourcePrefetchPredictorTables::DeleteSingleRedirectDataPoint,
             tables_, key, key_type));
   } else {
     RedirectData empty_redirect_data;
@@ skipping 51 matching lines @@
     // HistoryService is already loaded. Continue with Initialization.
     OnHistoryAndCacheLoaded();
     return;
   }
   DCHECK(!history_service_observer_.IsObserving(history_service));
   history_service_observer_.Add(history_service);
   return;
 }
 
 }  // namespace predictors