1 // Copyright 2024 The Pigweed Authors 2 // 3 // Licensed under the Apache License, Version 2.0 (the "License"); you may not 4 // use this file except in compliance with the License. You may obtain a copy of 5 // the License at 6 // 7 // https://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, WITHOUT 11 // WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. See the 12 // License for the specific language governing permissions and limitations under 13 // the License. 14 #pragma once 15 16 #include <cstddef> 17 #include <cstdint> 18 19 #include "pw_containers/intrusive_map.h" 20 #include "pw_metric/metric.h" 21 22 namespace pw::allocator { 23 namespace internal { 24 25 // Forward declaration for friending. 26 class GenericBlockAllocatorBenchmark; 27 28 /// Collection data relating to an allocating request. 29 struct BenchmarkSample { 30 /// How many nanoseconds the request took. 31 uint64_t nanoseconds = 0; 32 33 /// Current fragmentation reported by the block allocaor. 34 float fragmentation = 0.f; 35 36 /// Current single largest allocation that could succeed. 37 size_t largest = 0; 38 39 /// Result of the last allocator request. 40 bool failed = false; 41 }; 42 43 /// Base class for an accumulation of samples into a single measurement. 44 /// 45 /// As samples are collected, they are aggregated into a set of bins described 46 /// a specific domain and a range in that domain, e.g. the set of all 47 /// samples for requests of at least 512 bytes but less than 1024. 48 /// 49 /// This class describes the common behavior of those bins without referencing 50 /// specific domain. Callers should not use this class directly, and use 51 /// `Measurement` instead.measurement 52 class GenericMeasurement { 53 public: 54 GenericMeasurement(metric::Token name); 55 metrics()56 metric::Group& metrics() { return metrics_; } count()57 size_t count() const { return count_; } 58 nanoseconds()59 float nanoseconds() const { return nanoseconds_.value(); } fragmentation()60 float fragmentation() const { return fragmentation_.value(); } largest()61 float largest() const { return largest_.value(); } failures()62 uint32_t failures() const { return failures_.value(); } 63 64 void Update(const BenchmarkSample& data); 65 66 private: 67 metric::Group metrics_; 68 69 PW_METRIC(nanoseconds_, "mean response time (ns)", 0.f); 70 PW_METRIC(fragmentation_, "mean fragmentation metric", 0.f); 71 PW_METRIC(largest_, "mean max available (bytes)", 0.f); 72 PW_METRIC(failures_, "number of calls that failed", 0u); 73 74 size_t count_ = 0; 75 }; 76 77 } // namespace internal 78 79 /// An accumulation of samples into a single measurement. 80 /// 81 /// This class extends `GenericMeasurement` with a key that describes what 82 /// domain is being used to partition samples. It is intrusively mappable using 83 /// that key, allowing other objects such as `Measurements` to maintain sorted 84 /// containers of this type. 85 template <typename Key> 86 class Measurement : public internal::GenericMeasurement, 87 public IntrusiveMap<Key, Measurement<Key>>::Item { 88 public: Measurement(metric::Token name,Key lower_limit)89 Measurement(metric::Token name, Key lower_limit) 90 : internal::GenericMeasurement(name), lower_limit_(lower_limit) {} key()91 const Key& key() const { return lower_limit_; } 92 93 private: 94 Key lower_limit_; 95 }; 96 97 /// A collection of sorted containers of `Measurement`s. 98 /// 99 /// This collection includes sorting `Measurement`s by 100 /// * The number of allocator requests that have been performed. 101 /// * The level of fragmentation as measured by the block allocator. 102 /// * The size of the most recent allocator request. 103 class Measurements { 104 public: 105 explicit Measurements(metric::Token name); 106 metrics()107 metric::Group& metrics() { return metrics_; } 108 Measurement<size_t>& GetByCount(size_t count); 109 Measurement<float>& GetByFragmentation(float fragmentation); 110 Measurement<size_t>& GetBySize(size_t size); 111 112 protected: 113 void AddByCount(Measurement<size_t>& measurement); 114 void AddByFragmentation(Measurement<float>& measurement); 115 void AddBySize(Measurement<size_t>& measurement); 116 117 /// Removes measurements from the sorted 118 void Clear(); 119 120 private: 121 // Allow the benchmark harness to retrieve measurements. 122 friend class internal::GenericBlockAllocatorBenchmark; 123 124 metric::Group metrics_; 125 126 PW_METRIC_GROUP(metrics_by_count_, "by allocation count"); 127 IntrusiveMap<size_t, Measurement<size_t>> by_count_; 128 129 PW_METRIC_GROUP(metrics_by_fragmentation_, "by fragmentation"); 130 IntrusiveMap<float, Measurement<float>> by_fragmentation_; 131 132 PW_METRIC_GROUP(metrics_by_size_, "by allocation size"); 133 IntrusiveMap<size_t, Measurement<size_t>> by_size_; 134 }; 135 136 /// A default set of measurements for benchmarking allocators. 137 /// 138 /// This organizes measurements in to logarithmically increasing ranges of 139 /// alloations counts and sizes, as well as fragmentation quintiles. 140 class DefaultMeasurements final : public Measurements { 141 public: 142 DefaultMeasurements(metric::Token name); ~DefaultMeasurements()143 ~DefaultMeasurements() { Measurements::Clear(); } 144 145 private: 146 static constexpr size_t kNumByCount = 5; 147 std::array<Measurement<size_t>, kNumByCount> by_count_{{ 148 {PW_TOKENIZE_STRING_EXPR("allocation count in [0, 10)"), 0}, 149 {PW_TOKENIZE_STRING_EXPR("allocation count in [10, 100)"), 10}, 150 {PW_TOKENIZE_STRING_EXPR("allocation count in [100, 1,000)"), 100}, 151 {PW_TOKENIZE_STRING_EXPR("allocation count in [1,000, 10,000)"), 1000}, 152 {PW_TOKENIZE_STRING_EXPR("allocation count in [10,000, inf)"), 10000}, 153 }}; 154 155 static constexpr size_t kNumByFragmentation = 5; 156 std::array<Measurement<float>, kNumByFragmentation> by_fragmentation_ = {{ 157 {PW_TOKENIZE_STRING_EXPR("fragmentation in [0.0, 0.2)"), 0.0f}, 158 {PW_TOKENIZE_STRING_EXPR("fragmentation in [0.2, 0.4)"), 0.2f}, 159 {PW_TOKENIZE_STRING_EXPR("fragmentation in [0.4, 0.6)"), 0.4f}, 160 {PW_TOKENIZE_STRING_EXPR("fragmentation in [0.6, 0.8)"), 0.6f}, 161 {PW_TOKENIZE_STRING_EXPR("fragmentation in [0.8, 1.0]"), 0.8f}, 162 }}; 163 164 static constexpr size_t kNumBySize = 6; 165 std::array<Measurement<size_t>, kNumBySize> by_size_ = {{ 166 {PW_TOKENIZE_STRING_EXPR("usable size in [0, 16)"), 0}, 167 {PW_TOKENIZE_STRING_EXPR("usable size in [16, 64)"), 16}, 168 {PW_TOKENIZE_STRING_EXPR("usable size in [64, 256)"), 64}, 169 {PW_TOKENIZE_STRING_EXPR("usable size in [256, 1024)"), 256}, 170 {PW_TOKENIZE_STRING_EXPR("usable size in [1024, 4096)"), 1024}, 171 {PW_TOKENIZE_STRING_EXPR("usable size in [4096, inf)"), 4096}, 172 }}; 173 }; 174 175 } // namespace pw::allocator 176