We don't bite newbies here... much PerlMonks

### Acceleration ETA algorithm

by phizel (Acolyte)
 on Jan 27, 2024 at 17:49 UTC Need Help??

Was looking for a decent algorithm for determining the ETA of a long-running process, but everything on CPAN uses simplistic and inaccurate algorithms. Found this great article Benchmarking I/O ETA algorithms and converted the Acceleration algorithm to perl. And yes, it would be better to extract the state components into an object.
use Time::HiRes qw(time); sub eta { my (\$cur, \$total, \$time) = @_; return unless \$cur and \$time; state (\$last_progress, \$last_time, \$last_v, \$last_eta); state (@v, @eta, \$window_size, \$window_idx); state \$init = do { (\$last_progress, \$last_time, \$last_v, \$last_eta) = (0, 0, 0, - +1); (\$window_size, \$window_idx) = (10, 0); }; state \$sub_v_weight = sub { 1 + \$_[0] }; state \$sub_eta_weight = sub { \$_[0] ? 2 * \$_[1] : 1 }; state \$sub_weighted_avg = sub { my (\$sub_weight, \$avg, \$total_weight, \$w) = (shift, 0, 0, 0); for my \$i (0 .. \$#_) { # first version messed up the index. my \$j = (\$i + @_ - \$window_idx - 1) % @_; \$w = \$sub_weight->(\$j, \$w); \$avg += \$w * \$_[\$i]; \$total_weight += \$w; } return \$avg / \$total_weight; }; my \$v = (\$cur - \$last_progress) / ((\$time - \$last_time) || 1); \$v[\$window_idx] = \$v; \$v = \$sub_weighted_avg->(\$sub_v_weight, @v); if (\$v and \$last_v) { my (\$min_v, \$max_v) = \$v < \$last_v ? (\$v, \$last_v) : (\$last_v, + \$v); \$v = \$last_v + (\$v - \$last_v) * \$min_v / \$max_v; } my \$a = (\$v - \$last_v) / (\$last_time ? (\$time - \$last_time) : 1); my \$r = \$total - \$cur; my \$eta = \$last_eta; if (\$a and 0 < (my \$d = (\$v * \$v + 2 * \$a * \$r))) { \$eta = (sqrt(\$d) - \$v) / \$a; } elsif (\$v) { \$eta = \$r / \$v } \$eta[\$window_idx] = \$eta; \$eta = \$sub_weighted_avg->(\$sub_eta_weight, @eta); (\$last_progress, \$last_time, \$last_v, \$last_eta, \$window_idx) = (\$cur, \$time, \$v, \$eta, (\$window_idx + 1) % \$window_size); return \$eta > 0 ? \$eta : 0; }

Replies are listed 'Best First'.
Re: Acceleration ETA algorithm
by Anonymous Monk on Jan 28, 2024 at 10:28 UTC

How is this supposed to work?

say eta(1, 100, 1);

says 13.1067359796659 (shouldn't it be 100?). OK, with another call:

say eta(2, 100, 2);

says "Illegal division by zero" -- because \$total_weight is zero.

Re: Acceleration ETA algorithm
by stevieb (Canon) on Jan 27, 2024 at 18:25 UTC

Could you include a common use case?

When you want to print out progress but don't actually want a progress bar like Term::ProgressBar.
> like Term::ProgressBar.

Hmm, the thing with progress bars (as I know them) is that they only move right. A considerable slow down will stall them, without giving a hint about a new prognosis.

They often only show the amount of work done, like percentage of downloaded data.

But an ETA can adapt and give a better feedback, how long to wait.

Like if a torrent download is losing connection to seeders, and the ratio drops.

I still have to read this test in detail, I'm wondering by which objective criteria those algorithms are judged. (?)

Cheers Rolf
(addicted to the Perl Programming Language :)
see Wikisyntax for the Monastery

ETA = Estimated Time of Arrival

I had to search for it too. Don't think I heard it before in the context of applications.

The OP would have been clearer if it included at least one non-abbreviated reference.

Cheers Rolf
(addicted to the Perl Programming Language :)
see Wikisyntax for the Monastery

Re: Acceleration ETA algorithm
by LanX (Saint) on Jan 28, 2024 at 03:38 UTC
> And yes, it would be better to extract the state components into an object

I think it's easier (and better) rewritten in functional style with a generator function returning the ETA closure function.

Most of your states would be my-vars in the outer generators scope. And you wouldn't need the voodoo to initialize the first run.

This  state \$init = do {... } is an interesting trick tho. :)

Cheers Rolf
(addicted to the Perl Programming Language :)
see Wikisyntax for the Monastery

Create A New User
Domain Nodelet?
Node Status?
node history
Node Type: CUFP [id://11157303]
Front-paged by stevieb
help
Chatterbox?
and the web crawler heard nothing...

How do I use this?Last hourOther CB clients
Other Users?
Others exploiting the Monastery: (4)
As of 2024-06-19 07:45 GMT
Sections?
Information?
Find Nodes?
Leftovers?
Voting Booth?

No recent polls found

Notices?
 • erzuuli ‥ 🛈The London Perl and Raku Workshop takes place on 26th Oct 2024. If your company depends on Perl, please consider sponsoring and/or attending.