(kvrocks) branch unstable updated: Optimize the implementation of IntervalSet intersection (#2300)

[maplefu]

This is an automated email from the ASF dual-hosted git repository.

maplefu pushed a commit to branch unstable
in repository https://gitbox.apache.org/repos/asf/kvrocks.git


The following commit(s) were added to refs/heads/unstable by this push:
     new 1e23484f Optimize the implementation of IntervalSet intersection 
(#2300)
1e23484f is described below

commit 1e23484fbd88a7169859e66f398dd695fdf36128
Author: detached <54363053+13015517...@users.noreply.github.com>
AuthorDate: Sat May 11 15:58:26 2024 +0800

    Optimize the implementation of IntervalSet intersection (#2300)
    
    Co-authored-by: mwish <maplewish...@gmail.com>
    Co-authored-by: Twice <twice.m...@gmail.com>
---
 src/cluster/redis_slot.cc      |  2 --
 src/search/interval.h          | 27 ++++++++++++++++++++++++---
 tests/cppunit/interval_test.cc | 26 +++++++++++++++++++++++---
 3 files changed, 47 insertions(+), 8 deletions(-)

diff --git a/src/cluster/redis_slot.cc b/src/cluster/redis_slot.cc
index 5934fd2d..991b5d86 100644
--- a/src/cluster/redis_slot.cc
+++ b/src/cluster/redis_slot.cc
@@ -20,8 +20,6 @@
 
 #include "redis_slot.h"
 
-#include <stdlib.h>
-
 #include <algorithm>
 #include <cstdlib>
 #include <string>
diff --git a/src/search/interval.h b/src/search/interval.h
index 5ce90a45..efe462b4 100644
--- a/src/search/interval.h
+++ b/src/search/interval.h
@@ -128,11 +128,32 @@ struct IntervalSet {
   }
 
   friend IntervalSet operator&(const IntervalSet &l, const IntervalSet &r) {
-    if (l.IsEmpty() || r.IsEmpty()) {
-      return IntervalSet();
+    IntervalSet result;
+
+    if (l.intervals.empty() || r.intervals.empty()) {
+      return result;
+    }
+
+    auto it_l = l.intervals.begin();
+    auto it_r = r.intervals.begin();
+
+    while (it_l != l.intervals.end() && it_r != r.intervals.end()) {
+      // Find overlap between current intervals
+      double start = std::max(it_l->first, it_r->first);
+      double end = std::min(it_l->second, it_r->second);
+
+      if (start <= end) {
+        result.intervals.emplace_back(start, end);
+      }
+
+      if (it_l->second < it_r->second) {
+        ++it_l;
+      } else {
+        ++it_r;
+      }
     }
 
-    return ~(~l | ~r);
+    return result;
   }
 
   friend IntervalSet operator|(const IntervalSet &l, const IntervalSet &r) {
diff --git a/tests/cppunit/interval_test.cc b/tests/cppunit/interval_test.cc
index 5090c4c8..bffd5d63 100644
--- a/tests/cppunit/interval_test.cc
+++ b/tests/cppunit/interval_test.cc
@@ -48,6 +48,14 @@ TEST(IntervalSet, Simple) {
             (IntervalSet::DataType{{IntervalSet::minf, 1}, {4, 
IntervalSet::inf}}));
   ASSERT_EQ((IntervalSet(NumericCompareExpr::GET, 4) | 
IntervalSet(NumericCompareExpr::NE, 1)).intervals,
             (IntervalSet::DataType{{IntervalSet::minf, 1}, 
{IntervalSet::NextNum(1), IntervalSet::inf}}));
+
+  ASSERT_TRUE((IntervalSet(Interval(1, 2)) & IntervalSet(Interval(3, 
4))).IsEmpty());
+  ASSERT_EQ((IntervalSet(Interval(1, 2)) & IntervalSet(Interval(2, 
4))).intervals, (IntervalSet::DataType{{2, 2}}));
+  ASSERT_EQ((IntervalSet(Interval(1, 3)) & IntervalSet(Interval(2, 
4))).intervals, (IntervalSet::DataType{{2, 3}}));
+  ASSERT_EQ((IntervalSet(Interval(3, 8)) & (IntervalSet(Interval(1, 4)) | 
IntervalSet(Interval(5, 7)))).intervals,
+            (IntervalSet::DataType{{3, 4}, {5, 7}}));
+  ASSERT_EQ((IntervalSet(Interval(3, 8)) & (IntervalSet(Interval(1, 4)) | 
IntervalSet(Interval(9, 11)))).intervals,
+            (IntervalSet::DataType{{3, 4}}));
   ASSERT_EQ((IntervalSet(NumericCompareExpr::GET, 1) & 
IntervalSet(NumericCompareExpr::LT, 4)).intervals,
             (IntervalSet::DataType{{1, 4}}));
   ASSERT_EQ((IntervalSet(NumericCompareExpr::GET, 1) & 
IntervalSet(NumericCompareExpr::NE, 4)).intervals,
@@ -60,9 +68,21 @@ TEST(IntervalSet, Simple) {
             IntervalSet({2, 5}) | IntervalSet({7, 8}));
   ASSERT_EQ(~IntervalSet({2, 8}), IntervalSet({IntervalSet::minf, 2}) | 
IntervalSet({8, IntervalSet::inf}));
 
-  for (auto i = 0; i < 1000; ++i) {
-    auto gen = [] { return static_cast<double>(rand()) / 100; };
-    auto geni = [&gen] { return IntervalSet({gen(), gen()}); };
+  for (auto i = 0; i < 2000; ++i) {
+    auto gen = [] { return static_cast<double>(std::rand()) / 100; };
+    auto geni = [&gen] {
+      auto r = std::rand() % 50;
+      if (r == 0) {
+        return IntervalSet(NumericCompareExpr::GET, gen());
+      } else if (r == 1) {
+        return IntervalSet(NumericCompareExpr::LT, gen());
+      } else if (r == 2) {
+        return IntervalSet(NumericCompareExpr::NE, gen());
+      } else {
+        return IntervalSet({gen(), gen()});
+      }
+    };
+
     auto l = geni(), r = geni();
     for (int j = 0; j < i % 10; ++j) {
       l = l | geni();