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.

diff --git a/common/trace_callset.cpp b/common/trace_callset.cpp
index 93d145fa3a2b0f881794786d3aa23e7db047fbb9..02390283a96180d9b7d594c4654593cc33743878 100644 (file)
--- 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 a2f82134c558972eca41c090d660f4470a8105f1..35729c4cc0f66d81a1534048d5d2f0d00bc5354f 100644 (file)
--- 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 d7c4edc15d5e4e171a44ee6e38e4f2fc6d1f5b56..3b5c570b088b4eac9c6d38ec0f630050242f92f4 100644 (file)
--- 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 22893abcdc75cb67c04a534f0674370f3141a674..af20005ecd57fe1f427fce5618b0248d445fbcbc 100644 (file)
--- 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 */