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   public:
28         //! constructor
TreeStats()29       TreeStats() {reset();}
30 
31         /** \brief Given a root node, compute the stats for a tree
32          * \param impl MOAB instance pointer
33          * \param root_node Root entity set for the tree
34          */
35       ErrorCode compute_stats(Interface *impl, EntityHandle root_node);
36 
37         //! reset traversal counters
38       void reset_trav_stats();
39 
40         //! reset all counters
41       void reset();
42 
43         //! print the contents of this structure
44       void print() const ;
45 
46         //! output all the contents of this structure on a single line
47       void output_all_stats(const bool with_endl = true) const ;
48 
49         //! output just the traversal stats of this structure on a single line
50       void output_trav_stats(const bool with_endl = true) const ;
51 
52         // times
53       double initTime;
54 
55         // tree stats that depend only on structure (not traversal)
56       unsigned int maxDepth;
57       unsigned int numNodes;
58       unsigned int numLeaves;
59       double avgObjPerLeaf;
60       unsigned int minObjPerLeaf;
61       unsigned int maxObjPerLeaf;
62 
63 
64         // traversal statistics
65       unsigned int nodesVisited; // number of tree nodes visited since last reset
66       unsigned int leavesVisited; // number of tree leaves visited since last reset
67       unsigned int numTraversals; // number of tree traversals since last reset
68       unsigned int constructLeafObjectTests; // during construction, number of tests of objects (e.g. elements)
69       unsigned int traversalLeafObjectTests; // during traversals, number of tests of objects (e.g. elements)
70       unsigned int boxElemTests; // during construction, number of calls to GeomUtil::box_elem_overlap (KD tree only)
71 
72   private:
73       ErrorCode traverse(Interface *impl, EntityHandle node, unsigned int &depth);
74 
75     };
76 
compute_stats(Interface * impl,EntityHandle root_node)77     inline ErrorCode TreeStats::compute_stats(Interface *impl, EntityHandle root_node)
78     {
79       maxDepth = 0;
80       numNodes = 0;
81       numLeaves = 0;
82       avgObjPerLeaf = 0.0;
83       minObjPerLeaf = 0;
84       maxObjPerLeaf = 0;
85 
86       ErrorCode rval = traverse(impl, root_node, maxDepth);
87       avgObjPerLeaf = (avgObjPerLeaf > 0 ? avgObjPerLeaf/(double)numLeaves : 0.0);
88       return rval;
89     }
90 
traverse(Interface * impl,EntityHandle node,unsigned int & depth)91     inline ErrorCode TreeStats::traverse(Interface *impl, EntityHandle node, unsigned int &depth)
92     {
93       depth++;
94       numNodes++;
95       std::vector<EntityHandle> children;
96       children.reserve(2);
97       ErrorCode rval = impl->get_child_meshsets(node, children);
98       if (MB_SUCCESS != rval) return rval;
99       if (children.empty()) {
100         numLeaves++;
101         rval = impl->get_entities_by_handle(node, children);
102         if (MB_SUCCESS != rval) return rval;
103         avgObjPerLeaf += children.size();
104         minObjPerLeaf = std::min((unsigned int)children.size(), minObjPerLeaf);
105         maxObjPerLeaf = std::max((unsigned int)children.size(), maxObjPerLeaf);
106         return MB_SUCCESS;
107       }
108       else {
109         unsigned int right_depth = depth, left_depth = depth;
110         rval = traverse(impl, children[0], left_depth);
111         if (MB_SUCCESS != rval) return rval;
112         rval = traverse(impl, children[1], right_depth);
113         if (MB_SUCCESS != rval) return rval;
114         depth = std::max(left_depth, right_depth);
115         return MB_SUCCESS;
116       }
117     }
118 
reset()119     inline void TreeStats::reset()
120     {
121       initTime = 0.0;
122 
123       maxDepth = 0;
124       numNodes = 0;
125       numLeaves = 0;
126       constructLeafObjectTests = 0;
127       boxElemTests = 0;
128       avgObjPerLeaf = 0.0;
129       minObjPerLeaf = 0.0;
130       maxObjPerLeaf = 0.0;
131 
132       reset_trav_stats();
133     }
134 
reset_trav_stats()135     inline void TreeStats::reset_trav_stats()
136     {
137       nodesVisited = 0;
138       leavesVisited = 0;
139       numTraversals = 0;
140       traversalLeafObjectTests = 0;
141     }
142 
print() const143     inline void TreeStats::print() const {
144       std::cout << "Tree initialization time = " << initTime << " seconds" << std::endl;
145 
146       std::cout << "Num nodes         = " << numNodes << std::endl;
147       std::cout << "Num leaves        = " << numLeaves << std::endl;
148       std::cout << "Max depth         = " << maxDepth << std::endl << std::endl;
149 
150       std::cout << "Avg objs per leaf = " << avgObjPerLeaf << std::endl;
151       std::cout << "Min objs per leaf = " << minObjPerLeaf << std::endl;
152       std::cout << "Max objs per leaf = " << maxObjPerLeaf << std::endl;
153 
154       std::cout << "Construction Leaf Object Tests = " << constructLeafObjectTests << std::endl;
155       std::cout << "Box-Element Tests = " << boxElemTests << std::endl;
156 
157       std::cout << "NodesVisited      = " << nodesVisited << std::endl;
158       std::cout << "LeavesVisited     = " << leavesVisited << std::endl;
159       std::cout << "Num Traversals    = " << numTraversals << std::endl;
160       std::cout << "Traversal Leaf Object Tests = " << traversalLeafObjectTests << std::endl;
161     }
162 
output_all_stats(const bool with_endl) const163     inline void TreeStats::output_all_stats(const bool with_endl) const
164     {
165       std::cout << initTime << " " << numNodes << " " << numLeaves << " " << maxDepth << " "
166                 << avgObjPerLeaf << " " << minObjPerLeaf << " " << maxObjPerLeaf << " "
167                 << constructLeafObjectTests << " " << boxElemTests << " "
168                 << nodesVisited << " " << leavesVisited << " " << numTraversals << " " << traversalLeafObjectTests << " ";
169       if (with_endl) std::cout << std::endl;
170     }
171 
output_trav_stats(const bool with_endl) const172     inline void TreeStats::output_trav_stats(const bool with_endl) const
173     {
174       std::cout << nodesVisited << " " << leavesVisited << " " << numTraversals << " " << traversalLeafObjectTests << " ";
175       if (with_endl) std::cout << std::endl;
176     }
177 }
178 
179 
180 
181 
182 
183 #endif
184