1 /* Copyright 2020 Google LLC. All Rights Reserved.
2
3 Licensed under the Apache License, Version 2.0 (the "License");
4 you may not use this file except in compliance with the License.
5 You may obtain a copy of the License at
6
7 http://www.apache.org/licenses/LICENSE-2.0
8
9 Unless required by applicable law or agreed to in writing, software
10 distributed under the License is distributed on an "AS IS" BASIS,
11 WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
12 See the License for the specific language governing permissions and
13 limitations under the License.
14 ==============================================================================*/
15
16 #ifdef RUY_PROFILER
17
18 #include "ruy/profiler/treeview.h"
19
20 #include <algorithm>
21 #include <cassert>
22 #include <cstdio>
23 #include <functional>
24 #include <memory>
25 #include <vector>
26
27 namespace ruy {
28 namespace profiler {
29
30 namespace {
31
SortNode(TreeView::Node * node)32 void SortNode(TreeView::Node* node) {
33 using NodePtr = std::unique_ptr<TreeView::Node>;
34 std::sort(node->children.begin(), node->children.end(),
35 [](const NodePtr& n1, const NodePtr& n2) {
36 return n1->weight > n2->weight;
37 });
38 for (const auto& child : node->children) {
39 SortNode(child.get());
40 }
41 }
42
43 // Records a stack i.e. a sample in a treeview, by incrementing the weights
44 // of matching existing nodes and/or by creating new nodes as needed,
45 // recursively, below the given node.
AddStack(const detail::Stack & stack,TreeView::Node * node,int level)46 void AddStack(const detail::Stack& stack, TreeView::Node* node, int level) {
47 node->weight++;
48 if (stack.size == level) {
49 return;
50 }
51 TreeView::Node* child_to_add_to = nullptr;
52 for (const auto& child : node->children) {
53 if (child->label == stack.labels[level]) {
54 child_to_add_to = child.get();
55 break;
56 }
57 }
58 if (!child_to_add_to) {
59 child_to_add_to = new TreeView::Node;
60 child_to_add_to->label = stack.labels[level];
61 node->children.emplace_back(child_to_add_to);
62 }
63 AddStack(stack, child_to_add_to, level + 1);
64 }
65
66 // Recursively populates the treeview below the given node with 'other'
67 // entries documenting for each node the difference between its weight and the
68 // sum of its children's weight.
AddOther(TreeView::Node * node)69 void AddOther(TreeView::Node* node) {
70 int top_level_children_weight = 0;
71 for (const auto& child : node->children) {
72 AddOther(child.get());
73 top_level_children_weight += child->weight;
74 }
75 if (top_level_children_weight != 0 &&
76 top_level_children_weight != node->weight) {
77 auto* new_child = new TreeView::Node;
78 new_child->label = Label("[other]");
79 new_child->weight = node->weight - top_level_children_weight;
80 node->children.emplace_back(new_child);
81 }
82 }
83
84 } // namespace
85
Populate(const std::vector<char> & samples_buf_)86 void TreeView::Populate(const std::vector<char>& samples_buf_) {
87 thread_roots_.clear();
88 // Populate the treeview with regular nodes coming from samples.
89 const char* buf_ptr = samples_buf_.data();
90 const char* const buf_ptr_end = buf_ptr + samples_buf_.size();
91 while (buf_ptr < buf_ptr_end) {
92 detail::Stack stack;
93 detail::ReadFromBuffer(buf_ptr, &stack);
94 // Empty stacks should have been dropped during sampling.
95 assert(stack.size > 0);
96 buf_ptr += GetBufferSize(stack);
97 const int id = stack.id;
98 if (!thread_roots_[id]) {
99 thread_roots_[id].reset(new Node);
100 }
101 AddStack(stack, thread_roots_[id].get(), 0);
102 }
103 // Populate the treeview with additional 'other' nodes, sort, and set
104 // root labels.
105 for (const auto& thread_root : thread_roots_) {
106 std::uint32_t id = thread_root.first;
107 Node* root = thread_root.second.get();
108 AddOther(root);
109 SortNode(root);
110 root->label.Set("Thread %x (%d samples)", id, root->weight);
111 }
112 }
113
114 // Recursively prints the treeview below the given node. The 'root' node
115 // argument is only needed to compute weights ratios, with the root ratio
116 // as denominator.
PrintTreeBelow(const TreeView::Node & node,const TreeView::Node & root,int level)117 void PrintTreeBelow(const TreeView::Node& node, const TreeView::Node& root,
118 int level) {
119 if (&node == &root) {
120 printf("%s\n\n", node.label.Formatted().c_str());
121 } else {
122 for (int i = 1; i < level; i++) {
123 printf(" ");
124 }
125 printf("* %.2f%% %s\n", 100.0f * node.weight / root.weight,
126 node.label.Formatted().c_str());
127 }
128 for (const auto& child : node.children) {
129 PrintTreeBelow(*child, root, level + 1);
130 }
131 }
132
Print(const TreeView & treeview)133 void Print(const TreeView& treeview) {
134 printf("\n");
135 printf("Profile (%d threads):\n\n",
136 static_cast<int>(treeview.thread_roots().size()));
137 for (const auto& thread_root : treeview.thread_roots()) {
138 const TreeView::Node& root = *thread_root.second;
139 PrintTreeBelow(root, root, 0);
140 printf("\n");
141 }
142 }
143
DepthOfTreeBelow(const TreeView::Node & node)144 int DepthOfTreeBelow(const TreeView::Node& node) {
145 if (node.children.empty()) {
146 return 0;
147 } else {
148 int max_child_depth = 0;
149 for (const auto& child : node.children) {
150 max_child_depth = std::max(max_child_depth, DepthOfTreeBelow(*child));
151 }
152 return 1 + max_child_depth;
153 }
154 }
155
WeightBelowNodeMatchingFunction(const TreeView::Node & node,const std::function<bool (const Label &)> & match)156 int WeightBelowNodeMatchingFunction(
157 const TreeView::Node& node,
158 const std::function<bool(const Label&)>& match) {
159 int weight = 0;
160 if (match(node.label)) {
161 weight += node.weight;
162 }
163 for (const auto& child : node.children) {
164 weight += WeightBelowNodeMatchingFunction(*child, match);
165 }
166 return weight;
167 }
168
WeightBelowNodeMatchingUnformatted(const TreeView::Node & node,const std::string & format)169 int WeightBelowNodeMatchingUnformatted(const TreeView::Node& node,
170 const std::string& format) {
171 return WeightBelowNodeMatchingFunction(
172 node, [&format](const Label& label) { return label.format() == format; });
173 }
174
WeightBelowNodeMatchingFormatted(const TreeView::Node & node,const std::string & formatted)175 int WeightBelowNodeMatchingFormatted(const TreeView::Node& node,
176 const std::string& formatted) {
177 return WeightBelowNodeMatchingFunction(
178 node, [&formatted](const Label& label) {
179 return label.Formatted() == formatted;
180 });
181 }
182
CollapseNode(const TreeView::Node & node_in,int depth,TreeView::Node * node_out)183 void CollapseNode(const TreeView::Node& node_in, int depth,
184 TreeView::Node* node_out) {
185 node_out->label = node_in.label;
186 node_out->weight = node_in.weight;
187 node_out->children.clear();
188 if (depth > 0) {
189 for (const auto& child_in : node_in.children) {
190 auto* child_out = new TreeView::Node;
191 node_out->children.emplace_back(child_out);
192 CollapseNode(*child_in, depth - 1, child_out);
193 }
194 }
195 }
196
CollapseSubnodesMatchingFunction(const TreeView::Node & node_in,int depth,const std::function<bool (const Label &)> & match,TreeView::Node * node_out)197 void CollapseSubnodesMatchingFunction(
198 const TreeView::Node& node_in, int depth,
199 const std::function<bool(const Label&)>& match, TreeView::Node* node_out) {
200 if (match(node_in.label)) {
201 CollapseNode(node_in, depth, node_out);
202 } else {
203 node_out->label = node_in.label;
204 node_out->weight = node_in.weight;
205 node_out->children.clear();
206
207 for (const auto& child_in : node_in.children) {
208 auto* child_out = new TreeView::Node;
209 node_out->children.emplace_back(child_out);
210 CollapseSubnodesMatchingFunction(*child_in, depth, match, child_out);
211 }
212 }
213 }
214
CollapseNodesMatchingFunction(const TreeView & treeview_in,int depth,const std::function<bool (const Label &)> & match,TreeView * treeview_out)215 void CollapseNodesMatchingFunction(
216 const TreeView& treeview_in, int depth,
217 const std::function<bool(const Label&)>& match, TreeView* treeview_out) {
218 treeview_out->mutable_thread_roots()->clear();
219 for (const auto& thread_root_in : treeview_in.thread_roots()) {
220 std::uint32_t id = thread_root_in.first;
221 const auto& root_in = *thread_root_in.second;
222 auto* root_out = new TreeView::Node;
223 treeview_out->mutable_thread_roots()->emplace(
224 id, std::unique_ptr<TreeView::Node>(root_out));
225 CollapseSubnodesMatchingFunction(root_in, depth, match, root_out);
226 }
227 }
228
CollapseNodesMatchingUnformatted(const TreeView & treeview_in,int depth,const std::string & format,TreeView * treeview_out)229 void CollapseNodesMatchingUnformatted(const TreeView& treeview_in, int depth,
230 const std::string& format,
231 TreeView* treeview_out) {
232 CollapseNodesMatchingFunction(
233 treeview_in, depth,
234 [&format](const Label& label) { return label.format() == format; },
235 treeview_out);
236 }
237
CollapseNodesMatchingFormatted(const TreeView & treeview_in,int depth,const std::string & formatted,TreeView * treeview_out)238 void CollapseNodesMatchingFormatted(const TreeView& treeview_in, int depth,
239 const std::string& formatted,
240 TreeView* treeview_out) {
241 CollapseNodesMatchingFunction(
242 treeview_in, depth,
243 [&formatted](const Label& label) {
244 return label.Formatted() == formatted;
245 },
246 treeview_out);
247 }
248
249 } // namespace profiler
250 } // namespace ruy
251
252 #endif // RUY_PROFILER
253