Re: [Qemu-devel] [PATCH v6 08/15] qdist: add module to represent frequency distributions of data

[Emilio G. Cota]

On Tue, Jun 07, 2016 at 17:06:16 +0300, Sergey Fedorov wrote:
> On 07/06/16 02:40, Emilio G. Cota wrote:
> > On Fri, Jun 03, 2016 at 20:46:07 +0300, Sergey Fedorov wrote:
> >> Maybe something like
> >> https://en.wikipedia.org/wiki/Kahan_summation_algorithm could help?
> > That algorithm is overkill for what we're doing. Pairwise summation
> > should suffice:
> >
> > diff --git a/util/qdist.c b/util/qdist.c
> > index 3343640..909bd2b 100644
> > --- a/util/qdist.c
> > +++ b/util/qdist.c
> > @@ -367,20 +367,34 @@ unsigned long qdist_sample_count(const struct qdist 
> > *dist)
> >      return count;
> >  }
> >  
> > +static double qdist_pairwise_avg(const struct qdist *dist, size_t index,
> > +                                 size_t n, unsigned long count)
> > +{
> > +    if (n <= 2) {
> 
> We would like to amortize the overhead of the recursion by making the
> cut-off sufficiently large.

Yes, this was just for showing what it looked like.

We can use 128 here like JuliaLang does:
  https://github.com/JuliaLang/julia/blob/d98f2c0dcd/base/arraymath.jl#L366

(snip)
> Otherwise looks good.

Thanks!

                Emilio