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 <todd@apache.org>
Reviewed-by: Todd Lipcon <todd@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 <todd@apache.org>
Authored: Wed Nov 1 11:46:39 2017 -0700
Committer: Todd Lipcon <todd@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};
}
|