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
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
|
#pragma once
#include <util/generic/array_ref.h>
#include <util/generic/ptr.h>
#include <util/generic/vector.h>
#include <util/generic/yexception.h>
#include <cmath>
#include <limits>
namespace NMonitoring {
using TBucketBound = double;
using TBucketValue = ui64;
using TBucketBounds = TVector<TBucketBound>;
using TBucketValues = TVector<TBucketValue>;
constexpr ui32 HISTOGRAM_MAX_BUCKETS_COUNT = 51;
constexpr TBucketBound HISTOGRAM_INF_BOUND = std::numeric_limits<TBucketBound>::max();
///////////////////////////////////////////////////////////////////////////
// IHistogramSnapshot
///////////////////////////////////////////////////////////////////////////
class IHistogramSnapshot: public TAtomicRefCount<IHistogramSnapshot> {
public:
virtual ~IHistogramSnapshot() = default;
/**
* @return buckets count.
*/
virtual ui32 Count() const = 0;
/**
* @return upper bound for the bucket with particular index.
*/
virtual TBucketBound UpperBound(ui32 index) const = 0;
/**
* @return value stored in the bucket with particular index.
*/
virtual TBucketValue Value(ui32 index) const = 0;
};
using IHistogramSnapshotPtr = TIntrusivePtr<IHistogramSnapshot>;
///////////////////////////////////////////////////////////////////////////////
// TLinearHistogramSnapshot
///////////////////////////////////////////////////////////////////////////////
class TLinearHistogramSnapshot: public IHistogramSnapshot {
public:
TLinearHistogramSnapshot(
TBucketBound startValue, TBucketBound bucketWidth, TBucketValues values)
: StartValue_(startValue)
, BucketWidth_(bucketWidth)
, Values_(std::move(values))
{
}
ui32 Count() const override {
return static_cast<ui32>(Values_.size());
}
TBucketBound UpperBound(ui32 index) const override {
Y_ASSERT(index < Values_.size());
if (index == Count() - 1) {
return Max<TBucketBound>();
}
return StartValue_ + BucketWidth_ * index;
}
TBucketValue Value(ui32 index) const override {
Y_ASSERT(index < Values_.size());
return Values_[index];
}
ui64 MemorySizeBytes() {
return sizeof(*this) + Values_.capacity() * sizeof(decltype(Values_)::value_type);
}
private:
TBucketBound StartValue_;
TBucketBound BucketWidth_;
TBucketValues Values_;
};
///////////////////////////////////////////////////////////////////////////
// TExponentialHistogramSnapshot
///////////////////////////////////////////////////////////////////////////
class TExponentialHistogramSnapshot: public IHistogramSnapshot {
public:
TExponentialHistogramSnapshot(
double base, double scale, TBucketValues values)
: Base_(base)
, Scale_(scale)
, Values_(std::move(values))
{
}
ui32 Count() const override {
return static_cast<ui32>(Values_.size());
}
TBucketBound UpperBound(ui32 index) const override {
Y_ASSERT(index < Values_.size());
if (index == Values_.size() - 1) {
return Max<TBucketBound>();
}
return std::round(Scale_ * std::pow(Base_, index));
}
TBucketValue Value(ui32 index) const override {
Y_ASSERT(index < Values_.size());
return Values_[index];
}
ui64 MemorySizeBytes() {
return sizeof(*this) + Values_.capacity() * sizeof(decltype(Values_)::value_type);
}
private:
double Base_;
double Scale_;
TBucketValues Values_;
};
using TBucket = std::pair<TBucketBound, TBucketValue>;
///////////////////////////////////////////////////////////////////////
// TExplicitHistogramSnapshot
///////////////////////////////////////////////////////////////////////
//
// Memory layout (single contiguous block):
//
// +------+-----------+--------------+--------+--------+- -+--------+--------+
// | vptr | RefsCount | BucketsCount | Bound1 | Value1 | ... | BoundN | ValueN |
// +------+-----------+--------------+--------+--------+- -+--------+--------+
//
class alignas(TBucketValue) TExplicitHistogramSnapshot: public IHistogramSnapshot, private TNonCopyable {
public:
static TIntrusivePtr<TExplicitHistogramSnapshot> New(ui32 bucketsCount) {
size_t bucketsSize = bucketsCount * sizeof(TBucket);
Y_ENSURE(bucketsCount <= HISTOGRAM_MAX_BUCKETS_COUNT, "Cannot allocate a histogram with " << bucketsCount
<< " buckets. Bucket count is limited to " << HISTOGRAM_MAX_BUCKETS_COUNT);
return new(bucketsSize) TExplicitHistogramSnapshot(bucketsCount);
}
TBucket& operator[](ui32 index) noexcept {
return Bucket(index);
}
ui32 Count() const override {
return BucketsCount_;
}
TBucketBound UpperBound(ui32 index) const override {
return Bucket(index).first;
}
TBucketValue Value(ui32 index) const override {
return Bucket(index).second;
}
ui64 MemorySizeBytes() const {
return sizeof(*this) + BucketsCount_ * sizeof(TBucket);
}
private:
explicit TExplicitHistogramSnapshot(ui32 bucketsCount) noexcept
: BucketsCount_(bucketsCount)
{
}
static void* operator new(size_t size, size_t bucketsSize) {
return ::operator new(size + bucketsSize);
}
static void operator delete(void* mem) {
::operator delete(mem);
}
static void operator delete(void* mem, size_t, size_t) {
// this operator can be called as paired for custom new operator
::operator delete(mem);
}
TBucket& Bucket(ui32 index) noexcept {
Y_VERIFY_DEBUG(index < BucketsCount_);
return *(reinterpret_cast<TBucket*>(this + 1) + index);
}
const TBucket& Bucket(ui32 index) const noexcept {
Y_VERIFY_DEBUG(index < BucketsCount_);
return *(reinterpret_cast<const TBucket*>(this + 1) + index);
}
private:
ui32 BucketsCount_;
};
static_assert(alignof(TExplicitHistogramSnapshot) == alignof(TBucket),
"mismatched alingments of THistogramSnapshot and TBucket");
IHistogramSnapshotPtr ExplicitHistogramSnapshot(TConstArrayRef<TBucketBound> bounds, TConstArrayRef<TBucketValue> values);
} // namespace NMonitoring
std::ostream& operator<<(std::ostream& os, const NMonitoring::IHistogramSnapshot& hist);
|
