1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
|
#include "percentile_lg.h"
#include <library/cpp/testing/unittest/registar.h>
using namespace NMonitoring;
Y_UNIT_TEST_SUITE(PercentileTest) {
template<size_t A, size_t B, size_t B_BEGIN>
void printSizeAndLimit() {
using TPerc = TPercentileTrackerLg<A, B, 15>;
Cout << "TPercentileTrackerLg<" << A << ", " << B << ", 15>"
<< "; sizeof# " << LeftPad(HumanReadableSize(sizeof(TPerc), SF_BYTES), 7)
<< "; max_granularity# " << LeftPad(HumanReadableSize(TPerc::MAX_GRANULARITY, SF_QUANTITY), 5)
<< "; limit# " << LeftPad(HumanReadableSize(TPerc::TRACKER_LIMIT , SF_QUANTITY), 5) << Endl;
if constexpr (B > 1) {
printSizeAndLimit<A, B - 1, B_BEGIN>();
} else if constexpr (A > 1) {
Cout << Endl;
printSizeAndLimit<A - 1, B_BEGIN, B_BEGIN>();
}
}
Y_UNIT_TEST(PrintTrackerLgSizeAndLimits) {
printSizeAndLimit<10, 5, 5>();
}
Y_UNIT_TEST(TrackerLimitTest) {
{
using TPerc = TPercentileTrackerLg<1, 0, 1>;
TPerc tracker;
tracker.Increment(Max<size_t>());
UNIT_ASSERT_EQUAL(TPerc::TRACKER_LIMIT, tracker.GetPercentile(1.0));
}
{
using TPerc = TPercentileTrackerLg<1, 1, 1>;
TPerc tracker;
tracker.Increment(Max<size_t>());
UNIT_ASSERT_EQUAL(TPerc::TRACKER_LIMIT, tracker.GetPercentile(1.0));
}
{
using TPerc = TPercentileTrackerLg<1, 5, 1>;
TPerc tracker;
tracker.Increment(Max<size_t>());
UNIT_ASSERT_EQUAL(TPerc::TRACKER_LIMIT, tracker.GetPercentile(1.0));
}
{
using TPerc = TPercentileTrackerLg<2, 1, 1>;
TPerc tracker;
tracker.Increment(Max<size_t>());
UNIT_ASSERT_EQUAL(TPerc::TRACKER_LIMIT, tracker.GetPercentile(1.0));
}
{
using TPerc = TPercentileTrackerLg<5, 4, 1>;
TPerc tracker;
tracker.Increment(Max<size_t>());
UNIT_ASSERT_EQUAL(TPerc::TRACKER_LIMIT, tracker.GetPercentile(1.0));
}
}
Y_UNIT_TEST(BucketIdxIfvsBucketIdxBinarySearch) {
for (size_t var = 0; var < 5; var++) {
if (var == 0) {
TPercentileTrackerLg<3, 2, 15> tracker;
for (size_t i = 0; i < 3000000; i += 1) {
size_t num1 = tracker.BucketIdxMostSignificantBit(i);
size_t num2 = tracker.BucketIdxBinarySearch(i);
UNIT_ASSERT_EQUAL(num1, num2);
}
} else if (var == 1) {
TPercentileTrackerLg<4, 4, 15> tracker;
for (size_t i = 0; i < 3000000; i += 1) {
size_t num1 = tracker.BucketIdxMostSignificantBit(i);
size_t num2 = tracker.BucketIdxBinarySearch(i);
UNIT_ASSERT_EQUAL(num1, num2);
}
} else if (var == 2) {
TPercentileTrackerLg<5, 3, 15> tracker;
for (size_t i = 0; i < 3000000; i += 1) {
size_t num1 = tracker.BucketIdxMostSignificantBit(i);
size_t num2 = tracker.BucketIdxBinarySearch(i);
size_t num3 = tracker.BucketIdxIf(i);
UNIT_ASSERT_EQUAL(num1, num2);
UNIT_ASSERT_EQUAL(num2, num3);
}
} else if (var == 3) {
TPercentileTrackerLg<5, 4, 15> tracker;
for (size_t i = 0; i < 3000000; i += 1) {
size_t num1 = tracker.BucketIdxMostSignificantBit(i);
size_t num2 = tracker.BucketIdxBinarySearch(i);
size_t num3 = tracker.BucketIdxIf(i);
UNIT_ASSERT_EQUAL(num1, num2);
UNIT_ASSERT_EQUAL(num2, num3);
}
} else if (var == 4) {
TPercentileTrackerLg<6, 5, 15> tracker;
for (size_t i = 0; i < 3000000; i += 1) {
size_t num1 = tracker.BucketIdxMostSignificantBit(i);
size_t num2 = tracker.BucketIdxBinarySearch(i);
UNIT_ASSERT_EQUAL(num1, num2);
}
for (size_t i = 0; i < 400000000000ul; i += 1303) {
size_t num1 = tracker.BucketIdxMostSignificantBit(i);
size_t num2 = tracker.BucketIdxBinarySearch(i);
UNIT_ASSERT_EQUAL(num1, num2);
}
}
}
}
Y_UNIT_TEST(DifferentPercentiles) {
TPercentileTrackerLg<5, 4, 15> tracker;
TVector<size_t> values({0, 115, 1216, 15, 3234567, 1234567, 216546, 263421, 751654, 96, 224, 223, 225});
TVector<size_t> percentiles50({0, 0, 116, 15, 116, 116, 1216, 1216, 217056, 1216, 1216, 224, 232});
TVector<size_t> percentiles75({0, 116, 116, 116, 1216, 1245152, 217056, 270304, 753632, 753632,
270304, 270304, 270304});
TVector<size_t> percentiles90({ 0, 116, 1216, 1216, 2064352, 1245152, 1245152, 1245152, 1245152,
1245152, 1245152, 1245152, 1245152});
TVector<size_t> percentiles100({ 0, 116, 1216, 1216, 2064352, 2064352, 2064352, 2064352, 2064352,
2064352, 2064352, 2064352, 2064352 });
for (size_t i = 0; i < values.size(); ++i) {
tracker.Increment(values[i]);
UNIT_ASSERT_EQUAL(tracker.GetPercentile(0.5), percentiles50[i]);
UNIT_ASSERT_EQUAL(tracker.GetPercentile(0.75), percentiles75[i]);
UNIT_ASSERT_EQUAL(tracker.GetPercentile(0.90), percentiles90[i]);
UNIT_ASSERT_EQUAL(tracker.GetPercentile(1.0), percentiles100[i]);
}
}
}
|
