1 /* 2 * Portions (c) Meta Platforms, Inc. and affiliates. 3 * All rights reserved. 4 * 5 * This source code is licensed under the BSD-style license found in the 6 * LICENSE file in the root directory of this source tree. 7 */ 8 9 /* 10 * Code sourced from 11 * https://github.com/microsoft/ArchProbe/blob/main/include/stats.hpp with the 12 * following MIT license 13 * 14 * MIT License 15 * 16 * Copyright (c) Microsoft Corporation. 17 * 18 * Permission is hereby granted, free of charge, to any person obtaining a copy 19 * of this software and associated documentation files (the "Software"), to 20 * deal in the Software without restriction, including without limitation the 21 * rights to use, copy, modify, merge, publish, distribute, sublicense, and/or 22 * sell copies of the Software, and to permit persons to whom the Software is 23 * furnished to do so, subject to the following conditions: 24 * 25 * The above copyright notice and this permission notice shall be included in 26 * all copies or substantial portions of the Software. 27 * 28 * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR 29 * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, 30 * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE 31 * AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER 32 * LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING 33 * FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS 34 * IN THE SOFTWARE 35 */ 36 37 #pragma once 38 #include <array> 39 #include <cstdint> 40 41 template <typename T> 42 class AvgStats { 43 T sum_ = 0; 44 uint64_t n_ = 0; 45 46 public: 47 typedef T value_t; 48 push(T value)49 void push(T value) { 50 sum_ += value; 51 n_ += 1; 52 } has_value()53 inline bool has_value() const { 54 return n_ != 0; 55 } T()56 operator T() const { 57 return sum_ / n_; 58 } 59 }; 60 61 template <typename T, size_t NTap> 62 class NTapAvgStats { 63 std::array<double, NTap> hist_; 64 size_t cur_idx_; 65 bool ready_; 66 67 public: 68 typedef T value_t; 69 push(T value)70 void push(T value) { 71 hist_[cur_idx_++] = value; 72 if (cur_idx_ >= NTap) { 73 cur_idx_ = 0; 74 ready_ = true; 75 } 76 } has_value()77 inline bool has_value() const { 78 return ready_; 79 } T()80 operator T() const { 81 double out = 0.0; 82 for (double x : hist_) { 83 out += x; 84 } 85 out /= NTap; 86 return out; 87 } 88 }; 89 90 template <uint32_t NTap> 91 struct DtJumpFinder { 92 private: 93 NTapAvgStats<double, NTap> time_avg_; 94 AvgStats<double> dtime_avg_; 95 double compensation_; 96 double threshold_; 97 98 public: 99 // Compensation is a tiny additive to give on delta time so that the algorithm 100 // works smoothly when a sequence of identical timing is ingested, which is 101 // pretty common in our tests. Threshold is simply how many times the new 102 // delta has to be to be recognized as a deviation. 103 DtJumpFinder(double compensation = 0.01, double threshold = 10) time_avg_DtJumpFinder104 : time_avg_(), 105 dtime_avg_(), 106 compensation_(compensation), 107 threshold_(threshold) {} 108 109 // Returns true if the delta time regarding to the last data point seems 110 // normal; returns false if it seems the new data point is too much away from 111 // the historical records. pushDtJumpFinder112 bool push(double time) { 113 if (time_avg_.has_value()) { 114 double dtime = std::abs(time - time_avg_) + (compensation_ * time_avg_); 115 if (dtime_avg_.has_value()) { 116 double ddtime = std::abs(dtime - dtime_avg_); 117 if (ddtime > threshold_ * dtime_avg_) { 118 return true; 119 } 120 } 121 dtime_avg_.push(dtime); 122 } 123 time_avg_.push(time); 124 return false; 125 } 126 dtime_avgDtJumpFinder127 double dtime_avg() const { 128 return dtime_avg_; 129 } compensate_timeDtJumpFinder130 double compensate_time() const { 131 return compensation_ * time_avg_; 132 } 133 }; 134