Merged main

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()