moved source directories into `/src` (#264)

* moved source directories into `/src`
* updated bundle.lua for new `src` path
* moved some docs, icon
* removed old test trees

1 files changed, 715 insertions, 0 deletions

diff --git a/src/zencore/stats.cpp b/src/zencore/stats.cpp
new file mode 100644
index 000000000..372bc42f8
--- /dev/null
+++ b/src/zencore/stats.cpp
@@ -0,0 +1,715 @@
+// Copyright Epic Games, Inc. All Rights Reserved.
+
+#include "zencore/stats.h"
+
+#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
+
+//
+// Derived from https://github.com/dln/medida/blob/master/src/medida/stats/ewma.cc
+//
+
+namespace zen::metrics {
+
+static constinit int	kTickIntervalInSeconds = 5;
+static constinit double kSecondsPerMinute	   = 60.0;
+static constinit int	kOneMinute			   = 1;
+static constinit int	kFiveMinutes		   = 5;
+static constinit int	kFifteenMinutes		   = 15;
+
+static const double kM1_ALPHA  = 1.0 - std::exp(-kTickIntervalInSeconds / kSecondsPerMinute / kOneMinute);
+static const double kM5_ALPHA  = 1.0 - std::exp(-kTickIntervalInSeconds / kSecondsPerMinute / kFiveMinutes);
+static const double kM15_ALPHA = 1.0 - std::exp(-kTickIntervalInSeconds / kSecondsPerMinute / kFifteenMinutes);
+
+static const uint64_t CountPerTick	 = GetHifreqTimerFrequencySafe() * kTickIntervalInSeconds;
+static const uint64_t CountPerSecond = GetHifreqTimerFrequencySafe();
+
+//////////////////////////////////////////////////////////////////////////
+
+void
+RawEWMA::Tick(double Alpha, uint64_t Interval, uint64_t Count, bool IsInitialUpdate)
+{
+	const double InstantRate = double(Count) / Interval;
+
+	if (IsInitialUpdate)
+	{
+		m_Rate.store(InstantRate, std::memory_order_release);
+	}
+	else
+	{
+		double Delta = Alpha * (InstantRate - m_Rate);
+
+#if defined(__cpp_lib_atomic_float)
+		m_Rate.fetch_add(Delta);
+#else
+		double Value = m_Rate.load(std::memory_order_acquire);
+		double Next;
+		do
+		{
+			Next = Value + Delta;
+		} while (!m_Rate.compare_exchange_weak(Value, Next, std::memory_order_relaxed));
+#endif
+	}
+}
+
+double
+RawEWMA::Rate() const
+{
+	return m_Rate.load(std::memory_order_relaxed) * CountPerSecond;
+}
+
+//////////////////////////////////////////////////////////////////////////
+
+Meter::Meter() : m_StartTick{GetHifreqTimerValue()}, m_LastTick(m_StartTick.load())
+{
+}
+
+Meter::~Meter()
+{
+}
+
+void
+Meter::TickIfNecessary()
+{
+	uint64_t	   OldTick = m_LastTick.load();
+	const uint64_t NewTick = GetHifreqTimerValue();
+	const uint64_t Age	   = NewTick - OldTick;
+
+	if (Age > CountPerTick)
+	{
+		// Ensure only one thread at a time updates the time. This
+		// works because our tick interval should be sufficiently
+		// long to ensure two threads don't end up inside this block
+
+		if (m_LastTick.compare_exchange_strong(OldTick, NewTick))
+		{
+			m_Remainder.fetch_add(Age);
+
+			do
+			{
+				int64_t Remain = m_Remainder.load(std::memory_order_relaxed);
+
+				if (Remain < 0)
+				{
+					return;
+				}
+
+				if (m_Remainder.compare_exchange_strong(Remain, Remain - CountPerTick))
+				{
+					Tick();
+				}
+			} while (true);
+		}
+	}
+}
+
+void
+Meter::Tick()
+{
+	const uint64_t PendingCount = m_PendingCount.exchange(0);
+	const bool	   IsFirstTick	= m_IsFirstTick;
+
+	if (IsFirstTick)
+	{
+		m_IsFirstTick = false;
+	}
+
+	m_RateM1.Tick(kM1_ALPHA, CountPerTick, PendingCount, IsFirstTick);
+	m_RateM5.Tick(kM5_ALPHA, CountPerTick, PendingCount, IsFirstTick);
+	m_RateM15.Tick(kM15_ALPHA, CountPerTick, PendingCount, IsFirstTick);
+}
+
+double
+Meter::Rate1()
+{
+	TickIfNecessary();
+
+	return m_RateM1.Rate();
+}
+
+double
+Meter::Rate5()
+{
+	TickIfNecessary();
+
+	return m_RateM5.Rate();
+}
+
+double
+Meter::Rate15()
+{
+	TickIfNecessary();
+
+	return m_RateM15.Rate();
+}
+
+double
+Meter::MeanRate() const
+{
+	const uint64_t Count = m_TotalCount.load(std::memory_order_relaxed);
+
+	if (Count == 0)
+	{
+		return 0.0;
+	}
+
+	const uint64_t Elapsed = GetHifreqTimerValue() - m_StartTick;
+
+	return (double(Count) * GetHifreqTimerFrequency()) / Elapsed;
+}
+
+void
+Meter::Mark(uint64_t Count)
+{
+	TickIfNecessary();
+
+	m_TotalCount.fetch_add(Count);
+	m_PendingCount.fetch_add(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, n = int(ValuesSize); i < n; ++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
+{
+	if (m_Count)
+	{
+		return double(m_Sum.load(std::memory_order_relaxed)) / m_Count;
+	}
+	else
+	{
+		return 0.0;
+	}
+}
+
+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()
+{
+	Stop();
+}
+
+void
+OperationTiming::Scope::Stop()
+{
+	if (m_StartTick != 0)
+	{
+		m_Outer.Update(GetHifreqTimerValue() - m_StartTick);
+		m_StartTick = 0;
+	}
+}
+
+void
+OperationTiming::Scope::Cancel()
+{
+	m_StartTick = 0;
+}
+
+//////////////////////////////////////////////////////////////////////////
+
+RequestStats::RequestStats(int32_t SampleCount) : m_RequestTimeHistogram{SampleCount}, m_BytesHistogram{SampleCount}
+{
+}
+
+RequestStats::~RequestStats()
+{
+}
+
+void
+RequestStats::Update(int64_t Duration, int64_t Bytes)
+{
+	m_RequestMeter.Mark(1);
+	m_RequestTimeHistogram.Update(Duration);
+
+	m_BytesMeter.Mark(Bytes);
+	m_BytesHistogram.Update(Bytes);
+}
+
+uint64_t
+RequestStats::Count() const
+{
+	return m_RequestMeter.Count();
+}
+
+//////////////////////////////////////////////////////////////////////////
+
+void
+EmitSnapshot(Meter& Stat, CbObjectWriter& Cbo)
+{
+	Cbo << "count" << Stat.Count();
+	Cbo << "rate_mean" << Stat.MeanRate();
+	Cbo << "rate_1" << Stat.Rate1() << "rate_5" << Stat.Rate5() << "rate_15" << Stat.Rate15();
+}
+
+void
+RequestStats::EmitSnapshot(std::string_view Tag, CbObjectWriter& Cbo)
+{
+	Cbo.BeginObject(Tag);
+
+	Cbo.BeginObject("requests");
+	metrics::EmitSnapshot(m_RequestMeter, Cbo);
+	metrics::EmitSnapshot(m_RequestTimeHistogram, Cbo, GetHifreqTimerToSeconds());
+	Cbo.EndObject();
+
+	Cbo.BeginObject("bytes");
+	metrics::EmitSnapshot(m_BytesMeter, Cbo);
+	metrics::EmitSnapshot(m_BytesHistogram, Cbo, 1.0);
+	Cbo.EndObject();
+
+	Cbo.EndObject();
+}
+
+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, double ConversionFactor)
+{
+	Cbo.BeginObject(Tag);
+	EmitSnapshot(Stat, Cbo, ConversionFactor);
+	Cbo.EndObject();
+}
+
+void
+EmitSnapshot(const Histogram& Stat, CbObjectWriter& Cbo, double ConversionFactor)
+{
+	SampleSnapshot Snap = Stat.Snapshot();
+
+	Cbo << "count" << Stat.Count() * ConversionFactor << "avg" << Stat.Mean() * ConversionFactor;
+	Cbo << "min" << Stat.Min() * ConversionFactor << "max" << Stat.Max() * ConversionFactor;
+	Cbo << "p75" << Snap.Get75Percentile() * ConversionFactor << "p95" << Snap.Get95Percentile() * ConversionFactor << "p99"
+		<< Snap.Get99Percentile() * ConversionFactor << "p999" << Snap.Get999Percentile() * ConversionFactor;
+}
+
+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("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")
+	{
+		RawEWMA Ewma1;
+		Ewma1.Tick(kM1_ALPHA, CountPerSecond, 5, true);
+
+		CHECK(fabs(Ewma1.Rate() - 5) < 0.1);
+
+		for (int i = 0; i < 60; ++i)
+		{
+			Ewma1.Tick(kM1_ALPHA, CountPerSecond, 10, false);
+		}
+
+		CHECK(fabs(Ewma1.Rate() - 10) < 0.1);
+
+		for (int i = 0; i < 60; ++i)
+		{
+			Ewma1.Tick(kM1_ALPHA, CountPerSecond, 20, false);
+		}
+
+		CHECK(fabs(Ewma1.Rate() - 20) < 0.1);
+	}
+
+	SUBCASE("Simple_10")
+	{
+		RawEWMA Ewma1;
+		RawEWMA Ewma5;
+		RawEWMA Ewma15;
+		Ewma1.Tick(kM1_ALPHA, CountPerSecond, 5, true);
+		Ewma5.Tick(kM5_ALPHA, CountPerSecond, 5, true);
+		Ewma15.Tick(kM15_ALPHA, CountPerSecond, 5, true);
+
+		CHECK(fabs(Ewma1.Rate() - 5) < 0.1);
+		CHECK(fabs(Ewma5.Rate() - 5) < 0.1);
+		CHECK(fabs(Ewma15.Rate() - 5) < 0.1);
+
+		auto Tick1	= [&Ewma1](auto Value) { Ewma1.Tick(kM1_ALPHA, CountPerSecond, Value, false); };
+		auto Tick5	= [&Ewma5](auto Value) { Ewma5.Tick(kM5_ALPHA, CountPerSecond, Value, false); };
+		auto Tick15 = [&Ewma15](auto Value) { Ewma15.Tick(kM15_ALPHA, CountPerSecond, Value, false); };
+
+		for (int i = 0; i < 60; ++i)
+		{
+			Tick1(10);
+			Tick5(10);
+			Tick15(10);
+		}
+
+		CHECK(fabs(Ewma1.Rate() - 10) < 0.1);
+
+		for (int i = 0; i < 5 * 60; ++i)
+		{
+			Tick1(20);
+			Tick5(20);
+			Tick15(20);
+		}
+
+		CHECK(fabs(Ewma1.Rate() - 20) < 0.1);
+		CHECK(fabs(Ewma5.Rate() - 20) < 0.1);
+
+		for (int i = 0; i < 16 * 60; ++i)
+		{
+			Tick1(100);
+			Tick5(100);
+			Tick15(100);
+		}
+
+		CHECK(fabs(Ewma1.Rate() - 100) < 0.1);
+		CHECK(fabs(Ewma5.Rate() - 100) < 0.1);
+		CHECK(fabs(Ewma15.Rate() - 100) < 0.5);
+	}
+}
+
+#	if 0  // This is not really a unit test, but mildly useful to exercise some code
+TEST_CASE("Meter")
+{
+	Meter Meter1;
+	Meter1.Mark(1);
+	Sleep(1000);
+	Meter1.Mark(1);
+	Sleep(1000);
+	Meter1.Mark(1);
+	Sleep(1000);
+	Meter1.Mark(1);
+	Sleep(1000);
+	Meter1.Mark(1);
+	Sleep(1000);
+	Meter1.Mark(1);
+	Sleep(1000);
+	Meter1.Mark(1);
+	Sleep(1000);
+	Meter1.Mark(1);
+	Sleep(1000);
+	Meter1.Mark(1);
+	Sleep(1000);
+	[[maybe_unused]] double Rate = Meter1.MeanRate();
+}
+#	endif
+}
+
+namespace zen {
+
+void
+stats_forcelink()
+{
+}
+
+#endif
+
+}  // namespace zen::metrics