blob: 3a06fc59f293503f9e788ca38950b30a03537b2c (
plain) (
blame)
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
|
// Copyright Epic Games, Inc. All Rights Reserved.
#include <zentelemetry/hyperloglog.h>
namespace zen {
void
hyperloglog_forcelink()
{
}
} // namespace zen
#if ZEN_WITH_TESTS
# include <zencore/testing.h>
# include <fmt/format.h>
# include <set>
# include <string>
namespace zen::tests {
TEST_SUITE_BEGIN("telemetry.hyperloglog");
TEST_CASE("hyperloglog.empty")
{
metrics::HyperLogLog<> Hll;
CHECK_EQ(Hll.Count(), 0);
}
TEST_CASE("hyperloglog.single_element")
{
metrics::HyperLogLog<> Hll;
Hll.Add("hello");
CHECK(Hll.Count() >= 1);
CHECK(Hll.Count() <= 2);
}
TEST_CASE("hyperloglog.duplicates")
{
metrics::HyperLogLog<> Hll;
for (int i = 0; i < 1000; ++i)
{
Hll.Add("same_value");
}
CHECK_EQ(Hll.Count(), 1);
}
TEST_CASE("hyperloglog.estimate_accuracy")
{
// With precision 14, expected error is ~0.81%
// Use a generous margin (5%) for the test to be reliable
constexpr uint64_t N = 100000;
metrics::HyperLogLog<14> Hll;
for (uint64_t i = 0; i < N; ++i)
{
std::string Value = fmt::format("item_{}", i);
Hll.Add(Value);
}
uint64_t Estimate = Hll.Count();
double Error = std::abs(static_cast<double>(Estimate) - static_cast<double>(N)) / static_cast<double>(N);
CHECK(Error < 0.05);
}
TEST_CASE("hyperloglog.small_cardinality")
{
metrics::HyperLogLog<> Hll;
for (int i = 0; i < 10; ++i)
{
std::string Value = fmt::format("key_{}", i);
Hll.Add(Value);
}
uint64_t Estimate = Hll.Count();
CHECK(Estimate >= 8);
CHECK(Estimate <= 12);
}
TEST_CASE("hyperloglog.clear")
{
metrics::HyperLogLog<> Hll;
for (int i = 0; i < 100; ++i)
{
std::string Value = fmt::format("v_{}", i);
Hll.Add(Value);
}
CHECK(Hll.Count() > 0);
Hll.Clear();
CHECK_EQ(Hll.Count(), 0);
}
TEST_CASE("hyperloglog.merge")
{
constexpr uint64_t N = 50000;
metrics::HyperLogLog<14> A;
metrics::HyperLogLog<14> B;
// A gets even numbers, B gets odd numbers
for (uint64_t i = 0; i < N; ++i)
{
std::string Value = fmt::format("item_{}", i * 2);
A.Add(Value);
}
for (uint64_t i = 0; i < N; ++i)
{
std::string Value = fmt::format("item_{}", i * 2 + 1);
B.Add(Value);
}
A.Merge(B);
uint64_t Estimate = A.Count();
double Error = std::abs(static_cast<double>(Estimate) - static_cast<double>(N * 2)) / static_cast<double>(N * 2);
CHECK(Error < 0.05);
}
TEST_SUITE_END();
} // namespace zen::tests
#endif // ZEN_WITH_TESTS
|