summaryrefslogtreecommitdiffstats
path: root/ml/Tests.cc
diff options
context:
space:
mode:
authorDaniel Baumann <daniel.baumann@progress-linux.org>2021-12-01 06:15:04 +0000
committerDaniel Baumann <daniel.baumann@progress-linux.org>2021-12-01 06:15:04 +0000
commite970e0b37b8bd7f246feb3f70c4136418225e434 (patch)
tree0b67c0ca45f56f2f9d9c5c2e725279ecdf52d2eb /ml/Tests.cc
parentAdding upstream version 1.31.0. (diff)
downloadnetdata-e970e0b37b8bd7f246feb3f70c4136418225e434.tar.xz
netdata-e970e0b37b8bd7f246feb3f70c4136418225e434.zip
Adding upstream version 1.32.0.upstream/1.32.0
Signed-off-by: Daniel Baumann <daniel.baumann@progress-linux.org>
Diffstat (limited to 'ml/Tests.cc')
-rw-r--r--ml/Tests.cc301
1 files changed, 301 insertions, 0 deletions
diff --git a/ml/Tests.cc b/ml/Tests.cc
new file mode 100644
index 000000000..7d369d48d
--- /dev/null
+++ b/ml/Tests.cc
@@ -0,0 +1,301 @@
+// SPDX-License-Identifier: GPL-3.0-or-later
+
+#include "BitBufferCounter.h"
+#include "BitRateWindow.h"
+
+#include "gtest/gtest.h"
+
+using namespace ml;
+
+TEST(BitBufferCounterTest, Cap_4) {
+ size_t Capacity = 4;
+ BitBufferCounter BBC(Capacity);
+
+ // No bits set
+ EXPECT_EQ(BBC.numSetBits(), 0);
+
+ // All ones
+ for (size_t Idx = 0; Idx != (2 * Capacity); Idx++) {
+ BBC.insert(true);
+
+ EXPECT_EQ(BBC.numSetBits(), std::min(Idx + 1, Capacity));
+ }
+
+ // All zeroes
+ for (size_t Idx = 0; Idx != Capacity; Idx++) {
+ BBC.insert(false);
+
+ if (Idx < Capacity)
+ EXPECT_EQ(BBC.numSetBits(), Capacity - (Idx + 1));
+ else
+ EXPECT_EQ(BBC.numSetBits(), 0);
+ }
+
+ // Even ones/zeroes
+ for (size_t Idx = 0; Idx != (2 * Capacity); Idx++)
+ BBC.insert(Idx % 2 == 0);
+ EXPECT_EQ(BBC.numSetBits(), Capacity / 2);
+}
+
+using State = BitRateWindow::State;
+using Edge = BitRateWindow::Edge;
+using Result = std::pair<Edge, size_t>;
+
+TEST(BitRateWindowTest, Cycles) {
+ /* Test the FSM by going through its two cycles:
+ * 1) NotFilled -> AboveThreshold -> Idle -> NotFilled
+ * 2) NotFilled -> BelowThreshold -> AboveThreshold -> Idle -> NotFilled
+ *
+ * Check the window's length on every new state transition.
+ */
+
+ size_t MinLength = 4, MaxLength = 6, IdleLength = 5;
+ size_t SetBitsThreshold = 3;
+
+ Result R;
+ BitRateWindow BRW(MinLength, MaxLength, IdleLength, SetBitsThreshold);
+
+ /*
+ * 1st cycle
+ */
+
+ // NotFilled -> AboveThreshold
+ R = BRW.insert(true);
+ EXPECT_EQ(R.first, std::make_pair(State::NotFilled, State::NotFilled));
+ R = BRW.insert(true);
+ EXPECT_EQ(R.first, std::make_pair(State::NotFilled, State::NotFilled));
+ R = BRW.insert(true);
+ EXPECT_EQ(R.first, std::make_pair(State::NotFilled, State::NotFilled));
+ R = BRW.insert(true);
+ EXPECT_EQ(R.first, std::make_pair(State::NotFilled, State::AboveThreshold));
+ EXPECT_EQ(R.second, MinLength);
+
+ // AboveThreshold -> Idle
+ R = BRW.insert(true);
+ EXPECT_EQ(R.first, std::make_pair(State::AboveThreshold, State::AboveThreshold));
+ R = BRW.insert(true);
+ EXPECT_EQ(R.first, std::make_pair(State::AboveThreshold, State::AboveThreshold));
+
+ R = BRW.insert(true);
+ EXPECT_EQ(R.first, std::make_pair(State::AboveThreshold, State::Idle));
+ EXPECT_EQ(R.second, MaxLength);
+
+
+ // Idle -> NotFilled
+ R = BRW.insert(true);
+ EXPECT_EQ(R.first, std::make_pair(State::Idle, State::Idle));
+ R = BRW.insert(true);
+ EXPECT_EQ(R.first, std::make_pair(State::Idle, State::Idle));
+ R = BRW.insert(true);
+ EXPECT_EQ(R.first, std::make_pair(State::Idle, State::Idle));
+ R = BRW.insert(true);
+ EXPECT_EQ(R.first, std::make_pair(State::Idle, State::Idle));
+ R = BRW.insert(true);
+ EXPECT_EQ(R.first, std::make_pair(State::Idle, State::NotFilled));
+ EXPECT_EQ(R.second, 1);
+
+ // NotFilled -> AboveThreshold
+ R = BRW.insert(true);
+ EXPECT_EQ(R.first, std::make_pair(State::NotFilled, State::NotFilled));
+ R = BRW.insert(true);
+ EXPECT_EQ(R.first, std::make_pair(State::NotFilled, State::NotFilled));
+ R = BRW.insert(true);
+ EXPECT_EQ(R.first, std::make_pair(State::NotFilled, State::AboveThreshold));
+ EXPECT_EQ(R.second, MinLength);
+
+ /*
+ * 2nd cycle
+ */
+
+ BRW = BitRateWindow(MinLength, MaxLength, IdleLength, SetBitsThreshold);
+
+ // NotFilled -> BelowThreshold
+ R = BRW.insert(false);
+ EXPECT_EQ(R.first, std::make_pair(State::NotFilled, State::NotFilled));
+ R = BRW.insert(false);
+ EXPECT_EQ(R.first, std::make_pair(State::NotFilled, State::NotFilled));
+ R = BRW.insert(false);
+ EXPECT_EQ(R.first, std::make_pair(State::NotFilled, State::NotFilled));
+ R = BRW.insert(false);
+ EXPECT_EQ(R.first, std::make_pair(State::NotFilled, State::BelowThreshold));
+ EXPECT_EQ(R.second, MinLength);
+
+ // BelowThreshold -> BelowThreshold:
+ // Check the state's self loop by adding set bits that will keep the
+ // bit buffer below the specified threshold.
+ //
+ for (size_t Idx = 0; Idx != 2 * MaxLength; Idx++) {
+ R = BRW.insert(Idx % 2 == 0);
+ EXPECT_EQ(R.first, std::make_pair(State::BelowThreshold, State::BelowThreshold));
+ EXPECT_EQ(R.second, MinLength);
+ }
+
+ // Verify that at the end of the loop the internal bit buffer contains
+ // "1010". Do so by adding one set bit and checking that we remain below
+ // the specified threshold.
+ R = BRW.insert(true);
+ EXPECT_EQ(R.first, std::make_pair(State::BelowThreshold, State::BelowThreshold));
+ EXPECT_EQ(R.second, MinLength);
+
+ // BelowThreshold -> AboveThreshold
+ R = BRW.insert(true);
+ EXPECT_EQ(R.first, std::make_pair(State::BelowThreshold, State::AboveThreshold));
+ EXPECT_EQ(R.second, MinLength);
+
+ // AboveThreshold -> Idle:
+ // Do the transition without filling the max window size this time.
+ R = BRW.insert(false);
+ EXPECT_EQ(R.first, std::make_pair(State::AboveThreshold, State::Idle));
+ EXPECT_EQ(R.second, MinLength);
+
+ // Idle -> NotFilled
+ R = BRW.insert(false);
+ EXPECT_EQ(R.first, std::make_pair(State::Idle, State::Idle));
+ R = BRW.insert(false);
+ EXPECT_EQ(R.first, std::make_pair(State::Idle, State::Idle));
+ R = BRW.insert(false);
+ EXPECT_EQ(R.first, std::make_pair(State::Idle, State::Idle));
+ R = BRW.insert(false);
+ EXPECT_EQ(R.first, std::make_pair(State::Idle, State::Idle));
+ R = BRW.insert(false);
+ EXPECT_EQ(R.first, std::make_pair(State::Idle, State::NotFilled));
+ EXPECT_EQ(R.second, 1);
+
+ // NotFilled -> AboveThreshold
+ R = BRW.insert(true);
+ EXPECT_EQ(R.first, std::make_pair(State::NotFilled, State::NotFilled));
+ R = BRW.insert(true);
+ EXPECT_EQ(R.first, std::make_pair(State::NotFilled, State::NotFilled));
+ R = BRW.insert(true);
+ EXPECT_EQ(R.first, std::make_pair(State::NotFilled, State::AboveThreshold));
+ EXPECT_EQ(R.second, MinLength);
+}
+
+TEST(BitRateWindowTest, ConsecutiveOnes) {
+ size_t MinLength = 120, MaxLength = 240, IdleLength = 30;
+ size_t SetBitsThreshold = 30;
+
+ Result R;
+ BitRateWindow BRW(MinLength, MaxLength, IdleLength, SetBitsThreshold);
+
+ for (size_t Idx = 0; Idx != MaxLength; Idx++)
+ R = BRW.insert(false);
+ EXPECT_EQ(R.first, std::make_pair(State::BelowThreshold, State::BelowThreshold));
+ EXPECT_EQ(R.second, MinLength);
+
+ for (size_t Idx = 0; Idx != SetBitsThreshold; Idx++) {
+ EXPECT_EQ(R.first, std::make_pair(State::BelowThreshold, State::BelowThreshold));
+ R = BRW.insert(true);
+ }
+ EXPECT_EQ(R.first, std::make_pair(State::BelowThreshold, State::AboveThreshold));
+ EXPECT_EQ(R.second, MinLength);
+
+ // At this point the window's buffer contains:
+ // (MinLength - SetBitsThreshold = 90) 0s, followed by
+ // (SetBitsThreshold = 30) 1s.
+ //
+ // To go below the threshold, we need to add (90 + 1) more 0s in the window's
+ // buffer. At that point, the the window's buffer will contain:
+ // (SetBitsThreshold = 29) 1s, followed by
+ // (MinLength - SetBitsThreshold = 91) 0s.
+ //
+ // Right before adding the last 0, we expect the window's length to be equal to 210,
+ // because the bit buffer has gone through these bits:
+ // (MinLength - SetBitsThreshold = 90) 0s, followed by
+ // (SetBitsThreshold = 30) 1s, followed by
+ // (MinLength - SetBitsThreshold = 90) 0s.
+
+ for (size_t Idx = 0; Idx != (MinLength - SetBitsThreshold); Idx++) {
+ R = BRW.insert(false);
+ EXPECT_EQ(R.first, std::make_pair(State::AboveThreshold, State::AboveThreshold));
+ }
+ EXPECT_EQ(R.second, 2 * MinLength - SetBitsThreshold);
+ R = BRW.insert(false);
+ EXPECT_EQ(R.first, std::make_pair(State::AboveThreshold, State::Idle));
+
+ // Continue with the Idle -> NotFilled edge.
+ for (size_t Idx = 0; Idx != IdleLength - 1; Idx++) {
+ R = BRW.insert(false);
+ EXPECT_EQ(R.first, std::make_pair(State::Idle, State::Idle));
+ }
+ R = BRW.insert(false);
+ EXPECT_EQ(R.first, std::make_pair(State::Idle, State::NotFilled));
+ EXPECT_EQ(R.second, 1);
+}
+
+TEST(BitRateWindowTest, WithHoles) {
+ size_t MinLength = 120, MaxLength = 240, IdleLength = 30;
+ size_t SetBitsThreshold = 30;
+
+ Result R;
+ BitRateWindow BRW(MinLength, MaxLength, IdleLength, SetBitsThreshold);
+
+ for (size_t Idx = 0; Idx != MaxLength; Idx++)
+ R = BRW.insert(false);
+
+ for (size_t Idx = 0; Idx != SetBitsThreshold / 3; Idx++)
+ R = BRW.insert(true);
+ for (size_t Idx = 0; Idx != SetBitsThreshold / 3; Idx++)
+ R = BRW.insert(false);
+ for (size_t Idx = 0; Idx != SetBitsThreshold / 3; Idx++)
+ R = BRW.insert(true);
+ for (size_t Idx = 0; Idx != SetBitsThreshold / 3; Idx++)
+ R = BRW.insert(false);
+ for (size_t Idx = 0; Idx != SetBitsThreshold / 3; Idx++)
+ R = BRW.insert(true);
+
+ EXPECT_EQ(R.first, std::make_pair(State::BelowThreshold, State::AboveThreshold));
+ EXPECT_EQ(R.second, MinLength);
+
+ // The window's bit buffer contains:
+ // 70 0s, 10 1s, 10 0s, 10 1s, 10 0s, 10 1s.
+ // Where: 70 = MinLength - (5 / 3) * SetBitsThresholds, ie. we need
+ // to add (70 + 1) more zeros to make the bit buffer go below the
+ // threshold and then the window's length should be:
+ // 70 + 50 + 70 = 190.
+
+ BitRateWindow::Edge E;
+ do {
+ R = BRW.insert(false);
+ E = R.first;
+ } while (E.first != State::AboveThreshold || E.second != State::Idle);
+ EXPECT_EQ(R.second, 2 * MinLength - (5 * SetBitsThreshold) / 3);
+}
+
+TEST(BitRateWindowTest, MinWindow) {
+ size_t MinLength = 120, MaxLength = 240, IdleLength = 30;
+ size_t SetBitsThreshold = 30;
+
+ Result R;
+ BitRateWindow BRW(MinLength, MaxLength, IdleLength, SetBitsThreshold);
+
+ BRW.insert(true);
+ BRW.insert(false);
+ for (size_t Idx = 2; Idx != SetBitsThreshold; Idx++)
+ BRW.insert(true);
+ for (size_t Idx = SetBitsThreshold; Idx != MinLength - 1; Idx++)
+ BRW.insert(false);
+
+ R = BRW.insert(true);
+ EXPECT_EQ(R.first, std::make_pair(State::NotFilled, State::AboveThreshold));
+ EXPECT_EQ(R.second, MinLength);
+
+ R = BRW.insert(false);
+ EXPECT_EQ(R.first, std::make_pair(State::AboveThreshold, State::Idle));
+}
+
+TEST(BitRateWindowTest, MaxWindow) {
+ size_t MinLength = 100, MaxLength = 200, IdleLength = 30;
+ size_t SetBitsThreshold = 50;
+
+ Result R;
+ BitRateWindow BRW(MinLength, MaxLength, IdleLength, SetBitsThreshold);
+
+ for (size_t Idx = 0; Idx != MaxLength; Idx++)
+ R = BRW.insert(Idx % 2 == 0);
+ EXPECT_EQ(R.first, std::make_pair(State::AboveThreshold, State::AboveThreshold));
+ EXPECT_EQ(R.second, MaxLength);
+
+ R = BRW.insert(false);
+ EXPECT_EQ(R.first, std::make_pair(State::AboveThreshold, State::Idle));
+}