You are viewing a plain text version of this content. The canonical link for it is here.
Posted to commits@kudu.apache.org by to...@apache.org on 2017/11/01 23:42:26 UTC

[1/4] kudu git commit: compaction_policy: improve tests

Repository: kudu
Updated Branches:
  refs/heads/master 6696b4eb4 -> 9dd64e1b3


compaction_policy: improve tests

Adds tests cases for some more time-series-like layouts of rowsets.

Change-Id: Iaf19d382c916a807f9af3fa34da43e651a566663
Reviewed-on: http://gerrit.cloudera.org:8080/8443
Reviewed-by: Adar Dembo <ad...@cloudera.com>
Tested-by: Kudu Jenkins


Project: http://git-wip-us.apache.org/repos/asf/kudu/repo
Commit: http://git-wip-us.apache.org/repos/asf/kudu/commit/55dcdd05
Tree: http://git-wip-us.apache.org/repos/asf/kudu/tree/55dcdd05
Diff: http://git-wip-us.apache.org/repos/asf/kudu/diff/55dcdd05

Branch: refs/heads/master
Commit: 55dcdd05883004b18f2f8cb9e29414d358a6621b
Parents: 6696b4e
Author: Todd Lipcon <to...@apache.org>
Authored: Wed Nov 1 11:44:09 2017 -0700
Committer: Todd Lipcon <to...@apache.org>
Committed: Wed Nov 1 23:11:40 2017 +0000

----------------------------------------------------------------------
 src/kudu/tablet/compaction_policy-test.cc | 101 +++++++++++++++++++++----
 1 file changed, 87 insertions(+), 14 deletions(-)
----------------------------------------------------------------------


http://git-wip-us.apache.org/repos/asf/kudu/blob/55dcdd05/src/kudu/tablet/compaction_policy-test.cc
----------------------------------------------------------------------
diff --git a/src/kudu/tablet/compaction_policy-test.cc b/src/kudu/tablet/compaction_policy-test.cc
index 653b3a8..9b19230 100644
--- a/src/kudu/tablet/compaction_policy-test.cc
+++ b/src/kudu/tablet/compaction_policy-test.cc
@@ -26,6 +26,7 @@
 #include <glog/stl_logging.h>
 #include <gtest/gtest.h>
 
+#include "kudu/gutil/stringprintf.h"
 #include "kudu/gutil/strings/numbers.h"
 #include "kudu/gutil/strings/split.h"
 #include "kudu/gutil/strings/substitute.h"
@@ -39,8 +40,8 @@
 #include "kudu/util/status.h"
 #include "kudu/util/stopwatch.h"
 #include "kudu/util/test_macros.h"
+#include "kudu/util/test_util.h"
 
-using std::shared_ptr;
 using std::unordered_set;
 using std::string;
 using std::vector;
