Branch data Line data Source code
1 : : /**\file TreeStats.hpp
2 : : * \class moab::TreeStats
3 : : * \brief Traversal statistics accumulating and reporting
4 : : *
5 : : * Class to accumulate statistics on traversal performance. This structure contains the
6 : : * count of nodes visited at each level in a tree, and the count of traversals that ended
7 : : * at each level. One TrvStats structure can be used with multiple trees or multiple
8 : : * queries, or used on only a single tree or a single query.
9 : : *
10 : : * Note that these traversal statistics are not related to the stats() query below,
11 : : * which calculates static information about a tree. These statistics relate
12 : : * to a tree's dynamic behavior on particular operations.
13 : : */
14 : :
15 : : #ifndef TREESTATS_HPP
16 : : #define TREESTATS_HPP
17 : :
18 : : #include "moab/Interface.hpp"
19 : :
20 : : #include <vector>
21 : : #include <iostream>
22 : : #include <string>
23 : :
24 : : namespace moab
25 : : {
26 : : class TreeStats
27 : : {
28 : : public:
29 : : //! constructor
30 : 24 : TreeStats()
31 : : {
32 : 24 : reset();
33 : 24 : }
34 : :
35 : : /** \brief Given a root node, compute the stats for a tree
36 : : * \param impl MOAB instance pointer
37 : : * \param root_node Root entity set for the tree
38 : : */
39 : : ErrorCode compute_stats( Interface* impl, EntityHandle root_node );
40 : :
41 : : //! reset traversal counters
42 : : void reset_trav_stats();
43 : :
44 : : //! reset all counters
45 : : void reset();
46 : :
47 : : //! print the contents of this structure
48 : : void print() const;
49 : :
50 : : //! output all the contents of this structure on a single line
51 : : void output_all_stats( const bool with_endl = true ) const;
52 : :
53 : : //! output just the traversal stats of this structure on a single line
54 : : void output_trav_stats( const bool with_endl = true ) const;
55 : :
56 : : // times
57 : : double initTime;
58 : :
59 : : // tree stats that depend only on structure (not traversal)
60 : : unsigned int maxDepth;
61 : : unsigned int numNodes;
62 : : unsigned int numLeaves;
63 : : double avgObjPerLeaf;
64 : : unsigned int minObjPerLeaf;
65 : : unsigned int maxObjPerLeaf;
66 : :
67 : : // traversal statistics
68 : : unsigned int nodesVisited; // number of tree nodes visited since last reset
69 : : unsigned int leavesVisited; // number of tree leaves visited since last reset
70 : : unsigned int numTraversals; // number of tree traversals since last reset
71 : : unsigned int constructLeafObjectTests; // during construction, number of tests of objects (e.g.
72 : : // elements)
73 : : unsigned int traversalLeafObjectTests; // during traversals, number of tests of objects (e.g. elements)
74 : : unsigned int boxElemTests; // during construction, number of calls to
75 : : // GeomUtil::box_elem_overlap (KD tree only)
76 : :
77 : : private:
78 : : ErrorCode traverse( Interface* impl, EntityHandle node, unsigned int& depth );
79 : : };
80 : :
81 : 17 : inline ErrorCode TreeStats::compute_stats( Interface* impl, EntityHandle root_node )
82 : : {
83 : 17 : maxDepth = 0;
84 : 17 : numNodes = 0;
85 : 17 : numLeaves = 0;
86 : 17 : avgObjPerLeaf = 0.0;
87 : 17 : minObjPerLeaf = 0;
88 : 17 : maxObjPerLeaf = 0;
89 : :
90 : 17 : ErrorCode rval = traverse( impl, root_node, maxDepth );
91 [ + - ]: 17 : avgObjPerLeaf = ( avgObjPerLeaf > 0 ? avgObjPerLeaf / (double)numLeaves : 0.0 );
92 : 17 : return rval;
93 : : }
94 : :
95 : 7051 : inline ErrorCode TreeStats::traverse( Interface* impl, EntityHandle node, unsigned int& depth )
96 : : {
97 : 7051 : depth++;
98 : 7051 : numNodes++;
99 [ + - ]: 7051 : std::vector< EntityHandle > children;
100 [ + - ]: 7051 : children.reserve( 2 );
101 [ + - ]: 7051 : ErrorCode rval = impl->get_child_meshsets( node, children );
102 [ - + ]: 7051 : if( MB_SUCCESS != rval ) return rval;
103 [ + + ]: 7051 : if( children.empty() )
104 : : {
105 : 3534 : numLeaves++;
106 [ + - ]: 3534 : rval = impl->get_entities_by_handle( node, children );
107 [ - + ]: 3534 : if( MB_SUCCESS != rval ) return rval;
108 : 3534 : avgObjPerLeaf += children.size();
109 [ + - ]: 3534 : minObjPerLeaf = std::min( (unsigned int)children.size(), minObjPerLeaf );
110 [ + - ]: 3534 : maxObjPerLeaf = std::max( (unsigned int)children.size(), maxObjPerLeaf );
111 : 3534 : return MB_SUCCESS;
112 : : }
113 : : else
114 : : {
115 : 3517 : unsigned int right_depth = depth, left_depth = depth;
116 [ + - ][ + - ]: 3517 : rval = traverse( impl, children[0], left_depth );
117 [ - + ]: 3517 : if( MB_SUCCESS != rval ) return rval;
118 [ + - ][ + - ]: 3517 : rval = traverse( impl, children[1], right_depth );
119 [ - + ]: 3517 : if( MB_SUCCESS != rval ) return rval;
120 [ + - ]: 3517 : depth = std::max( left_depth, right_depth );
121 : 3517 : return MB_SUCCESS;
122 : 7051 : }
123 : : }
124 : :
125 : 25 : inline void TreeStats::reset()
126 : : {
127 : 25 : initTime = 0.0;
128 : :
129 : 25 : maxDepth = 0;
130 : 25 : numNodes = 0;
131 : 25 : numLeaves = 0;
132 : 25 : constructLeafObjectTests = 0;
133 : 25 : boxElemTests = 0;
134 : 25 : avgObjPerLeaf = 0.0;
135 : 25 : minObjPerLeaf = 0.0;
136 : 25 : maxObjPerLeaf = 0.0;
137 : :
138 : 25 : reset_trav_stats();
139 : 25 : }
140 : :
141 : 25 : inline void TreeStats::reset_trav_stats()
142 : : {
143 : 25 : nodesVisited = 0;
144 : 25 : leavesVisited = 0;
145 : 25 : numTraversals = 0;
146 : 25 : traversalLeafObjectTests = 0;
147 : 25 : }
148 : :
149 : : inline void TreeStats::print() const
150 : : {
151 : : std::cout << "Tree initialization time = " << initTime << " seconds" << std::endl;
152 : :
153 : : std::cout << "Num nodes = " << numNodes << std::endl;
154 : : std::cout << "Num leaves = " << numLeaves << std::endl;
155 : : std::cout << "Max depth = " << maxDepth << std::endl << std::endl;
156 : :
157 : : std::cout << "Avg objs per leaf = " << avgObjPerLeaf << std::endl;
158 : : std::cout << "Min objs per leaf = " << minObjPerLeaf << std::endl;
159 : : std::cout << "Max objs per leaf = " << maxObjPerLeaf << std::endl;
160 : :
161 : : std::cout << "Construction Leaf Object Tests = " << constructLeafObjectTests << std::endl;
162 : : std::cout << "Box-Element Tests = " << boxElemTests << std::endl;
163 : :
164 : : std::cout << "NodesVisited = " << nodesVisited << std::endl;
165 : : std::cout << "LeavesVisited = " << leavesVisited << std::endl;
166 : : std::cout << "Num Traversals = " << numTraversals << std::endl;
167 : : std::cout << "Traversal Leaf Object Tests = " << traversalLeafObjectTests << std::endl;
168 : : }
169 : :
170 : : inline void TreeStats::output_all_stats( const bool with_endl ) const
171 : : {
172 : : std::cout << initTime << " " << numNodes << " " << numLeaves << " " << maxDepth << " " << avgObjPerLeaf << " "
173 : : << minObjPerLeaf << " " << maxObjPerLeaf << " " << constructLeafObjectTests << " " << boxElemTests << " "
174 : : << nodesVisited << " " << leavesVisited << " " << numTraversals << " " << traversalLeafObjectTests << " ";
175 : : if( with_endl ) std::cout << std::endl;
176 : : }
177 : :
178 : 4 : inline void TreeStats::output_trav_stats( const bool with_endl ) const
179 : : {
180 : 4 : std::cout << nodesVisited << " " << leavesVisited << " " << numTraversals << " " << traversalLeafObjectTests << " ";
181 [ + - ]: 4 : if( with_endl ) std::cout << std::endl;
182 : 4 : }
183 : : } // namespace moab
184 : :
185 : : #endif
|
