Simulate a basic local browsing based prerender algorithm, and report timings

in histograms.  This is for canary/dev to collect metrics only
at this point, and will be removed again.
R=cbentzel
BUG=130164
Review URL: https://chromiumcodereview.appspot.com/10387220

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

6 files changed, 287 insertions, 19 deletions

diff --git a/chrome/browser/prerender/prerender_histograms.cc b/chrome/browser/prerender/prerender_histograms.cc
index 19b62c7..395c8f3 100644
--- a/chrome/browser/prerender/prerender_histograms.cc
+++ b/chrome/browser/prerender/prerender_histograms.cc
@@ -283,6 +283,22 @@ void PrerenderHistograms::RecordPageLoadTimeNotSwappedIn(
   RECORD_PLT("PrerenderNotSwappedInPLT", page_load_time);
 }
 
+void PrerenderHistograms::RecordSimulatedLocalBrowsingBaselinePLT(
+    base::TimeDelta page_load_time, const GURL& url) const {
+  // If the URL to be prerendered is not a http[s] URL do not record.
+  if (!IsWebURL(url))
+    return;
+  RECORD_PLT("SimulatedLocalBrowsingBaselinePLT", page_load_time);
+}
+
+void PrerenderHistograms::RecordSimulatedLocalBrowsingPLT(
+    base::TimeDelta page_load_time, const GURL& url) const {
+  // If the URL to be prerendered is not a http[s] URL do not record.
+  if (!IsWebURL(url))
+    return;
+  RECORD_PLT("SimulatedLocalBrowsingPLT", page_load_time);
+}
+
 void PrerenderHistograms::RecordPercentLoadDoneAtSwapin(double fraction)
     const {
   if (fraction < 0.0 || fraction > 1.0)
@@ -382,4 +398,13 @@ bool PrerenderHistograms::IsOriginExperimentWash() const {
   return origin_experiment_wash_;
 }
 
+void PrerenderHistograms::RecordLocalPredictorEvent(
+    PrerenderLocalPredictor::Event event) const {
+  UMA_HISTOGRAM_ENUMERATION(
+      ComposeHistogramName("", base::FieldTrial::MakeName(
+          "LocalPredictorEvent", "Prerender")),
+      event,
+      PrerenderLocalPredictor::EVENT_MAX_VALUE);
+}
+
 }  // namespace prerender
diff --git a/chrome/browser/prerender/prerender_histograms.h b/chrome/browser/prerender/prerender_histograms.h
index 85dea4f..9c6ba77 100644
--- a/chrome/browser/prerender/prerender_histograms.h
+++ b/chrome/browser/prerender/prerender_histograms.h
@@ -11,6 +11,7 @@
 #include "base/time.h"
 #include "chrome/browser/prerender/prerender_contents.h"
 #include "chrome/browser/prerender/prerender_final_status.h"
+#include "chrome/browser/prerender/prerender_local_predictor.h"
 #include "chrome/browser/prerender/prerender_origin.h"
 #include "googleurl/src/gurl.h"
 
