From 5c3775815a433a028618b239f5a4bebacff3dc4b Mon Sep 17 00:00:00 2001 From: Zac Medico Date: Mon, 25 Sep 2017 23:13:57 -0700 Subject: [PATCH] inverval_set: optimize subset_of with sequential search Optimize subset_of to use sequential search when it performs better than the lower_bound method, for set size ratios smaller than 10. This is analogous to intersection_of behavior since commit 825470fcf919. The subset_of method can be used in some cases as a less-expensive alternative to the intersection_of method, since subset_of can return early if any element of the smaller set is not contained in the larger set, and intersection_of has the added burden of storing the intersecting elements. Signed-off-by: Zac Medico --- src/include/interval_set.h | 47 ++++++++++++++++++++++++++++ src/test/common/test_interval_set.cc | 31 ++++++++++++++++++ 2 files changed, 78 insertions(+) diff --git a/src/include/interval_set.h b/src/include/interval_set.h index a8446ad080880..67b7ac2e53e3b 100644 --- a/src/include/interval_set.h +++ b/src/include/interval_set.h @@ -286,6 +286,38 @@ class interval_set { } } } + + bool subset_size_sym(const interval_set &b) const { + auto pa = m.cbegin(), pb = b.m.cbegin(); + const auto a_end = m.cend(), b_end = b.m.cend(); + + while (pa != a_end && pb != b_end) { + while (pb->first + pb->second <= pa->first) { + ++pb; + if (pb == b_end) + return false; + } + + if (*pa == *pb) { + do { + ++pa; + ++pb; + } while (pa != a_end && pb != b_end && *pa == *pb); + continue; + } + + // interval begins before other + if (pa->first < pb->first) + return false; + // interval is longer than other + if (pa->first + pa->second > pb->first + pb->second) + return false; + + ++pa; + } + + return pa == a_end; + } public: bool operator==(const interval_set& other) const { @@ -606,6 +638,21 @@ class interval_set { } bool subset_of(const interval_set &big) const { + if (!size()) + return true; + if (size() > big.size()) + return false; + if (range_end() > big.range_end()) + return false; + + /* + * Use the lower_bound algorithm for larger size ratios + * where it performs better, but not for smaller size + * ratios where sequential search performs better. + */ + if (big.size() / size() < 10) + return subset_size_sym(big); + for (typename std::map::const_iterator i = m.begin(); i != m.end(); i++) diff --git a/src/test/common/test_interval_set.cc b/src/test/common/test_interval_set.cc index 66a79a6e4945a..f44f35e316fa2 100644 --- a/src/test/common/test_interval_set.cc +++ b/src/test/common/test_interval_set.cc @@ -526,6 +526,37 @@ TYPED_TEST(IntervalSetTest, subset_of) { iset1.insert( 24, 1); ASSERT_FALSE(iset1.subset_of(iset2)); + + iset2.insert( 24, 1); + ASSERT_TRUE(iset1.subset_of(iset2)); + + iset1.insert( 30, 5); + ASSERT_FALSE(iset1.subset_of(iset2)); + + iset2.insert( 30, 5); + ASSERT_TRUE(iset1.subset_of(iset2)); + + iset2.erase( 30, 1); + ASSERT_FALSE(iset1.subset_of(iset2)); + + iset1.erase( 30, 1); + ASSERT_TRUE(iset1.subset_of(iset2)); + + iset2.erase( 34, 1); + ASSERT_FALSE(iset1.subset_of(iset2)); + + iset1.erase( 34, 1); + ASSERT_TRUE(iset1.subset_of(iset2)); + + iset1.insert( 40, 5); + ASSERT_FALSE(iset1.subset_of(iset2)); + + iset2.insert( 39, 7); + ASSERT_TRUE(iset1.subset_of(iset2)); + + iset1.insert( 50, 5); + iset2.insert( 55, 2); + ASSERT_FALSE(iset1.subset_of(iset2)); } TYPED_TEST(IntervalSetTest, span_of) { -- 2.39.5