tp: implement an implicit segment-tree like data structure
This CL implements an implicit variant of a segment-tree [1] most
closely described by [2].
This data structure will be used in upcoming CLs to compute aggregations
over events in large traces for the UI, significantly speeding up
the queries UI makes against trace processor.
[1] https://en.algorithmica.org/hpc/data-structures/segment-trees/
[2] https://thume.ca/2021/03/14/iforests/
Change-Id: I9fe71b67985b1c777733407136e95900f6e9c5a3
diff --git a/Android.bp b/Android.bp
index 6cb0053..db1ef89 100644
--- a/Android.bp
+++ b/Android.bp
@@ -11304,6 +11304,7 @@
name: "perfetto_src_trace_processor_containers_unittests",
srcs: [
"src/trace_processor/containers/bit_vector_unittest.cc",
+ "src/trace_processor/containers/implicit_segment_forest_unittest.cc",
"src/trace_processor/containers/null_term_string_view_unittest.cc",
"src/trace_processor/containers/row_map_unittest.cc",
"src/trace_processor/containers/string_pool_unittest.cc",
diff --git a/BUILD b/BUILD
index 12fe725..0608cb1 100644
--- a/BUILD
+++ b/BUILD
@@ -1366,6 +1366,7 @@
":include_perfetto_public_base",
":include_perfetto_public_protozero",
"src/trace_processor/containers/bit_vector.h",
+ "src/trace_processor/containers/implicit_segment_forest.h",
"src/trace_processor/containers/null_term_string_view.h",
"src/trace_processor/containers/row_map.h",
"src/trace_processor/containers/row_map_algorithms.h",
diff --git a/src/trace_processor/containers/BUILD.gn b/src/trace_processor/containers/BUILD.gn
index 43e9603..c724df8 100644
--- a/src/trace_processor/containers/BUILD.gn
+++ b/src/trace_processor/containers/BUILD.gn
@@ -22,6 +22,7 @@
perfetto_component("containers") {
public = [
"bit_vector.h",
+ "implicit_segment_forest.h",
"null_term_string_view.h",
"row_map.h",
"row_map_algorithms.h",
@@ -44,6 +45,7 @@
testonly = true
sources = [
"bit_vector_unittest.cc",
+ "implicit_segment_forest_unittest.cc",
"null_term_string_view_unittest.cc",
"row_map_unittest.cc",
"string_pool_unittest.cc",
diff --git a/src/trace_processor/containers/implicit_segment_forest.h b/src/trace_processor/containers/implicit_segment_forest.h
new file mode 100644
index 0000000..f699181
--- /dev/null
+++ b/src/trace_processor/containers/implicit_segment_forest.h
@@ -0,0 +1,134 @@
+/*
+ * Copyright (C) 2024 The Android Open Source Project
+ *
+ * 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 SRC_TRACE_PROCESSOR_CONTAINERS_IMPLICIT_SEGMENT_FOREST_H_
+#define SRC_TRACE_PROCESSOR_CONTAINERS_IMPLICIT_SEGMENT_FOREST_H_
+
+#include <cstddef>
+#include <cstdint>
+#include <vector>
+
+#include "perfetto/base/logging.h"
+
+namespace perfetto::trace_processor {
+
+// An implementation of a segment tree data structure [1] with:
+// 1) parent-child relationships are implicit, saving memory.
+// 2) the requirement for the number of values being a power of two, turning
+// the tree into a forest.
+//
+// Segment trees are a very powerful data structure allowing O(log(n)) aggregate
+// queries to be performed on an arbitrary range of elements in an array.
+// Specifically, for `T x[n]`, and an associative and commutative operation
+// AggOp (e.g. +, *, min, max, etc.), segment trees can compute
+// ```
+// T y = AggOp()(x[i], x[i + 1], x[i + 2], ..., x[j])
+// ```
+// in O(log(n)) time.
+//
+// Practically, in trace processor, this is useful for computing aggregations
+// over events in a trace. For example:
+// ```
+// struct Slice { int64_t ts; int64_t dur; };
+// struct MaxDurSlice {
+// Slice operator()(const Slice& a, const Slice& b) {
+// return a.dur < b.dur ? b : a;
+// }
+// }
+// using MipMap = ImplicitSegmentForest<Slice, MaxDurSlice>;
+// ```
+// allows building a "mipmap" [2] of a track in a trace in a UI. The UI can show
+// a representation of the items in the track when very zoomed out while
+// skipping the rendering slices which are smaller than one pixel.
+//
+// The design and implementation of this class takes heavy inspiration from
+// Tristan Hume's "IForestIndex" data structure [3] as described in his blog
+// post [4].
+//
+// [1] https://en.algorithmica.org/hpc/data-structures/segment-trees/
+// [2] https://en.wikipedia.org/wiki/Mipmap
+// [3]
+// https://github.com/trishume/gigatrace/blob/dfde0d7244f356bdc9aeefb387d904dd8b09d94a/src/iforest.rs
+// [4] https://thume.ca/2021/03/14/iforests/
+template <typename T, typename AggOp>
+class ImplicitSegmentForest {
+ public:
+ // Computes the aggregation (as specified by operator() in AggOp) over all
+ // elements in the tree between the indices [start, end). Requires that
+ // start < end.
+ //
+ // Complexity:
+ // This function performs O(log(n)) operations (n = end - start).
+ //
+ // Returns:
+ // 1) values[start]: if start + 1 == end
+ // 2) AggOp()(values[start], ..., values[end - 1]) otherwise
+ T Query(uint32_t start, uint32_t end) const {
+ PERFETTO_DCHECK(start < end);
+
+ const uint32_t in_start = start * 2;
+ const uint32_t in_end = end * 2;
+
+ uint32_t first_skip = LargestPrefixInsideSkip(in_start, in_end);
+ T aggregated = values_[AggNode(in_start, first_skip)];
+ for (uint32_t i = in_start + first_skip; i < in_end;) {
+ uint32_t skip = LargestPrefixInsideSkip(i, in_end);
+ aggregated = AggOp()(aggregated, values_[AggNode(i, skip)]);
+ i += skip;
+ }
+ return aggregated;
+ }
+
+ // Pushes a new element to right-most part of the tree. This index of this
+ // element can be used in future calls to |Query|.
+ void Push(T v) {
+ values_.emplace_back(std::move(v));
+
+ size_t len = values_.size();
+ auto levels_to_index = static_cast<uint32_t>(__builtin_ctzl(~len)) - 1;
+
+ size_t cur = len - 1;
+ for (uint32_t level = 0; level < levels_to_index; ++level) {
+ size_t prev_higher_level = cur - (1 << level);
+ values_[prev_higher_level] =
+ AggOp()(values_[prev_higher_level], values_[cur]);
+ cur = prev_higher_level;
+ }
+ values_.emplace_back(values_[len - (1 << levels_to_index)]);
+ }
+
+ // Returns the value at |n| in the tree: this corresponds to the |n|th
+ // element |Push|-ed into the tree.
+ const T& operator[](uint32_t n) { return values_[n * 2]; }
+
+ private:
+ static uint32_t Lsp(uint32_t x) { return x & -x; }
+ static uint32_t Msp(uint32_t x) {
+ return (1u << (sizeof(x) * 8 - 1)) >> __builtin_clz(x);
+ }
+ static uint32_t LargestPrefixInsideSkip(uint32_t min, uint32_t max) {
+ return Lsp(min | Msp(max - min));
+ }
+ static uint32_t AggNode(uint32_t i, uint32_t offset) {
+ return i + (offset >> 1) - 1;
+ }
+
+ std::vector<T> values_;
+};
+
+} // namespace perfetto::trace_processor
+
+#endif // SRC_TRACE_PROCESSOR_CONTAINERS_IMPLICIT_SEGMENT_FOREST_H_
diff --git a/src/trace_processor/containers/implicit_segment_forest_unittest.cc b/src/trace_processor/containers/implicit_segment_forest_unittest.cc
new file mode 100644
index 0000000..16dd262
--- /dev/null
+++ b/src/trace_processor/containers/implicit_segment_forest_unittest.cc
@@ -0,0 +1,76 @@
+/*
+ * Copyright (C) 2024 The Android Open Source Project
+ *
+ * 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 "src/trace_processor/containers/implicit_segment_forest.h"
+
+#include <cstddef>
+#include <cstdint>
+#include <numeric>
+#include <random>
+#include <vector>
+
+#include "test/gtest_and_gmock.h"
+
+namespace perfetto::trace_processor {
+namespace {
+
+struct Value {
+ uint32_t value;
+};
+
+struct Sum {
+ Value operator()(const Value& a, const Value& b) {
+ return Value{a.value + b.value};
+ }
+};
+
+TEST(ImplicitSegmentTree, SimpleSum) {
+ std::vector<uint32_t> res = {209, 330, 901, 3, 10, 0, 3903, 309, 490};
+
+ ImplicitSegmentForest<Value, Sum> forest;
+ for (uint32_t x : res) {
+ forest.Push(Value{x});
+ }
+
+ for (uint32_t i = 0; i < res.size(); ++i) {
+ for (uint32_t j = i + 1; j < res.size(); ++j) {
+ ASSERT_EQ(forest.Query(i, j).value,
+ std::accumulate(res.begin() + i, res.begin() + j, 0u));
+ }
+ }
+}
+
+TEST(ImplicitSegmentTree, Stress) {
+ static constexpr size_t kCount = 9249;
+ std::minstd_rand0 rng(42);
+
+ std::vector<uint32_t> res;
+ ImplicitSegmentForest<Value, Sum> forest;
+ for (uint32_t i = 0; i < kCount; ++i) {
+ res.push_back(static_cast<uint32_t>(rng()));
+ forest.Push(Value{res.back()});
+ }
+
+ for (uint32_t i = 0; i < 10000; ++i) {
+ uint32_t s = rng() % kCount;
+ uint32_t e = s + 1 + (rng() % (kCount - s));
+ ASSERT_EQ(forest.Query(s, e).value,
+ std::accumulate(res.begin() + s, res.begin() + e, 0u));
+ }
+}
+
+} // namespace
+} // namespace perfetto::trace_processor
