1 /* 2 * Copyright (C) 2024 The Android Open Source Project 3 * 4 * Licensed under the Apache License, Version 2.0 (the "License"); 5 * you may not use this file except in compliance with the License. 6 * You may obtain a copy of the License at 7 * 8 * http://www.apache.org/licenses/LICENSE-2.0 9 * 10 * Unless required by applicable law or agreed to in writing, software 11 * distributed under the License is distributed on an "AS IS" BASIS, 12 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. 13 * See the License for the specific language governing permissions and 14 * limitations under the License. 15 */ 16 17 #ifndef SRC_TRACE_PROCESSOR_CONTAINERS_IMPLICIT_SEGMENT_FOREST_H_ 18 #define SRC_TRACE_PROCESSOR_CONTAINERS_IMPLICIT_SEGMENT_FOREST_H_ 19 20 #include <cstddef> 21 #include <cstdint> 22 #include <vector> 23 24 #include "perfetto/base/logging.h" 25 26 namespace perfetto::trace_processor { 27 28 // An implementation of a segment tree data structure [1] with: 29 // 1) parent-child relationships are implicit, saving memory. 30 // 2) the requirement for the number of values being a power of two, turning 31 // the tree into a forest. 32 // 33 // Segment trees are a very powerful data structure allowing O(log(n)) aggregate 34 // queries to be performed on an arbitrary range of elements in an array. 35 // Specifically, for `T x[n]`, and an associative and commutative operation 36 // AggOp (e.g. +, *, min, max, etc.), segment trees can compute 37 // ``` 38 // T y = AggOp()(x[i], x[i + 1], x[i + 2], ..., x[j]) 39 // ``` 40 // in O(log(n)) time. 41 // 42 // Practically, in trace processor, this is useful for computing aggregations 43 // over events in a trace. For example: 44 // ``` 45 // struct Slice { int64_t ts; int64_t dur; }; 46 // struct MaxDurSlice { 47 // Slice operator()(const Slice& a, const Slice& b) { 48 // return a.dur < b.dur ? b : a; 49 // } 50 // } 51 // using MipMap = ImplicitSegmentForest<Slice, MaxDurSlice>; 52 // ``` 53 // allows building a "mipmap" [2] of a track in a trace in a UI. The UI can show 54 // a representation of the items in the track when very zoomed out while 55 // skipping the rendering slices which are smaller than one pixel. 56 // 57 // The design and implementation of this class takes heavy inspiration from 58 // Tristan Hume's "IForestIndex" data structure [3] as described in his blog 59 // post [4]. 60 // 61 // [1] https://en.algorithmica.org/hpc/data-structures/segment-trees/ 62 // [2] https://en.wikipedia.org/wiki/Mipmap 63 // [3] 64 // https://github.com/trishume/gigatrace/blob/dfde0d7244f356bdc9aeefb387d904dd8b09d94a/src/iforest.rs 65 // [4] https://thume.ca/2021/03/14/iforests/ 66 template <typename T, typename AggOp> 67 class ImplicitSegmentForest { 68 public: 69 // Computes the aggregation (as specified by operator() in AggOp) over all 70 // elements in the tree between the indices [start, end). Requires that 71 // start < end. 72 // 73 // Complexity: 74 // This function performs O(log(n)) operations (n = end - start). 75 // 76 // Returns: 77 // 1) values[start]: if start + 1 == end 78 // 2) AggOp()(values[start], ..., values[end - 1]) otherwise Query(uint32_t start,uint32_t end)79 T Query(uint32_t start, uint32_t end) const { 80 PERFETTO_DCHECK(start < end); 81 82 const uint32_t in_start = start * 2; 83 const uint32_t in_end = end * 2; 84 85 uint32_t first_skip = LargestPrefixInsideSkip(in_start, in_end); 86 T aggregated = values_[AggNode(in_start, first_skip)]; 87 for (uint32_t i = in_start + first_skip; i < in_end;) { 88 uint32_t skip = LargestPrefixInsideSkip(i, in_end); 89 aggregated = AggOp()(aggregated, values_[AggNode(i, skip)]); 90 i += skip; 91 } 92 return aggregated; 93 } 94 95 // Pushes a new element to right-most part of the tree. This index of this 96 // element can be used in future calls to |Query|. Push(T v)97 void Push(T v) { 98 values_.emplace_back(std::move(v)); 99 100 size_t len = values_.size(); 101 auto levels_to_index = static_cast<uint32_t>(__builtin_ctzl( 102 static_cast<unsigned long>(~len))) - 103 1; 104 105 size_t cur = len - 1; 106 for (uint32_t level = 0; level < levels_to_index; ++level) { 107 size_t prev_higher_level = cur - (1 << level); 108 values_[prev_higher_level] = 109 AggOp()(values_[prev_higher_level], values_[cur]); 110 cur = prev_higher_level; 111 } 112 values_.emplace_back(values_[len - (1 << levels_to_index)]); 113 } 114 115 // Returns the value at |n| in the tree: this corresponds to the |n|th 116 // element |Push|-ed into the tree. 117 const T& operator[](uint32_t n) { return values_[n * 2]; } 118 119 // Returns the number of elements pushed into the forest. size()120 uint32_t size() const { return static_cast<uint32_t>(values_.size() / 2); } 121 122 private: Lsp(uint32_t x)123 static uint32_t Lsp(uint32_t x) { return x & -x; } Msp(uint32_t x)124 static uint32_t Msp(uint32_t x) { 125 return (1u << (sizeof(x) * 8 - 1)) >> __builtin_clz(x); 126 } LargestPrefixInsideSkip(uint32_t min,uint32_t max)127 static uint32_t LargestPrefixInsideSkip(uint32_t min, uint32_t max) { 128 return Lsp(min | Msp(max - min)); 129 } AggNode(uint32_t i,uint32_t offset)130 static uint32_t AggNode(uint32_t i, uint32_t offset) { 131 return i + (offset >> 1) - 1; 132 } 133 134 std::vector<T> values_; 135 }; 136 137 } // namespace perfetto::trace_processor 138 139 #endif // SRC_TRACE_PROCESSOR_CONTAINERS_IMPLICIT_SEGMENT_FOREST_H_ 140