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

[Paolo Bonzini]

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 <address@hidden>

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);
> +}

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---------|


- 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