Re: [Qemu-devel] [PATCH v2 3/3] util: Add an utility infrastructure used to compute an average on a time slice

["Benoît Canet" <benoit.canet@irqsave.net>]

The Monday 08 Sep 2014 à 16:29:26 (+0200), Paolo Bonzini wrote :
> Il 08/09/2014 14:18, Benoît Canet ha scritto:
> > The algorithm used was defined on the list while discussing the new IO accounting
> > overhaul.
> > See http://lists.nongnu.org/archive/html/qemu-devel/2014-08/msg04954.html
> > 
> > Also the module takes care of computing minimal and maximal values over the time
> > slice duration.
> > 
> > Signed-off-by: Benoît Canet <benoit.canet@nodalink.com>
> 
> If you add
> 
> int64_t cpu_get_clock(void)
> {
>     return my_clock_value;
> }
> 
> to the test, and use a QEMU_CLOCK_VIRTUAL-based average, you should be
> able to advance the clock directly in the test with no need for sleep()
> and with 100% deterministic results.
> 
> > 
> > +/* Check if the ta->periods seconds time slice has expired
> > + *
> > + * If the slice has expired the counters will be reseted
> > + *
> > + * @ta: the timed average structure used
> > + */
> > +static void timed_average_check_expiration(TimedAverage *ta)
> > +{
> > +    int64_t now = qemu_clock_get_ns(ta->clock_type);
> > +
> > +    /* if we are still in the period slice do nothing */
> > +    if (now < ta->expiration) {
> > +        return;
> > +    }
> > +
> > +    /* the slice has expired -> create a new slice */
> > +    ta->min = UINT64_MAX;
> > +    ta->sum = 0;
> > +    ta->max = 0;
> > +    ta->count = 0;
> > +    timed_average_set_expiration(ta);
> > +}
> 
Thanks for reviewing.

> This can produce very noisy results if you invoke min/avg/max at the
> wrong time.  Some alternatives include:
> 
> - create two windows, with twice the suggested expiration period, and
> return min/avg/max from the oldest window.  Example
> 
>        t=0          |t=1          |t=2          |t=3          |t=4
>        wnd0: [0,1)  |wnd0: [1,3)  |             |wnd0: [3,5)  |
>        wnd1: [0,2)  |             |wnd1: [2,4)  |             |
> 
> Values are returned from:
> 
>        wnd0---------|wnd1---------|wnd0---------|wnd1---------|


This is neat.
As I think that knowing the minimal and maximal latencies of a block device
would be handy I will implement this.

Best regards

Benoît

> 
> 
> - if you do not need min/max, you can use exponential smoothing, with a
> weighted factor that depends on the time since the last sample.
> http://www.drdobbs.com/tools/discontiguous-exponential-averaging/184410671
> -- for example, giving 90% weight to the last second.  Of course the
> exponential nature means that, in that case, 1-sqrt(10%)=68.3% weight is
> given to the last half second, 21.6% weight is given to the previous
> half second, and 10% to the entire previous history.  This cannot give
> min/max, but can give avg/stdev.
> 
> Paolo
>