diff options
4 files changed, 129 insertions, 8 deletions
diff --git a/spark-common/src/main/java/me/lucko/spark/common/sampler/node/StackTraceNode.java b/spark-common/src/main/java/me/lucko/spark/common/sampler/node/StackTraceNode.java index ed938d5..c0dcc5b 100644 --- a/spark-common/src/main/java/me/lucko/spark/common/sampler/node/StackTraceNode.java +++ b/spark-common/src/main/java/me/lucko/spark/common/sampler/node/StackTraceNode.java @@ -65,7 +65,7 @@ public final class StackTraceNode extends AbstractNode { return this.description.parentLineNumber; } - public SparkSamplerProtos.StackTraceNode toProto(MergeMode mergeMode, ProtoTimeEncoder timeEncoder) { + public SparkSamplerProtos.StackTraceNode toProto(MergeMode mergeMode, ProtoTimeEncoder timeEncoder, Iterable<Integer> childrenRefs) { SparkSamplerProtos.StackTraceNode.Builder proto = SparkSamplerProtos.StackTraceNode.newBuilder() .setClassName(this.description.className) .setMethodName(this.description.methodName); @@ -91,9 +91,7 @@ public final class StackTraceNode extends AbstractNode { .ifPresent(proto::setMethodDesc); } - for (StackTraceNode child : exportChildren(mergeMode)) { - proto.addChildren(child.toProto(mergeMode, timeEncoder)); - } + proto.addAllChildrenRefs(childrenRefs); return proto.build(); } diff --git a/spark-common/src/main/java/me/lucko/spark/common/sampler/node/ThreadNode.java b/spark-common/src/main/java/me/lucko/spark/common/sampler/node/ThreadNode.java index 1dce523..9faece6 100644 --- a/spark-common/src/main/java/me/lucko/spark/common/sampler/node/ThreadNode.java +++ b/spark-common/src/main/java/me/lucko/spark/common/sampler/node/ThreadNode.java @@ -21,8 +21,14 @@ package me.lucko.spark.common.sampler.node; import me.lucko.spark.common.sampler.window.ProtoTimeEncoder; +import me.lucko.spark.common.util.IndexedListBuilder; import me.lucko.spark.proto.SparkSamplerProtos; +import java.util.ArrayDeque; +import java.util.Deque; +import java.util.LinkedList; +import java.util.List; + /** * The root of a sampling stack for a given thread / thread group. */ @@ -92,10 +98,83 @@ public final class ThreadNode extends AbstractNode { proto.addTimes(time); } + // When converting to a proto, we change the data structure from a recursive tree to an array. + // Effectively, instead of: + // + // { + // data: 'one', + // children: [ + // { + // data: 'two', + // children: [{ data: 'four' }] + // }, + // { data: 'three' } + // ] + // } + // + // we transmit: + // + // [ + // { data: 'one', children: [1, 2] }, + // { data: 'two', children: [3] } + // { data: 'three', children: [] } + // { data: 'four', children: [] } + // ] + // + + // the flattened array of nodes + IndexedListBuilder<SparkSamplerProtos.StackTraceNode> nodesArray = new IndexedListBuilder<>(); + + // Perform a depth-first post order traversal of the tree + Deque<Node> stack = new ArrayDeque<>(); + + // push the thread node's children to the stack + List<Integer> childrenRefs = new LinkedList<>(); for (StackTraceNode child : exportChildren(mergeMode)) { - proto.addChildren(child.toProto(mergeMode, timeEncoder)); + stack.push(new Node(child, childrenRefs)); + } + + Node node; + while (!stack.isEmpty()) { + node = stack.peek(); + + // on the first visit, just push this node's children and leave it on the stack + if (node.firstVisit) { + for (StackTraceNode child : node.stackTraceNode.exportChildren(mergeMode)) { + stack.push(new Node(child, node.childrenRefs)); + } + node.firstVisit = false; + continue; + } + + // convert StackTraceNode to a proto + // - at this stage, we have already visited this node's children + // - the refs for each child are stored in node.childrenRefs + SparkSamplerProtos.StackTraceNode childProto = node.stackTraceNode.toProto(mergeMode, timeEncoder, node.childrenRefs); + + // add the child proto to the nodes array, and record the ref in the parent + int childIndex = nodesArray.add(childProto); + node.parentChildrenRefs.add(childIndex); + + // pop from the stack + stack.pop(); } + proto.addAllChildrenRefs(childrenRefs); + proto.addAllChildren(nodesArray.build()); + return proto.build(); } + + private static final class Node { + private final StackTraceNode stackTraceNode; + private boolean firstVisit = true; + private final List<Integer> childrenRefs = new LinkedList<>(); + private final List<Integer> parentChildrenRefs; + + private Node(StackTraceNode node, List<Integer> parentChildrenRefs) { + this.stackTraceNode = node; + this.parentChildrenRefs = parentChildrenRefs; + } + } } diff --git a/spark-common/src/main/java/me/lucko/spark/common/util/IndexedListBuilder.java b/spark-common/src/main/java/me/lucko/spark/common/util/IndexedListBuilder.java new file mode 100644 index 0000000..b2315f9 --- /dev/null +++ b/spark-common/src/main/java/me/lucko/spark/common/util/IndexedListBuilder.java @@ -0,0 +1,43 @@ +/* + * This file is part of spark. + * + * Copyright (c) lucko (Luck) <luck@lucko.me> + * Copyright (c) contributors + * + * This program is free software: you can redistribute it and/or modify + * it under the terms of the GNU General Public License as published by + * the Free Software Foundation, either version 3 of the License, or + * (at your option) any later version. + * + * This program is distributed in the hope that it will be useful, + * but WITHOUT ANY WARRANTY; without even the implied warranty of + * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the + * GNU General Public License for more details. + * + * You should have received a copy of the GNU General Public License + * along with this program. If not, see <http://www.gnu.org/licenses/>. + */ + +package me.lucko.spark.common.util; + +import java.util.ArrayList; +import java.util.List; + +/** + * List builder that returns the index of the inserted element. + * + * @param <T> generic type + */ +public class IndexedListBuilder<T> { + private int i = 0; + private final List<T> nodes = new ArrayList<>(); + + public int add(T node) { + this.nodes.add(node); + return this.i++; + } + + public List<T> build() { + return this.nodes; + } +} diff --git a/spark-common/src/main/proto/spark/spark_sampler.proto b/spark-common/src/main/proto/spark/spark_sampler.proto index 2cb08f1..245da37 100644 --- a/spark-common/src/main/proto/spark/spark_sampler.proto +++ b/spark-common/src/main/proto/spark/spark_sampler.proto @@ -78,18 +78,19 @@ message ThreadNode { repeated StackTraceNode children = 3; repeated double times = 4; + repeated int32 children_refs = 5; } message StackTraceNode { // replaced - reserved 1; - reserved "time"; + reserved 1, 2; + reserved "time", "children"; - repeated StackTraceNode children = 2; string class_name = 3; string method_name = 4; int32 parent_line_number = 5; // optional int32 line_number = 6; // optional string method_desc = 7; // optional repeated double times = 8; + repeated int32 children_refs = 9; } |