Adding performance tests for HQP that represent importance of optimising HistoryItemsForTerms method

components/omnibox/browser/history_quick_provider_performance_unittest.cc

Index: components/omnibox/browser/history_quick_provider_performance_unittest.cc
diff --git a/components/omnibox/browser/history_quick_provider_performance_unittest.cc b/components/omnibox/browser/history_quick_provider_performance_unittest.cc
new file mode 100644
index 0000000000000000000000000000000000000000..193f6f687c12d57a0bb36fa0f2cb29978c56eadc
--- /dev/null
+++ b/components/omnibox/browser/history_quick_provider_performance_unittest.cc
@@ -0,0 +1,287 @@
+// Copyright 2016 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 "components/omnibox/browser/history_quick_provider.h"
+
+#include <memory>
+#include <string>
+
+#include "base/macros.h"
+#include "base/run_loop.h"
+#include "base/scoped_observer.h"
+#include "base/strings/utf_string_conversions.h"
+#include "components/history/core/browser/history_backend.h"
+#include "components/history/core/browser/history_database.h"
+#include "components/history/core/browser/history_service.h"
+#include "components/history/core/test/history_service_test_util.h"
+#include "components/omnibox/browser/fake_autocomplete_provider_client.h"
+#include "components/omnibox/browser/history_test_util.h"
+#include "components/omnibox/browser/in_memory_url_index_test_util.h"
+#include "testing/gtest/include/gtest/gtest.h"
+#include "testing/perf/perf_test.h"
+
+using base::ASCIIToUTF16;

[Peter Kasting, 2016/10/24 22:28:29]

You don't use this symbol.

[dyaroshev, 2016/10/25 18:11:34]

Done.

+using base::Time;
+using base::TimeDelta;

[Peter Kasting, 2016/10/24 22:28:29]

Nit: Half the time this file explicitly qualifies these anyway, sometimes it
doesn't.  Do one or the other.  My preference is to always qualify, and nuke
these using directives.

[dyaroshev, 2016/10/25 18:11:35]

Done.

