From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: from mail-wg0-f47.google.com (mail-wg0-f47.google.com [74.125.82.47]) (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 18E8B200B29 for ; Fri, 4 May 2012 08:19:30 -0700 (PDT) Received: by wgbfa7 with SMTP id fa7so2294457wgb.28 for ; Fri, 04 May 2012 08:19:29 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20120113; h=mime-version:in-reply-to:references:date:message-id:subject:from:to :cc:content-type:content-transfer-encoding; bh=tZsTb91+xZxUpcL/ZVtoPuc/gboBdRDDmx11qhlBlQ0=; b=wiHsVMLPzYdqaZ4jcrIKpcfsCvojzBwJFL6DNDSdpNi9B0AsEzjEqml+AEbyHerf7d /cG7Txk0IDmIyenDxm8YpmGFhF+VtJzRexXARAMxVOFsVTO1ANteQ8ouD/GsPhBqb+Dx rv4029PmuQHZMHHhvFDHCqFD3WqaeKDQVRIyaSQrk8FDhmyIfo1WiurL8dzoiT5M0f9I zMW9Ns6szPM2xhqa+/tjyVe6rGIyWaTlXirYP+OUoI4OYxtKjdL78pADyf7b+24HBZ0W B5MiikM4N5DR6Pn5ZYw9X2+JtN/ojC1fqBq7t+vlmO/2A9ZhAc4xb8naLUqFeYd+Id7h PSLw== MIME-Version: 1.0 Received: by 10.180.105.69 with SMTP id gk5mr15888513wib.3.1336144741951; Fri, 04 May 2012 08:19:01 -0700 (PDT) Received: by 10.223.112.66 with HTTP; Fri, 4 May 2012 08:19:01 -0700 (PDT) In-Reply-To: <4FA3F248.3070101@freedesktop.org> References: <4FA3F248.3070101@freedesktop.org> Date: Fri, 4 May 2012 08:19:01 -0700 Message-ID: From: Dave Taht To: Jim Gettys Content-Type: text/plain; charset=ISO-8859-1 Content-Transfer-Encoding: quoted-printable 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 List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , X-List-Received-Date: Fri, 04 May 2012 15:19:31 -0000 On Fri, May 4, 2012 at 8:14 AM, Jim Gettys wrote: > On 05/04/2012 11:11 AM, Dave Taht wrote: >> The linux kernel has no floating point in it, so I'd substituted the >> internal int_sqrt as a substitute, >> just to get something to work. >> >> static inline ktime_t control_law(const struct codel_sched_data *q, ktim= e_t t) >> { >> =A0 =A0 =A0 =A0 return ktime_add_ns(t, q->interval / int_sqrt(q->count))= ; >> } >> >> Often ns2 models use floating point. Having not seen the model I don't >> know that for sure. >> >> The series for an integer sqrt is far more 'chunky' than a fp one. >> >> int sqrt 1,2,3,4 =3D 1 1 1 2 >> fp sqrt 1 2 3 4 =3D 1 1.4.1 1.73 2 >> >> and gets even more chunky as you get larger values, eg, sqrt(36 >> through 48) =3D 6, sqrt(49) =3D 7 >> >> So we could precalculate the interval/sqrt(count) using floating point >> in the control law calculation, >> early, during qdisc setup, thus neatly avoiding both the divide and >> sqrt in the control law path. >> >> Or we could do fixed point. >> >> Kathie: In the sim, in various simulations, what is the dynamic range >> of count? And is it floating point sqrt? >> > The Wikipedia article on fast inverse sqrt is enlightening on computing > this really fast. > > See: > > http://en.wikipedia.org/wiki/Fast_inverse_square_root > > This has little to do with whether an integer or floating point value is > better algorithmically. Neat trick, that. I'm delighted the wikipedia article kept the fully commented original code around! That said, you can't use FP at all without special handling in the kernel. It's certainly a terrible idea on a hot path... > =A0 =A0 =A0 =A0 =A0 =A0 =A0 =A0 =A0 =A0 =A0 =A0 =A0 =A0- Jim --=20 Dave T=E4ht SKYPE: davetaht US Tel: 1-239-829-5608 http://www.bufferbloat.net