From 56e64d62c1ed1a77ec12e0eed63da26d24a87bba Mon Sep 17 00:00:00 2001 From: sebres Date: Wed, 22 Jan 2025 17:24:29 +0000 Subject: fixes timerate command (avoids drastic growth of execution time on iteration with quadratic complexity, O(n**2) etc) --- generic/tclCmdMZ.c | 126 ++++++++++++++++++++++++++++++++++++----------------- 1 file changed, 87 insertions(+), 39 deletions(-) diff --git a/generic/tclCmdMZ.c b/generic/tclCmdMZ.c index 0629a81..acd07c9 100644 --- a/generic/tclCmdMZ.c +++ b/generic/tclCmdMZ.c @@ -3997,18 +3997,30 @@ Tcl_TimeRateObjCmd( register int result, i; Tcl_Obj *calibrate = NULL, *direct = NULL; TclWideMUInt count = 0; /* Holds repetition count */ + TclWideMUInt lastCount = 0; /* Repetition count since last calculation. */ Tcl_WideInt maxms = WIDE_MIN; /* Maximal running time (in milliseconds) */ - TclWideMUInt maxcnt = WIDE_MAX; + TclWideMUInt maxcnt = UWIDE_MAX; /* Maximal count of iterations. */ TclWideMUInt threshold = 1; /* Current threshold for check time (faster * repeat count without time check) */ - TclWideMUInt maxIterTm = 1; /* Max time of some iteration as max - * threshold, additionally avoiding divide to - * zero (i.e., never < 1) */ - unsigned short factor = 50; /* Factor (4..50) limiting threshold to avoid + TclWideMUInt avgIterTm = 1; /* Average time of all processed iterations. */ + TclWideMUInt lastIterTm = 1;/* Average time of last block of iterations. */ + double estIterTm = 1.0; /* Estimated time of next iteration, + * considering the growth of lastIterTm. */ +#ifdef TCL_WIDE_CLICKS +# define TR_SCALE 10 /* Fraction is 10ns (from wide click 100ns). */ +#else +# define TR_SCALE 100 /* Fraction is 10ns (from 1us = 1000ns). */ +#endif +#define TR_MIN_FACTOR 2 /* Min allowed factor calculating threshold. */ +#define TR_MAX_FACTOR 50 /* Max allowed factor calculating threshold. */ +#define TR_FACT_SINGLE_ITER 25 /* This or larger factor value will force the + * threshold 1, to avoid drastic growth of + * execution time by quadratic O() complexity. */ + unsigned short factor = 16; /* Factor (2..50) limiting threshold to avoid * growth of execution time. */ - register Tcl_WideInt start, middle, stop; + register Tcl_WideInt start, last, middle, stop; #ifndef TCL_WIDE_CLICKS Tcl_Time now; #endif /* !TCL_WIDE_CLICKS */ @@ -4210,7 +4222,7 @@ Tcl_TimeRateObjCmd( */ #ifdef TCL_WIDE_CLICKS - start = middle = TclpGetWideClicks(); + start = last = middle = TclpGetWideClicks(); /* * Time to stop execution (in wide clicks). @@ -4222,7 +4234,7 @@ Tcl_TimeRateObjCmd( start = now.sec; start *= 1000000; start += now.usec; - middle = start; + last = middle = start; /* * Time to stop execution (in microsecs). @@ -4301,59 +4313,91 @@ Tcl_TimeRateObjCmd( } /* - * Don't calculate threshold by few iterations, because sometimes - * first iteration(s) can be too fast or slow (cached, delayed - * clean up, etc). + * Average iteration time (scaled) in fractions of wide clicks + * or microseconds. */ - if (count < 10) { - threshold = 1; - continue; - } - - /* - * Average iteration time in microsecs. - */ - - threshold = (middle - start) / count; - if (threshold > maxIterTm) { - maxIterTm = threshold; + threshold = (TclWideMUInt)(middle - start) * TR_SCALE / count; + if (threshold > avgIterTm) { /* * Iterations seem to be longer. */ - if (threshold > maxIterTm * 2) { + if (threshold > avgIterTm * 2) { factor *= 2; - if (factor > 50) { - factor = 50; - } } else { - if (factor < 50) { - factor++; - } + factor++; } - } else if (factor > 4) { + if (factor > TR_MAX_FACTOR) { + factor = TR_MAX_FACTOR; + } + } else if (factor > TR_MIN_FACTOR) { /* * Iterations seem to be shorter. */ - if (threshold < (maxIterTm / 2)) { + if (threshold < (avgIterTm / 2)) { factor /= 2; - if (factor < 4) { - factor = 4; + if (factor < TR_MIN_FACTOR) { + factor = TR_MIN_FACTOR; } } else { factor--; } } + if (!threshold) { + /* too short and too few iterations */ + threshold = 1; + continue; + } + avgIterTm = threshold; + /* - * As relation between remaining time and time since last check, - * maximal some % of time (by factor), so avoid growing of the - * execution time if iterations are not consistent, e.g. was - * continuously on time). + * Estimate last iteration time growth and time of next iteration. */ + lastCount = count - lastCount; + if (last != start && lastCount) { + TclWideMUInt lastTm; + + lastTm = (TclWideMUInt)(middle - last) * TR_SCALE / lastCount; + estIterTm = (double)lastTm / (lastIterTm ? lastIterTm : avgIterTm); + lastIterTm = lastTm > avgIterTm ? lastTm : avgIterTm; + } else { + lastIterTm = avgIterTm; + } + estIterTm *= lastIterTm; + last = middle; lastCount = count; - threshold = ((stop - middle) / maxIterTm) / factor + 1; + /* + * Calculate next threshold to check. + * Firstly check iteration time is not larger than remaining time, + * considering last known iteration growth factor. + */ + threshold = (TclWideMUInt)(stop - middle) * TR_SCALE; + /* + * Estimated count of iteration til the end of execution. + * Thereby 2.5% longer execution time would be OK. + */ + if (threshold / estIterTm < 0.975) { + /* estimated time for next iteration is too large */ + break; + } + threshold /= estIterTm; + /* + * Don't use threshold by few iterations, because sometimes + * first iteration(s) can be too fast or slow (cached, delayed + * clean up, etc). Also avoid unexpected execution time growth, + * so if iterations continuously grow, stay by single iteration. + */ + if (count < 10 || factor >= TR_FACT_SINGLE_ITER) { + threshold = 1; + continue; + } + /* + * Reduce it by last known factor, to avoid unexpected execution + * time growth if iterations are not consistent (may be longer). + */ + threshold = threshold / factor + 1; if (threshold > 100000) { /* fix for too large threshold */ threshold = 100000; } @@ -4502,6 +4546,10 @@ Tcl_TimeRateObjCmd( TclReleaseByteCode(codePtr); } return result; +#undef TR_SCALE +#undef TR_MIN_FACTOR +#undef TR_MAX_FACTOR +#undef TR_FACT_SINGLE_ITER } /* -- cgit v0.12