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