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.