@@ -48,27 +49,99 @@ using std::vector;
 namespace kudu {
 namespace tablet {
 
+class TestCompactionPolicy : public KuduTest {
+ protected:
+  void RunTestCase(const RowSetVector& vec,
+                   int size_budget_mb,
+                   unordered_set<RowSet*>* picked,
+                   double* quality) {
+    RowSetTree tree;
+    ASSERT_OK(tree.Reset(vec));
+
+    BudgetedCompactionPolicy policy(size_budget_mb);
+
+    ASSERT_OK(policy.PickRowSets(tree, picked, quality, nullptr));
+  }
+};
+
+
 // Simple test for budgeted compaction: with three rowsets which
 // mostly overlap, and an high budget, they should all be selected.
-TEST(TestCompactionPolicy, TestBudgetedSelection) {
-  RowSetVector vec;
-  vec.push_back(shared_ptr<RowSet>(new MockDiskRowSet("C", "c")));
-  vec.push_back(shared_ptr<RowSet>(new MockDiskRowSet("B", "a")));
-  vec.push_back(shared_ptr<RowSet>(new MockDiskRowSet("A", "b")));
-
-  RowSetTree tree;
-  ASSERT_OK(tree.Reset(vec));
+TEST_F(TestCompactionPolicy, TestBudgetedSelection) {
+  RowSetVector vec = {
+    std::make_shared<MockDiskRowSet>("C", "c"),
+    std::make_shared<MockDiskRowSet>("B", "a"),
+    std::make_shared<MockDiskRowSet>("A", "b")
+  };
 
   const int kBudgetMb = 1000; // enough to select all
-  BudgetedCompactionPolicy policy(kBudgetMb);
-
   unordered_set<RowSet*> picked;
   double quality = 0;
-  ASSERT_OK(policy.PickRowSets(tree, &picked, &quality, nullptr));
+  NO_FATALS(RunTestCase(vec, kBudgetMb, &picked, &quality));
   ASSERT_EQ(3, picked.size());
   ASSERT_GE(quality, 1.0);
 }
 
+// Test for the case when we have many rowsets, but none of them
+// overlap at all. This is likely to occur in workloads where the
+// primary key is always increasing (such as a timestamp).
+TEST_F(TestCompactionPolicy, TestNonOverlappingRowsets) {
+  if (!AllowSlowTests()) {
+    LOG(INFO) << "Skipped";
+    return;
+  }
+  RowSetVector vec;
+  for (int i = 0; i < 10000;  i++) {
+    vec.emplace_back(new MockDiskRowSet(
+        StringPrintf("%010d", i * 2),
+        StringPrintf("%010d", i * 2 + 1)));
+  }
+  unordered_set<RowSet*> picked;
+  double quality = 0;
+  NO_FATALS(RunTestCase(vec, /*size_budget_mb=*/128, &picked, &quality));
+  ASSERT_EQ(quality, 0);
+  ASSERT_TRUE(picked.empty());
+}
+
+// Similar to the above, but with some small overlap between adjacent
+// rowsets.
+TEST_F(TestCompactionPolicy, TestTinyOverlapRowsets) {
+  if (!AllowSlowTests()) {
+    LOG(INFO) << "Skipped";
+    return;
+  }
+
+  RowSetVector vec;
+  for (int i = 0; i < 10000;  i++) {
+    vec.emplace_back(new MockDiskRowSet(
+        StringPrintf("%010d", i * 10000),
+        StringPrintf("%010d", i * 10000 + 11000)));
+  }
+  unordered_set<RowSet*> picked;
+  double quality = 0;
+  NO_FATALS(RunTestCase(vec, /*size_budget_mb=*/128, &picked, &quality));
+  ASSERT_EQ(quality, 0);
+  ASSERT_TRUE(picked.empty());
+}
+
+// Test case with 100 rowsets, each of which overlaps with its two
+// neighbors to the right.
+TEST_F(TestCompactionPolicy, TestSignificantOverlap) {
+  RowSetVector vec;
+  for (int i = 0; i < 100;  i++) {
+    vec.emplace_back(new MockDiskRowSet(
+        StringPrintf("%010d", i * 10000),
+        StringPrintf("%010d", (i + 2) * 10000)));
+  }
+  unordered_set<RowSet*> picked;
+  double quality = 0;
+  const int kBudgetMb = 64;
+  NO_FATALS(RunTestCase(vec, kBudgetMb, &picked, &quality));
+  ASSERT_GT(quality, 0.5);
+  // Each rowset is 1MB so we should exactly fill the budget.
+  ASSERT_EQ(picked.size(), kBudgetMb);
+}
+
 // Return the directory of the currently-running executable.
 static string GetExecutableDir() {
   string exec;
@@ -100,8 +173,8 @@ static RowSetVector LoadFile(const string& name) {
 // Realistic test using data scraped from a tablet containing 200+GB of YCSB data.
 // This test can be used as a benchmark for optimizing the compaction policy,
 // and also serves as a basic regression/stress test using real data.
-TEST(TestCompactionPolicy, TestYcsbCompaction) {
-  RowSetVector vec = LoadFile("ycsb-test-rowsets.tsv");;
+TEST_F(TestCompactionPolicy, TestYcsbCompaction) {
+  RowSetVector vec = LoadFile("ycsb-test-rowsets.tsv");
   RowSetTree tree;
   ASSERT_OK(tree.Reset(vec));
   vector<double> qualities;


[2/4] kudu git commit: compaction_policy: don't run a compaction if it provides very little improvement

Posted by to...@apache.org.
compaction_policy: don't run a compaction if it provides very little improvement

In the case that a compaction only results in a tiny amount of
improvement (eg reducing height in only 1% of the key space or less)
then we should not bother to run it. This patch implements this short
circuit behavior and also ensures that we short-circuit the compaction
policy calculation early as soon as we can see that we aren't going to
find a worthwhile compaction.

This provided a huge speedup on evaluating the compaction policies for cases
where the rowsets don't (or minimally) overlap.

Original:
 Performance counter stats for 'build/latest/bin/compaction_policy-test --gtest_filter=*TinyOver*' (10 runs):

       6475.676701      task-clock (msec)         #    1.000 CPUs utilized            ( +-  1.35% )
                10      context-switches          #    0.001 K/sec                    ( +- 29.76% )
                 0      cpu-migrations            #    0.000 K/sec                    ( +-100.00% )
             2,505      page-faults               #    0.387 K/sec                    ( +-  4.24% )
    24,174,771,160      cycles                    #    3.733 GHz                      ( +-  0.50% )
    79,871,269,334      instructions              #    3.30  insn per cycle           ( +-  0.00% )
    14,113,123,041      branches                  # 2179.405 M/sec                    ( +-  0.00% )
        58,160,529      branch-misses             #    0.41% of all branches          ( +-  0.02% )

       6.476139848 seconds time elapsed                                          ( +-  1.35% )

With patch:
 Performance counter stats for 'build/latest/bin/compaction_policy-test --gtest_filter=*TinyOver*' (10 runs):

        426.861117      task-clock (msec)         #    0.999 CPUs utilized            ( +-  0.87% )
                 2      context-switches          #    0.004 K/sec                    ( +- 23.13% )
                 0      cpu-migrations            #    0.000 K/sec
             2,476      page-faults               #    0.006 M/sec                    ( +-  4.38% )
     1,597,139,052      cycles                    #    3.742 GHz                      ( +-  0.67% )
     4,013,990,056      instructions              #    2.51  insn per cycle           ( +-  0.01% )
       628,035,462      branches                  # 1471.288 M/sec                    ( +-  0.01% )
         2,408,063      branch-misses             #    0.38% of all branches          ( +-  0.13% )

       0.427287921 seconds time elapsed                                          ( +-  0.86% )

Change-Id: I2522f960ee5413b54c9936721eef5ef200586bc9
Reviewed-on: http://gerrit.cloudera.org:8080/8444
Reviewed-by: Todd Lipcon <to...@apache.org>
Tested-by: Todd Lipcon <to...@apache.org>


Project: http://git-wip-us.apache.org/repos/asf/kudu/repo
Commit: http://git-wip-us.apache.org/repos/asf/kudu/commit/db3894f6
Tree: http://git-wip-us.apache.org/repos/asf/kudu/tree/db3894f6
Diff: http://git-wip-us.apache.org/repos/asf/kudu/diff/db3894f6

Branch: refs/heads/master
Commit: db3894f6fa6a96da1118341d2ee40c71f863e570
Parents: 55dcdd0
Author: Todd Lipcon <to...@apache.org>
Authored: Wed Nov 1 11:45:20 2017 -0700
Committer: Todd Lipcon <to...@apache.org>
Committed: Wed Nov 1 23:17:20 2017 +0000

----------------------------------------------------------------------
 src/kudu/tablet/compaction_policy.cc | 25 ++++++++++++++++++++++---
 1 file changed, 22 insertions(+), 3 deletions(-)
----------------------------------------------------------------------


http://git-wip-us.apache.org/repos/asf/kudu/blob/db3894f6/src/kudu/tablet/compaction_policy.cc
----------------------------------------------------------------------
diff --git a/src/kudu/tablet/compaction_policy.cc b/src/kudu/tablet/compaction_policy.cc
index 1e7dbf4..d2695b1 100644
--- a/src/kudu/tablet/compaction_policy.cc
+++ b/src/kudu/tablet/compaction_policy.cc
@@ -50,6 +50,11 @@ DEFINE_double(compaction_approximation_ratio, 1.05f,
               "if it is known to be within 5% of the optimal solution.");
 TAG_FLAG(compaction_approximation_ratio, experimental);
 
+DEFINE_double(compaction_minimum_improvement, 0.01f,
+              "The minimum quality for a compaction to run. If a compaction does not "
+              "improve the average height of DiskRowSets by at least this amount, the "
+              "compaction will be considered ineligible.");
+
 namespace kudu {
 namespace tablet {
 
@@ -301,7 +306,7 @@ void BudgetedCompactionPolicy::RunExact(
     // Here we also build in the approximation ratio as slop: the upper bound doesn't need
     // to just be better than the current solution, but needs to be better by at least
     // the approximation ratio before we bother looking for it.
-    if (upper_bound < best_solution->value * FLAGS_compaction_approximation_ratio) {
+    if (upper_bound <= best_solution->value * FLAGS_compaction_approximation_ratio) {
       continue;
     }
 
@@ -414,6 +419,17 @@ Status BudgetedCompactionPolicy::PickRowSets(const RowSetTree &tree,
   vector<double> best_upper_bounds;
   RunApproximation(asc_min_key, asc_max_key, &best_upper_bounds, &best_solution);
 
+  // If the best solution found above is less than some tiny threshold, we don't
+  // need to bother searching for the exact solution, since it could be at most twice
+  // the approximate solution.
+  if (best_solution.value * 2 <= FLAGS_compaction_minimum_improvement ||
+      *std::max_element(best_upper_bounds.begin(), best_upper_bounds.end()) <=
+      FLAGS_compaction_minimum_improvement) {
+    VLOG(1) << "Approximation algorithm short-circuited exact compaction calculation";
+    *quality = 0;
+    return Status::OK();
+  }
+
   // Pass 2 (precise)
   // ------------------------------------------------------------
   // Now that we've found an approximate solution and upper bounds, do another pass.
@@ -437,8 +453,11 @@ Status BudgetedCompactionPolicy::PickRowSets(const RowSetTree &tree,
 
   *quality = best_solution.value;
 
-  if (best_solution.value <= 0) {
-    VLOG(1) << "Best compaction available makes things worse. Not compacting.";
+  if (best_solution.value <= FLAGS_compaction_minimum_improvement) {
+    VLOG(1) << "Best compaction available (" << best_solution.value << " less than "
+            << "minimum quality " << FLAGS_compaction_minimum_improvement
+            << ": not compacting.";
+    *quality = 0;
     return Status::OK();
   }
 


[3/4] kudu git commit: compaction_policy: avoid a division in approximation algorithm

Posted by to...@apache.org.
compaction_policy: avoid a division in approximation algorithm

This does some simple mathematical substitution to avoid an unnecessary
division instruction in the approximation algorithm in the compaction
policy. This provided a ~5% speedup:

Before:

 Performance counter stats for 'build/latest/bin/compaction_policy-test --gtest_filter=*TinyOver*' (10 runs):

        426.861117      task-clock (msec)         #    0.999 CPUs utilized            ( +-  0.87% )
                 2      context-switches          #    0.004 K/sec                    ( +- 23.13% )
                 0      cpu-migrations            #    0.000 K/sec
             2,476      page-faults               #    0.006 M/sec                    ( +-  4.38% )
     1,597,139,052      cycles                    #    3.742 GHz                      ( +-  0.67% )
     4,013,990,056      instructions              #    2.51  insn per cycle           ( +-  0.01% )
       628,035,462      branches                  # 1471.288 M/sec                    ( +-  0.01% )
         2,408,063      branch-misses             #    0.38% of all branches          ( +-  0.13% )

       0.427287921 seconds time elapsed                                          ( +-  0.86% )

After:

 Performance counter stats for 'build/latest/bin/compaction_policy-test --gtest_filter=*TinyOver*' (10 runs):

        404.664720      task-clock (msec)         #    0.999 CPUs utilized            ( +-  0.93% )
                 1      context-switches          #    0.003 K/sec                    ( +- 28.21% )
                 0      cpu-migrations            #    0.000 K/sec
             2,531      page-faults               #    0.006 M/sec                    ( +-  3.54% )
     1,508,535,824      cycles                    #    3.728 GHz                      ( +-  0.22% )
     3,916,607,007      instructions              #    2.60  insn per cycle           ( +-  0.01% )
       628,048,996      branches                  # 1552.023 M/sec                    ( +-  0.01% )
         2,380,872      branch-misses             #    0.38% of all branches          ( +-  0.08% )

       0.404947434 seconds time elapsed                                          ( +-  0.94% )

Change-Id: I018a81987744c35ff672765ac9e212fd3654638d
Reviewed-on: http://gerrit.cloudera.org:8080/8445
Tested-by: Todd Lipcon <to...@apache.org>
Reviewed-by: Todd Lipcon <to...@apache.org>


Project: http://git-wip-us.apache.org/repos/asf/kudu/repo
Commit: http://git-wip-us.apache.org/repos/asf/kudu/commit/810b9603
Tree: http://git-wip-us.apache.org/repos/asf/kudu/tree/810b9603
Diff: http://git-wip-us.apache.org/repos/asf/kudu/diff/810b9603

Branch: refs/heads/master
Commit: 810b9603a0b36778ee99862bc653ee59c53d1eda
Parents: db3894f
Author: Todd Lipcon <to...@apache.org>
Authored: Wed Nov 1 11:46:39 2017 -0700
Committer: Todd Lipcon <to...@apache.org>
Committed: Wed Nov 1 23:18:29 2017 +0000

----------------------------------------------------------------------
 src/kudu/tablet/compaction_policy.cc | 16 +++++++++++++---
 1 file changed, 13 insertions(+), 3 deletions(-)
----------------------------------------------------------------------


http://git-wip-us.apache.org/repos/asf/kudu/blob/810b9603/src/kudu/tablet/compaction_policy.cc
----------------------------------------------------------------------
diff --git a/src/kudu/tablet/compaction_policy.cc b/src/kudu/tablet/compaction_policy.cc
index d2695b1..711a9b8 100644
--- a/src/kudu/tablet/compaction_policy.cc
+++ b/src/kudu/tablet/compaction_policy.cc
@@ -202,9 +202,19 @@ class BoundCalculator {
     // This is a 2-approximation (i.e. no worse than 1/2 of the best solution).
     // See https://courses.engr.illinois.edu/cs598csc/sp2009/lectures/lecture_4.pdf
     double lower_bound = std::max(total_value_ - top.width(), top.width());
-    double fraction_of_top_to_remove = static_cast<double>(excess_weight) / top.size_mb();
-    DCHECK_GT(fraction_of_top_to_remove, 0);
-    double upper_bound = total_value_ - fraction_of_top_to_remove * top.width();
+
+    // An upper bound for the integer problem is the solution to the fractional problem:
+    // in the fractional problem we can add just a portion of the top element. The
+    // portion to remove is determined by the amount of excess weight:
+    //
+    //   fraction_to_remove = excess_weight / top.size_mb();
+    //   portion_to_remove = fraction_to_remove * top.width()
+    //
+    // To avoid the division, we can just use the fact that density = width/size:
+    double portion_of_top_to_remove = static_cast<double>(excess_weight) * top.density();
+    DCHECK_GT(portion_of_top_to_remove, 0);
+    double upper_bound = total_value_ - portion_of_top_to_remove;
+
     return {lower_bound, upper_bound};
   }
 


[4/4] kudu git commit: compaction_policy: out-of-line inessential fields in RowSetInfo

Posted by to...@apache.org.
compaction_policy: out-of-line inessential fields in RowSetInfo

Based on analysis using toplev.py from pmu-tools[1] I found that the
compaction algorithm was memory-bandwidth bound for the benchmarks in
compaction_policy-test.

The core algorithms of the compaction policy only access a subset of
the fields in the object, meaning that some fields are accessed far
more frequently than others. This can also be illustrated by building
with -fsanitize=cache-efficiency-frag which generates the following
report for the RowSetInfo struct:

==8130==   # 0: offset = 0,	 size = 8,	 count = 20000,	 type = %"class.kudu::tablet::RowSet"*
==8130==   # 1: offset = 8,	 size = 4,	 count = 39998,	 type = i32
==8130==   # 2: offset = 12,	 size = 4,	 count = 107698980,	 type = i32
==8130==   # 3: offset = 16,	 size = 1,	 count = 39998,	 type = i8
==8130==   # 4: offset = 24,	 size = 32,	 count = 210001,	 type = %"class.std::__cxx11::basic_string" = type { %"struct.std::__cxx11::basic_string<char, std::char_traits<char>, std::allocator<char> >::_Alloc_hider", i64, %union.anon }
==8130==   # 5: offset = 56,	 size = 32,	 count = 210001,	 type = %"class.std::__cxx11::basic_string" = type { %"struct.std::__cxx11::basic_string<char, std::char_traits<char>, std::allocator<char> >::_Alloc_hider", i64, %union.anon }
==8130==   # 6: offset = 88,	 size = 8,	 count = 300940510,	 type = double
==8130==   # 7: offset = 96,	 size = 8,	 count = 200930507,	 type = double
==8130==   # 8: offset = 104,	 size = 8,	 count = 89700226,	 type = double

Here we can see that the second i32 (size_mb) as well as the three
doubles (cdf_min, cdf_max, and density) are accessed orders of
magnitude more than the other fields.

An easy fix for this is to out-of-line the other fields into an ancillary
struct elsewhere on the heap, and store just a pointer to the struct.
This ensures that the frequently-accessed fields fit into a smaller
memory footprint and thus involve far fewer memory accesses.

I benchmarked using both the 'TinyOverlap' case and the 'Ycsb' case,
measuring CPU cache misses at each level along with total runtime.

TinyOverlap case
------------------

Before:
 Performance counter stats for 'build/latest/bin/compaction_policy-test --gtest_filter=*TinyOver*' (10 runs):

        55,773,441      mem_load_retired.l1_miss                                      ( +-  0.91% )  (66.20%)
     1,200,071,033      mem_load_retired.l1_hit                                       ( +-  0.19% )  (66.51%)
        44,324,227      mem_load_retired.l2_miss                                      ( +-  1.21% )  (67.02%)
        11,525,953      mem_load_retired.l2_hit                                       ( +-  3.75% )  (67.34%)
            42,298      mem_load_retired.l3_miss                                      ( +-  8.56% )  (67.07%)
        44,461,423      mem_load_retired.l3_hit                                       ( +-  1.16% )  (66.44%)

       0.399781701 seconds time elapsed                                          ( +-  0.84% )
After:
 Performance counter stats for 'build/latest/bin/compaction_policy-test --gtest_filter=*TinyOver*' (10 runs):

        24,864,656      mem_load_retired.l1_miss                                      ( +-  1.37% )  (66.51%)
     1,261,166,288      mem_load_retired.l1_hit                                       ( +-  0.13% )  (66.73%)
         5,694,166      mem_load_retired.l2_miss                                      ( +-  4.37% )  (66.75%)
        18,221,204      mem_load_retired.l2_hit                                       ( +-  1.13% )  (66.97%)
            28,574      mem_load_retired.l3_miss                                      ( +- 16.39% )  (67.10%)
         5,829,783      mem_load_retired.l3_hit                                       ( +-  5.19% )  (66.63%)

       0.360860837 seconds time elapsed                                          ( +-  0.35% )

Summary of improvements:
  - ~10% improvement in wall time
  - L1 cache: 45% reduction in misses
  - L2 cache: 93% reduction in misses
  - L3 cache: 68% reduction in misses

YCSB test case
---------------

Before:
 Performance counter stats for 'build/latest/bin/compaction_policy-test --gtest_filter=*Ycsb*' (10 runs):

        97,654,120      mem_load_retired.l1_miss                                      ( +-  1.13% )  (66.41%)
     2,205,803,278      mem_load_retired.l1_hit                                       ( +-  0.13% )  (66.57%)
        80,632,313      mem_load_retired.l2_miss                                      ( +-  1.68% )  (66.73%)
        16,742,677      mem_load_retired.l2_hit                                       ( +-  3.77% )  (66.99%)
            60,874      mem_load_retired.l3_miss                                      ( +-  5.64% )  (67.02%)
        82,209,502      mem_load_retired.l3_hit                                       ( +-  1.08% )  (66.61%)

       0.747246686 seconds time elapsed                                          ( +-  0.49% )

After:
 Performance counter stats for 'build/latest/bin/compaction_policy-test --gtest_filter=*Ycsb*' (10 runs):

        39,568,838      mem_load_retired.l1_miss                                      ( +-  0.94% )  (66.49%)
     2,328,627,974      mem_load_retired.l1_hit                                       ( +-  0.12% )  (66.67%)
         6,673,404      mem_load_retired.l2_miss                                      ( +-  3.58% )  (66.76%)
        31,882,992      mem_load_retired.l2_hit                                       ( +-  1.11% )  (66.95%)
            59,963      mem_load_retired.l3_miss                                      ( +- 10.28% )  (66.95%)
         6,378,458      mem_load_retired.l3_hit                                       ( +-  3.19% )  (66.58%)

       0.676610184 seconds time elapsed                                          ( +-  0.44% )

Summary:
  - ~10% improvement in wall time
  - L1 cache: 59% reduction in misses
  - L2 cache: 92% reduction in misses
  - L3 cache: 1% reduction (apparently this workload always fit well
    in L3)

As this is the third in a set of patches for optimizations that were
concentrating on the "TinyOverlap" test case, I also verified
before/after of the "YCSB" compaction test case since the beginning of
series.  This also showed about a 14% improvement:

ycsb at start:
 Performance counter stats for 'build/latest/bin/compaction_policy-test --gtest_filter=*Ycsb*' (10 runs):

        795.924340      task-clock (msec)         #    0.998 CPUs utilized            ( +-  0.53% )
                27      context-switches          #    0.034 K/sec                    ( +- 60.21% )
                 0      cpu-migrations            #    0.000 K/sec                    ( +-100.00% )
             2,672      page-faults               #    0.003 M/sec                    ( +-  1.36% )
     2,998,040,105      cycles                    #    3.767 GHz                      ( +-  0.35% )
     7,457,801,099      instructions              #    2.49  insn per cycle           ( +-  0.00% )
     1,212,318,353      branches                  # 1523.158 M/sec                    ( +-  0.00% )
         9,741,331      branch-misses             #    0.80% of all branches          ( +-  0.03% )

       0.797407974 seconds time elapsed                                          ( +-  0.58% )

ycsb at end:
 Performance counter stats for 'build/latest/bin/compaction_policy-test --gtest_filter=*Ycsb*' (10 runs):

        681.047998      task-clock (msec)         #    0.999 CPUs utilized            ( +-  0.52% )
                 2      context-switches          #    0.003 K/sec                    ( +- 46.55% )
                 0      cpu-migrations            #    0.000 K/sec
             2,474      page-faults               #    0.004 M/sec                    ( +-  1.22% )
     2,581,500,560      cycles                    #    3.790 GHz                      ( +-  0.42% )
     7,267,792,155      instructions              #    2.82  insn per cycle           ( +-  0.00% )
     1,210,494,552      branches                  # 1777.400 M/sec                    ( +-  0.00% )
         9,790,631      branch-misses             #    0.81% of all branches          ( +-  0.02% )

       0.681425636 seconds time elapsed                                          ( +-  0.52% )

[1] https://github.com/andikleen/pmu-tools/wiki/toplev-manual

Change-Id: I148b8c976577cbe0020ed887f3bc4c7a2cb2c3ae
Reviewed-on: http://gerrit.cloudera.org:8080/8446
Tested-by: Kudu Jenkins
Reviewed-by: Adar Dembo <ad...@cloudera.com>


Project: http://git-wip-us.apache.org/repos/asf/kudu/repo
Commit: http://git-wip-us.apache.org/repos/asf/kudu/commit/9dd64e1b
Tree: http://git-wip-us.apache.org/repos/asf/kudu/tree/9dd64e1b
Diff: http://git-wip-us.apache.org/repos/asf/kudu/diff/9dd64e1b

Branch: refs/heads/master
Commit: 9dd64e1b3a3ab1a732fb6e0ababe66858cfbfa86
Parents: 810b960
Author: Todd Lipcon <to...@apache.org>
Authored: Wed Nov 1 12:45:22 2017 -0700
Committer: Todd Lipcon <to...@apache.org>
Committed: Wed Nov 1 23:41:57 2017 +0000

----------------------------------------------------------------------
 src/kudu/tablet/rowset_info.cc | 23 ++++++++++---------
 src/kudu/tablet/rowset_info.h  | 46 ++++++++++++++++++++++---------------
 src/kudu/tablet/rowset_tree.cc |  7 +++++-
 3 files changed, 46 insertions(+), 30 deletions(-)
----------------------------------------------------------------------


http://git-wip-us.apache.org/repos/asf/kudu/blob/9dd64e1b/src/kudu/tablet/rowset_info.cc
----------------------------------------------------------------------
diff --git a/src/kudu/tablet/rowset_info.cc b/src/kudu/tablet/rowset_info.cc
index fbe02a0..4c12780 100644
--- a/src/kudu/tablet/rowset_info.cc
+++ b/src/kudu/tablet/rowset_info.cc
@@ -257,12 +257,13 @@ void RowSetInfo::CollectOrdered(const RowSetTree& tree,
 }
 
 RowSetInfo::RowSetInfo(RowSet* rs, double init_cdf)
-  : rowset_(rs),
-    size_bytes_(rs->OnDiskBaseDataSizeWithRedos()),
-    size_mb_(std::max(implicit_cast<int>(size_bytes_ / 1024 / 1024), kMinSizeMb)),
-    cdf_min_key_(init_cdf),
-    cdf_max_key_(init_cdf) {
-  has_bounds_ = rs->GetBounds(&min_key_, &max_key_).ok();
+    : cdf_min_key_(init_cdf),
+      cdf_max_key_(init_cdf),
+      extra_(new ExtraData()) {
+  extra_->rowset = rs;
+  extra_->size_bytes = rs->OnDiskBaseDataSizeWithRedos();
+  extra_->has_bounds = rs->GetBounds(&extra_->min_key, &extra_->max_key).ok();
+  size_mb_ = std::max(implicit_cast<int>(extra_->size_bytes / 1024 / 1024), kMinSizeMb);
 }
 
 void RowSetInfo::FinalizeCDFVector(vector<RowSetInfo>* vec,
@@ -270,7 +271,7 @@ void RowSetInfo::FinalizeCDFVector(vector<RowSetInfo>* vec,
   if (quot == 0) return;
   for (RowSetInfo& cdf_rs : *vec) {
     CHECK_GT(cdf_rs.size_mb_, 0) << "Expected file size to be at least 1MB "
-                                 << "for RowSet " << cdf_rs.rowset_->ToString()
+                                 << "for RowSet " << cdf_rs.rowset()->ToString()
                                  << ", was " << cdf_rs.size_bytes()
                                  << " bytes.";
     cdf_rs.cdf_min_key_ /= quot;
@@ -282,12 +283,12 @@ void RowSetInfo::FinalizeCDFVector(vector<RowSetInfo>* vec,
 
 string RowSetInfo::ToString() const {
   string ret;
-  ret.append(rowset_->ToString());
+  ret.append(rowset()->ToString());
   StringAppendF(&ret, "(% 3dM) [%.04f, %.04f]", size_mb_,
                 cdf_min_key_, cdf_max_key_);
-  if (has_bounds_) {
-    ret.append(" [").append(KUDU_REDACT(Slice(min_key_).ToDebugString()));
-    ret.append(",").append(KUDU_REDACT(Slice(max_key_).ToDebugString()));
+  if (extra_->has_bounds) {
+    ret.append(" [").append(KUDU_REDACT(Slice(extra_->min_key).ToDebugString()));
+    ret.append(",").append(KUDU_REDACT(Slice(extra_->max_key).ToDebugString()));
     ret.append("]");
   }
   return ret;

http://git-wip-us.apache.org/repos/asf/kudu/blob/9dd64e1b/src/kudu/tablet/rowset_info.h
----------------------------------------------------------------------
diff --git a/src/kudu/tablet/rowset_info.h b/src/kudu/tablet/rowset_info.h
index 96d1147..6cc5588 100644
--- a/src/kudu/tablet/rowset_info.h
+++ b/src/kudu/tablet/rowset_info.h
@@ -17,6 +17,8 @@
 #ifndef KUDU_TABLET_ROWSET_INFO_H_
 #define KUDU_TABLET_ROWSET_INFO_H_
 
+#include "kudu/gutil/ref_counted.h"
+
 #include <string>
 #include <vector>
 
@@ -41,7 +43,7 @@ class RowSetInfo {
                              std::vector<RowSetInfo>* min_key,
                              std::vector<RowSetInfo>* max_key);
 
-  int size_bytes() const { return size_bytes_; }
+  int size_bytes() const { return extra_->size_bytes; }
   int size_mb() const { return size_mb_; }
 
   // Return the value of the CDF at the minimum key of this candidate.
@@ -49,9 +51,9 @@ class RowSetInfo {
   // Return the value of the CDF at the maximum key of this candidate.
   double cdf_max_key() const { return cdf_max_key_; }
 
-  bool has_bounds() const { return has_bounds_; }
-  const std::string& min_key() const { return min_key_; }
-  const std::string& max_key() const { return max_key_; }
+  bool has_bounds() const { return extra_->has_bounds;  }
+  const std::string& min_key() const { return extra_->min_key; }
+  const std::string& max_key() const { return extra_->max_key; }
 
   // Return the "width" of the candidate rowset.
   //
@@ -64,7 +66,7 @@ class RowSetInfo {
 
   double density() const { return density_; }
 
-  RowSet* rowset() const { return rowset_; }
+  RowSet* rowset() const { return extra_->rowset; }
 
   std::string ToString() const;
 
@@ -81,24 +83,32 @@ class RowSetInfo {
   static void FinalizeCDFVector(std::vector<RowSetInfo>* vec,
                                 double quot);
 
-  RowSet* const rowset_;
-
-  // Cached version of rowset_->OnDiskBaseDataSize().
-  const int size_bytes_;
-
   // The size in MB, already clamped so that all rowsets have size at least
   // 1MB. This is cached to avoid the branch during the selection hot path.
-  const int size_mb_;
-
-  // True if the RowSet has known bounds.
-  // MemRowSets in particular do not.
-  bool has_bounds_;
-
-  // The bounds, if known.
-  std::string min_key_, max_key_;
+  int size_mb_;
 
   double cdf_min_key_, cdf_max_key_;
   double density_;
+
+  // We move these out of the RowSetInfo object because the std::strings are relatively
+  // large objects, and we'd like the RowSetInfos to be as small as possible so that
+  // the algorithm can fit mostly in CPU cache. The string bounds themselves are rarely
+  // accessed in the hot part of the algorithm so it's worth out-of-lining them.
+  //
+  // These are ref-counted so that RowSetInfo is copyable.
+  struct ExtraData : public RefCounted<ExtraData> {
+    // Cached version of rowset_->OnDiskBaseDataSize().
+    int size_bytes;
+
+    // True if the RowSet has known bounds.
+    // MemRowSets in particular do not.
+    bool has_bounds;
+    std::string min_key, max_key;
+
+    // The original RowSet that this RowSetInfo was constructed from.
+    RowSet* rowset;
+  };
+  const scoped_refptr<ExtraData> extra_;
 };
 
 } // namespace tablet

http://git-wip-us.apache.org/repos/asf/kudu/blob/9dd64e1b/src/kudu/tablet/rowset_tree.cc
----------------------------------------------------------------------
diff --git a/src/kudu/tablet/rowset_tree.cc b/src/kudu/tablet/rowset_tree.cc
index 073877a..829477f 100644
--- a/src/kudu/tablet/rowset_tree.cc
+++ b/src/kudu/tablet/rowset_tree.cc
@@ -66,9 +66,14 @@ struct QueryStruct {
 
 // Entry for use in the interval tree.
 struct RowSetWithBounds {
-  RowSet *rowset;
   string min_key;
   string max_key;
+
+  // NOTE: the ordering of struct fields here is purposeful: we access
+  // min_key and max_key frequently, so putting them first in the struct
+  // ensures they fill a single 64-byte cache line (each is 32 bytes).
+  // The 'rowset' pointer is accessed comparitively rarely.
+  RowSet *rowset;
 };
 
 // Traits struct for IntervalTree.