Return-Path: X-Original-To: archive-asf-public-internal@cust-asf2.ponee.io Delivered-To: archive-asf-public-internal@cust-asf2.ponee.io Received: from cust-asf.ponee.io (cust-asf.ponee.io [163.172.22.183]) by cust-asf2.ponee.io (Postfix) with ESMTP id 932A4200C56 for ; Thu, 30 Mar 2017 21:40:18 +0200 (CEST) Received: by cust-asf.ponee.io (Postfix) id 91ABE160B7E; Thu, 30 Mar 2017 19:40:18 +0000 (UTC) Delivered-To: archive-asf-public@cust-asf.ponee.io Received: from mail.apache.org (hermes.apache.org [140.211.11.3]) by cust-asf.ponee.io (Postfix) with SMTP id B0250160B8B for ; Thu, 30 Mar 2017 21:40:17 +0200 (CEST) Received: (qmail 13745 invoked by uid 500); 30 Mar 2017 19:40:16 -0000 Mailing-List: contact commits-help@kudu.apache.org; run by ezmlm Precedence: bulk List-Help: List-Unsubscribe: List-Post: List-Id: Reply-To: dev@kudu.apache.org Delivered-To: mailing list commits@kudu.apache.org Received: (qmail 13707 invoked by uid 99); 30 Mar 2017 19:40:15 -0000 Received: from git1-us-west.apache.org (HELO git1-us-west.apache.org) (140.211.11.23) by apache.org (qpsmtpd/0.29) with ESMTP; Thu, 30 Mar 2017 19:40:15 +0000 Received: by git1-us-west.apache.org (ASF Mail Server at git1-us-west.apache.org, from userid 33) id 10012E024D; Thu, 30 Mar 2017 19:40:15 +0000 (UTC) Content-Type: text/plain; charset="us-ascii" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit From: todd@apache.org To: commits@kudu.apache.org Date: Thu, 30 Mar 2017 19:40:18 -0000 Message-Id: <322f9522e0e24c2aac1e9232fb13c883@git.apache.org> In-Reply-To: <30b1e7dd69c144e1b2ac37579fe37aaf@git.apache.org> References: <30b1e7dd69c144e1b2ac37579fe37aaf@git.apache.org> X-Mailer: ASF-Git Admin Mailer Subject: [4/5] kudu git commit: interval_tree: improve an O(n) loop to O(lg n) archived-at: Thu, 30 Mar 2017 19:40:18 -0000 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 stalled-cycles-frontend 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 stalled-cycles-frontend 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 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 Authored: Mon Mar 27 18:58:30 2017 -0700 Committer: Todd Lipcon 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 #include +#include "kudu/util/interval_tree.h" + namespace kudu { template @@ -223,13 +225,12 @@ void ITNode::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::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::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.