kudu-commits mailing list archives

Site index · List index
Message view « Date » · « Thread »
Top « Date » · « Thread »
From t...@apache.org
Subject [4/5] kudu git commit: interval_tree: improve an O(n) loop to O(lg n)
Date Thu, 30 Mar 2017 19:40:18 GMT
interval_tree: improve an O(n) loop to O(lg n)

In the interval tree implementation, we were scanning forward through a
sorted list to find the first element for which a comparison predicate
returned false. Since we know that the list is sorted, we can use
std::partition_point instead for a logarithmic search instead of linear.

Before:
  Performance counter stats for 'build/latest/bin/rowset_tree-test --gtest_repeat=10 --gtest_filter=*Perf*':

       4583.429978      task-clock (msec)         #    0.999 CPUs utilized
               133      context-switches          #    0.029 K/sec
                 0      cpu-migrations            #    0.000 K/sec
               693      page-faults               #    0.151 K/sec
    14,480,814,146      cycles                    #    3.159 GHz
   <not supported>      stalled-cycles-frontend
   <not supported>      stalled-cycles-backend
    36,542,995,670      instructions              #    2.52  insns per cycle
     6,044,686,478      branches                  # 1318.813 M/sec
        63,527,970      branch-misses             #    1.05% of all branches

       4.585735270 seconds time elapsed

After:
  Performance counter stats for 'build/latest/bin/rowset_tree-test --gtest_repeat=10 --gtest_filter=*Perf*':

       4044.192209      task-clock (msec)         #    1.000 CPUs utilized
                 5      context-switches          #    0.001 K/sec
                 0      cpu-migrations            #    0.000 K/sec
               509      page-faults               #    0.126 K/sec
    13,329,589,168      cycles                    #    3.296 GHz
   <not supported>      stalled-cycles-frontend
   <not supported>      stalled-cycles-backend
    30,484,446,619      instructions              #    2.29  insns per cycle
     5,094,736,604      branches                  # 1259.766 M/sec
        86,320,621      branch-misses             #    1.69% of all branches

       4.044156458 seconds time elapsed

Overall speeds up around 10%.

Change-Id: Ib8c9463fb901b7bf75d32b00cb528e96c119101e
Reviewed-on: http://gerrit.cloudera.org:8080/6496
Tested-by: Kudu Jenkins
Reviewed-by: David Ribeiro Alves <dralves@apache.org>


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

Branch: refs/heads/master
Commit: f8e88fa0be3bb64c5f05e755e3db55f3ac7cb998
Parents: 4be39fe
Author: Todd Lipcon <todd@apache.org>
Authored: Mon Mar 27 18:58:30 2017 -0700
Committer: Todd Lipcon <todd@apache.org>
Committed: Thu Mar 30 01:20:43 2017 +0000

----------------------------------------------------------------------
 src/kudu/util/interval_tree-inl.h | 64 ++++++++++++++++++----------------
 1 file changed, 33 insertions(+), 31 deletions(-)
----------------------------------------------------------------------


http://git-wip-us.apache.org/repos/asf/kudu/blob/f8e88fa0/src/kudu/util/interval_tree-inl.h
----------------------------------------------------------------------
diff --git a/src/kudu/util/interval_tree-inl.h b/src/kudu/util/interval_tree-inl.h
index 7e88e42..ec65390 100644
--- a/src/kudu/util/interval_tree-inl.h
+++ b/src/kudu/util/interval_tree-inl.h
@@ -20,6 +20,8 @@
 #include <algorithm>
 #include <vector>
 
+#include "kudu/util/interval_tree.h"
+
 namespace kudu {
 
 template<class Traits>
@@ -223,13 +225,12 @@ void ITNode<Traits>::FindContainingPoint(const point_type &query,
 
     // Any intervals which start before the query point and overlap the split point
     // must therefore contain the query point.
-    for (const interval_type &interval : overlapping_by_asc_left_) {
-      if (Traits::compare(Traits::get_left(interval), query) <= 0) {
-        results->push_back(interval);
-      } else {
-        break;
-      }
-    }
+    auto p = std::partition_point(
+        overlapping_by_asc_left_.cbegin(), overlapping_by_asc_left_.cend(),
+        [&](const interval_type& interval) {
+          return Traits::compare(Traits::get_left(interval), query) <= 0;
+        });
+    results->insert(results->end(), overlapping_by_asc_left_.cbegin(), p);
   } else if (cmp > 0) {
     // None of the intervals in left_ may intersect this.
     if (right_ != NULL) {
@@ -238,13 +239,12 @@ void ITNode<Traits>::FindContainingPoint(const point_type &query,
 
     // Any intervals which end after the query point and overlap the split point
     // must therefore contain the query point.
-    for (const interval_type &interval : overlapping_by_desc_right_) {
-      if (Traits::compare(Traits::get_right(interval), query) >= 0) {
-        results->push_back(interval);
-      } else {
-        break;
-      }
-    }
+    auto p = std::partition_point(
+        overlapping_by_desc_right_.cbegin(), overlapping_by_desc_right_.cend(),
+        [&](const interval_type& interval) {
+          return Traits::compare(Traits::get_right(interval), query) >= 0;
+        });
+    results->insert(results->end(), overlapping_by_desc_right_.cbegin(), p);
   } else {
     DCHECK_EQ(cmp, 0);
     // The query is exactly our split point -- in this case we've already got
@@ -265,30 +265,32 @@ void ITNode<Traits>::FindIntersectingInterval(const interval_type
&query,
     }
 
     // Any intervals whose left edge is <= the query interval's right edge
-    // intersect the query interval.
-    for (const interval_type &interval : overlapping_by_asc_left_) {
-      if (Traits::compare(Traits::get_left(interval),Traits::get_right(query)) <= 0) {
-        results->push_back(interval);
-      } else {
-        break;
-      }
-    }
+    // intersect the query interval. 'std::partition_point' returns the first
+    // such interval which does not meet that criterion, so we insert all
+    // up to that point.
+    auto first_greater = std::partition_point(
+        overlapping_by_asc_left_.cbegin(), overlapping_by_asc_left_.cend(),
+        [&](const interval_type& interval) {
+          return Traits::compare(Traits::get_left(interval), Traits::get_right(query)) <=
0;
+        });
+    results->insert(results->end(), overlapping_by_asc_left_.cbegin(), first_greater);
   } else if (Traits::compare(Traits::get_left(query), split_point_) > 0) {
     // The interval is fully right of the split point. So, it may not overlap
-    // with any in 'left_'
+    // with any in 'left_'.
     if (right_ != NULL) {
       right_->FindIntersectingInterval(query, results);
     }
 
     // Any intervals whose right edge is >= the query interval's left edge
-    // intersect the query interval.
-    for (const interval_type &interval : overlapping_by_desc_right_) {
-      if (Traits::compare(Traits::get_right(interval), Traits::get_left(query)) >= 0)
{
-        results->push_back(interval);
-      } else {
-        break;
-      }
-    }
+    // intersect the query interval. 'std::partition_point' returns the first
+    // such interval which does not meet that criterion, so we insert all
+    // up to that point.
+    auto first_lesser = std::partition_point(
+        overlapping_by_desc_right_.cbegin(), overlapping_by_desc_right_.cend(),
+        [&](const interval_type& interval) {
+          return Traits::compare(Traits::get_right(interval), Traits::get_left(query)) >=
0;
+        });
+    results->insert(results->end(), overlapping_by_desc_right_.cbegin(), first_lesser);
   } else {
     // The query interval contains the split point. Therefore all other intervals
     // which also contain the split point are intersecting.


Mime
View raw message