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