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