From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: from mail-yx0-f171.google.com (mail-yx0-f171.google.com [209.85.213.171]) (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 4D0D1200B29 for ; Fri, 4 May 2012 08:26:12 -0700 (PDT) Received: by yenq11 with SMTP id q11so3311086yen.16 for ; Fri, 04 May 2012 08:26:11 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20120113; h=sender:message-id:date:from:organization:user-agent:mime-version:to :cc:subject:references:in-reply-to:content-type :content-transfer-encoding; bh=ojchwv8RBeewDdIFlq52wW++oD4dSc9kkeVbNPhCj28=; b=MbwV4YVxnKrYIn/ActbIxdqlHVFAOayGQcQTGh8WCNnB1ULYd394ytPJalbnbFpQdX TsoDu1JYqJvxtgktnRQo9xfVQERgo+XosV4nJA9S1aWaUVk752OuFcAyIYB2AZC0PpsG Cs07tA2thXsWuD+fv7r5pwC/5pgAYHFkvxR6H8JCEqGQW/+VrhPreiSG7eycGVLVqxZi ikMiFV+hytau6lroM1BD7Ion5P1Olr/9WBeVzxdZuRYWunYMk0JXfKgotcFutiCLur15 J4jQqRpTMK+g36RqY2xpQJWDW95fJKoIEaDRgWR8NUcOWjHdF6x5lQ4qXYbdq8U3Tutg KoiQ== Received: by 10.236.80.66 with SMTP id j42mr8473677yhe.110.1336145171153; Fri, 04 May 2012 08:26:11 -0700 (PDT) Received: from [10.0.0.4] (c-24-218-179-128.hsd1.ma.comcast.net. [24.218.179.128]) by mx.google.com with ESMTPS id i7sm13800057ani.17.2012.05.04.08.26.08 (version=SSLv3 cipher=OTHER); Fri, 04 May 2012 08:26:09 -0700 (PDT) Sender: Jim Gettys Message-ID: <4FA3F50D.7080406@freedesktop.org> Date: Fri, 04 May 2012 11:26:05 -0400 From: Jim Gettys Organization: Bell Labs User-Agent: Mozilla/5.0 (X11; Linux x86_64; rv:11.0) Gecko/20120329 Thunderbird/11.0.1 MIME-Version: 1.0 To: Dave Taht References: <4FA3F248.3070101@freedesktop.org> In-Reply-To: Content-Type: text/plain; charset=ISO-8859-1 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 List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , X-List-Received-Date: Fri, 04 May 2012 15:26:12 -0000 On 05/04/2012 11:19 AM, Dave Taht wrote: > 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, ktime_t t) >>> { >>> 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 = 1 1 1 2 >>> fp sqrt 1 2 3 4 = 1 1.4.1 1.73 2 >>> >>> and gets even more chunky as you get larger values, eg, sqrt(36 >>> through 48) = 6, sqrt(49) = 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! I don't think that is the "original", which predates quake by a lot according to the article. > > 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... 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. - Jim