Of stupid algos and code complexity

[grinvader]

The question: who'd be interested in a smart(er) ETA calculator at the price of pretty fat code complexity ?

[funkyass]

whut?

[SquareHead]

whut?

Seconded

[byuu]

[adventure_of_link]

whut?

Seconded

thirded

[Johan_H]

Oh, estimated time of arrival. I want to take back my vote now :(
I don't think I really care. I guess I'd rather save a small amount of energy than be given a better estimation that's bound to not be really reliable anyway?
*shrugses*

[Rashidi]

best ETA i have encountered that would be RAR (2.0) Dos' ETA (pre-winrar one).

most current ETAs are not as realible as those in Dos era before.
is that indicate that smart(er) ETA doesn't really-trully need all those GHz it could get?

[odditude]

most current ETAs are not as realible as those in Dos era before.
is that indicate that smart(er) ETA doesn't really-trully need all those GHz it could get?

no, it indicates that it's much simpler to produce an accurate ETA in a single-tasking environment.

[diminish]

Hmm, I guess it would mainly depend on the userbase and application, but I'm generally against these kind of estimations, I would personally rather work with raw or intermediate data. Reasons for that are:

• gigahurtz wasted for luxury when they could do something more productive
• it's still estimation after all
• more fun to watch several much more accurate variables

On the other side, there are cases where such estimation comes in handy - where it could provide a point in critical decision making, I'm thinking here about situations with relatively big/small estimation values where they could be an indication of unfavorable state for the user which isn't blatantly obvious. So, conditionally, option 1 of the poll at the moment, problem seems more complex than one would think.

[franpa]

Doesn't Microsofts focus on max. speed instead of average speed when determining a ETA? would explain the gargantuan swings in the ETA.

[Cyrus]

I got an angry Core 2 from the mesozoic era and it has gigahurtz to burn.

[grinvader]

explicative notice

Much appreciated.

Doesn't Microsofts focus on max. speed instead of average speed when determining a ETA? would explain the gargantuan swings in the ETA.

It initialises the expected transfer rate at the max configurated, then averages it as it goes - leading to 321465465 days ETAs if the transfer dies.
At least in stuff I witnessed.

best ETA i have encountered that would be RAR (2.0) Dos' ETA (pre-winrar one).

most current ETAs are not as realible as those in Dos era before.
is that indicate that smart(er) ETA doesn't really-trully need all those GHz it could get?

This is an example of almost-constant rate where the stupid algo works out fine.

[Nightcrawler]

An accurate percentage progress bar is probably more useful to me. ETA are rarely ever spot on, especially if your computer is busy doing any other tasks.

[franpa]

Even IE downloads fail to have accurate ETA's. Firefox downloads however, well that has pretty decent ETA.

[Nach]

Well, you know I asked for this before. I'd like to be have a smarter algo in my ETA lib which I've been using everywhere.

Now when you say pretty fat code complexity, do you mean it'll be so fat that updating the ETA will take so long that the updates happening at per second intervals will take so long several seconds will pass in between?

You don't want the overhead to take longer than the operation itself for that chunk. We need the right trade off here. I think the algo should be 'instant' on a 1GHz processor, or something in that neighborhood.

[paulguy]

I selected 1 because I really don't like code that's hard to read. But even a complex algorithm could be written and commented in such a way to make it more apparent, which is what I'd go for.

On the flip side, a lot of coders like to make the simplest algorithms look like crazy mathematical operations because they like to cram as much as they can in to a single statement.

[grinvader]

when you say pretty fat code complexity, do you mean it'll be so fat that updating the ETA will take so long that the updates happening at per second intervals will take so long several seconds will pass in between?

That would be pretty suck.

Pretty fat is "eats ram". Hundreds of bytes !!1!
The operation itself will also be immensely slower than a stupid algo and several times slower than a straightforward 'short-term memory' algo, but we're still talking fractions of millisecond per execution here.

On the flip side, a lot of coders like to make the simplest algorithms look like crazy mathematical operations because they like to cram as much as they can in to a single statement. :|

¬_¬

"meh"

Edit: look, it's commented and all

Code: Select all

  hbuf[id].total += sample - hbuf[id].sample[hbuf[id].ofs]; // \^_^

124 lines, 3117 bytes comments included.
Allocates ~1.8kB.

[paulguy]

That line is reasonably understandable. I'm mostly referring to crap like *(ptr++) += 4 as a relatively mild example. Sure the meaning of that is readily apparent now, but a large chunk of code with that similar quality to it can be rather hairy... especially when people just use a, b, c, d, etc for variables.

[grinvader]

I don't see how you find structure-array-member-indexed structure array member array understandable but not a simple pointed update+pointer advance like your example (oh, and remove the (), since p++ is prioritary over both *p and +=)

Anyway, that's just the next line. :p

Code: Select all

  hbuf[id].sample[hbuf[id].ofs++] = sample;

[Nach]

Pretty fat is "eats ram". Hundreds of bytes !!1!
The operation itself will also be immensely slower than a stupid algo and several times slower than a straightforward 'short-term memory' algo, but we're still talking fractions of millisecond per execution here.

If that's the case, then I don't even see the question involved, of course go for it!!!

Also, alongside ETA, if measuring any kind of data per time calculation is involved, it'd be nice if that can presented somehow too. Like 21.37 MB/s.

[funkyass]

make it smooth.

[grinvader]

Also, alongside ETA, if measuring any kind of data per time calculation is involved, it'd be nice if that can presented somehow too. Like 21.37 MB/s.

Hmm, that's more a job for the caller - since the current code returns the ETA in number of calls (if you call the function at whatever interval you want, the caller then converts the number of calls into seconds), I could even remove the extrapolation step from my code and just return the computed speed (in bytes per call) to use.
The caller would then use that value to display it, extrapolate ETA, kick puppies, and so on.

make it smooth.

... as in ?

[funkyass]

as in no sudden jumps in the displayed transfer rate.

[grinvader]

The goal is to prevent seesaw ETAs - high for some time, low for some time, when it's obvious the real result is in the middle and you just need a larger memory span to 'see' the stable average.

On the contrary, there will be sudden variations if your transfer rate suddenly changes and then remains stable instead of a fake rate that still remembers stale values. Only logical.
If the rate changes erratically, the larger buffer is used to flatten the average.

See what I mean ?

Anyway, have a shot. It's still alpha, mind you. A smart compiler is needed to prevent fpu exceptions, too.

Code: Select all

/*
 * grinvader's revised estimated arrival time v0.1a
 * distributed under the badass licence
 * (if you don't get it, don't use it)
 *
 * lawlz (L) 2009/11
 *

 keeps 4 'short'-memory buffers (relative sizes 1,4,16,64), computes average
 amount per call when enough data is gathered, checks stream stability and uses
 the largest range stable speed to compute how many calls are left.

 currently designed around a single transfer at a time - for simultaneous
 transfers, extend the code so that you get an array of hbuf[4]s, and pass the
 transfer id to the various hb functions/macros, obviously.

 need more comments ? how about no
*/

#include <stdio.h>
#include <string.h>
#include <stdint.h>

#define INIT_HB(id) \
  memset(hbuf[id].sample, 0, 4*sizeof(uint64_t)); \
  hbuf[id].stable = hbuf[id].ofs = hbuf[id].mean = hbuf[id].total = 0; \
  hbuf[id].range = 2*id; \
  hbuf[id].calc = 8

#define UPDATE_HB(id) if (call_cnt >> hbuf[id].range) fill_hb(id, sample)

#define SET_RESULT(id) if (hbuf[id].stable) result = left_sz / hbuf[id].mean

struct {
  uint64_t sample[4];
  uint64_t total;
  uint64_t mean;
  uint8_t range;
  uint8_t calc;
  uint8_t ofs;
  uint8_t stable;
} hbuf[4];

int_fast8_t call_cnt;

static void init_hb()
{
  INIT_HB(0);
  INIT_HB(1);
  INIT_HB(2);
  INIT_HB(3);

  call_cnt = 0;
}

static void fill_hb(const uint8_t id, uint64_t sample)
{
  if (id) { sample = hbuf[id-1].total; }

  hbuf[id].total += sample - hbuf[id].sample[hbuf[id].ofs]; // \^_^
  hbuf[id].sample[hbuf[id].ofs++] = sample;
  hbuf[id].ofs &= 3;
  hbuf[id].calc /= 2;

  if (!hbuf[id].calc)
  {
    int_fast8_t i = 4;

    hbuf[id].stable = 1;
    hbuf[id].mean = hbuf[id].total / (4 << hbuf[id].range);
// less than 1 byte between each call ? kill yourself.
    while (hbuf[id].stable && i--)
    {
      uint64_t diff = (hbuf[id].mean > hbuf[id].sample[i]) ?
                      hbuf[id].mean - hbuf[id].sample[i] :
                      hbuf[id].sample[i] - hbuf[id].mean;
      hbuf[id].stable &= hbuf[id].mean &&
                         (((float)diff / (hbuf[id].mean << id)) < 0.12f);
    }
  }
}

static int64_t get_ETA(const uint64_t sample, const uint64_t left_sz)
{
  int64_t result = -1; // in number of calls

  call_cnt = (call_cnt & 63) + 1;

  UPDATE_HB(0);
  UPDATE_HB(1);
  UPDATE_HB(2);
  UPDATE_HB(3);

  SET_RESULT(3);
  else SET_RESULT(2);
  else SET_RESULT(1);
  else SET_RESULT(0);

  return (result); // you should display -1 as "--w--d--:--:--" or "DNF" or smth
}

int main() // an example
{
  uint64_t cur_xfer, prev_xfer = 0, total_sz, time_between_calls;

// yak yak stuff here

  init_hb(); // once per transfer procedure

// initiate your transfer loop here
  {
    int64_t calls_remaining, time_remaining;
// code that includes smth like cur_xfer = total_amount_transferred();
    calls_remaining = get_ETA(cur_xfer - prev_xfer, total_sz - cur_xfer);
    time_remaining = calls_remaining * time_between_calls;
// stuff here if you still need the old value of prev_xfer
    prev_xfer = cur_xfer;
// more code
  }

// even more code

  return (0); // thanks for reading, HAND
}

[Nach]

Thanks, I'll go pop this into my download client and see how it does.