From mboxrd@z Thu Jan  1 00:00:00 1970
Received: from eggs.gnu.org ([2001:4830:134:3::10]:59207)
	by lists.gnu.org with esmtp (Exim 4.71)
	(envelope-from <serge.fdrv@gmail.com>) id 1bAdEc-0005IC-MP
	for qemu-devel@nongnu.org; Wed, 08 Jun 2016 09:09:27 -0400
Received: from Debian-exim by eggs.gnu.org with spam-scanned (Exim 4.71)
	(envelope-from <serge.fdrv@gmail.com>) id 1bAdEY-0000KO-AS
	for qemu-devel@nongnu.org; Wed, 08 Jun 2016 09:09:25 -0400
Received: from mail-lf0-x243.google.com ([2a00:1450:4010:c07::243]:33097)
	by eggs.gnu.org with esmtp (Exim 4.71)
	(envelope-from <serge.fdrv@gmail.com>) id 1bAdEY-0000KG-2R
	for qemu-devel@nongnu.org; Wed, 08 Jun 2016 09:09:22 -0400
Received: by mail-lf0-x243.google.com with SMTP id u74so771056lff.0
	for <qemu-devel@nongnu.org>; Wed, 08 Jun 2016 06:09:21 -0700 (PDT)
References: <1464138802-23503-1-git-send-email-cota@braap.org>
	<1464138802-23503-9-git-send-email-cota@braap.org>
	<5749E02A.3080909@gmail.com> <20160603172245.GA8361@flamenco>
	<5751BE73.2090402@gmail.com> <5751C25F.6080801@gmail.com>
	<20160606234014.GA4418@flamenco> <5756D4D8.7060202@gmail.com>
	<20160607225300.GA16255@flamenco>
From: Sergey Fedorov <serge.fdrv@gmail.com>
Message-ID: <575818FF.1090802@gmail.com>
Date: Wed, 8 Jun 2016 16:09:19 +0300
MIME-Version: 1.0
In-Reply-To: <20160607225300.GA16255@flamenco>
Content-Type: text/plain; charset=windows-1252
Content-Transfer-Encoding: 7bit
Subject: Re: [Qemu-devel] [PATCH v6 08/15] qdist: add module to represent
 frequency distributions of data
List-Id: <qemu-devel.nongnu.org>
List-Unsubscribe: <https://lists.nongnu.org/mailman/options/qemu-devel>,
	<mailto:qemu-devel-request@nongnu.org?subject=unsubscribe>
List-Archive: <http://lists.nongnu.org/archive/html/qemu-devel/>
List-Post: <mailto:qemu-devel@nongnu.org>
List-Help: <mailto:qemu-devel-request@nongnu.org?subject=help>
List-Subscribe: <https://lists.nongnu.org/mailman/listinfo/qemu-devel>,
	<mailto:qemu-devel-request@nongnu.org?subject=subscribe>
To: "Emilio G. Cota" <cota@braap.org>
Cc: QEMU Developers <qemu-devel@nongnu.org>, MTTCG Devel <mttcg@listserver.greensocs.com>, =?UTF-8?Q?Alex_Benn=c3=a9e?= <alex.bennee@linaro.org>, Paolo Bonzini <pbonzini@redhat.com>, Richard Henderson <rth@twiddle.net>

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