Line data Source code
1 : #ifndef HEADER_fd_src_util_hist_fd_histf_h
2 : #define HEADER_fd_src_util_hist_fd_histf_h
3 :
4 : /* Simple fast fixed-size exponential histograms. Histograms are
5 : bucketed exponentially up to a maximum value, with an overflow bucket
6 : for any other measurements. */
7 :
8 : #include <math.h> /* FIXME: HMMM */
9 : #include "../log/fd_log.h"
10 :
11 : #if FD_HAS_AVX
12 : /* GCC generic vectors rather than fd_avx.h to keep this widely included
13 : header off the intrinsics headers */
14 : typedef long fd_histf_v4l_t __attribute__((__vector_size__(32),__may_alias__));
15 : typedef long fd_histf_v4l_u_t __attribute__((__vector_size__(32),__may_alias__,__aligned__(8)));
16 : #endif
17 :
18 0 : #define FD_HISTF_BUCKET_CNT 16UL
19 :
20 0 : #define FD_HISTF_ALIGN (32UL)
21 0 : #define FD_HISTF_FOOTPRINT (FD_ULONG_ALIGN_UP( FD_HISTF_BUCKET_CNT*sizeof(ulong)+(FD_HISTF_BUCKET_CNT+1UL)*sizeof(long), FD_HISTF_ALIGN ))
22 : /* Static assertion FOOTPRINT==sizeof in test */
23 :
24 : struct __attribute__((aligned(FD_HISTF_ALIGN))) fd_histf_private {
25 : ulong counts[ FD_HISTF_BUCKET_CNT ];
26 : /* A value x belongs to bucket i if
27 : left_edge[i] <= x - 2^63 < left_edge[i+1].
28 : The overflow bucket has no upper bound.
29 :
30 : For AVX2, there's no unsiged comparison instruction. We follow
31 : what wv_gt does and implement it by subtracting 2^63 from each
32 : operand. Rather than perform the subtraction at each comparison,
33 : we pre-subtract here. */
34 : long left_edge[ FD_HISTF_BUCKET_CNT+1 ];
35 : ulong sum; /* the sum of all the samples, useful for computing mean */
36 : };
37 :
38 : typedef struct fd_histf_private fd_histf_t;
39 :
40 : FD_PROTOTYPES_BEGIN
41 :
42 0 : FD_FN_CONST static inline ulong fd_histf_align ( void ) { return FD_HISTF_ALIGN; }
43 0 : FD_FN_CONST static inline ulong fd_histf_footprint( void ) { return FD_HISTF_FOOTPRINT; }
44 :
45 : /* fd_histf_new_edges is fd_histf_new with caller supplied bucket
46 : edges. edges[i] is the left edge of bucket i+1, so bucket 0 is
47 : [ 0, edges[0] ) and bucket 15 is [ edges[14], inf ). Edges must be
48 : nonzero and strictly increasing. Returns NULL on bad edges. */
49 :
50 : static inline void *
51 : fd_histf_new_edges( void * mem,
52 0 : ulong const edges[ FD_HISTF_BUCKET_CNT-1UL ] ) {
53 0 : if( FD_UNLIKELY( !edges[ 0 ] ) ) return NULL;
54 0 : for( ulong i=1UL; i<(FD_HISTF_BUCKET_CNT-1UL); i++ ) {
55 0 : if( FD_UNLIKELY( edges[ i ]<=edges[ i-1UL ] ) ) return NULL;
56 0 : }
57 :
58 0 : fd_histf_t * hist = (fd_histf_t*)mem;
59 0 : fd_memset( hist->counts, 0, FD_HISTF_BUCKET_CNT*sizeof(ulong) );
60 0 : hist->sum = 0UL;
61 0 : hist->left_edge[ 0 ] = (long)(0UL - (1UL<<63));
62 0 : for( ulong i=0UL; i<(FD_HISTF_BUCKET_CNT-1UL); i++ ) hist->left_edge[ i+1UL ] = (long)(edges[ i ] - (1UL<<63));
63 0 : hist->left_edge[ FD_HISTF_BUCKET_CNT ] = LONG_MAX;
64 :
65 0 : return (void*)hist;
66 0 : }
67 :
68 : /* fd_histf_new takes ownership of the memory region pointed to by mem
69 : (which is assumed to be non-NULL with the appropriate alignment and
70 : footprint) and formats it as a fd_hist. The histogram will be
71 : initialized with buckets roughly exponentially spaced between
72 : min_value and max_value. min_value must be > 0. Returns mem (which
73 : will be formatted for use).
74 :
75 : Every histogram has special buckets for underflow values (strictly
76 : less than min_val) and overflow values (larger than or equal to the
77 : max_value).
78 :
79 : [ 0, min_value )
80 : [ min_value, approx. min_value * z )
81 : [ approx. min_value * z, approx. min_value * z^2 )
82 : ...
83 : [ approx. min_value * z^13, max_value )
84 : [ max_value, inf )
85 :
86 : z is chosen so that max_value is approximately min_value * z^14 The
87 : approximations come from the fact that all bucket edges are integers,
88 : and no bucket is empty.
89 :
90 : If max_value < min_value+14, then max_value will be increased to
91 : min_value+14 so that no buckets are empty. Note that this histogram
92 : contains strictly more information than what was requested, so an
93 : end-user could postprocess and reduce the number of bins again
94 : without losing any information.
95 :
96 : For example, if min_value is 1 and max_value is 100, the buckets
97 : will be
98 :
99 : 0: [ 0, 1)
100 : 1: [ 1, 2)
101 : 2: [ 2, 3)
102 : 3: [ 3, 4)
103 : 4: [ 4, 5)
104 : 5: [ 5, 7)
105 : 6: [ 7, 9)
106 : 7: [ 9, 12)
107 : 8: [ 12, 16)
108 : 9: [ 16, 22)
109 : 10: [ 22, 30)
110 : 11: [ 30, 41)
111 : 12: [ 41, 55)
112 : 13: [ 55, 74)
113 : 14: [ 74, 100)
114 : 15: [100, inf) */
115 :
116 : static inline void *
117 : fd_histf_new( void * mem,
118 : ulong min_value,
119 0 : ulong max_value ) {
120 0 : if( FD_UNLIKELY( max_value<=min_value ) ) return NULL;
121 :
122 0 : min_value = fd_ulong_max( min_value, 1UL );
123 0 : max_value = fd_ulong_max( max_value, min_value + FD_HISTF_BUCKET_CNT - 2UL );
124 :
125 0 : ulong left_edge[ FD_HISTF_BUCKET_CNT ];
126 0 : left_edge[ 0 ] = 0;
127 0 : left_edge[ 1 ] = min_value;
128 0 : for( ulong i=2UL; i<(FD_HISTF_BUCKET_CNT-1UL); i++ ) {
129 0 : #if FD_HAS_DOUBLE
130 0 : ulong le = (ulong)(0.5 + (double)left_edge[ i-1UL ] * pow ( (double)max_value / (double)left_edge[ i-1UL ], 1.0 /(double)(FD_HISTF_BUCKET_CNT - i) ) );
131 : #else
132 : ulong le = (ulong)(0.5f + (float )left_edge[ i-1UL ] * powf( (float )max_value / (float )left_edge[ i-1UL ], 1.0f/(float )(FD_HISTF_BUCKET_CNT - i) ) );
133 : #endif
134 0 : le = fd_ulong_max( le, left_edge[ i-1UL ] + 1UL ); /* Make sure bucket is not empty */
135 0 : left_edge[ i ] = le;
136 0 : }
137 0 : left_edge[ FD_HISTF_BUCKET_CNT - 1UL ] = max_value;
138 :
139 0 : return fd_histf_new_edges( mem, left_edge+1UL );
140 0 : }
141 :
142 0 : static inline fd_histf_t * fd_histf_join ( void * _hist ) { return (fd_histf_t *)_hist; }
143 0 : static inline void * fd_histf_leave ( fd_histf_t * _hist ) { return (void *)_hist; }
144 0 : static inline void * fd_histf_delete( void * _hist ) { return (void *)_hist; }
145 :
146 : /* Return the number of buckets in the histogram, including the overflow
147 : bucket. */
148 0 : FD_FN_PURE static inline ulong fd_histf_bucket_cnt( fd_histf_t * hist ) { (void)hist; return FD_HISTF_BUCKET_CNT; }
149 :
150 : /* Add a sample to the histogram. If the sample is larger than or equal
151 : to the max_value it will be added to a special overflow bucket. */
152 : static inline void
153 : fd_histf_sample( fd_histf_t * hist,
154 0 : ulong value ) {
155 0 : hist->sum += value;
156 0 : long shifted_v = (long)(value - (1UL<<63));
157 0 : #if FD_HAS_AVX
158 0 : fd_histf_v4l_t x = { shifted_v, shifted_v, shifted_v, shifted_v };
159 : /* !(x-2^63 < left_edge[i]) & (x-2^63 < left_edge[i+1]) <=>
160 : left_edge[i] <= x-2^63 < left_edge[i+1]. Vector compares yield
161 : 0/-1 lanes. */
162 0 : fd_histf_v4l_t const overflow_mask = { 0L, 0L, 0L, -1L };
163 0 : fd_histf_v4l_t select0 = ~( x < *(fd_histf_v4l_t const *)(hist->left_edge ) )
164 0 : & ( x < *(fd_histf_v4l_u_t const *)(hist->left_edge+ 1UL ) );
165 0 : fd_histf_v4l_t select1 = ~( x < *(fd_histf_v4l_t const *)(hist->left_edge+ 4UL ) )
166 0 : & ( x < *(fd_histf_v4l_u_t const *)(hist->left_edge+ 5UL ) );
167 0 : fd_histf_v4l_t select2 = ~( x < *(fd_histf_v4l_t const *)(hist->left_edge+ 8UL ) )
168 0 : & ( x < *(fd_histf_v4l_u_t const *)(hist->left_edge+ 9UL ) );
169 0 : fd_histf_v4l_t select3 = ~( x < *(fd_histf_v4l_t const *)(hist->left_edge+12UL ) )
170 0 : & ((x < *(fd_histf_v4l_u_t const *)(hist->left_edge+13UL )) | overflow_mask );
171 : /* In exactly one of these, we have a -1 (aka ULONG_MAX). We'll
172 : subtract that from the counts, effectively adding 1. */
173 0 : *(fd_histf_v4l_t *)(hist->counts ) -= select0;
174 0 : *(fd_histf_v4l_t *)(hist->counts+ 4UL ) -= select1;
175 0 : *(fd_histf_v4l_t *)(hist->counts+ 8UL ) -= select2;
176 0 : *(fd_histf_v4l_t *)(hist->counts+12UL ) -= select3;
177 : #else
178 : for( ulong i=0UL; i<FD_HISTF_BUCKET_CNT; i++ ) hist->counts[ i ] += (ulong)( (hist->left_edge[ i ] <= shifted_v) & (shifted_v < hist->left_edge[ i+1UL ]) );
179 : hist->counts[ FD_HISTF_BUCKET_CNT-1UL ] += (ulong)(shifted_v == LONG_MAX);
180 : #endif
181 0 : }
182 :
183 : /* fd_histf_cnt gets the count of samples in a particular bucket of the
184 : histogram.
185 :
186 : fd_histf_{left,right} get the sample values that map to bucket b,
187 : with a half-open interval [left, right).
188 : The overflow bucket has no upper bound; right returns ULONG_MAX.
189 :
190 : fd_histf_sum gets the sum of all samples that have been added. I.e.
191 : fd_histf_sum() / sum(fd_histf_cnt(j) for j in [0, 16)) is the average
192 : sample value.
193 :
194 : For these functions, b, the bucket index is in [0, 16). */
195 0 : FD_FN_PURE static inline ulong fd_histf_cnt ( fd_histf_t const * hist, ulong b ) { return hist->counts [ b ]; }
196 0 : FD_FN_PURE static inline ulong fd_histf_left ( fd_histf_t const * hist, ulong b ) { return (ulong)hist->left_edge[ b ]+(1UL<<63); }
197 0 : FD_FN_PURE static inline ulong fd_histf_right( fd_histf_t const * hist, ulong b ) { return (ulong)hist->left_edge[ b+1UL ]+(1UL<<63); }
198 0 : FD_FN_PURE static inline ulong fd_histf_sum ( fd_histf_t const * hist ) { return hist->sum; }
199 :
200 : /* fd_histf_percentile computes a percentile estimate. Note that for
201 : tail-end percentiles, its possible that samples will have landed in
202 : the overflow/underflow bucket. Since these are "catch-all" buckets,
203 : we don't know how their samples are distributed. For the underflow
204 : bucket, since its bounds are known a linear interpolation is used to
205 : estimate percentile. For the overflow bucket, its bounds are
206 : unknown, so the sentinel is returned */
207 : FD_FN_PURE static inline ulong
208 0 : fd_histf_percentile( fd_histf_t const * hist, uchar percentile, ulong sentinel ) {
209 0 : if( FD_UNLIKELY( percentile > 100 ) ) FD_LOG_ERR(( "fd_histf_percentile: percentile must be in [0, 100]. got %u", percentile ));
210 :
211 0 : ulong total_sample_cnt = 0UL;
212 0 : for( ulong b=0UL; b<FD_HISTF_BUCKET_CNT; b++ ) total_sample_cnt += fd_histf_cnt( hist, b );
213 0 : if( FD_UNLIKELY( !total_sample_cnt ) ) return sentinel;
214 :
215 0 : #define MAP(x, in_min, in_max, out_min, out_max) \
216 0 : ((in_min == in_max) ? ((out_min + out_max) / 2) : (((x) - (in_min)) * ((out_max) - (out_min)) / ((in_max) - (in_min)) + (out_min)))
217 :
218 0 : ulong rank = MAP((ulong)percentile, 0UL, 100UL, 0UL, total_sample_cnt-1UL);
219 0 : ulong sum = 0UL;
220 :
221 0 : for( ulong b=0UL; b<FD_HISTF_BUCKET_CNT; b++ ) {
222 0 : ulong count = fd_histf_cnt ( hist, b );
223 0 : sum += count;
224 0 : if( sum > rank ) {
225 0 : ulong left = fd_histf_left ( hist, b );
226 0 : ulong right = fd_histf_right( hist, b );
227 0 : ulong prev = sum - count; /* the number of samples in previous buckets */
228 :
229 0 : if( FD_UNLIKELY( b==0 ) ) {
230 : /* for the underflow bucket, use linear interpolation */
231 0 : return MAP(rank - prev, 0UL, count-1UL, left, right);
232 0 : } else if( FD_UNLIKELY( b==(FD_HISTF_BUCKET_CNT - 1UL) )) {
233 : /* for the overflow bucket, return sentinel */
234 0 : return sentinel;
235 0 : } else {
236 : /* max_value is the right value for the bucket before the
237 : overflow bucket */
238 0 : ulong max_value = fd_histf_right( hist, FD_HISTF_BUCKET_CNT - 2UL );
239 :
240 : /* interpolate using the same equation used to construct bucket
241 : sizes */
242 0 : #if FD_HAS_DOUBLE
243 0 : return (ulong)(0.5 + (double)left * pow ( (double)max_value / (double)left, MAP((double)(rank - prev), 0.0, (double)(count-1UL), 0.0, 1.0)/(double)(FD_HISTF_BUCKET_CNT - b - 1UL) ) );
244 : #else
245 : return (ulong)(0.5f + (float )left * powf( (float )max_value / (float )left, MAP((float )(rank - prev), 0.0f, (float )(count-1UL), 0.0f, 1.0f)/(float )(FD_HISTF_BUCKET_CNT - b - 1UL) ) );
246 : #endif
247 0 : }
248 0 : }
249 0 : }
250 :
251 0 : #undef MAP
252 :
253 0 : FD_LOG_ERR(( "unreachable" ));
254 0 : }
255 :
256 : /* fd_histf_subtract subtracts other_hist from hist and stores the
257 : resulting histogram in hist. In order to coherently subtract two
258 : histograms, the sample history of other_hist must be a prefix to the
259 : sample history of hist. This effectively "erases" all the samples
260 : from hist that were taken at or before the last sample in other_hist. */
261 : static inline void
262 0 : fd_histf_subtract( fd_histf_t const * hist, fd_histf_t const * prefix_hist, fd_histf_t * out ) {
263 0 : out->sum = hist->sum - prefix_hist->sum;
264 0 : for( ulong b=0UL; b<FD_HISTF_BUCKET_CNT; b++ ) out->counts[ b ] = hist->counts[ b ] - prefix_hist->counts[ b ];
265 0 : for( ulong b=0UL; b<=FD_HISTF_BUCKET_CNT; b++ ) out->left_edge[ b ] = hist->left_edge[ b ];
266 0 : }
267 :
268 : FD_PROTOTYPES_END
269 :
270 : #endif /* HEADER_fd_src_util_hist_fd_histf_h */
|
