1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173 174 175 176 177 178 179 180 181 182 183 184 185 186 187 188 189 190 191 192 193 194 195 196 197 198 199 200 201
//! Provides a helper which computes a average of a series of values.
//!
//! This is intended to be used when measuring the system performance which is often tracked as
//! averages (e.g. execution duration of commands).
//!
//! An [Average](Average) is internally mutable without needing a mutable reference as we rely on
//! atomic intrinsics as provided by modern processors / compilers.
//!
//! # Example
//!
//! ```
//! # use apollo_framework::average::Average;
//! let avg = Average::new();
//! avg.add(10);
//! avg.add(20);
//! avg.add(30);
//!
//! assert_eq!(avg.avg(), 20);
//! assert_eq!(avg.count(), 3);
//! ```
use crate::fmt::format_micros;
use std::fmt;
use std::fmt::Display;
use std::sync::atomic::{AtomicU64, Ordering};
/// Computes a sliding average of a series of values.
///
/// This is intended to record performance measurements and to keep track of the sliding average
/// as well as the total number of recorded values.
///
/// Note that this class overflows gracefully.
///
/// # Example
///
/// ```
/// # use apollo_framework::average::Average;
/// let avg = Average::new();
/// avg.add(10);
/// avg.add(20);
/// avg.add(30);
///
/// assert_eq!(avg.avg(), 20);
/// assert_eq!(avg.count(), 3);
/// ```
#[derive(Default)]
pub struct Average {
sum_and_count: AtomicU64,
count: AtomicU64,
}
impl Clone for Average {
fn clone(&self) -> Self {
Average {
sum_and_count: AtomicU64::new(self.sum_and_count.load(Ordering::Relaxed)),
count: AtomicU64::new(self.count.load(Ordering::Relaxed)),
}
}
}
impl Average {
/// Creates a new average.
pub fn new() -> Average {
Average {
sum_and_count: AtomicU64::new(0),
count: AtomicU64::new(0),
}
}
fn sum_and_count(&self) -> (i32, i32) {
let last_sum_and_count = self.sum_and_count.load(Ordering::Relaxed);
let count = (last_sum_and_count & 0xFFFFFFFF) as i32;
let sum = ((last_sum_and_count >> 32) & 0xFFFFFFFF) as i32;
(sum, count)
}
/// Adds another value to be added to the average calculation.
///
/// Internally we simply update the global u64 counter to keep track of the total recorded
/// values. Additionally, we have another u64 which is split into two i32 fields. One of these
/// is used to keep the actual count of the sliding average and another is used to store the
/// sum of the values.
///
/// Whenever we recorded 100 values or the sum counter might overflow, we divide both values
/// by two and add the new values. This yields a sliding average which is fit for our purposes.
///
/// As the main task is to store the average duration of a task in microseconds, the i32 sum
/// field shouldn't overflow under normal conditions.
///
/// We perform this trickery (splitting a single field into two) so that this algorithm is
/// completely lock and wait free, as we only utilize atomic load and store operations. This
/// guarantees correctness while ensuring maximal performance.
pub fn add(&self, value: i32) {
let _ = self.count.fetch_add(1, Ordering::Relaxed);
let (mut sum, mut count) = self.sum_and_count();
while count > 100 || sum as i64 + value as i64 > i32::MAX as i64 {
sum = count / 2 * sum / count;
count /= 2;
}
sum += value;
count += 1;
let next_sum_and_count = (sum as u64 & 0xFFFFFFFF) << 32 | (count as u64 & 0xFFFFFFFF);
self.sum_and_count
.store(next_sum_and_count, Ordering::Relaxed);
}
/// Returns the total number of recorded values (unless an overflow of the internal u64 counter
/// occurred).
pub fn count(&self) -> u64 {
self.count.load(Ordering::Relaxed)
}
/// Computes the sliding average of the last 100 values.
pub fn avg(&self) -> i32 {
let (sum, count) = self.sum_and_count();
if sum == 0 {
0
} else {
sum / count
}
}
}
impl Display for Average {
fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
format_micros(self.avg(), f)?;
write!(f, " ({})", self.count())?;
Ok(())
}
}
#[cfg(test)]
mod test {
use crate::average::Average;
#[test]
fn empty_average_is_properly_initialized() {
let avg = Average::new();
assert_eq!(avg.avg(), 0);
assert_eq!(avg.count(), 0);
}
#[test]
fn average_with_some_values_works() {
let avg = Average::new();
for i in 1..=10 {
avg.add(i);
}
assert_eq!(avg.avg(), 5);
assert_eq!(avg.count(), 10);
}
#[test]
fn formatting_average_works() {
let avg = Average::new();
avg.add(10_123);
assert_eq!(format!("{}", avg), "10.1 ms (1)");
}
#[test]
fn average_with_many_values_keeps_count() {
let avg = Average::new();
for i in 1..=1000 {
avg.add(i);
}
assert_eq!(avg.avg(), 928);
assert_eq!(avg.count(), 1000);
}
#[test]
fn average_overflows_sanely() {
{
let avg = Average::new();
avg.add(i32::MAX);
assert_eq!(avg.avg(), i32::MAX);
avg.add(i32::MAX);
assert_eq!(avg.avg(), i32::MAX);
avg.add(i32::MAX / 2);
avg.add(i32::MAX / 2);
assert_eq!(avg.avg(), i32::MAX / 2);
}
{
let avg = Average::new();
avg.add(10);
avg.add(i32::MAX - 50);
avg.add(60);
// If an overflow occurs, we compute the internal average (in this case the average of
// 10 and std::i32::MAX - 50. We then accept the next value (60) and compute the average
// between these two as result...
let average_before_overflow = (i32::MAX - 50 + 10) / 2;
let expected_average = (average_before_overflow + 60) / 2;
assert_eq!(avg.avg(), expected_average);
}
}
}