@@ -46,6 +47,16 @@ class PrerenderHistograms {
   void RecordPageLoadTimeNotSwappedIn(base::TimeDelta page_load_time,
                                       const GURL& url) const;
 
+  // For simulated local browsing prerendering, records the PLT without
+  // any local browsing prerendering.
+  void RecordSimulatedLocalBrowsingBaselinePLT(base::TimeDelta page_load_time,
+                                               const GURL& url) const;
+
+  // For simulated local browsing prerendering, records the PLT with
+  // local browsing prerendering.
+  void RecordSimulatedLocalBrowsingPLT(base::TimeDelta page_load_time,
+                                       const GURL& url) const;
+
   // Records the time from when a page starts prerendering to when the user
   // navigates to it. This must be called on the UI thread.
   void RecordTimeUntilUsed(base::TimeDelta time_until_used,
@@ -79,6 +90,9 @@ class PrerenderHistograms {
   // swap-in.
   void RecordFractionPixelsFinalAtSwapin(double fraction) const;
 
+  // Record the occurrence of an event from the local predictor.
+  void RecordLocalPredictorEvent(PrerenderLocalPredictor::Event event) const;
+
  private:
   base::TimeTicks GetCurrentTimeTicks() const;
 
diff --git a/chrome/browser/prerender/prerender_local_predictor.cc b/chrome/browser/prerender/prerender_local_predictor.cc
index ba16e8b..662ecad 100644
--- a/chrome/browser/prerender/prerender_local_predictor.cc
+++ b/chrome/browser/prerender/prerender_local_predictor.cc
@@ -4,14 +4,21 @@
 
 #include "chrome/browser/prerender/prerender_local_predictor.h"
 
+#include <map>
+#include <set>
+
 #include "base/timer.h"
+#include "chrome/browser/prerender/prerender_histograms.h"
 #include "chrome/browser/prerender/prerender_manager.h"
 #include "chrome/browser/profiles/profile.h"
 #include "chrome/browser/history/history.h"
 #include "chrome/browser/history/history_database.h"
 #include "content/public/browser/browser_thread.h"
+#include "content/public/common/page_transition_types.h"
 
 using content::BrowserThread;
+using content::PageTransition;
+using history::URLID;
 
 namespace prerender {
 
@@ -21,7 +28,7 @@ namespace {
 class GetURLForURLIDTask : public HistoryDBTask {
  public:
   GetURLForURLIDTask(PrerenderLocalPredictor* local_predictor,
-                     history::URLID url_id)
+                     URLID url_id)
       : local_predictor_(local_predictor),
         url_id_(url_id),
         success_(false) {
@@ -45,7 +52,7 @@ class GetURLForURLIDTask : public HistoryDBTask {
   virtual ~GetURLForURLIDTask() {}
 
   PrerenderLocalPredictor* local_predictor_;
-  history::URLID url_id_;
+  URLID url_id_;
   bool success_;
   GURL url_;
   DISALLOW_COPY_AND_ASSIGN(GetURLForURLIDTask);
@@ -83,17 +90,53 @@ class GetVisitHistoryTask : public HistoryDBTask {
 // Maximum visit history to retrieve from the visit database.
 const int kMaxVisitHistory = 100 * 1000;
 
+// Visit history size at which to trigger pruning, and number of items to prune.
+const int kVisitHistoryPruneThreshold = 120 * 1000;
+const int kVisitHistoryPruneAmount = 20 * 1000;
+
+const int kMaxLocalPredictionTimeMs = 300 * 1000;
+const int kMinLocalPredictionTimeMs = 500;
+
+bool IsBackForward(PageTransition transition) {
+  return (transition & content::PAGE_TRANSITION_FORWARD_BACK) != 0;
+}
+
+bool IsHomePage(PageTransition transition) {
+  return (transition & content::PAGE_TRANSITION_HOME_PAGE) != 0;
+}
+
+bool IsIntermediateRedirect(PageTransition transition) {
+  return (transition & content::PAGE_TRANSITION_CHAIN_END) == 0;
+}
+
+bool ShouldExcludeTransitionForPrediction(PageTransition transition) {
+  return IsBackForward(transition) || IsHomePage(transition) ||
+      IsIntermediateRedirect(transition);
+}
+
+base::Time GetCurrentTime() {
+  return base::Time::Now();
+}
+
 }  // namespace
 
+struct PrerenderLocalPredictor::PrerenderData {
+  base::Time start_time;
+  URLID url_id;
+  double priority;
+  GURL url;
+};
+
 PrerenderLocalPredictor::PrerenderLocalPredictor(
     PrerenderManager* prerender_manager)
-    : prerender_manager_(prerender_manager),
-      visit_history_initialized_(false) {
+    : prerender_manager_(prerender_manager) {
+  RecordEvent(EVENT_CONSTRUCTED);
   if (MessageLoop::current()) {
     timer_.Start(FROM_HERE,
                  base::TimeDelta::FromMilliseconds(kInitDelayMs),
                  this,
                  &PrerenderLocalPredictor::Init);
+    RecordEvent(EVENT_INIT_SCHEDULED);
   }
 }
 
@@ -104,24 +147,128 @@ PrerenderLocalPredictor::~PrerenderLocalPredictor() {
 
 void PrerenderLocalPredictor::OnAddVisit(const history::BriefVisitInfo& info) {
   DCHECK(BrowserThread::CurrentlyOn(BrowserThread::UI));
-  HistoryService* history = GetHistoryIfExists();
-  if (history) {
-    history->ScheduleDBTask(
-        new GetURLForURLIDTask(this, info.url_id),
-        &history_db_consumer_);
+  RecordEvent(EVENT_ADD_VISIT);
+  if (!visit_history_.get())
+    return;
+  visit_history_->push_back(info);
+  if (static_cast<int>(visit_history_->size()) > kVisitHistoryPruneThreshold) {
+    visit_history_->erase(visit_history_->begin(),
+                          visit_history_->begin() + kVisitHistoryPruneAmount);
+  }
+  RecordEvent(EVENT_ADD_VISIT_INITIALIZED);
+  if (current_prerender_.get() &&
+      current_prerender_->url_id == info.url_id &&
+      IsPrerenderStillValid(current_prerender_.get())) {
+    last_swapped_in_prerender_.reset(current_prerender_.release());
+    RecordEvent(EVENT_ADD_VISIT_PRERENDER_IDENTIFIED);
+  }
+  if (ShouldExcludeTransitionForPrediction(info.transition))
+    return;
+  RecordEvent(EVENT_ADD_VISIT_RELEVANT_TRANSITION);
+  base::TimeDelta max_age =
+      base::TimeDelta::FromMilliseconds(kMaxLocalPredictionTimeMs);
+  base::TimeDelta min_age =
+      base::TimeDelta::FromMilliseconds(kMinLocalPredictionTimeMs);
+  std::set<URLID> next_urls_currently_found;
+  std::map<URLID, int> next_urls_num_found;
+  int num_occurrences_of_current_visit = 0;
+  base::Time last_visited;
+  URLID best_next_url = 0;
+  int best_next_url_count = 0;
+  const std::vector<history::BriefVisitInfo>& visits = *(visit_history_.get());
+  for (int i = 0; i < static_cast<int>(visits.size()); i++) {
+    if (!ShouldExcludeTransitionForPrediction(visits[i].transition)) {
+      if (visits[i].url_id == info.url_id) {
+        last_visited = visits[i].time;
+        num_occurrences_of_current_visit++;
+        next_urls_currently_found.clear();
+        continue;
+      }
+      if (!last_visited.is_null() &&
+          last_visited > visits[i].time - max_age &&
+          last_visited < visits[i].time - min_age) {
+        next_urls_currently_found.insert(visits[i].url_id);
+      }
+    }
+    if (i == static_cast<int>(visits.size()) - 1 ||
+        visits[i+1].url_id == info.url_id) {
+      for (std::set<URLID>::iterator it = next_urls_currently_found.begin();
+           it != next_urls_currently_found.end();
+           ++it) {
+        std::pair<std::map<URLID, int>::iterator, bool> insert_ret =
+            next_urls_num_found.insert(std::pair<URLID, int>(*it, 0));
+        std::map<URLID, int>::iterator num_found_it = insert_ret.first;
+        num_found_it->second++;
+        if (num_found_it->second > best_next_url_count) {
+          best_next_url_count = num_found_it->second;
+          best_next_url = *it;
+        }
+      }
+    }
+  }
+
+  // Only consider a candidate next page for prerendering if it was viewed
+  // at least twice, and at least 10% of the time.
+  if (num_occurrences_of_current_visit > 0 &&
+      best_next_url_count > 1 &&
+      best_next_url_count * 10 >= num_occurrences_of_current_visit) {
+    RecordEvent(EVENT_ADD_VISIT_IDENTIFIED_PRERENDER_CANDIDATE);
+    double priority = static_cast<double>(best_next_url_count) /
+        static_cast<double>(num_occurrences_of_current_visit);
+    base::Time current_time = GetCurrentTime();
+    if (!current_prerender_.get() ||
+        current_prerender_->priority < priority ||
+        current_prerender_->start_time < current_time - max_age) {
+      RecordEvent(EVENT_ADD_VISIT_PRERENDERING);
+      if (!current_prerender_.get() ||
+          current_prerender_->url_id != best_next_url) {
+        current_prerender_.reset(new PrerenderData());
+        current_prerender_->url_id = best_next_url;
+        current_prerender_->priority = priority;
+        current_prerender_->start_time = current_time;
+      } else {
+        if (priority > current_prerender_->priority)
+          current_prerender_->priority = priority;
+        // If the prerender already existed, we want to extend it.  However,
+        // we do not want to set its start_time to the current time to
+        // disadvantage PLT computations when the prerender is swapped in.
+        // So we set the new start time to current_time - 10s (since the vast
+        // majority of PLTs are < 10s), provided that is not before the actual
+        // time the prerender was started (so as to not artificially advantage
+        // the PLT computation).
+        base::Time simulated_new_start_time =
+            current_time - base::TimeDelta::FromSeconds(10);
+        if (simulated_new_start_time > current_prerender_->start_time)
+          current_prerender_->start_time = simulated_new_start_time;
+      }
+      if (current_prerender_->url.is_empty()) {
+        HistoryService* history = GetHistoryIfExists();
+        if (history) {
+          history->ScheduleDBTask(
+              new GetURLForURLIDTask(this, current_prerender_->url_id),
+              &history_db_consumer_);
+        }
+      }
+    }
   }
 }
 
 void PrerenderLocalPredictor::OnLookupURL(history::URLID url_id,
                                           const GURL& url) {
+  if (current_prerender_.get() && current_prerender_->url_id == url_id) {
+    current_prerender_->url = url;
+    RecordEvent(EVENT_GOT_PRERENDER_URL);
+  }
 }
 
 void PrerenderLocalPredictor::OnGetInitialVisitHistory(
     scoped_ptr<std::vector<history::BriefVisitInfo> > visit_history) {
   DCHECK(BrowserThread::CurrentlyOn(BrowserThread::UI));
-  DCHECK(!visit_history_initialized_);
-  visit_history_.reset(visit_history.release());
-  visit_history_initialized_ = true;
+  DCHECK(!visit_history_.get());
+  RecordEvent(EVENT_INIT_SUCCEEDED);
+  // Since the visit history has descending timestamps, we must reverse it.
+  visit_history_.reset(new std::vector<history::BriefVisitInfo>(
+      visit_history->rbegin(), visit_history->rend()));
 }
 
 HistoryService* PrerenderLocalPredictor::GetHistoryIfExists() const {
@@ -133,10 +280,10 @@ HistoryService* PrerenderLocalPredictor::GetHistoryIfExists() const {
 
 void PrerenderLocalPredictor::Init() {
   DCHECK(BrowserThread::CurrentlyOn(BrowserThread::UI));
+  RecordEvent(EVENT_INIT_STARTED);
   HistoryService* history = GetHistoryIfExists();
   if (!history) {
-    // TODO(tburkard): Record this somewhere (eg histogram) and/or try again
-    // later.
+    RecordEvent(EVENT_INIT_FAILED_NO_HISTORY);
     return;
   }
   history->ScheduleDBTask(
@@ -146,4 +293,56 @@ void PrerenderLocalPredictor::Init() {
   observing_history_service_->AddVisitDatabaseObserver(this);
 }
 
+void PrerenderLocalPredictor::OnPLTEventForURL(const GURL& url,
+                                               base::TimeDelta page_load_time) {
+  scoped_ptr<PrerenderData> prerender;
+  if (DoesPrerenderMatchPLTRecord(last_swapped_in_prerender_.get(),
+                                  url, page_load_time)) {
+    prerender.reset(last_swapped_in_prerender_.release());
+  }
+  if (DoesPrerenderMatchPLTRecord(current_prerender_.get(),
+                                  url, page_load_time)) {
+    prerender.reset(current_prerender_.release());
+  }
+  if (!prerender.get())
+    return;
+  if (IsPrerenderStillValid(prerender.get())) {
+    base::TimeDelta prerender_age = GetCurrentTime() - prerender->start_time;
+    prerender_manager_->histograms()->RecordSimulatedLocalBrowsingBaselinePLT(
+        page_load_time, url);
+    if (prerender_age > page_load_time) {
+      base::TimeDelta new_plt;
+      if (prerender_age <  2 * page_load_time)
+        new_plt = 2 * page_load_time - prerender_age;
+      prerender_manager_->histograms()->RecordSimulatedLocalBrowsingPLT(
+          new_plt, url);
+    }
+
+  }
+}
+
+bool PrerenderLocalPredictor::IsPrerenderStillValid(
+    PrerenderLocalPredictor::PrerenderData* prerender) const {
+  return (prerender &&
+          (prerender->start_time +
+           base::TimeDelta::FromMilliseconds(kMaxLocalPredictionTimeMs))
+          > GetCurrentTime());
+}
+
+void PrerenderLocalPredictor::RecordEvent(PrerenderLocalPredictor::Event event)
+    const {
+  prerender_manager_->histograms()->RecordLocalPredictorEvent(event);
+}
+
+bool PrerenderLocalPredictor::DoesPrerenderMatchPLTRecord(
+    PrerenderData* prerender, const GURL& url, base::TimeDelta plt) const {
+  if (prerender && prerender->start_time < GetCurrentTime() - plt) {
+    if (prerender->url.is_empty())
+      RecordEvent(EVENT_ERROR_NO_PRERENDER_URL_FOR_PLT);
+    return (prerender->url == url);
+  } else {
+    return false;
+  }
+}
+
 }  // namespace prerender
diff --git a/chrome/browser/prerender/prerender_local_predictor.h b/chrome/browser/prerender/prerender_local_predictor.h
index 031cbaf..2947e37 100644
--- a/chrome/browser/prerender/prerender_local_predictor.h
+++ b/chrome/browser/prerender/prerender_local_predictor.h
@@ -21,11 +21,27 @@ class PrerenderManager;
 
 // PrerenderLocalPredictor maintains local browsing history to make prerender
 // predictions.
-// At this point, the class is just illustrating the interface with the
-// Chrome History.
-// TODO(tburkard): Fill in actual prerender prediction logic.
+// At this point, the class is not actually creating prerenders, but just
+// recording timing stats about the effect prerendering would have.
 class PrerenderLocalPredictor : history::VisitDatabaseObserver {
  public:
+  enum Event {
+    EVENT_CONSTRUCTED = 0,
+    EVENT_INIT_SCHEDULED = 1,
+    EVENT_INIT_STARTED = 2,
+    EVENT_INIT_FAILED_NO_HISTORY = 3,
+    EVENT_INIT_SUCCEEDED = 4,
+    EVENT_ADD_VISIT = 5,
+    EVENT_ADD_VISIT_INITIALIZED = 6,
+    EVENT_ADD_VISIT_PRERENDER_IDENTIFIED = 7,
+    EVENT_ADD_VISIT_RELEVANT_TRANSITION = 8,
+    EVENT_ADD_VISIT_IDENTIFIED_PRERENDER_CANDIDATE = 9,
+    EVENT_ADD_VISIT_PRERENDERING = 10,
+    EVENT_GOT_PRERENDER_URL = 11,
+    EVENT_ERROR_NO_PRERENDER_URL_FOR_PLT = 12,
+    EVENT_MAX_VALUE
+  };
+
   // A PrerenderLocalPredictor is owned by the PrerenderManager specified
   // in the constructor.  It will be destoryed at the time its owning
   // PrerenderManager is destroyed.
@@ -40,9 +56,17 @@ class PrerenderLocalPredictor : history::VisitDatabaseObserver {
   void OnGetInitialVisitHistory(
       scoped_ptr<std::vector<history::BriefVisitInfo> > visit_history);
 
+  void OnPLTEventForURL(const GURL& url, base::TimeDelta page_load_time);
+
  private:
+  struct PrerenderData;
   HistoryService* GetHistoryIfExists() const;
   void Init();
+  bool IsPrerenderStillValid(PrerenderData* prerender) const;
+  bool DoesPrerenderMatchPLTRecord(PrerenderData* prerender,
+                                   const GURL& url,
+                                   base::TimeDelta plt) const;
+  void RecordEvent(Event event) const;
 
   PrerenderManager* prerender_manager_;
   base::OneShotTimer<PrerenderLocalPredictor> timer_;
@@ -54,7 +78,6 @@ class PrerenderLocalPredictor : history::VisitDatabaseObserver {
   CancelableRequestConsumer history_db_consumer_;
 
   scoped_ptr<std::vector<history::BriefVisitInfo> > visit_history_;
-  bool visit_history_initialized_;
 
   // We keep a reference to the HistoryService which we registered to
   // observe.  On destruction, we have to remove ourselves from that history
@@ -64,6 +87,9 @@ class PrerenderLocalPredictor : history::VisitDatabaseObserver {
   // the PrerenderLocalPredictor.
   scoped_refptr<HistoryService> observing_history_service_;
 
+  scoped_ptr<PrerenderData> current_prerender_;
+  scoped_ptr<PrerenderData> last_swapped_in_prerender_;
+
   DISALLOW_COPY_AND_ASSIGN(PrerenderLocalPredictor);
 };
 
diff --git a/chrome/browser/prerender/prerender_manager.cc b/chrome/browser/prerender/prerender_manager.cc
index b41e31a..2e738773 100644
--- a/chrome/browser/prerender/prerender_manager.cc
+++ b/chrome/browser/prerender/prerender_manager.cc
@@ -259,7 +259,8 @@ PrerenderManager::PrerenderManager(Profile* profile,
           base::TimeDelta::FromMilliseconds(kMinTimeBetweenPrerendersMs)),
       weak_factory_(this),
       prerender_history_(new PrerenderHistory(kHistoryLength)),
-      histograms_(new PrerenderHistograms()) {
+      histograms_(new PrerenderHistograms()),
+      local_predictor_(new PrerenderLocalPredictor(this)) {
   // There are some assumptions that the PrerenderManager is on the UI thread.
   // Any other checks simply make sure that the PrerenderManager is accessed on
   // the same thread that it was created on.
@@ -603,6 +604,8 @@ void PrerenderManager::RecordPerceivedPageLoadTime(
         perceived_page_load_time, was_prerender, was_complete_prerender, url);
     prerender_manager->histograms_->RecordPercentLoadDoneAtSwapin(
         fraction_plt_elapsed_at_swap_in);
+    prerender_manager->local_predictor_->
+        OnPLTEventForURL(url, perceived_page_load_time);
   }
 }
 
diff --git a/chrome/browser/prerender/prerender_tab_helper.cc b/chrome/browser/prerender/prerender_tab_helper.cc
index e8053e3..2a78304 100644
--- a/chrome/browser/prerender/prerender_tab_helper.cc
+++ b/chrome/browser/prerender/prerender_tab_helper.cc
@@ -178,6 +178,7 @@ void PrerenderTabHelper::DidCommitProvisionalLoadForFrame(
     content::RenderViewHost* render_view_host) {
   if (!is_main_frame)
     return;
+  url_ = validated_url;
   PrerenderManager* prerender_manager = MaybeGetPrerenderManager();
   if (!prerender_manager)
     return;