You are viewing a plain text version of this content. The canonical link for it is here.
Posted to commits@quickstep.apache.org by ji...@apache.org on 2016/06/30 22:00:24 UTC
[8/9] incubator-quickstep git commit: Initial commit
http://git-wip-us.apache.org/repos/asf/incubator-quickstep/blob/77013338/utility/DAGVisualizer.cpp
----------------------------------------------------------------------
diff --git a/utility/DAGVisualizer.cpp b/utility/DAGVisualizer.cpp
new file mode 100644
index 0000000..e62f948
--- /dev/null
+++ b/utility/DAGVisualizer.cpp
@@ -0,0 +1,167 @@
+/**
+ * Copyright 2016, Quickstep Research Group, Computer Sciences Department,
+ * University of Wisconsin\u2014Madison.
+ *
+ * Licensed under the Apache License, Version 2.0 (the "License");
+ * you may not use this file except in compliance with the License.
+ * You may obtain a copy of the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ **/
+
+#include "utility/DAGVisualizer.hpp"
+#include "utility/EventProfiler.hpp"
+
+#include <cmath>
+#include <cstddef>
+#include <iomanip>
+#include <memory>
+#include <sstream>
+#include <string>
+#include <unordered_map>
+#include <vector>
+
+#include "query_optimizer/QueryPlan.hpp"
+#include "utility/EventProfiler.hpp"
+#include "utility/StringUtil.hpp"
+
+#include "glog/logging.h"
+
+namespace quickstep {
+
+std::string DAGVisualizer::toDOT() {
+ std::set<std::string> no_display_op_names =
+ { "DestroyHashOperator", "DropTableOperator" };
+
+ const auto &dag = plan_.getQueryPlanDAG();
+ const std::size_t num_nodes = dag.size();
+
+ std::vector<double> time_elapsed(num_nodes, 0);
+ std::vector<double> time_percentage(num_nodes, 0);
+ std::vector<double> time_start(num_nodes, std::numeric_limits<double>::max());
+ std::vector<double> time_end(num_nodes, 0);
+ const auto &zero_time = relop_profiler.zero_time();
+ for (const auto &container : relop_profiler.containers()) {
+ for (const auto &line : container.second.events) {
+ const std::size_t relop_index = line.first;
+ for (const auto &event : line.second) {
+ time_elapsed[relop_index] +=
+ std::chrono::duration<double>(event.end_time - event.start_time).count();
+ time_start[relop_index] =
+ std::min(time_start[relop_index],
+ std::chrono::duration<double>(event.start_time - zero_time).count());
+ time_end[relop_index] =
+ std::max(time_end[relop_index],
+ std::chrono::duration<double>(event.end_time - zero_time).count());
+ }
+ }
+ }
+ const std::size_t num_threads = relop_profiler.containers().size();
+ double total_time_elapsed = 0;
+ double max_percentage = 0;
+ for (std::size_t i = 0; i < time_elapsed.size(); ++i) {
+ time_elapsed[i] /= num_threads;
+ total_time_elapsed += time_elapsed[i];
+ }
+ for (std::size_t i = 0; i < time_elapsed.size(); ++i) {
+ time_percentage[i] = time_elapsed[i] / total_time_elapsed;
+ max_percentage = std::max(max_percentage, time_percentage[i]);
+ }
+
+ std::vector<bool> display_ops(num_nodes, false);
+ for (std::size_t node_index = 0; node_index < num_nodes; ++node_index) {
+ const auto &node = dag.getNodePayload(node_index);
+ const std::string relop_name = node.getName();
+ if (no_display_op_names.find(relop_name) == no_display_op_names.end()) {
+ display_ops[node_index] = true;
+
+ nodes_.emplace_back();
+ NodeInfo &node_info = nodes_.back();
+ node_info.id = node_index;
+
+ std::string hue =
+ std::to_string(std::sqrt(time_percentage[node_index] / max_percentage));
+ node_info.color = hue + " " + hue + " 1.0";
+
+ node_info.labels.emplace_back(
+ "[" + std::to_string(node.getOperatorIndex()) + "] " + relop_name);
+ node_info.labels.emplace_back(
+ std::to_string(std::lround(time_elapsed[node_index] * 1000)) +
+ "ms (" + PercentageToString(time_percentage[node_index] * 100) + "%)");
+ node_info.labels.emplace_back(
+ "span: [" +
+ std::to_string(std::lround(time_start[node_index] * 1000)) + "ms, " +
+ std::to_string(std::lround(time_end[node_index] * 1000)) + "ms]");
+ }
+ }
+ for (std::size_t node_index = 0; node_index < num_nodes; ++node_index) {
+ if (display_ops[node_index]) {
+ for (const auto &link : dag.getDependents(node_index)) {
+ if (display_ops[link.first]) {
+ edges_.emplace_back();
+ EdgeInfo &edge_info = edges_.back();
+ edge_info.src_node_id = node_index;
+ edge_info.dst_node_id = link.first;
+ edge_info.is_pipeline_breaker = link.second;
+ }
+ }
+ }
+ }
+
+ // Format output graph
+ std::ostringstream graph_oss;
+ graph_oss << "digraph g {\n";
+ graph_oss << " rankdir=BT\n";
+ graph_oss << " node [penwidth=2]\n";
+ graph_oss << " edge [fontsize=16 fontcolor=gray penwidth=2]\n\n";
+
+ // Format nodes
+ for (const NodeInfo &node_info : nodes_) {
+ graph_oss << " " << node_info.id << " [ ";
+ if (!node_info.labels.empty()) {
+ graph_oss << "label=\""
+ << EscapeSpecialChars(JoinToString(node_info.labels, " "))
+ << "\" ";
+ }
+ if (!node_info.color.empty()) {
+ graph_oss << "style=filled fillcolor=\"" << node_info.color << "\" ";
+ }
+ graph_oss << "]\n";
+ }
+ graph_oss << "\n";
+
+ // Format edges
+ for (const EdgeInfo &edge_info : edges_) {
+ graph_oss << " " << edge_info.src_node_id << " -> "
+ << edge_info.dst_node_id << " [ ";
+ if (edge_info.is_pipeline_breaker) {
+ graph_oss << "style=dashed ";
+ }
+ if (!edge_info.labels.empty()) {
+ graph_oss << "label=\""
+ << EscapeSpecialChars(JoinToString(edge_info.labels, " "))
+ << "\" ";
+ }
+ graph_oss << "]\n";
+ }
+
+ graph_oss << "}\n";
+
+ return graph_oss.str();
+}
+
+std::string DAGVisualizer::PercentageToString(double percentage) {
+ std::ostringstream oss;
+ oss << static_cast<std::uint32_t>(percentage) << ".";
+ int digits = std::lround(percentage * 10000) % 100;
+ oss << digits / 10 << digits % 10;
+ return oss.str();
+}
+
+} // namespace quickstep
http://git-wip-us.apache.org/repos/asf/incubator-quickstep/blob/77013338/utility/DAGVisualizer.hpp
----------------------------------------------------------------------
diff --git a/utility/DAGVisualizer.hpp b/utility/DAGVisualizer.hpp
new file mode 100644
index 0000000..5c81d22
--- /dev/null
+++ b/utility/DAGVisualizer.hpp
@@ -0,0 +1,85 @@
+/**
+ * Copyright 2016, Quickstep Research Group, Computer Sciences Department,
+ * University of Wisconsin\u2014Madison.
+ *
+ * Licensed under the Apache License, Version 2.0 (the "License");
+ * you may not use this file except in compliance with the License.
+ * You may obtain a copy of the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ **/
+
+#ifndef QUICKSTEP_UTILITY_DAG_VISUALIZER_HPP_
+#define QUICKSTEP_UTILITY_DAG_VISUALIZER_HPP_
+
+#include <memory>
+#include <string>
+#include <unordered_map>
+#include <vector>
+
+#include "utility/Macros.hpp"
+
+namespace quickstep {
+
+class QueryPlan;
+
+/** \addtogroup Utility
+ * @{
+ */
+
+/**
+ * @brief A visualizer that converts an execution plan DAG into a graph in
+ * DOT format. Note that DOT is a plain text graph description language.
+ *
+ * @note This utility tool can be further extended to be more generic.
+ */
+class DAGVisualizer {
+ public:
+ DAGVisualizer(const QueryPlan &plan)
+ : plan_(plan) {}
+
+ ~DAGVisualizer() {}
+
+ std::string toDOT();
+
+ private:
+ static std::string PercentageToString(double percentage);
+
+ /**
+ * @brief Information of a graph node.
+ */
+ struct NodeInfo {
+ std::size_t id;
+ std::vector<std::string> labels;
+ std::string color;
+ };
+
+ /**
+ * @brief Information of a graph edge.
+ */
+ struct EdgeInfo {
+ std::size_t src_node_id;
+ std::size_t dst_node_id;
+ std::vector<std::string> labels;
+ bool is_pipeline_breaker;
+ };
+
+ const QueryPlan &plan_;
+
+ std::vector<NodeInfo> nodes_;
+ std::vector<EdgeInfo> edges_;
+
+ DISALLOW_COPY_AND_ASSIGN(DAGVisualizer);
+};
+
+/** @} */
+
+} // namespace quickstep
+
+#endif /* QUICKSTEP_UTILITY_DAG_VISUALIZER_HPP_ */
http://git-wip-us.apache.org/repos/asf/incubator-quickstep/blob/77013338/utility/EventProfiler.cpp
----------------------------------------------------------------------
diff --git a/utility/EventProfiler.cpp b/utility/EventProfiler.cpp
new file mode 100644
index 0000000..cac6737
--- /dev/null
+++ b/utility/EventProfiler.cpp
@@ -0,0 +1,29 @@
+/**
+ * Copyright 2016, Quickstep Research Group, Computer Sciences Department,
+ * University of Wisconsin\u2014Madison.
+ *
+ * Licensed under the Apache License, Version 2.0 (the "License");
+ * you may not use this file except in compliance with the License.
+ * You may obtain a copy of the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ **/
+
+#include "utility/EventProfiler.hpp"
+
+#include <cstddef>
+#include <string>
+#include <vector>
+
+namespace quickstep {
+
+EventProfiler<std::string, int> simple_profiler;
+EventProfiler<std::size_t> relop_profiler;
+
+} // namespace quickstep
http://git-wip-us.apache.org/repos/asf/incubator-quickstep/blob/77013338/utility/EventProfiler.hpp
----------------------------------------------------------------------
diff --git a/utility/EventProfiler.hpp b/utility/EventProfiler.hpp
new file mode 100644
index 0000000..ca91593
--- /dev/null
+++ b/utility/EventProfiler.hpp
@@ -0,0 +1,176 @@
+/**
+ * Copyright 2016, Quickstep Research Group, Computer Sciences Department,
+ * University of Wisconsin\u2014Madison.
+ *
+ * Licensed under the Apache License, Version 2.0 (the "License");
+ * you may not use this file except in compliance with the License.
+ * You may obtain a copy of the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ **/
+
+#ifndef QUICKSTEP_UTILITY_EVENT_PROFILER_HPP_
+#define QUICKSTEP_UTILITY_EVENT_PROFILER_HPP_
+
+#include <chrono>
+#include <cstddef>
+#include <cstring>
+#include <ctime>
+#include <iomanip>
+#include <map>
+#include <ostream>
+#include <thread>
+#include <type_traits>
+#include <utility>
+#include <vector>
+
+#include "threading/Mutex.hpp"
+
+#include "glog/logging.h"
+
+namespace quickstep {
+
+/** \addtogroup Utility
+ * @{
+ */
+
+using clock = std::chrono::steady_clock;
+
+template <typename TagT, typename ...PayloadT>
+class EventProfiler {
+
+ public:
+ EventProfiler()
+ : zero_time_(clock::now()) {
+ }
+
+ struct EventInfo {
+ clock::time_point start_time;
+ clock::time_point end_time;
+ bool is_finished;
+ std::tuple<PayloadT...> payload;
+
+ explicit EventInfo(const clock::time_point &start_time_in)
+ : start_time(start_time_in),
+ is_finished(false) {
+ }
+
+ EventInfo()
+ : start_time(clock::now()),
+ is_finished(false) {
+ }
+
+ inline void setPayload(PayloadT &&...in_payload) {
+ payload = std::make_tuple(in_payload...);
+ }
+
+ inline void endEvent() {
+ end_time = clock::now();
+ is_finished = true;
+ }
+ };
+
+ struct EventContainer {
+ inline void startEvent(const TagT &tag) {
+ events[tag].emplace_back(clock::now());
+ }
+
+ inline void endEvent(const TagT &tag) {
+ auto &event_info = events.at(tag).back();
+ event_info.is_finished = true;
+ event_info.end_time = clock::now();
+ }
+
+ inline std::vector<EventInfo> *getEventLine(const TagT &tag) {
+ return &events[tag];
+ }
+
+ std::map<TagT, std::vector<EventInfo>> events;
+ };
+
+ EventContainer *getContainer() {
+ MutexLock lock(mutex_);
+ return &thread_map_[std::this_thread::get_id()];
+ }
+
+ void writeToStream(std::ostream &os) const {
+ time_t rawtime;
+ time(&rawtime);
+ char event_id[32];
+ strftime(event_id, sizeof event_id, "%Y-%m-%d %H:%M:%S", localtime(&rawtime));
+
+ int thread_id = 0;
+ for (const auto &thread_ctx : thread_map_) {
+ for (const auto &event_group : thread_ctx.second.events) {
+ for (const auto &event_info : event_group.second) {
+ CHECK(event_info.is_finished) << "Unfinished profiling event";
+
+ os << std::setprecision(12)
+ << event_id << ","
+ << thread_id << "," << event_group.first << ",";
+
+ PrintTuple(os, event_info.payload, ",");
+
+ os << std::chrono::duration<double>(event_info.start_time - zero_time_).count()
+ << ","
+ << std::chrono::duration<double>(event_info.end_time - zero_time_).count()
+ << "\n";
+ }
+ }
+ ++thread_id;
+ }
+ }
+
+ void clear() {
+ zero_time_ = clock::now();
+ thread_map_.clear();
+ }
+
+ const std::map<std::thread::id, EventContainer> &containers() {
+ return thread_map_;
+ }
+
+ const clock::time_point &zero_time() {
+ return zero_time_;
+ }
+
+ private:
+ template<class Tuple, std::size_t N>
+ struct TuplePrinter {
+ static void Print(std::ostream &os, const Tuple &t, const std::string &sep) {
+ TuplePrinter<Tuple, N-1>::Print(os, t, sep);
+ os << std::get<N-1>(t) << sep;
+ }
+ };
+
+ template<class Tuple>
+ struct TuplePrinter<Tuple, 1> {
+ static void Print(std::ostream &os, const Tuple &t, const std::string &sep) {
+ os << std::get<0>(t) << sep;
+ }
+ };
+
+ template<class... Args>
+ static void PrintTuple(std::ostream &os, const std::tuple<Args...>& t, const std::string &sep) {
+ TuplePrinter<decltype(t), sizeof...(Args)>::Print(os, t, sep);
+ }
+
+ clock::time_point zero_time_;
+ std::map<std::thread::id, EventContainer> thread_map_;
+ Mutex mutex_;
+};
+
+extern EventProfiler<std::string, int> simple_profiler;
+extern EventProfiler<std::size_t> relop_profiler;
+
+/** @} */
+
+} // namespace quickstep
+
+#endif // QUICKSTEP_UTILITY_EVENT_PROFILER_HPP_