From 5adfc653dc201ec4faa60a5f78431ab68f0f4e19 Mon Sep 17 00:00:00 2001 From: Zac Medico Date: Sun, 27 Aug 2017 05:25:01 -0700 Subject: [PATCH] interval_set: optimize intersect_of for identical spans Optimize comparisons for identical spans of intervals. When this patch is combined with the previous map insert optimization, a benchmark using 400000 identical intervals shows a 7 times performance improvement in comparison to without the patches. Signed-off-by: Zac Medico (cherry picked from commit b6a035666c2765f8895ee9991348dbc025613ed7) --- src/include/interval_set.h | 11 +++++++++++ 1 file changed, 11 insertions(+) diff --git a/src/include/interval_set.h b/src/include/interval_set.h index 6a7dcc6d12734..d35a11f57c12c 100644 --- a/src/include/interval_set.h +++ b/src/include/interval_set.h @@ -455,6 +455,17 @@ class interval_set { { pa++; continue; } if (pb->first + pb->second <= pa->first) { pb++; continue; } + + if (*pa == *pb) { + do { + mi = m.insert(mi, *pa); + _size += pa->second; + ++pa; + ++pb; + } while (pa != a.m.end() && pb != b.m.end() && *pa == *pb); + continue; + } + T start = MAX(pa->first, pb->first); T en = MIN(pa->first+pa->second, pb->first+pb->second); assert(en > start); -- 2.39.5