jupp0r/prometheus-cpp | Build 4192383612 | core/src/detail/ckms_quantiles.cc | Coveralls

11

CKMSQuantiles::Quantile::Quantile(double quantile, double error)

78✔

14

      u(2.0 * error / (1.0 - quantile)),

78✔

15

      v(2.0 * error / quantile) {}

78✔

17

CKMSQuantiles::Item::Item(double value, int lower_delta, int delta)

1,000,018✔

18

    : value(value), g(lower_delta), delta(delta) {}

1,000,018✔

20

CKMSQuantiles::CKMSQuantiles(const std::vector<Quantile>& quantiles)

38✔

21

    : quantiles_(quantiles), count_(0), buffer_{}, buffer_count_(0) {}

38✔

23

void CKMSQuantiles::insert(double value) {

1,000,158✔

24

  buffer_[buffer_count_] = value;

1,000,158✔

25

  ++buffer_count_;

1,000,158✔

27

  if (buffer_count_ == buffer_.size()) {

1,000,158✔

28

    insertBatch();

2,000✔

29

    compress();

2,000✔

31

1,000,158✔

33

double CKMSQuantiles::get(double q) {

76✔

34

  insertBatch();

76✔

35

  compress();

76✔

37

  if (sample_.empty()) {

76✔

38

    return std::numeric_limits<double>::quiet_NaN();

60✔

41

  int rankMin = 0;

16✔

42

  const auto desired = static_cast<int>(q * count_);

16✔

43

  const auto bound = desired + (allowableError(desired) / 2);

16✔

45

  auto it = sample_.begin();

16✔

46

  decltype(it) prev;

16✔

47

  auto cur = it++;

16✔

49

  while (it != sample_.end()) {

2,608✔

50

    prev = cur;

2,604✔

51

    cur = it++;

2,604✔

53

    rankMin += prev->g;

2,604✔

55

    if (rankMin + cur->g + cur->delta > bound) {

2,604✔

56

      return prev->value;

12✔

60

  return sample_.back().value;

4✔

63

void CKMSQuantiles::reset() {

4✔

64

  count_ = 0;

4✔

65

  sample_.clear();

4✔

66

  buffer_count_ = 0;

4✔

67

4✔

69

double CKMSQuantiles::allowableError(int rank) {

2,623,120✔

70

  auto size = sample_.size();

2,623,120✔

71

  double minError = size + 1;

2,623,120✔

73

  for (const auto& q : quantiles_.get()) {

10,492,480✔

75

    if (rank <= q.quantile * size) {

7,869,360✔

76

      error = q.u * (size - rank);

4,188,520✔

78

      error = q.v * rank;

3,680,840✔

80

    if (error < minError) {

7,869,360✔

81

      minError = error;

6,803,600✔

85

  return minError;

2,623,120✔

88

bool CKMSQuantiles::insertBatch() {

2,076✔

89

  if (buffer_count_ == 0) {

2,076✔

90

    return false;

66✔

93

  std::sort(buffer_.begin(), buffer_.begin() + buffer_count_);

2,010✔

95

  std::size_t start = 0;

2,010✔

96

  if (sample_.empty()) {

2,010✔

97

    sample_.emplace_back(buffer_[0], 1, 0);

20✔

98

    ++start;

20✔

99

    ++count_;

20✔

102

  std::size_t idx = 0;

2,010✔

103

  std::size_t item = idx++;

2,010✔

105

  for (std::size_t i = start; i < buffer_count_; ++i) {

1,002,008✔

106

    double v = buffer_[i];

999,998✔

107

    while (idx < sample_.size() && sample_[item].value < v) {

2,608,020✔

108

      item = idx++;

1,608,030✔

111

    if (sample_[item].value > v) {

999,998✔

116

    if (idx - 1 == 0 || idx + 1 == sample_.size()) {

999,998✔

117

      delta = 0;

16✔

119

      delta = static_cast<int>(std::floor(allowableError(idx + 1))) + 1;

999,982✔

122

    sample_.emplace(sample_.begin() + idx, v, 1, delta);

999,998✔

123

    count_++;

999,998✔

124

    item = idx++;

999,998✔

127

  buffer_count_ = 0;

2,010✔

128

  return true;

2,010✔

131

void CKMSQuantiles::compress() {

2,076✔

132

  if (sample_.size() < 2) {

2,076✔

133

    return;

64✔

136

  std::size_t idx = 0;

2,012✔

138

  std::size_t next = idx++;

2,012✔

140

  while (idx < sample_.size()) {

1,625,144✔

141

    prev = next;

1,623,132✔

142

    next = idx++;

1,623,132✔

144

    if (sample_[prev].g + sample_[next].g + sample_[next].delta <=

3,246,260✔

145

        allowableError(idx - 1)) {

1,623,132✔

146

      sample_[next].g += sample_[prev].g;

990,096✔

147

      sample_.erase(sample_.begin() + prev);

990,096✔

jupp0r / prometheus-cpp / 4192383612

Source File
Press 'n' to go to next uncovered line, 'b' for previous

1	#include "prometheus/detail/ckms_quantiles.h" // IWYU pragma: export
2
3	#include <algorithm>
4	#include <cmath>
5	#include <limits>
6	#include <memory>
7
8	namespace prometheus {
9	namespace detail {
10
11	CKMSQuantiles::Quantile::Quantile(double quantile, double error)	78✔
12	: quantile(quantile),
13	error(error),
14	u(2.0 * error / (1.0 - quantile)),	78✔
15	v(2.0 * error / quantile) {}	78✔
16
17	CKMSQuantiles::Item::Item(double value, int lower_delta, int delta)	1,000,018✔
18	: value(value), g(lower_delta), delta(delta) {}	1,000,018✔
19
20	CKMSQuantiles::CKMSQuantiles(const std::vector<Quantile>& quantiles)	38✔
21	: quantiles_(quantiles), count_(0), buffer_{}, buffer_count_(0) {}	38✔
22
23	void CKMSQuantiles::insert(double value) {	1,000,158✔
24	buffer_[buffer_count_] = value;	1,000,158✔
25	++buffer_count_;	1,000,158✔
26
27	if (buffer_count_ == buffer_.size()) {	1,000,158✔
28	insertBatch();	2,000✔
29	compress();	2,000✔
30	}
31	}	1,000,158✔
32
33	double CKMSQuantiles::get(double q) {	76✔
34	insertBatch();	76✔
35	compress();	76✔
36
37	if (sample_.empty()) {	76✔
38	return std::numeric_limits<double>::quiet_NaN();	60✔
39	}
40
41	int rankMin = 0;	16✔
42	const auto desired = static_cast<int>(q * count_);	16✔
43	const auto bound = desired + (allowableError(desired) / 2);	16✔
44
45	auto it = sample_.begin();	16✔
46	decltype(it) prev;	16✔
47	auto cur = it++;	16✔
48
49	while (it != sample_.end()) {	2,608✔
50	prev = cur;	2,604✔
51	cur = it++;	2,604✔
52
53	rankMin += prev->g;	2,604✔
54
55	if (rankMin + cur->g + cur->delta > bound) {	2,604✔
56	return prev->value;	12✔
57	}
58	}
59
60	return sample_.back().value;	4✔
61	}
62
63	void CKMSQuantiles::reset() {	4✔
64	count_ = 0;	4✔
65	sample_.clear();	4✔
66	buffer_count_ = 0;	4✔
67	}	4✔
68
69	double CKMSQuantiles::allowableError(int rank) {	2,623,120✔
70	auto size = sample_.size();	2,623,120✔
71	double minError = size + 1;	2,623,120✔
72
73	for (const auto& q : quantiles_.get()) {	10,492,480✔
74	double error;
75	if (rank <= q.quantile * size) {	7,869,360✔
76	error = q.u * (size - rank);	4,188,520✔
77	} else {
78	error = q.v * rank;	3,680,840✔
79	}
80	if (error < minError) {	7,869,360✔
81	minError = error;	6,803,600✔
82	}
83	}
84
85	return minError;	2,623,120✔
86	}
87
88	bool CKMSQuantiles::insertBatch() {	2,076✔
89	if (buffer_count_ == 0) {	2,076✔
90	return false;	66✔
91	}
92
93	std::sort(buffer_.begin(), buffer_.begin() + buffer_count_);	2,010✔
94
95	std::size_t start = 0;	2,010✔
96	if (sample_.empty()) {	2,010✔
97	sample_.emplace_back(buffer_[0], 1, 0);	20✔
98	++start;	20✔
99	++count_;	20✔
100	}
101
102	std::size_t idx = 0;	2,010✔
103	std::size_t item = idx++;	2,010✔
104
105	for (std::size_t i = start; i < buffer_count_; ++i) {	1,002,008✔
106	double v = buffer_[i];	999,998✔
107	while (idx < sample_.size() && sample_[item].value < v) {	2,608,020✔
108	item = idx++;	1,608,030✔
109	}
110
111	if (sample_[item].value > v) {	999,998✔
112	--idx;	×
113	}
114
115	int delta;
116	if (idx - 1 == 0 \|\| idx + 1 == sample_.size()) {	999,998✔
117	delta = 0;	16✔
118	} else {
119	delta = static_cast<int>(std::floor(allowableError(idx + 1))) + 1;	999,982✔
120	}
121
122	sample_.emplace(sample_.begin() + idx, v, 1, delta);	999,998✔
123	count_++;	999,998✔
124	item = idx++;	999,998✔
125	}
126
127	buffer_count_ = 0;	2,010✔
128	return true;	2,010✔
129	}
130
131	void CKMSQuantiles::compress() {	2,076✔
132	if (sample_.size() < 2) {	2,076✔
133	return;	64✔
134	}
135
136	std::size_t idx = 0;	2,012✔
137	std::size_t prev;
138	std::size_t next = idx++;	2,012✔
139
140	while (idx < sample_.size()) {	1,625,144✔
141	prev = next;	1,623,132✔
142	next = idx++;	1,623,132✔
143
144	if (sample_[prev].g + sample_[next].g + sample_[next].delta <=	3,246,260✔
145	allowableError(idx - 1)) {	1,623,132✔
146	sample_[next].g += sample_[prev].g;	990,096✔
147	sample_.erase(sample_.begin() + prev);	990,096✔
148	}
149	}
150	}
151
152	} // namespace detail
153	} // namespace prometheus

jupp0r / prometheus-cpp / 4192383612

Source File Press 'n' to go to next uncovered line, 'b' for previous

Source File
Press 'n' to go to next uncovered line, 'b' for previous