diff options
Diffstat (limited to 'zencore/stats.cpp')
| -rw-r--r-- | zencore/stats.cpp | 367 |
1 files changed, 360 insertions, 7 deletions
diff --git a/zencore/stats.cpp b/zencore/stats.cpp index 9ae2ddd28..34dc2828f 100644 --- a/zencore/stats.cpp +++ b/zencore/stats.cpp @@ -1,10 +1,15 @@ // Copyright Epic Games, Inc. All Rights Reserved. #include "zencore/stats.h" -#include <cmath> + +#include <zencore/compactbinarybuilder.h> +#include "zencore/intmath.h" #include "zencore/thread.h" #include "zencore/timer.h" +#include <cmath> +#include <gsl/gsl-lite.hpp> + #if ZEN_WITH_TESTS # include <zencore/testing.h> #endif @@ -13,7 +18,7 @@ // Derived from https://github.com/dln/medida/blob/master/src/medida/stats/ewma.cc // -namespace zen { +namespace zen::metrics { static constinit int kTickIntervalInSeconds = 5; static constinit double kSecondsPerMinute = 60.0; @@ -76,18 +81,18 @@ Meter::TickIfNecessary() if (m_LastTick.compare_exchange_strong(OldTick, NewTick)) { - m_Remain.fetch_add(Age); + m_Remainder.fetch_add(Age); do { - int64_t Remain = m_Remain.load(std::memory_order_relaxed); + int64_t Remain = m_Remainder.load(std::memory_order_relaxed); if (Remain < 0) { return; } - if (m_Remain.compare_exchange_strong(Remain, Remain - CountPerTick)) + if (m_Remainder.compare_exchange_strong(Remain, Remain - CountPerTick)) { Tick(); } @@ -137,7 +142,7 @@ Meter::Rate15() } double -Meter::MeanRate() +Meter::MeanRate() const { const uint64_t Count = m_TotalCount.load(std::memory_order_relaxed); @@ -162,9 +167,354 @@ Meter::Mark(uint64_t Count) ////////////////////////////////////////////////////////////////////////// +// TODO: should consider a cheaper RNG here, this will run for every thread +// that gets created + +thread_local std::mt19937_64 ThreadLocalRng; + +UniformSample::UniformSample(uint32_t ReservoirSize) : m_Values(ReservoirSize) +{ +} + +UniformSample::~UniformSample() +{ +} + +void +UniformSample::Clear() +{ + for (auto& Value : m_Values) + { + Value.store(0); + } + m_SampleCounter = 0; +} + +uint32_t +UniformSample::Size() const +{ + return gsl::narrow_cast<uint32_t>(Min(m_SampleCounter.load(), m_Values.size())); +} + +void +UniformSample::Update(int64_t Value) +{ + const uint64_t Count = m_SampleCounter++; + const uint64_t Size = m_Values.size(); + + if (Count < Size) + { + m_Values[Count] = Value; + } + else + { + // Randomly choose an old entry to potentially replace (the probability + // of replacing an entry diminishes with time) + + std::uniform_int_distribution<uint64_t> UniformDist(0, Count); + uint64_t SampleIndex = UniformDist(ThreadLocalRng); + + if (SampleIndex < Size) + { + m_Values[SampleIndex].store(Value, std::memory_order_release); + } + } +} + +SampleSnapshot +UniformSample::Snapshot() const +{ + uint64_t ValuesSize = Size(); + std::vector<double> Values(ValuesSize); + + for (int i = 0; i < ValuesSize; ++i) + { + Values[i] = double(m_Values[i]); + } + + return SampleSnapshot(std::move(Values)); +} + +////////////////////////////////////////////////////////////////////////// + +Histogram::Histogram(int32_t SampleCount) : m_Sample(SampleCount) +{ +} + +Histogram::~Histogram() +{ +} + +void +Histogram::Clear() +{ + m_Min = m_Max = m_Sum = m_Count = 0; + m_Sample.Clear(); +} + +void +Histogram::Update(int64_t Value) +{ + m_Sample.Update(Value); + + if (m_Count == 0) + { + m_Min = m_Max = Value; + } + else + { + int64_t CurrentMax = m_Max.load(std::memory_order_relaxed); + + while ((CurrentMax < Value) && !m_Max.compare_exchange_weak(CurrentMax, Value)) + { + } + + int64_t CurrentMin = m_Min.load(std::memory_order_relaxed); + + while ((CurrentMin > Value) && !m_Min.compare_exchange_weak(CurrentMin, Value)) + { + } + } + + m_Sum += Value; + ++m_Count; +} + +int64_t +Histogram::Max() const +{ + return m_Max.load(std::memory_order_relaxed); +} + +int64_t +Histogram::Min() const +{ + return m_Min.load(std::memory_order_relaxed); +} + +double +Histogram::Mean() const +{ + return double(m_Sum.load(std::memory_order_relaxed)) / m_Count; +} + +uint64_t +Histogram::Count() const +{ + return m_Count.load(std::memory_order_relaxed); +} + +////////////////////////////////////////////////////////////////////////// + +SampleSnapshot::SampleSnapshot(std::vector<double>&& Values) : m_Values(std::move(Values)) +{ + std::sort(begin(m_Values), end(m_Values)); +} + +SampleSnapshot::~SampleSnapshot() +{ +} + +double +SampleSnapshot::GetQuantileValue(double Quantile) +{ + ZEN_ASSERT((Quantile >= 0.0) && (Quantile <= 1.0)); + + if (m_Values.empty()) + { + return 0.0; + } + + const double Pos = Quantile * (m_Values.size() + 1); + + if (Pos < 1) + { + return m_Values.front(); + } + + if (Pos >= m_Values.size()) + { + return m_Values.back(); + } + + const int32_t Index = (int32_t)Pos; + const double Lower = m_Values[Index - 1]; + const double Upper = m_Values[Index]; + + // Lerp + return Lower + (Pos - std::floor(Pos)) * (Upper - Lower); +} + +const std::vector<double>& +SampleSnapshot::GetValues() const +{ + return m_Values; +} + +////////////////////////////////////////////////////////////////////////// + +OperationTiming::OperationTiming(int32_t SampleCount) : m_Histogram{SampleCount} +{ +} + +OperationTiming::~OperationTiming() +{ +} + +void +OperationTiming::Update(int64_t Duration) +{ + m_Meter.Mark(1); + m_Histogram.Update(Duration); +} + +int64_t +OperationTiming::Max() const +{ + return m_Histogram.Max(); +} + +int64_t +OperationTiming::Min() const +{ + return m_Histogram.Min(); +} + +double +OperationTiming::Mean() const +{ + return m_Histogram.Mean(); +} + +uint64_t +OperationTiming::Count() const +{ + return m_Meter.Count(); +} + +OperationTiming::Scope::Scope(OperationTiming& Outer) : m_Outer(Outer), m_StartTick(GetHifreqTimerValue()) +{ +} + +OperationTiming::Scope::~Scope() +{ + m_Outer.Update(GetHifreqTimerValue() - m_StartTick); +} + +////////////////////////////////////////////////////////////////////////// + +void +EmitSnapshot(std::string_view Tag, OperationTiming& Stat, CbObjectWriter& Cbo) +{ + Cbo.BeginObject(Tag); + + SampleSnapshot Snap = Stat.Snapshot(); + + Cbo << "count" << Stat.Count(); + + Cbo << "rate_mean" << Stat.MeanRate(); + Cbo << "rate_1" << Stat.Rate1() << "rate_5" << Stat.Rate5() << "rate_15" << Stat.Rate15(); + + const double ToSeconds = GetHifreqTimerToSeconds(); + + Cbo << "t_avg" << Stat.Mean() * ToSeconds; + Cbo << "t_min" << Stat.Min() * ToSeconds << "t_max" << Stat.Max() * ToSeconds; + Cbo << "t_p75" << Snap.Get75Percentile() * ToSeconds << "t_p95" << Snap.Get95Percentile() * ToSeconds << "t_p99" + << Snap.Get99Percentile() * ToSeconds << "t_p999" << Snap.Get999Percentile() * ToSeconds; + + Cbo.EndObject(); +} + +void +EmitSnapshot(std::string_view Tag, const Histogram& Stat, CbObjectWriter& Cbo) +{ + Cbo.BeginObject(Tag); + + SampleSnapshot Snap = Stat.Snapshot(); + + Cbo << "count" << Stat.Count() << "avg" << Stat.Mean(); + Cbo << "min" << Stat.Min() << "max" << Stat.Max(); + Cbo << "p75" << Snap.Get75Percentile() << "p95" << Snap.Get95Percentile() << "p99" << Snap.Get99Percentile() << "p999" + << Snap.Get999Percentile(); + + Cbo.EndObject(); +} + +void +EmitSnapshot(std::string_view Tag, Meter& Stat, CbObjectWriter& Cbo) +{ + Cbo.BeginObject(Tag); + + Cbo << "count" << Stat.Count() << "rate_mean" << Stat.MeanRate(); + Cbo << "rate_1" << Stat.Rate1() << "rate_5" << Stat.Rate5() << "rate_15" << Stat.Rate15(); + + Cbo.EndObject(); +} + +////////////////////////////////////////////////////////////////////////// + #if ZEN_WITH_TESTS -TEST_CASE("EWMA") +TEST_CASE("Core.Stats.Histogram") +{ + Histogram Histo{258}; + + SampleSnapshot Snap1 = Histo.Snapshot(); + CHECK_EQ(Snap1.Size(), 0); + CHECK_EQ(Snap1.GetMedian(), 0); + + Histo.Update(1); + CHECK_EQ(Histo.Min(), 1); + CHECK_EQ(Histo.Max(), 1); + + SampleSnapshot Snap2 = Histo.Snapshot(); + CHECK_EQ(Snap2.Size(), 1); + + Histo.Update(2); + CHECK_EQ(Histo.Min(), 1); + CHECK_EQ(Histo.Max(), 2); + + SampleSnapshot Snap3 = Histo.Snapshot(); + CHECK_EQ(Snap3.Size(), 2); + + Histo.Update(-2); + CHECK_EQ(Histo.Min(), -2); + CHECK_EQ(Histo.Max(), 2); + CHECK_EQ(Histo.Mean(), 1 / 3.0); + + SampleSnapshot Snap4 = Histo.Snapshot(); + CHECK_EQ(Snap4.Size(), 3); + CHECK_EQ(Snap4.GetMedian(), 1); + CHECK_EQ(Snap4.Get999Percentile(), 2); + CHECK_EQ(Snap4.GetQuantileValue(0), -2); +} + +TEST_CASE("Core.Stats.UniformSample") +{ + UniformSample Sample1{100}; + + for (int i = 0; i < 100; ++i) + { + for (int j = 1; j <= 100; ++j) + { + Sample1.Update(j); + } + } + + int64_t Sum = 0; + int64_t Count = 0; + + Sample1.IterateValues([&](int64_t Value) { + ++Count; + Sum += Value; + }); + + double Average = double(Sum) / Count; + + CHECK(fabs(Average - 50) < 10); // What's the right test here? The result could vary massively and still be technically correct +} + +TEST_CASE("Core.Stats.EWMA") { SUBCASE("Simple_1") { @@ -262,6 +612,9 @@ TEST_CASE("Meter") [[maybe_unused]] double Rate = Meter1.MeanRate(); } # endif +} + +namespace zen { void stats_forcelink() |