From mboxrd@z Thu Jan  1 00:00:00 1970
Return-Path: <eric.dumazet@gmail.com>
Received: from mail-bk0-f43.google.com (mail-bk0-f43.google.com
	[209.85.214.43]) (using TLSv1 with cipher RC4-SHA (128/128 bits))
	(Client CN "smtp.gmail.com",
	Issuer "Google Internet Authority" (verified OK))
	by huchra.bufferbloat.net (Postfix) with ESMTPS id 2635B200B29
	for <codel@lists.bufferbloat.net>; Fri,  4 May 2012 08:56:45 -0700 (PDT)
Received: by bkty5 with SMTP id y5so5289309bkt.16
	for <codel@lists.bufferbloat.net>; Fri, 04 May 2012 08:56:43 -0700 (PDT)
DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20120113;
	h=subject:from:to:cc:in-reply-to:references:content-type:date
	:message-id:mime-version:x-mailer:content-transfer-encoding;
	bh=1iP1zr99wd85aMj91hPPycOkMSxyDog/3mJHN4GRDF4=;
	b=rtm31Wak3215HbyKXbTCGUhtPE9xfRIBaEqlo270HICu9PGslc/11frR9AhVpQIggc
	PYdI1XXBdT3seRare87GzYxAZ8W5+AvZP88o7XlGWs8evaCZsoSZAjNgf7NbC12a83tL
	pEBpNE7sI8lVuEgWS7923Za/MnsgxcFEF4X62G8XVQmneVaARAEMolxBqs7t/Se+3inf
	CQGWjS11QuVVnWV/KY3nQ8zuTrpfAdxr0i8XUnjZarXgCmnMtR0FmEDEEjCVulKF6Vu9
	Tl4xvuLmNcOKP2wu/qDxE9JEaX2nRUnv0pRx5BrL6eBFnlR38AIRY7ufPLn3xkXDRr70
	2Nug==
Received: by 10.204.156.215 with SMTP id y23mr2343681bkw.35.1336147003186;
	Fri, 04 May 2012 08:56:43 -0700 (PDT)
Received: from [172.28.131.195] ([74.125.122.49])
	by mx.google.com with ESMTPS id g5sm17801711bkt.9.2012.05.04.08.56.35
	(version=SSLv3 cipher=OTHER); Fri, 04 May 2012 08:56:42 -0700 (PDT)
From: Eric Dumazet <eric.dumazet@gmail.com>
To: Jim Gettys <jg@freedesktop.org>
In-Reply-To: <4FA3F50D.7080406@freedesktop.org>
References: <CAA93jw49KZZHBfb47cGN7tTxw8RbGzHHEVodhdpzmbOp78CREQ@mail.gmail.com>
	<4FA3F248.3070101@freedesktop.org>
	<CAA93jw4wzVLrMOq+RzP2FTHCHaPrFAY06xJX=Q94nPO0z2-OcQ@mail.gmail.com>
	<4FA3F50D.7080406@freedesktop.org>
Content-Type: text/plain; charset="UTF-8"
Date: Fri, 04 May 2012 17:56:33 +0200
Message-ID: <1336146993.3752.354.camel@edumazet-glaptop>
Mime-Version: 1.0
X-Mailer: Evolution 2.28.3 
Content-Transfer-Encoding: 7bit
Cc: codel@lists.bufferbloat.net
Subject: Re: [Codel] fp sqrt vis int sqrt?
X-BeenThere: codel@lists.bufferbloat.net
X-Mailman-Version: 2.1.13
Precedence: list
List-Id: CoDel AQM discussions <codel.lists.bufferbloat.net>
List-Unsubscribe: <https://lists.bufferbloat.net/options/codel>,
	<mailto:codel-request@lists.bufferbloat.net?subject=unsubscribe>
List-Archive: <https://lists.bufferbloat.net/private/codel>
List-Post: <mailto:codel@lists.bufferbloat.net>
List-Help: <mailto:codel-request@lists.bufferbloat.net?subject=help>
List-Subscribe: <https://lists.bufferbloat.net/listinfo/codel>,
	<mailto:codel-request@lists.bufferbloat.net?subject=subscribe>
X-List-Received-Date: Fri, 04 May 2012 15:56:46 -0000

On Fri, 2012-05-04 at 11:26 -0400, Jim Gettys wrote:

> 
> I suspect there are fully integer implementations kicking around... 
> It's just that x86 finally got fast enough FP that doing one multiply in
> floating point beat the alternative.

Anyway we dont need to compute sqrt() at all.

This can be done easily when we do the q->count++, if we hold in
q->sqrt_count the estimated value of sqrt(count)

Ie replace :

q->count++;

by:

q->count++;
n = q->sqrt_count + 1;
if (n * n <= q->count)
	q->sqrt_count = n;

A multiply is an acceptable cost.


Of course, you need to reset sqrt_count to 1 when count is reset to 1