Line data Source code
1 : #include "../fd_tango.h"
2 : #include "../../util/math/fd_stat.h"
3 :
4 : #if FD_HAS_DOUBLE
5 :
6 : double
7 60 : fd_tempo_wallclock_model( double * opt_tau ) {
8 60 : static double t0;
9 60 : static double tau;
10 :
11 126 : FD_ONCE_BEGIN {
12 :
13 : /* Assuming fd_log_wallclock() observes the application wallclock at
14 : a consistent point between when the call was made and when it
15 : returns, the difference between two adjacent calls is an estimate
16 : of the number of ns required for a call. We expect this
17 : difference to have a well defined minimum time with sporadic
18 : delays due to various sources of jitter. The natural approach is
19 : to model call overhead then as a shifted exponential random
20 : variable. To parameterize the model, we repeatedly measure how
21 : long a call takes. The minimum of a bunch of IID samples is very
22 : fast converging for estimating the minimum but easily corrupted
23 : if there are weird outliers on the negative side. As such, we
24 : use a robust estimator to estimate the minimal overhead and
25 : jitter. */
26 :
27 3 : ulong iter = 0UL;
28 3 : for(;;) {
29 198 : # define TRIAL_CNT 64UL
30 6 : # define TRIM_CNT 8UL
31 3 : double trial[ TRIAL_CNT ];
32 195 : for( ulong trial_idx=0UL; trial_idx<TRIAL_CNT; trial_idx++ ) {
33 192 : FD_COMPILER_MFENCE();
34 192 : long tic = fd_log_wallclock();
35 192 : FD_COMPILER_MFENCE();
36 192 : long toc = fd_log_wallclock();
37 192 : FD_COMPILER_MFENCE();
38 192 : trial[ trial_idx ] = (double)(toc - tic);
39 192 : FD_COMPILER_MFENCE();
40 192 : }
41 3 : double * sample = trial + TRIM_CNT;
42 3 : ulong sample_cnt = TRIAL_CNT - 2UL*TRIM_CNT;
43 3 : ulong thresh = sample_cnt >> 1;
44 3 : if( FD_LIKELY( fd_stat_robust_exp_fit_double( &t0, &tau, sample, sample_cnt, sample )>thresh ) && FD_LIKELY( t0>0. ) ) break;
45 0 : # undef TRIM_CNT
46 0 : # undef TRIAL_CNT
47 0 : iter++;
48 0 : if( iter==3UL ) {
49 0 : FD_LOG_WARNING(( "unable to model fd_log_wallclock() performance; using fallback and attempting to continue" ));
50 0 : t0 = 27.; tau = 1.;
51 0 : break;
52 0 : }
53 0 : }
54 :
55 3 : } FD_ONCE_END;
56 :
57 60 : if( opt_tau ) opt_tau[0] = tau;
58 60 : return t0;
59 60 : }
60 :
61 : double
62 60 : fd_tempo_tickcount_model( double * opt_tau ) {
63 60 : static double t0;
64 60 : static double tau;
65 :
66 126 : FD_ONCE_BEGIN {
67 :
68 : /* Same as the above but for fd_tickcount(). */
69 :
70 3 : ulong iter = 0UL;
71 3 : for(;;) {
72 1542 : # define TRIAL_CNT 512UL
73 6 : # define TRIM_CNT 64UL
74 3 : double trial[ TRIAL_CNT ];
75 1539 : for( ulong trial_idx=0UL; trial_idx<TRIAL_CNT; trial_idx++ ) {
76 1536 : FD_COMPILER_MFENCE();
77 1536 : long tic = fd_tickcount();
78 1536 : FD_COMPILER_MFENCE();
79 1536 : long toc = fd_tickcount();
80 1536 : FD_COMPILER_MFENCE();
81 1536 : trial[ trial_idx ] = (double)(toc - tic);
82 1536 : FD_COMPILER_MFENCE();
83 1536 : }
84 3 : double * sample = trial + TRIM_CNT;
85 3 : ulong sample_cnt = TRIAL_CNT - 2UL*TRIM_CNT;
86 3 : ulong thresh = sample_cnt >> 1;
87 3 : if( FD_LIKELY( fd_stat_robust_exp_fit_double( &t0, &tau, sample, sample_cnt, sample )>thresh ) && FD_LIKELY( t0>0. ) ) break;
88 0 : # undef TRIM_CNT
89 0 : # undef TRIAL_CNT
90 0 : iter++;
91 0 : if( iter==3UL ) {
92 0 : FD_LOG_WARNING(( "unable to model fd_tickcount() performance; using fallback and attempting to continue" ));
93 0 : t0 = 24.; tau = 4.;
94 0 : break;
95 0 : }
96 0 : }
97 :
98 3 : } FD_ONCE_END;
99 :
100 60 : if( opt_tau ) opt_tau[0] = tau;
101 60 : return t0;
102 60 : }
103 :
104 : static double mu;
105 : static double sigma;
106 : static int explicit_set;
107 :
108 : void
109 : fd_tempo_set_tick_per_ns( double _mu,
110 3 : double _sigma ) {
111 3 : explicit_set = 1;
112 3 : mu = _mu;
113 3 : sigma = _sigma;
114 3 : }
115 :
116 : /* tick_per_ns_sample measures the fd_tickcount()/fd_log_wallclock()
117 : rate and writes the file-scope mu/sigma. Per trial, it observes a
118 : (wallclock,tickcount) pair, sleeps sleep_ns, observes another pair,
119 : and forms d_ticks/d_ns; it then drops the first and last trim_cnt
120 : samples (in time order, to skip warmup/cooldown outliers) and does a
121 : robust normal fit over the remainder.
122 :
123 : The rate accuracy is set by the total observed interval
124 : (trial_cnt*sleep_ns) relative to the observe_pair jitter, and the fit
125 : needs a few samples for sigma. Callers pick the (trial,trim,sleep)
126 : budget that trades wall-clock cost against precision. trial_cnt must
127 : be at most TRIAL_MAX and leave a positive sample count after
128 : trimming (2*trim_cnt<trial_cnt). */
129 :
130 : static void
131 : tick_per_ns_sample( ulong trial_cnt,
132 : ulong trim_cnt,
133 15 : long sleep_ns ) {
134 15 : # define TRIAL_MAX (64UL)
135 15 : if( FD_UNLIKELY( trial_cnt>TRIAL_MAX ) ) FD_LOG_ERR(( "tick_per_ns_sample: trial_cnt %lu exceeds TRIAL_MAX %lu", trial_cnt, TRIAL_MAX ));
136 15 : if( FD_UNLIKELY( 2UL*trim_cnt>=trial_cnt ) ) FD_LOG_ERR(( "tick_per_ns_sample: trim_cnt %lu leaves no samples for trial_cnt %lu", trim_cnt, trial_cnt ));
137 15 : ulong iter = 0UL;
138 15 : for(;;) {
139 15 : double trial[ TRIAL_MAX ];
140 495 : for( ulong trial_idx=0UL; trial_idx<trial_cnt; trial_idx++ ) {
141 480 : long then; long toc; fd_tempo_observe_pair( &then, &toc );
142 480 : fd_log_sleep( sleep_ns );
143 480 : long now; long tic; fd_tempo_observe_pair( &now, &tic );
144 480 : trial[ trial_idx ] = (double)(tic-toc) / (double)(now-then);
145 480 : }
146 15 : double * sample = trial + trim_cnt;
147 15 : ulong sample_cnt = trial_cnt - 2UL*trim_cnt;
148 15 : ulong thresh = sample_cnt >> 1;
149 15 : if( FD_LIKELY( fd_stat_robust_norm_fit_double( &mu, &sigma, sample, sample_cnt, sample )>thresh ) && FD_LIKELY( mu>0. ) )
150 15 : break;
151 0 : iter++;
152 0 : if( iter==3UL ) {
153 0 : FD_LOG_WARNING(( "unable to measure tick_per_ns accurately; using fallback and attempting to continue" ));
154 0 : mu = 3.; sigma = 1e-7;
155 0 : break;
156 0 : }
157 0 : }
158 15 : #undef TRIAL_MAX
159 15 : }
160 :
161 : double
162 183 : fd_tempo_tick_per_ns( double * opt_sigma ) {
163 :
164 402 : FD_ONCE_BEGIN {
165 :
166 : /* If the value has already been set explicitly, no need to sample. */
167 :
168 18 : if( FD_LIKELY( !explicit_set ) ) {
169 :
170 : /* We measure repeatedly how much the tickcount and wallclock change
171 : over the same approximately constant time interval. We do a pair
172 : observations to minimize errors in computing the interval (note
173 : that any remaining jitters should be zero mean such that they
174 : should statistically cancel in the rate calculation). We use a
175 : robust estimate to get the avg and rms in the face of random
176 : sources of noise, assuming the sample distribution is reasonably
177 : well modeled as normal. */
178 :
179 15 : tick_per_ns_sample( 32UL, 4UL, 16777216L /* ~16.8 ms */ );
180 15 : }
181 :
182 18 : } FD_ONCE_END;
183 :
184 183 : if( opt_sigma ) opt_sigma[0] = sigma;
185 183 : return mu;
186 183 : }
187 :
188 : double
189 0 : fd_tempo_tick_per_ns_dev( double * opt_sigma ) {
190 :
191 0 : FD_ONCE_BEGIN {
192 :
193 0 : if( FD_LIKELY( !explicit_set ) ) {
194 :
195 : /* Development-only fast path. 4 trials of ~0.25 ms (~1 ms total)
196 : measures the rate to a few ppm and keeps sigma well defined
197 : (>=2 trials), versus ~0.5 s for the production path. This is
198 : intended for firedancer-dev, where boot latency matters and the
199 : rate is not used for anything consensus critical. See
200 : bench_tempo_calib for the accuracy/cost sweep that motivates
201 : these constants. */
202 :
203 0 : tick_per_ns_sample( 4UL, 0UL, 262144L /* ~0.25 ms */ );
204 :
205 : /* Mark the value explicit so a subsequent fd_tempo_tick_per_ns()
206 : (e.g. later in fd_config_fill) returns this measurement instead
207 : of re-running the slow production sampling. */
208 :
209 0 : explicit_set = 1;
210 0 : }
211 :
212 0 : } FD_ONCE_END;
213 :
214 0 : if( opt_sigma ) opt_sigma[0] = sigma;
215 0 : return mu;
216 0 : }
217 :
218 : #endif
219 :
220 : long
221 : fd_tempo_observe_pair( long * opt_now,
222 1011 : long * opt_tic ) {
223 1011 : long best_wc;
224 1011 : long best_tc;
225 1011 : long best_jt;
226 :
227 1011 : do {
228 :
229 : /* Do an alternating series of:
230 :
231 : tickcount
232 : wallclock
233 : tickcount
234 : wallclock
235 : tickcount
236 : ...
237 : wallclock
238 : tickcount
239 :
240 : observations and pick the wallclock observation that had the
241 : smallest elapsed number of ticks between adjacent tickcount
242 : observations.
243 :
244 : Since the wallclock / tickcounter returns a monotonically
245 : non-decreasing observation of the wallclock / tickcount at a
246 : point in time between when the call was made and when it
247 : returned, we know that this wallclock observation is the one we
248 : made that we know best when it was made in the tickcount stream.
249 : Further, we have lower and upper bounds of the value of the
250 : tickcounter in this read. We start the alternation with the
251 : tickcount because that is typically the lower overhead, more
252 : deterministic one and less likely to get jerked around behind our
253 : back.
254 :
255 : Theoretically, this exploits how the minimum of a shifted
256 : exponential random variable converges. Since the time to read
257 : the various clocks is expected to be reasonably modeled as a
258 : shifted exponential random variable, it doesn't take many trials
259 : to get something close to the minimum (estimating the minimum of
260 : a shifted exponential random variable takes way fewer samples and
261 : is way more accurate than say the estimating the average of a
262 : normally distributed random variable). */
263 :
264 9099 : # define TRIAL_CNT (4) /* 1 "warmup", 3 real reads */
265 :
266 1011 : long wc[ TRIAL_CNT+1 ];
267 1011 : long tc[ TRIAL_CNT+1 ];
268 1011 : FD_COMPILER_MFENCE();
269 1011 : tc[0] = fd_tickcount();
270 1011 : FD_COMPILER_MFENCE();
271 5055 : for( ulong trial_idx=0UL; trial_idx<TRIAL_CNT; trial_idx++ ) {
272 4044 : wc[ trial_idx+1UL ] = fd_log_wallclock();
273 4044 : FD_COMPILER_MFENCE();
274 4044 : tc[ trial_idx+1UL ] = fd_tickcount();
275 4044 : FD_COMPILER_MFENCE();
276 4044 : }
277 :
278 1011 : best_wc = wc[1];
279 1011 : best_tc = tc[1];
280 1011 : best_jt = best_tc - tc[0];
281 4044 : for( ulong trial_idx=1UL; trial_idx<TRIAL_CNT; trial_idx++ ) {
282 3033 : long wci = wc[ trial_idx+1UL ];
283 3033 : long tci = tc[ trial_idx+1UL ];
284 3033 : long jti = tci - tc[ trial_idx ];
285 3033 : int c = (jti<=best_jt);
286 3033 : best_wc = fd_long_if( c, wci, best_wc );
287 3033 : best_tc = fd_long_if( c, tci, best_tc );
288 3033 : best_jt = fd_long_if( c, jti, best_jt );
289 3033 : }
290 :
291 1011 : # undef TRIAL_CNT
292 :
293 1011 : } while(0);
294 :
295 1011 : if( FD_UNLIKELY( best_jt<0L ) ) { /* paranoia */
296 0 : FD_LOG_WARNING(( "fd_tickcount() does not appear to be monotonic; joint read may not be accurate; attempting to continue" ));
297 0 : best_jt = 0L;
298 0 : }
299 :
300 1011 : if( opt_now ) opt_now[0] = best_wc;
301 1011 : if( opt_tic ) opt_tic[0] = best_tc - (best_jt>>1); /* Use lower and upper bound midpoint (could be improved statistically) */
302 1011 : return best_jt;
303 1011 : }
304 :
305 : ulong
306 : fd_tempo_async_min( long lazy,
307 : ulong event_cnt,
308 24 : float tick_per_ns ) {
309 24 : if( FD_UNLIKELY( !((1L<=lazy) & (lazy<(1L<<31))) ) ) {
310 3 : FD_LOG_WARNING(( "lazy should be in [1,2^31)" ));
311 3 : return 0UL;
312 3 : }
313 :
314 21 : if( FD_UNLIKELY( !((1UL<=event_cnt) & (event_cnt<(1UL<<31)) ) ) ) {
315 3 : FD_LOG_WARNING(( "event_cnt should be in [1,2^31)" ));
316 3 : return 0UL;
317 3 : }
318 :
319 18 : float tick_per_ns_max = FLT_MAX / (float)(1L<<31); /* exact, compile time, ~1.5e29 */
320 18 : if( FD_UNLIKELY( !((0.f<tick_per_ns) & (tick_per_ns<=tick_per_ns_max)) ) ) { /* robust against nan */
321 3 : FD_LOG_WARNING(( "tick_per_ns should in (0,~1.5e29)" ));
322 3 : return 0UL;
323 3 : }
324 :
325 15 : float _lazy = (float)lazy; /* typically exact, up to 0.5 ulp error if >~ 2^24 */
326 15 : float _event_cnt = (float)event_cnt; /* typically exact, up to 0.5 ulp error if >~ 2^24 */
327 15 : float _async_target = (tick_per_ns*_lazy) / _event_cnt; /* non-negative finite result, O(1) ulp error typically */
328 :
329 15 : if( FD_UNLIKELY( !(1.f<=_async_target) ) ) {
330 3 : FD_LOG_WARNING(( "lazy, event_cnt and tick_per_ns imply an unreasonably small async_min" ));
331 3 : return 0UL;
332 3 : }
333 :
334 12 : if( FD_UNLIKELY( !(_async_target<((float)(1UL<<32))) ) ) {
335 0 : FD_LOG_WARNING(( "lazy, event_cnt and tick_per_ns imply an unreasonably large async_min" ));
336 0 : return 0UL;
337 0 : }
338 :
339 12 : ulong async_target = (ulong)_async_target; /* in [1,2^32), O(1) ulp error typically (biased conservative) */
340 12 : return 1UL << fd_ulong_find_msb( async_target ); /* guaranteed power of 2 in [1,2^31] */
341 12 : }
|
