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 : #if FD_HAS_AVX
11 : #include "../simd/fd_avx.h"
12 : #endif
13 :
14 363384 : #define FD_HISTF_BUCKET_CNT 16UL
15 :
16 3 : #define FD_HISTF_ALIGN (32UL)
17 3 : #define FD_HISTF_FOOTPRINT (FD_ULONG_ALIGN_UP( FD_HISTF_BUCKET_CNT*sizeof(ulong)+(FD_HISTF_BUCKET_CNT+1UL)*sizeof(long), FD_HISTF_ALIGN ))
18 : /* Static assertion FOOTPRINT==sizeof in test */
19 :
20 : struct __attribute__((aligned(FD_HISTF_ALIGN))) fd_histf_private {
21 : ulong counts[ FD_HISTF_BUCKET_CNT ];
22 : /* A value x belongs to bucket i if
23 : left_edge[i] <= x - 2^63 < left_edge[i+1].
24 :
25 : For AVX2, there's no unsiged comparison instruction. We follow
26 : what wv_gt does and implement it by subtracting 2^63 from each
27 : operand. Rather than perform the subtraction at each comparison,
28 : we pre-subtract here. */
29 : long left_edge[ FD_HISTF_BUCKET_CNT+1 ];
30 : ulong sum; /* the sum of all the samples, useful for computing mean */
31 : };
32 :
33 : typedef struct fd_histf_private fd_histf_t;
34 :
35 : FD_PROTOTYPES_BEGIN
36 :
37 0 : FD_FN_CONST static inline ulong fd_histf_align ( void ) { return FD_HISTF_ALIGN; }
38 0 : FD_FN_CONST static inline ulong fd_histf_footprint( void ) { return FD_HISTF_FOOTPRINT; }
39 :
40 : /* fd_histf_new takes ownership of the memory region pointed to by mem
41 : (which is assumed to be non-NULL with the appropriate alignment and
42 : footprint) and formats it as a fd_hist. The histogram will be
43 : initialized with buckets roughly exponentially spaced between
44 : min_value and max_value. min_value must be > 0. Returns mem (which
45 : will be formatted for use).
46 :
47 : Every histogram has special buckets for underflow values (strictly
48 : less than min_val) and overflow values (larger than or equal to the
49 : max_value).
50 :
51 : [ 0, min_value )
52 : [ min_value, approx. min_value * z )
53 : [ approx. min_value * z, approx. min_value * z^2 )
54 : ...
55 : [ approx. min_value * z^13, max_value )
56 : [ max_value, inf )
57 :
58 : z is chosen so that max_value is approximately min_value * z^14 The
59 : approximations come from the fact that all bucket edges are integers,
60 : and no bucket is empty.
61 :
62 : If max_value < min_value+14, then max_value will be increased to
63 : min_value+14 so that no buckets are empty. Note that this histogram
64 : contains strictly more information than what was requested, so an
65 : end-user could postprocess and reduce the number of bins again
66 : without losing any information.
67 :
68 : For example, if min_value is 1 and max_value is 100, the buckets
69 : will be
70 :
71 : 0: [ 0, 1)
72 : 1: [ 1, 2)
73 : 2: [ 2, 3)
74 : 3: [ 3, 4)
75 : 4: [ 4, 5)
76 : 5: [ 5, 7)
77 : 6: [ 7, 9)
78 : 7: [ 9, 12)
79 : 8: [ 12, 16)
80 : 9: [ 16, 22)
81 : 10: [ 22, 30)
82 : 11: [ 30, 41)
83 : 12: [ 41, 55)
84 : 13: [ 55, 74)
85 : 14: [ 74, 100)
86 : 15: [100, inf) */
87 :
88 : static inline void *
89 : fd_histf_new( void * mem,
90 : ulong min_value,
91 2607 : ulong max_value ) {
92 2607 : if( FD_UNLIKELY( max_value<=min_value ) ) return NULL;
93 :
94 2607 : min_value = fd_ulong_max( min_value, 1UL );
95 2607 : max_value = fd_ulong_max( max_value, min_value + FD_HISTF_BUCKET_CNT - 2UL );
96 :
97 2607 : fd_histf_t * hist = (fd_histf_t*)mem;
98 2607 : fd_memset( hist->counts, 0, FD_HISTF_BUCKET_CNT*sizeof(ulong) );
99 2607 : hist->sum = 0UL;
100 2607 : ulong left_edge[ FD_HISTF_BUCKET_CNT ]; /* without the -2^63 shift */
101 2607 : left_edge[ 0 ] = 0;
102 2607 : left_edge[ 1 ] = min_value;
103 36498 : for( ulong i=2UL; i<(FD_HISTF_BUCKET_CNT-1UL); i++ ) {
104 33891 : #if FD_HAS_DOUBLE
105 33891 : 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) ) );
106 : #else
107 : 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) ) );
108 : #endif
109 33891 : le = fd_ulong_max( le, left_edge[ i-1UL ] + 1UL ); /* Make sure bucket is not empty */
110 33891 : left_edge[ i ] = le;
111 33891 : }
112 2607 : left_edge[ FD_HISTF_BUCKET_CNT - 1UL ] = max_value;
113 :
114 44319 : for( ulong i=0UL; i<FD_HISTF_BUCKET_CNT; i++ ) hist->left_edge[ i ] = (long)(left_edge[ i ] - (1UL<<63));
115 2607 : hist->left_edge[ FD_HISTF_BUCKET_CNT ] = LONG_MAX;
116 :
117 2607 : return (void*)hist;
118 2607 : }
119 :
120 6 : static inline fd_histf_t * fd_histf_join ( void * _hist ) { return (fd_histf_t *)_hist; }
121 6 : static inline void * fd_histf_leave ( fd_histf_t * _hist ) { return (void *)_hist; }
122 6 : static inline void * fd_histf_delete( void * _hist ) { return (void *)_hist; }
123 :
124 : /* Return the number of buckets in the histogram, including the overflow
125 : bucket. */
126 0 : FD_FN_PURE static inline ulong fd_histf_bucket_cnt( fd_histf_t * hist ) { (void)hist; return FD_HISTF_BUCKET_CNT; }
127 :
128 : /* Add a sample to the histogram. If the sample is larger than or equal
129 : to the max_value it will be added to a special overflow bucket. */
130 : static inline void
131 : fd_histf_sample( fd_histf_t * hist,
132 3135002071 : ulong value ) {
133 3135002071 : hist->sum += value;
134 3135002071 : long shifted_v = (long)(value - (1UL<<63));
135 3135002071 : #if FD_HAS_AVX
136 3135002071 : wl_t x = wl_bcast( shifted_v );
137 : /* !(x-2^63 < left_edge[i]) & (x-2^63 < left_edge[i+1]) <=>
138 : left_edge[i] <= x-2^63 < left_edge[i+1] */
139 3135002071 : wc_t select0 = wc_andnot( wl_lt( x, wl_ld ( hist->left_edge ) ),
140 3135002071 : wl_lt( x, wl_ldu( hist->left_edge+ 1UL ) ) );
141 3135002071 : wc_t select1 = wc_andnot( wl_lt( x, wl_ld ( hist->left_edge+ 4UL ) ),
142 3135002071 : wl_lt( x, wl_ldu( hist->left_edge+ 5UL ) ) );
143 3135002071 : wc_t select2 = wc_andnot( wl_lt( x, wl_ld ( hist->left_edge+ 8UL ) ),
144 3135002071 : wl_lt( x, wl_ldu( hist->left_edge+ 9UL ) ) );
145 3135002071 : wc_t select3 = wc_andnot( wl_lt( x, wl_ld ( hist->left_edge+12UL ) ),
146 3135002071 : wl_lt( x, wl_ldu( hist->left_edge+13UL ) ) );
147 : /* In exactly one of these, we have a -1 (aka ULONG_MAX). We'll
148 : subtract that from the counts, effectively adding 1. */
149 3135002071 : wv_st( hist->counts, wv_sub( wv_ld( hist->counts ), wc_to_wv_raw( select0 ) ) );
150 3135002071 : wv_st( hist->counts+ 4UL, wv_sub( wv_ld( hist->counts+ 4UL ), wc_to_wv_raw( select1 ) ) );
151 3135002071 : wv_st( hist->counts+ 8UL, wv_sub( wv_ld( hist->counts+ 8UL ), wc_to_wv_raw( select2 ) ) );
152 3135002071 : wv_st( hist->counts+12UL, wv_sub( wv_ld( hist->counts+12UL ), wc_to_wv_raw( select3 ) ) );
153 : #else
154 : for( ulong i=0UL; i<16UL; i++ ) hist->counts[ i ] += (ulong)( (hist->left_edge[ i ] <= shifted_v) & (shifted_v < hist->left_edge[ i+1UL ]) );
155 : #endif
156 3135002071 : }
157 :
158 : /* fd_histf_cnt gets the count of samples in a particular bucket of the
159 : historgram.
160 :
161 : fd_histf_{left,right} get the sample values that map to bucket b,
162 : with a half-open interval [left, right).
163 :
164 : fd_histf_sum gets the sum of all samples that have been added. I.e.
165 : fd_histf_sum() / sum(fd_histf_cnt(j) for j in [0, 16)) is the average
166 : sample value.
167 :
168 : For these functions, b, the bucket index is in [0, 16). */
169 591 : FD_FN_PURE static inline ulong fd_histf_cnt ( fd_histf_t const * hist, ulong b ) { return hist->counts [ b ]; }
170 45 : FD_FN_PURE static inline ulong fd_histf_left ( fd_histf_t const * hist, ulong b ) { return (ulong)hist->left_edge[ b ]+(1UL<<63); }
171 135 : 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); }
172 93 : FD_FN_PURE static inline ulong fd_histf_sum ( fd_histf_t const * hist ) { return hist->sum; }
173 :
174 : FD_PROTOTYPES_END
175 :
176 : #endif /* HEADER_fd_src_util_hist_fd_histf_h */
|
