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