stats: added Histogram, UniformSample and SampleSnapshot

1 files changed, 254 insertions, 3 deletions

diff --git a/zencore/stats.cpp b/zencore/stats.cpp
index 9ae2ddd28..2a9b0a06f 100644
--- a/zencore/stats.cpp
+++ b/zencore/stats.cpp
@@ -1,10 +1,13 @@
 // Copyright Epic Games, Inc. All Rights Reserved.
 
 #include "zencore/stats.h"
-#include <cmath>
+#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 +16,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;
@@ -162,9 +165,254 @@ 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;
+}
+
+//////////////////////////////////////////////////////////////////////////
+
 #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 +510,9 @@ TEST_CASE("Meter")
 	[[maybe_unused]] double Rate = Meter1.MeanRate();
 }
 #	endif
+}
+
+namespace zen {
 
 void
 stats_forcelink()