kudu-commits mailing list archives

Site index · List index
Message view « Date » · « Thread »
Top « Date » · « Thread »
From t...@apache.org
Subject [3/4] kudu git commit: compaction_policy: avoid a division in approximation algorithm
Date Wed, 01 Nov 2017 23:42:28 GMT
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};
   }
 


Mime
View raw message