From owner-freebsd-hackers@FreeBSD.ORG Fri Oct 15 13:08:41 2010 Return-Path: Delivered-To: freebsd-hackers@freebsd.org Received: from mx1.freebsd.org (mx1.freebsd.org [IPv6:2001:4f8:fff6::34]) by hub.freebsd.org (Postfix) with ESMTP id 072BF10657EF; Fri, 15 Oct 2010 13:08:38 +0000 (UTC) (envelope-from jhb@freebsd.org) Received: from cyrus.watson.org (cyrus.watson.org [65.122.17.42]) by mx1.freebsd.org (Postfix) with ESMTP id EAD6F8FC13; Fri, 15 Oct 2010 13:08:37 +0000 (UTC) Received: from bigwig.baldwin.cx (66.111.2.69.static.nyinternet.net [66.111.2.69]) by cyrus.watson.org (Postfix) with ESMTPSA id 82C2B46C05; Fri, 15 Oct 2010 09:08:37 -0400 (EDT) Received: from jhbbsd.localnet (smtp.hudson-trading.com [209.249.190.9]) by bigwig.baldwin.cx (Postfix) with ESMTPSA id 90F3A8A027; Fri, 15 Oct 2010 09:08:36 -0400 (EDT) From: John Baldwin To: Garrett Cooper Date: Fri, 15 Oct 2010 08:51:14 -0400 User-Agent: KMail/1.13.5 (FreeBSD/7.3-CBSD-20100819; KDE/4.4.5; amd64; ; ) References: <201010140937.51953.jhb@freebsd.org> In-Reply-To: MIME-Version: 1.0 Content-Type: Text/Plain; charset="iso-8859-1" Content-Transfer-Encoding: 7bit Message-Id: <201010150851.14749.jhb@freebsd.org> X-Greylist: Sender succeeded SMTP AUTH, not delayed by milter-greylist-4.2.6 (bigwig.baldwin.cx); Fri, 15 Oct 2010 09:08:36 -0400 (EDT) X-Virus-Scanned: clamav-milter 0.96.3 at bigwig.baldwin.cx X-Virus-Status: Clean X-Spam-Status: No, score=-1.9 required=4.2 tests=BAYES_00 autolearn=ham version=3.3.1 X-Spam-Checker-Version: SpamAssassin 3.3.1 (2010-03-16) on bigwig.baldwin.cx Cc: freebsd-hackers@freebsd.org, Andriy Gapon Subject: Re: [PATCH] Bug with powerof2 macro in sys/param.h X-BeenThere: freebsd-hackers@freebsd.org X-Mailman-Version: 2.1.5 Precedence: list List-Id: Technical Discussions relating to FreeBSD List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , X-List-Received-Date: Fri, 15 Oct 2010 13:08:41 -0000 On Thursday, October 14, 2010 11:49:23 pm Garrett Cooper wrote: > On Thu, Oct 14, 2010 at 6:37 AM, John Baldwin wrote: > > On Thursday, October 14, 2010 7:58:32 am Andriy Gapon wrote: > >> on 14/10/2010 00:30 Garrett Cooper said the following: > >> > I was talking to someone today about this macro, and he noted that > >> > the algorithm is incorrect -- it fails the base case with ((x) == 0 -- > >> > which makes sense because 2^(x) cannot equal 0 (mathematically > >> > impossible, unless you consider the limit as x goes to negative > >> > infinity as log (0) / log(2) is undefined). I tested out his claim and > >> > he was right: > >> > >> That's kind of obvious given the code. > >> I think that this might be an intentional optimization. > >> I guess that it doesn't really make sense to apply powerof2 to zero and the users > >> of the macro should do the check on their own if they expect zero as input (many > >> places in the do not allow that). > > But the point is that this could be micro-optimizing things > incorrectly. I'm running simple iteration tests to see what the > performance is like, but the runtime is going to take a while to > produce stable results. > > Mathematically there is a conflict with the definition of the macro, > so it might confuse folks who pay attention to the math as opposed to > the details (if you want I'll gladly add a comment around the macro in > a patch to note the caveats of using powerof2). We aren't dealing with mathematicians, but programmers. > > I agree, the current macro is this way on purpose (and straight out of > > "Hacker's Delight"). And this book trumps you on that case. Using the powerof2() macro as it currently stands is a widely-used practice among folks who write systems-level code. If you were writing a powerof2() function for a higher level language where performance doesn't matter and bit twiddling isn't common, then a super-safe variant of powerof2() might be appropriate. However, this is C, and C programmers are expected to know how this stuff works. > > sys/net/flowtable.c: ft->ft_lock_count = > > 2*(powerof2(mp_maxid + 1) ? (mp_maxid + 1): > > > > Clearly, 'mp_maxid + 1' will not be zero (barring a bizarre overflow case > > which will not happen until we support 2^32 CPUs), so this is fine. > > But that should be caught by the mp_machdep code, correct? Yes, hence "bizarre". It is also way unrealistic and not worth excessive pessimizations scattered throughout the tree. > What about the other patches? The mfiutil and mptutil ones at least > get the two beforementioned tools in sync with sys/param.h at least, > so I see some degree of value in the patches (even if they're just > cleanup). No, powerof2() should not change. It would most likely be a POLA violation to change how it works given 1) it's historical behavior, and 2) it's underlying idiom's common (and well-understood) use among the software world. -- John Baldwin