From: Carl Worth Date: Mon, 11 Mar 2013 20:05:52 +0000 (-0700) Subject: Rename trim::CallSet to trace::FastCallSet X-Git-Url: https://git.cworth.org/git?p=apitrace;a=commitdiff_plain;h=ec8f5a61f393e75e4c3e3e22f84c773af66810e9 Rename trim::CallSet to trace::FastCallSet This is in preparation for being able to use this code to optimize the common cases in trace::CallSet, (callsets without step or freq). --- diff --git a/CMakeLists.txt b/CMakeLists.txt index 9394282..ac046f5 100644 --- a/CMakeLists.txt +++ b/CMakeLists.txt @@ -299,6 +299,7 @@ endif () add_library (common STATIC common/trace_callset.cpp common/trace_dump.cpp + common/trace_fast_callset.cpp common/trace_file.cpp common/trace_file_read.cpp common/trace_file_write.cpp diff --git a/cli/CMakeLists.txt b/cli/CMakeLists.txt index 3165f7d..689374d 100644 --- a/cli/CMakeLists.txt +++ b/cli/CMakeLists.txt @@ -24,7 +24,6 @@ add_executable (apitrace cli_trim.cpp cli_resources.cpp trace_analyzer.cpp - trim_callset.cpp ) target_link_libraries (apitrace diff --git a/cli/cli_trim.cpp b/cli/cli_trim.cpp index 6694737..342e66b 100644 --- a/cli/cli_trim.cpp +++ b/cli/cli_trim.cpp @@ -203,7 +203,7 @@ trim_trace(const char *filename, struct trim_options *options) trace::ParseBookmark beginning; trace::Parser p; TraceAnalyzer analyzer(options->trim_flags); - trim::CallSet *required; + trace::FastCallSet *required; unsigned frame; int call_range_first, call_range_last; diff --git a/cli/trace_analyzer.cpp b/cli/trace_analyzer.cpp index 80ec15e..f98eaa7 100644 --- a/cli/trace_analyzer.cpp +++ b/cli/trace_analyzer.cpp @@ -760,7 +760,7 @@ TraceAnalyzer::require(trace::Call *call) /* Return a set of all the required calls, (both those calls added * explicitly with require() and those implicitly depended * upon. */ -trim::CallSet * +trace::FastCallSet * TraceAnalyzer::get_required(void) { return &required; diff --git a/cli/trace_analyzer.hpp b/cli/trace_analyzer.hpp index 6e9140a..3e4013b 100644 --- a/cli/trace_analyzer.hpp +++ b/cli/trace_analyzer.hpp @@ -29,7 +29,7 @@ #include #include "trace_callset.hpp" -#include "trim_callset.hpp" +#include "trace_fast_callset.hpp" #include "trace_parser.hpp" typedef unsigned TrimFlags; @@ -59,7 +59,7 @@ private: std::map texture_map; - trim::CallSet required; + trace::FastCallSet required; bool transformFeedbackActive; bool framebufferObjectActive; @@ -110,5 +110,5 @@ public: /* Return a set of all the required calls, (both those calls added * explicitly with require() and those implicitly depended * upon. */ - trim::CallSet *get_required(void); + trace::FastCallSet *get_required(void); }; diff --git a/cli/trim_callset.cpp b/cli/trim_callset.cpp deleted file mode 100644 index 69ed818..0000000 --- a/cli/trim_callset.cpp +++ /dev/null @@ -1,203 +0,0 @@ -/********************************************************************* - * - * Copyright 2006 Keith Packard and Carl Worth - * Copyright 2012 Intel Corporation - * Copyright 2012 VMware, Inc. - * All Rights Reserved. - * - * Permission is hereby granted, free of charge, to any person - * obtaining a copy of this software and associated documentation - * files (the "Software"), to deal in the Software without - * restriction, including without limitation the rights to use, copy, - * modify, merge, publish, distribute, sublicense, and/or sell copies - * of the Software, and to permit persons to whom the Software is - * furnished to do so, subject to the following conditions: - * - * The above copyright notice and this permission notice shall be - * included in all copies or substantial portions of the Software. - * - * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, - * EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF - * MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND - * NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS - * BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN - * ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN - * CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE - * SOFTWARE. - * - *********************************************************************/ - -#include -#include -#include - -#include "trim_callset.hpp" - -using namespace trim; - -#define MAX_LEVEL 16 - -CallRange::CallRange(CallNo first, CallNo last, int level) -{ - this->first = first; - this->last = last; - this->level = level; - - next = new CallRange*[level]; -} - -bool -CallRange::contains(CallNo call_no) -{ - return (first <= call_no && last >= call_no); -} - -CallSet::CallSet(): head(0, 0, MAX_LEVEL) -{ - head.first = std::numeric_limits::max(); - head.last = std::numeric_limits::min(); - - for (int i = 0; i < MAX_LEVEL; i++) - head.next[i] = NULL; - - max_level = 0; -} - -/* - * Generate a random level number, distributed - * so that each level is 1/4 as likely as the one before - * - * Note that level numbers run 1 <= level < MAX_LEVEL - */ -static int -random_level (void) -{ - /* tricky bit -- each bit is '1' 75% of the time */ - long int bits = random() | random(); - int level = 1; - - while (level < MAX_LEVEL) - { - if (bits & 1) - break; - level++; - bits >>= 1; - } - - return level; -} - -void -CallSet::add(CallNo first, CallNo last) -{ - CallRange **update[MAX_LEVEL]; - CallRange *node, *next; - int i, level; - - /* Find node immediately before insertion point. */ - node = &head; - for (i = max_level - 1; i >= 0; i--) { - while (node->next[i] && first > node->next[i]->last) { - node = node->next[i]; - } - update[i] = &node->next[i]; - } - - /* Can we contain first by expanding tail of current range by 1? */ - if (node != &head && node->last == first - 1) { - - node->last = last; - goto MERGE_NODE_WITH_SUBSEQUENT_COVERED_NODES; - - } - - /* Current range could not contain first, look at next. */ - - node = node->next[0]; - - if (node) { - /* Do nothing if new range is already entirely contained. */ - if (node->first <= first && node->last >= last) { - return; - } - - /* If last is already included, we can simply expand - * node->first to fully include the range. */ - if (node->first <= last && node->last >= last) { - node->first = first; - return; - } - - /* This is our candidate node if first is contained */ - if (node->first <= first && node->last >= first) { - node->last = last; - goto MERGE_NODE_WITH_SUBSEQUENT_COVERED_NODES; - } - } - - /* Not possible to expand any existing node, so create a new one. */ - - level = random_level(); - - /* Handle first node of this level. */ - if (level > max_level) { - level = max_level + 1; - update[max_level] = &head.next[max_level]; - max_level = level; - } - - node = new CallRange(first, last, level); - - /* Perform insertion into all lists. */ - for (i = 0; i < level; i++) { - node->next[i] = *update[i]; - *update[i] = node; - } - -MERGE_NODE_WITH_SUBSEQUENT_COVERED_NODES: - next = node->next[0]; - while (next && next->first <= node->last + 1) { - if (next->last > node->last) - node->last = next->last; - - /* Delete node 'next' */ - for (i = 0; i < node->level && i < next->level; i++) { - node->next[i] = next->next[i]; - } - - for (; i < next->level; i++) { - *update[i] = next->next[i]; - } - - delete next; - - next = node->next[0]; - } -} - -void -CallSet::add(CallNo call_no) -{ - this->add(call_no, call_no); -} - -bool -CallSet::contains(CallNo call_no) -{ - CallRange *node; - int i; - - node = &head; - for (i = max_level - 1; i >= 0; i--) { - while (node->next[i] && call_no > node->next[i]->last) { - node = node->next[i]; - } - } - - node = node->next[0]; - - if (node == NULL) - return false; - - return node->contains(call_no); -} diff --git a/cli/trim_callset.hpp b/cli/trim_callset.hpp deleted file mode 100644 index fb2c92a..0000000 --- a/cli/trim_callset.hpp +++ /dev/null @@ -1,97 +0,0 @@ -/********************************************************************* - * - * Copyright 2012 Intel Corporation - * Copyright 2012 VMware, Inc. - * All Rights Reserved. - * - * Permission is hereby granted, free of charge, to any person - * obtaining a copy of this software and associated documentation - * files (the "Software"), to deal in the Software without - * restriction, including without limitation the rights to use, copy, - * modify, merge, publish, distribute, sublicense, and/or sell copies - * of the Software, and to permit persons to whom the Software is - * furnished to do so, subject to the following conditions: - * - * The above copyright notice and this permission notice shall be - * included in all copies or substantial portions of the Software. - * - * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, - * EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF - * MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND - * NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS - * BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN - * ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN - * CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE - * SOFTWARE. - * - *********************************************************************/ - -#ifndef _TRIM_CALLSET_HPP_ -#define _TRIM_CALLSET_HPP_ - -namespace trim { - -/* A set of call numbers. - * - * This is designed as a more efficient replacement for - * std::set which is used heavily within the trim code's - * TraceAnalyzer. This is quite similar to the trace::CallSet with the - * following differences: - * - * Simplifications: - * - * * There is no support here for the 'step' and 'freq' features - * supported by trace::CallSet. - * - * Sophistications: - * - * * This callset is implemented with a skip list for - * (probabilistically) logarithmic lookup times for - * out-of-order lookups. - * - * * This callset optimizes the addition of new calls which are - * within or adjacent to existing ranges, (by either doing - * nothing, expanding the limits of an existing range, or also - * merging two ranges). This keeps the length of the list down - * when succesively adding individual calls that could be - * efficiently expressed with a range. - * - * It would not be impossible to extend this code to support the - * missing features of trace::CallSet, (though the 'step' and 'freq' - * features would prevent some range-extending and merging - * optimizations in some cases). Currently, trace::CallSet is not used - * in any performance-critical areas, so it may not be important to - * provide the performance imrpovements to it. - */ - -typedef unsigned CallNo; - -class CallRange { -public: - CallNo first; - CallNo last; - int level; - CallRange **next; - - CallRange(CallNo first, CallNo last, int level); - - bool contains(CallNo call_no); -}; - -class CallSet { -public: - CallRange head; - int max_level; - - CallSet(); - - void add(CallNo first, CallNo last); - - void add(CallNo call_no); - - bool contains(CallNo call_no); -}; - -} /* namespace trim */ - -#endif /* _TRIM_CALLSET_HPP_ */ diff --git a/common/trace_callset.hpp b/common/trace_callset.hpp index 4a4a52d..a2f8213 100644 --- a/common/trace_callset.hpp +++ b/common/trace_callset.hpp @@ -56,11 +56,6 @@ namespace trace { - - // Should match Call::no - typedef unsigned CallNo; - - // Aliases for call flags enum { FREQUENCY_NONE = 0, diff --git a/common/trace_fast_callset.cpp b/common/trace_fast_callset.cpp new file mode 100644 index 0000000..d7c4edc --- /dev/null +++ b/common/trace_fast_callset.cpp @@ -0,0 +1,202 @@ +/********************************************************************* + * + * Copyright 2006 Keith Packard and Carl Worth + * Copyright 2012 Intel Corporation + * Copyright 2012 VMware, Inc. + * All Rights Reserved. + * + * Permission is hereby granted, free of charge, to any person + * obtaining a copy of this software and associated documentation + * files (the "Software"), to deal in the Software without + * restriction, including without limitation the rights to use, copy, + * modify, merge, publish, distribute, sublicense, and/or sell copies + * of the Software, and to permit persons to whom the Software is + * furnished to do so, subject to the following conditions: + * + * The above copyright notice and this permission notice shall be + * included in all copies or substantial portions of the Software. + * + * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, + * EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF + * MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND + * NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS + * BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN + * ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN + * CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE + * SOFTWARE. + * + *********************************************************************/ + +#include +#include +#include + +#include "trace_fast_callset.hpp" + +using namespace trace; + +#define MAX_LEVEL 16 + +FastCallRange::FastCallRange(CallNo first, CallNo last, int level) +{ + this->first = first; + this->last = last; + this->level = level; + + next = new FastCallRange*[level]; +} + +bool +FastCallRange::contains(CallNo call_no) +{ + return (first <= call_no && last >= call_no); +} + +FastCallSet::FastCallSet(): head(0, 0, MAX_LEVEL) +{ + head.first = std::numeric_limits::max(); + head.last = std::numeric_limits::min(); + + for (int i = 0; i < MAX_LEVEL; i++) + head.next[i] = NULL; + + max_level = 0; +} + +/* + * Generate a random level number, distributed + * so that each level is 1/4 as likely as the one before + * + * Note that level numbers run 1 <= level < MAX_LEVEL + */ +static int +random_level (void) +{ + /* tricky bit -- each bit is '1' 75% of the time */ + long int bits = random() | random(); + int level = 1; + + while (level < MAX_LEVEL) + { + if (bits & 1) + break; + level++; + bits >>= 1; + } + + return level; +} + +void +FastCallSet::add(CallNo first, CallNo last) +{ + FastCallRange **update[MAX_LEVEL]; + FastCallRange *node, *next; + int i, level; + + /* Find node immediately before insertion point. */ + node = &head; + for (i = max_level - 1; i >= 0; i--) { + while (node->next[i] && first > node->next[i]->last) { + node = node->next[i]; + } + update[i] = &node->next[i]; + } + + /* Can we contain first by expanding tail of current range by 1? */ + if (node != &head && node->last == first - 1) { + + node->last = last; + goto MERGE_NODE_WITH_SUBSEQUENT_COVERED_NODES; + + } + + /* Current range could not contain first, look at next. */ + node = node->next[0]; + + if (node) { + /* Do nothing if new range is already entirely contained. */ + if (node->first <= first && node->last >= last) { + return; + } + + /* If last is already included, we can simply expand + * node->first to fully include the range. */ + if (node->first <= last && node->last >= last) { + node->first = first; + return; + } + + /* This is our candidate node if first is contained */ + if (node->first <= first && node->last >= first) { + node->last = last; + goto MERGE_NODE_WITH_SUBSEQUENT_COVERED_NODES; + } + } + + /* Not possible to expand any existing node, so create a new one. */ + + level = random_level(); + + /* Handle first node of this level. */ + if (level > max_level) { + level = max_level + 1; + update[max_level] = &head.next[max_level]; + max_level = level; + } + + node = new FastCallRange(first, last, level); + + /* Perform insertion into all lists. */ + for (i = 0; i < level; i++) { + node->next[i] = *update[i]; + *update[i] = node; + } + +MERGE_NODE_WITH_SUBSEQUENT_COVERED_NODES: + next = node->next[0]; + while (next && next->first <= node->last + 1) { + if (next->last > node->last) + node->last = next->last; + + /* Delete node 'next' */ + for (i = 0; i < node->level && i < next->level; i++) { + node->next[i] = next->next[i]; + } + + for (; i < next->level; i++) { + *update[i] = next->next[i]; + } + + delete next; + + next = node->next[0]; + } +} + +void +FastCallSet::add(CallNo call_no) +{ + this->add(call_no, call_no); +} + +bool +FastCallSet::contains(CallNo call_no) +{ + FastCallRange *node; + int i; + + node = &head; + for (i = max_level - 1; i >= 0; i--) { + while (node->next[i] && call_no > node->next[i]->last) { + node = node->next[i]; + } + } + + node = node->next[0]; + + if (node == NULL) + return false; + + return node->contains(call_no); +} diff --git a/common/trace_fast_callset.hpp b/common/trace_fast_callset.hpp new file mode 100644 index 0000000..22893ab --- /dev/null +++ b/common/trace_fast_callset.hpp @@ -0,0 +1,93 @@ +/********************************************************************* + * + * Copyright 2012 Intel Corporation + * Copyright 2012 VMware, Inc. + * All Rights Reserved. + * + * Permission is hereby granted, free of charge, to any person + * obtaining a copy of this software and associated documentation + * files (the "Software"), to deal in the Software without + * restriction, including without limitation the rights to use, copy, + * modify, merge, publish, distribute, sublicense, and/or sell copies + * of the Software, and to permit persons to whom the Software is + * furnished to do so, subject to the following conditions: + * + * The above copyright notice and this permission notice shall be + * included in all copies or substantial portions of the Software. + * + * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, + * EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF + * MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND + * NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS + * BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN + * ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN + * CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE + * SOFTWARE. + * + *********************************************************************/ + +#ifndef _TRACE_FAST_CALLSET_HPP_ +#define _TRACE_FAST_CALLSET_HPP_ + +#include "trace_model.hpp" + +namespace trace { + +/* A set of call numbers. + * + * This was originally designed as a more efficient replacement for + * std::set which was used heavily within the trim code's + * TraceAnalyzer. This is quite similar to the trace::CallSet with the + * following differences: + * + * Simplifications: + * + * * There is no support here for the 'step' and 'freq' features + * supported by trace::CallSet. + * + * Sophistications: + * + * * This callset is implemented with a skip list for + * (probabilistically) logarithmic lookup times for + * out-of-order lookups. + * + * * This callset optimizes the addition of new calls which are + * within or adjacent to existing ranges, (by either doing + * nothing, expanding the limits of an existing range, or also + * merging two or more ranges). + * + * It would not be impossible to extend this code to support the + * missing features of trace::CallSet, (though the 'step' and 'freq' + * features would prevent some range-extending and merging + * optimizations in some cases). + */ + +class FastCallRange { +public: + CallNo first; + CallNo last; + int level; + FastCallRange **next; + + FastCallRange(CallNo first, CallNo last, int level); + + bool contains(CallNo call_no); +}; + +class FastCallSet { +public: + FastCallRange head; + int max_level; + + FastCallSet(); + + void add(CallNo first, CallNo last); + + void add(CallNo call_no); + + bool contains(CallNo call_no); +}; + +} /* namespace trace */ + +#endif /* _TRACE_FAST_CALLSET_HPP_ */ diff --git a/common/trace_model.hpp b/common/trace_model.hpp index 9558225..9336321 100644 --- a/common/trace_model.hpp +++ b/common/trace_model.hpp @@ -41,6 +41,10 @@ namespace trace { +// Should match Call::no +typedef unsigned CallNo; + + typedef unsigned Id;