+
+namespace history {
+
+namespace {
+
+constexpr std::size_t kSimilarUrlCount = 10000;

[Peter Kasting, 2016/10/24 22:28:29]

Nit: For better or worse, we don't std::-qualify size_t in Chromium code.
(several places)

[dyaroshev, 2016/10/25 18:11:34]

Done.

+constexpr std::size_t kTestGroupSize = 5;
+
+struct TestURLInfo {
+  std::string url;
+  std::string title;
+  int visit_count;
+  int typed_count;
+  int days_from_now;
+};
+
+std::string GenerateSymbolsToChooseFrom() {
+  std::string res;
+  auto append_chars = [&res](char from, char to) {
+    for (char ch = from; ch <= to; ++ch)
+      res += ch;
+  };
+  append_chars('a', 'z');
+  append_chars('A', 'Z');
+  append_chars('0', '9');
+  res += ",/=+?#";
+  return res;
+}
+
+std::string GenerateWeiredShortString(int seed) {

[Peter Kasting, 2016/10/24 22:28:28]

Nit: Weird

(But I don't love "weird" in a function name.  What kind of a short string is a
"weird" one?  Add comments on what this means and use a different name.)

[dyaroshev, 2016/10/25 18:11:35]

Done.

+  CR_DEFINE_STATIC_LOCAL(std::string, syms, (GenerateSymbolsToChooseFrom()));

[Peter Kasting, 2016/10/24 22:28:29]

Why not just:

  static constexpr char kSyms[] =
      "abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ0123456789,/=+?#";
  static constexpr size_t kSymsSize = arraysize(kSyms) - 1;

This avoids the CR_DEFINE_STATIC_LOCAL and the function above.

[dyaroshev, 2016/10/25 18:11:35]

Done.

+  std::string res;
+  // Much like translating into another calculation system.
+  for (auto i = std::hash<int>()(seed); i; i /= syms.size()) {

[Peter Kasting, 2016/10/24 22:28:29]

Do you really need to hash?  Or do you just want random characters?  It looks as
if you're using "hash" here to get randomness, not to actually hash?  But maybe
I'm wrong.

[dyaroshev, 2016/10/25 18:11:35]

I want to get somewhat uniformly distributed deterministic integers. std::hash
seemed better than std::rand and uniform_distribution is not allowed

[Peter Kasting, 2016/10/25 18:27:56]

Because <random> is still on the TBD list for Chromium C++11 support?  I just
sent an email requesting that we move that to the allowed list.  I'll know
shortly what the fate of that is, but for now I'd try recoding this using
std::uniform_int_distribution or similar.  That seems clearer than this code.

[dyaroshev, 2016/10/26 22:29:12]

Rewrote with <random>. Will this slow down this patch?

+    res += syms[i % syms.size()];
+  }
+  return res;
+}
+
+std::string GeneratePopularUrlVariation(std::size_t seed) {
+  constexpr char kPopularUrl[] =

[Peter Kasting, 2016/10/24 22:28:28]

Nit: static

[dyaroshev, 2016/10/25 18:11:35]

Done.

+      "http://long.popular_url_with.many_variations/";
+  std::string res = kPopularUrl;
+
+  constexpr int kShortStringsCount = 5;
+  for (std::size_t i = seed; i < seed + kShortStringsCount; ++i)
+    res += GenerateWeiredShortString(i);
+
+  return res;
+}
+
+}  // namespace
+
+// This test is based on HistoryQuickProviderTest

[Peter Kasting, 2016/10/24 22:28:29]

Nit: Based how?  And why is this useful information for the reader?  Does it
explain some piece of strange code, or suggest something about how it should be
maintained?  If not, remove this comment.

[dyaroshev, 2016/10/25 18:11:34]

Done.

+class HQPPerfTestBase : public testing::Test {
+ public:
+  HQPPerfTestBase() = default;
+
+ protected:
+  void SetUp() override;
+  void TearDown() override;
+
+  void PrepareData(std::size_t data_count);

[Peter Kasting, 2016/10/24 22:28:28]

Nit: Add comments on these functions about what they do (in particular, what the
arguments mean).

[Peter Kasting, 2016/10/27 00:59:38]

Still need this

[dyaroshev, 2016/10/27 06:09:21]

Done.

+
+  base::TimeDelta RunTest(const base::string16& text);
+
+  void PrintMeasurements(const std::string& trace_name,
+                         const std::vector<base::TimeDelta>& measurements);
+
+  history::HistoryBackend* history_backend() {
+    return client_->GetHistoryService()->history_backend_.get();
+  }
+
+ private:
+  void FillData(std::size_t data_count);
+
+  // Customisation point to data generation,

[dyaroshev, 2016/10/24 17:07:08]

Customisation point for data generation.

+  virtual TestURLInfo GenerateNextUrlInfo() = 0;
+
+  base::MessageLoop message_loop_;
+  std::unique_ptr<FakeAutocompleteProviderClient> client_;
+
+  ACMatches ac_matches_;  // The resulting matches after running RunTest.
+
+  scoped_refptr<HistoryQuickProvider> provider_;
+};

[Peter Kasting, 2016/10/24 22:28:28]

Nit: DISALLOW_COPY_AND_ASSIGN

[dyaroshev, 2016/10/25 18:11:35]

Doesn't work for test classes. I get compilation errors.

[Peter Kasting, 2016/10/25 18:27:56]

Oh?  https://cs.chromium.org/chromium/src/base/bind_unittest.cc?rcl=0&l=316 is
an example of a testing::Test subclass that has this, and there are many more. 
What are the errors you're seeing?

[dyaroshev, 2016/10/26 22:29:13]

I forgot semicolon after DISALLOW_COPY_AND_ASSIGN. Understanding that from error
messages wasn't easy)
Done.

+
+void HQPPerfTestBase::SetUp() {
+  if (base::ThreadTicks::IsSupported())
+    base::ThreadTicks::WaitUntilInitialized();
+  client_.reset(new FakeAutocompleteProviderClient());
+  ASSERT_TRUE(client_->GetHistoryService());
+}
+
+void HQPPerfTestBase::TearDown() {
+  provider_ = nullptr;
+  // The InMemoryURLIndex must be explicitly shut down or it will DCHECK() in
+  // its destructor.
+  client_->GetInMemoryURLIndex()->Shutdown();
+  client_->set_in_memory_url_index(nullptr);
+  // History index rebuild task is created from main thread during SetUp,
+  // performed on DB thread and must be deleted on main thread.
+  // Run main loop to process delete task, to prevent leaks.
+  base::RunLoop().RunUntilIdle();
+}
+
+void HQPPerfTestBase::PrepareData(std::size_t data_count) {
+  FillData(data_count);
+
+  // |FillData()| must be called before |RebuildFromHistory()|. This will
+  // ensure that the index is properly populated with data from the database.
+  InMemoryURLIndex* url_index = client_->GetInMemoryURLIndex();
+  url_index->RebuildFromHistory(
+      client_->GetHistoryService()->history_backend_->db());
+  BlockUntilInMemoryURLIndexIsRefreshed(url_index);
+
+  // History index refresh creates rebuilt tasks to run on history thread.
+  // Block here to make sure that all of them are complete.
+  history::BlockUntilHistoryProcessesPendingRequests(
+      client_->GetHistoryService());
+
+  provider_ = new HistoryQuickProvider(client_.get());
+}
+
+void HQPPerfTestBase::FillData(std::size_t data_count) {
+  sql::Connection& db(history_backend()->db()->GetDB());
+  ASSERT_TRUE(db.is_open());
+
+  size_t visit_id = 1;
+  for (size_t i = 0; i < data_count; ++i) {
+    TestURLInfo cur = GenerateNextUrlInfo();
+    Time visit_time = Time::Now() - TimeDelta::FromDays(cur.days_from_now);
+    AddURLToDBForTests(&db, i + 1, cur.url, cur.title, cur.visit_count,
+                       cur.typed_count, visit_time);

[Peter Kasting, 2016/10/24 22:28:28]

Nit: Basically this whole loop body is also in
history_quick_provider_unittest.cc.  Maybe factor to a common base location.

[dyaroshev, 2016/10/25 18:11:35]

Done.

+
+    auto add_visit = [&db, &visit_id, &visit_time,
+                      &i](ui::PageTransition transtition) mutable {
+      // Assume earlier visits are at one-day intervals.
+      visit_time -= TimeDelta::FromDays(1);
+      history::AddVisitToDBForTests(&db, visit_id++, i + 1, visit_time,
+                                    transtition);
+    };
+
+    // Mark the most recent |cur.typed_count| visits as typed.
+    for (int j = 0; j < cur.typed_count; ++j)
+      add_visit(ui::PAGE_TRANSITION_TYPED);
+
+    for (int j = cur.typed_count; j < cur.visit_count; ++j)
+      add_visit(ui::PAGE_TRANSITION_LINK);
+  }
+}
+
+void HQPPerfTestBase::PrintMeasurements(
+    const std::string& trace_name,
+    const std::vector<base::TimeDelta>& measurements) {
+  auto test_info = ::testing::UnitTest::GetInstance()->current_test_info();
+
+  std::string durations;
+  for (const auto& measurement : measurements)
+    durations += std::to_string(measurement.InMillisecondsRoundedUp()) + ',';
+
+  perf_test::PrintResultList(test_info->test_case_name(), test_info->name(),
+                             trace_name, durations, "ms", true);
+}
+
+base::TimeDelta HQPPerfTestBase::RunTest(const base::string16& text) {
+  base::RunLoop().RunUntilIdle();
+  AutocompleteInput input(text, base::string16::npos, std::string(), GURL(),
+                          metrics::OmniboxEventProto::INVALID_SPEC, false,
+                          false, true, true, false, TestSchemeClassifier());
+
+  base::Time regular_start = base::Time::Now();
+  base::ThreadTicks thread_start;
+  if (base::ThreadTicks::IsSupported())
+    thread_start = base::ThreadTicks::Now();
+
+  provider_->Start(input, false);
+  EXPECT_TRUE(provider_->done());
+
+  if (base::ThreadTicks::IsSupported())
+    return base::ThreadTicks::Now() - thread_start;
+
+  return base::Time::Now() - regular_start;

[Peter Kasting, 2016/10/24 22:28:29]

Nit: I think it would be clearer to do something like:

  // In class declaration so it's inlined
  void TestBody(const AutocompleteInput& input) {
    provider_->Start(input, false);
    EXPECT_TRUE(provider_->done());
  }

// Here
base::TimeDelta HQPPerfTestBase::RunTest(const base::string16& text) {
  ...

  // Time using the more-accurate ThreadTicks method if supported.
  if (base::ThreadTicks::IsSupported()) {
    const base::ThreadTicks start = base::ThreadTicks::Now();
    TestBody();
    return base::ThreadTicks::Now() - start;
  }

  // Fall back to wall clock time.
  const base::Time start = base::Time::Now();
  TestBody();
  return base::Time::Now() - start;
}

[dyaroshev, 2016/10/25 18:11:35]

Done.

+}
+
+class HQPPerfTestOnePopularURL : public HQPPerfTestBase {

[Peter Kasting, 2016/10/24 22:28:29]

Nit: Do we really buy much by splitting this out into its own subclass for now? 
Unless you already have more perf tests planned, how do you know that this is
the right interface for them?

Using the "design for what you need now" principle, I'd probably merge these two
classes into a single HQPPerfTest class and refactor later if need be (again,
unless you have more tests planned).

[dyaroshev, 2016/10/25 18:11:34]

Done.

+ public:
+  void SetUp() override {
+    HQPPerfTestBase::SetUp();
+    PrepareData(kSimilarUrlCount);
+  }
+
+ private:
+  TestURLInfo GenerateNextUrlInfo() final {
+    ++call_count_;
+    return {
+        GeneratePopularUrlVariation(call_count_),
+        "Page " + std::to_string(call_count_),
+        1,
+        1,
+        1,
+    };
+  }
+
+  int call_count_;
+};

[Peter Kasting, 2016/10/24 22:28:29]

Nit: DISALLOW_COPY_AND_ASSIGN

+
+TEST_F(HQPPerfTestOnePopularURL, Typing) {
+  auto test_url = GeneratePopularUrlVariation(kSimilarUrlCount + 1);
+
+  auto url_position_to_string = [&test_url](std::string::iterator it) {
+    return std::to_string(it - test_url.begin());
+  };
+
+  std::vector<base::TimeDelta> measurements;
+  measurements.reserve(kTestGroupSize);
+
+  for (auto i = test_url.begin(); i != test_url.end();) {
+    auto group_start = i;
+    auto group_end = std::min(i + kTestGroupSize, test_url.end());
+
+    for (auto j = group_start; j != group_end; ++j)
+      measurements.push_back(RunTest(base::UTF8ToUTF16({test_url.begin(), j})));

[Peter Kasting, 2016/10/24 22:28:29]

Nit: AFAICT, this line is the only thing that differs from the case below. 
Consider some kind of helper function/refactoring to allow these to share as
much code as possible?

If you don't do this, then all the comments below apply up here too.

[dyaroshev, 2016/10/25 18:11:34]

Haven't got around to it yet. I thought about it when first wrote it, and it's
not obvious how to refactor it.

[Peter Kasting, 2016/10/25 18:27:56]

Write this as a template, and pass begin()/end() to one version and
rbegin()/rend() to the other?  That doesn't solve the .base() call, but I can
think of a couple (possibly ugly) ways to do that.

Or, always do the iteration forward, but in the second test, reverse the URL
string before passing it in?

[dyaroshev, 2016/10/26 22:29:13]

Rewrote with StringPiece. I think, looks nice.

+
+    auto trace_name = url_position_to_string(group_start) + '-' +
+                      url_position_to_string(group_end);
+
+    PrintMeasurements(trace_name, measurements);
+    i = group_end;
+    measurements.clear();
+  }
+}
+
+TEST_F(HQPPerfTestOnePopularURL, Backspacing) {
+  auto test_url = GeneratePopularUrlVariation(kSimilarUrlCount + 1);

[Peter Kasting, 2016/10/24 22:28:29]

Nit: I'd prefer to use "auto" a little less aggressively in this function,
because it makes it hard to tell what e.g. the type of j.base() is below ("j is
an auto... of the same type as group_start, which is an auto... of the same type
as i, which is an auto... of a reverse_iterator type for test_url, which is an
auto... of the return type of GeneratePopularUrlVariation()... now I gotta look
that up").

Feel free to use it for loop iterator types and the type of the lambda below, or
in places where the type is already explicitly present once in the statement,
but in a case like this, I would use an explicit typename.

[dyaroshev, 2016/10/25 18:11:35]

Done.

+
+  auto url_position_to_string = [&test_url](std::string::reverse_iterator it) {

[Peter Kasting, 2016/10/24 22:28:29]

Nit: I don't know if we have a rule on this, but I tend to prefer naming local
lambdas like functions (CamelCaseName) rather than like variables
(hacker_case_name).

const& on |it|?

[dyaroshev, 2016/10/25 18:11:35]

Haven't got around to it yet.

[dyaroshev, 2016/10/26 22:29:13]

Done, if I haven't missed anything.

+    return std::to_string(it.base() - test_url.begin());
+  };
+
+  std::vector<base::TimeDelta> measurements;
+  measurements.reserve(test_url.length());
+
+  for (auto i = test_url.rbegin(); i != test_url.rend();) {

[Peter Kasting, 2016/10/24 22:28:29]

Nit: Place space between ; and ), unless this is how clang-format did it

[dyaroshev, 2016/10/25 18:11:35]

clang-format

+    auto group_start = i;
+    auto group_end = std::min(i + kTestGroupSize, test_url.rend());
+
+    for (auto j = group_start; j != group_end; ++j)

[Peter Kasting, 2016/10/24 22:28:29]

Nit: Why not just

    for (; i != group_end; ++i) {

Then use |i| in the body and eliminate the "i = group_end;" line below.

[dyaroshev, 2016/10/25 18:11:34]

Haven't got around to it yet.

[dyaroshev, 2016/10/26 22:29:13]

I've done smth cleaner than before.

+      measurements.push_back(
+          RunTest(base::UTF8ToUTF16({test_url.begin(), j.base()})));
+
+    auto trace_name = url_position_to_string(group_start) + '-' +
+                      url_position_to_string(group_end);

[Peter Kasting, 2016/10/24 22:28:29]

Nit: I'd probably just inline this into the next statement, but whatever

[dyaroshev, 2016/10/26 22:29:12]

Done.

+
+    PrintMeasurements(trace_name, measurements);
+    i = group_end;
+    measurements.clear();
+  }
+}
+
+}  // namespace history