[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]
Re: [Qemu-devel] [PATCH v6 08/15] qdist: add module to represent frequen
From: |
Sergey Fedorov |
Subject: |
Re: [Qemu-devel] [PATCH v6 08/15] qdist: add module to represent frequency distributions of data |
Date: |
Wed, 8 Jun 2016 16:09:19 +0300 |
User-agent: |
Mozilla/5.0 (X11; Linux x86_64; rv:38.0) Gecko/20100101 Thunderbird/38.8.0 |
On 08/06/16 01:53, Emilio G. Cota wrote:
> 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
>
>
Probably cut-off of ~10 items would be enough to amortize the recursion
in C.
Kind regards,
Sergey