From 570d8ccab67e230f61f9c79e4eaa6a1159bb6428 Mon Sep 17 00:00:00 2001
From: Carl Worth <cworth@cworth.org>
Date: Mon, 11 Mar 2013 13:22:05 -0700
Subject: [PATCH] Use skiplist-based FastCallSet within trace::CallSet

The FastCallSet supports only ranges step of 1 and freq of
FREQUENCY_ALL, so store any such ranges there, and store all other
ranges in the existing, linear list of CallRange.

For manually entered call sets on the command line, the performance
hit of the linear lookup was not generally a problem. But when taking
the (potentially huge) output of "apitrace trim --print-callset" the
performance hit made things quite painful. This makes things usable
again.
---
 common/trace_callset.cpp      |  1 -
 common/trace_callset.hpp      | 27 +++++++++++++++++++--------
 common/trace_fast_callset.cpp | 12 +++++++++---
 common/trace_fast_callset.hpp |  6 ++++--
 4 files changed, 32 insertions(+), 14 deletions(-)

diff --git a/common/trace_callset.cpp b/common/trace_callset.cpp
index 93d145f..0239028 100644
--- a/common/trace_callset.cpp
+++ b/common/trace_callset.cpp
@@ -34,7 +34,6 @@
 
 #include <trace_callset.hpp>
 
-
 using namespace trace;
 
 
diff --git a/common/trace_callset.hpp b/common/trace_callset.hpp
index a2f8213..35729c4 100644
--- a/common/trace_callset.hpp
+++ b/common/trace_callset.hpp
@@ -52,7 +52,7 @@
 #include <list>
 
 #include "trace_model.hpp"
-
+#include "trace_fast_callset.hpp"
 
 namespace trace {
 
@@ -106,7 +106,11 @@ namespace trace {
         CallRange limits;
 
     public:
-        // TODO: use binary tree to speed up lookups
+        FastCallSet fast_call_set;
+
+        // TODO: use binary tree to speed up lookups, (less important
+        // now that we are using FastCallSet for ranges without step
+        // or freq).
         typedef std::list< CallRange > RangeList;
         RangeList ranges;
 
@@ -119,7 +123,7 @@ namespace trace {
         // Not empty set
         inline bool
         empty() const {
-            return ranges.empty();
+            return fast_call_set.empty() && ranges.empty();
         }
 
         void
@@ -137,12 +141,17 @@ namespace trace {
                         limits.stop = range.stop;
                 }
 
-                RangeList::iterator it = ranges.begin();
-                while (it != ranges.end() && it->start < range.start) {
-                    ++it;
-                }
+                /* Optimize by using fast_call_set whenever possible */
+                if (range.step == 1 && range.freq == FREQUENCY_ALL) {
+                    fast_call_set.add(range.start, range.stop);
+                } else {
+                    RangeList::iterator it = ranges.begin();
+                    while (it != ranges.end() && it->start < range.start) {
+                        ++it;
+                    }
 
-                ranges.insert(it, range);
+                    ranges.insert(it, range);
+                }
             }
         }
 
@@ -151,6 +160,8 @@ namespace trace {
             if (empty()) {
                 return false;
             }
+            if (fast_call_set.contains(callNo))
+                return true;
             RangeList::const_iterator it;
             for (it = ranges.begin(); it != ranges.end() && it->start <= callNo; ++it) {
                 if (it->contains(callNo, callFlags)) {
diff --git a/common/trace_fast_callset.cpp b/common/trace_fast_callset.cpp
index d7c4edc..3b5c570 100644
--- a/common/trace_fast_callset.cpp
+++ b/common/trace_fast_callset.cpp
@@ -47,11 +47,17 @@ FastCallRange::FastCallRange(CallNo first, CallNo last, int level)
 }
 
 bool
-FastCallRange::contains(CallNo call_no)
+FastCallRange::contains(CallNo call_no) const
 {
     return (first <= call_no && last >= call_no);
 }
 
+bool
+FastCallSet::empty(void) const
+{
+    return max_level == 0;
+}
+
 FastCallSet::FastCallSet(): head(0, 0, MAX_LEVEL)
 {
     head.first = std::numeric_limits<CallNo>::max();
@@ -181,9 +187,9 @@ FastCallSet::add(CallNo call_no)
 }
 
 bool
-FastCallSet::contains(CallNo call_no)
+FastCallSet::contains(CallNo call_no) const
 {
-    FastCallRange *node;
+    const FastCallRange *node;
     int i;
 
     node = &head;
diff --git a/common/trace_fast_callset.hpp b/common/trace_fast_callset.hpp
index 22893ab..af20005 100644
--- a/common/trace_fast_callset.hpp
+++ b/common/trace_fast_callset.hpp
@@ -71,7 +71,7 @@ public:
 
     FastCallRange(CallNo first, CallNo last, int level);
 
-    bool contains(CallNo call_no);
+    bool contains(CallNo call_no) const;
 };
 
 class FastCallSet {
@@ -81,11 +81,13 @@ public:
 
     FastCallSet();
 
+    bool empty(void) const;
+
     void add(CallNo first, CallNo last);
 
     void add(CallNo call_no);
 
-    bool contains(CallNo call_no);
+    bool contains(CallNo call_no) const;
 };
 
 } /* namespace trace */
-- 
2.43.0