From mboxrd@z Thu Jan 1 00:00:00 1970 Received: from eggs.gnu.org ([2001:4830:134:3::10]:38967) by lists.gnu.org with esmtp (Exim 4.71) (envelope-from ) id 1YTXRb-0007jO-M3 for qemu-devel@nongnu.org; Thu, 05 Mar 2015 10:12:16 -0500 Received: from Debian-exim by eggs.gnu.org with spam-scanned (Exim 4.71) (envelope-from ) id 1YTXRU-000708-VR for qemu-devel@nongnu.org; Thu, 05 Mar 2015 10:12:11 -0500 Received: from mx1.redhat.com ([209.132.183.28]:37641) by eggs.gnu.org with esmtp (Exim 4.71) (envelope-from ) id 1YTXRU-0006zv-PA for qemu-devel@nongnu.org; Thu, 05 Mar 2015 10:12:04 -0500 Received: from int-mx09.intmail.prod.int.phx2.redhat.com (int-mx09.intmail.prod.int.phx2.redhat.com [10.5.11.22]) by mx1.redhat.com (8.14.4/8.14.4) with ESMTP id t25FC4eD015178 (version=TLSv1/SSLv3 cipher=DHE-RSA-AES256-GCM-SHA384 bits=256 verify=FAIL) for ; Thu, 5 Mar 2015 10:12:04 -0500 Date: Thu, 5 Mar 2015 16:12:01 +0100 From: Radim =?utf-8?B?S3LEjW3DocWZ?= Message-ID: <20150305151200.GA3361@potion.redhat.com> References: <1425479449-11480-1-git-send-email-kraxel@redhat.com> <1425479449-11480-4-git-send-email-kraxel@redhat.com> <87twxzai0i.fsf@blackfin.pond.sub.org> MIME-Version: 1.0 Content-Type: text/plain; charset=utf-8 Content-Disposition: inline In-Reply-To: <87twxzai0i.fsf@blackfin.pond.sub.org> Content-Transfer-Encoding: quoted-printable Subject: Re: [Qemu-devel] [PULL 3/7] qxl: refactor rounding up to a nearest power of 2 List-Id: List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , To: Markus Armbruster Cc: Gerd Hoffmann , qemu-devel@nongnu.org 2015-03-05 10:52+0100, Markus Armbruster: > Gerd Hoffmann writes: >=20 > > From: Radim Kr=C4=8Dm=C3=A1=C5=99 > > > > We already have pow2floor, mirror it and use instead of a function wi= th > > similar results (same in used domain), to clarify our intent. > > > > Signed-off-by: Radim Kr=C4=8Dm=C3=A1=C5=99 > > Signed-off-by: Gerd Hoffmann > [...] > > +/* round up to the nearest power of 2 (0 if overflow) */ >=20 > Callers need to check for overflow, but that's the callers' problem. It's obvious that the return value is 0 in this case -- the correct result would have been a multiple of the modulo, but I wanted to be explicit about it. > > +uint64_t pow2ceil(uint64_t value) > > +{ > > + uint8_t nlz =3D clz64(value); >=20 > You convert the value of clz64() from int to uint8_t only to promote it > right back to int in every single use. Please don't muddy the waters > that way. Ok, the down-cast might cause some runtime overhead. (I don't understand why the return value of clz64() is 'int' -- using the smallest sufficient data type seems clearer to me.) > > + if (is_power_of_2(value)) { > > + return value; > > + } > > + if (!nlz) { > > + return 0; > > + } > > + return 1ULL << (64 - nlz); > > +} >=20 > Doesn't really mirror pow2floor() in master, because that one uses > int64_t. Fine with me, because my "[PATCH 0/2] Proactive pow2floor() > fix, and dead code removal" changes pow2floor() to uint64_t. Yeah, I didn't understand why that returned 'int64_t' either. I understood that pow2floor() used is_power_of_2() because it expected higher probability of numbers that already are the power, so the clunky code was balanced by a faster common case; and I duplicated this. (clz64() without hardware support is slow.) > Unfortunately, the two patches conflict. >=20 > This patch's implementation of pow2ceil() is needlessly complicated, > just like pow2floor() in master. Simpler: >=20 > uint64_t pow2ceil2(uint64_t value) > { > int n =3D clz64(value - 1); > return n ? 1ull << (64 - n) : 0; Mapping 0 to 0 is probably what we would want in most uses, but I'd name the function differently then -- the closest power of 2 bigger than (or equal to) 0 is 1, and 2^64 =3D=3D 0, so the result was mathematically correct. We also lose the ability to detect overflow after the call, so callers would have to do it before, with a code like 'passed_value > DESTINATION_TYPE_MAX / 2 + 1' > I can rebase my patch on top of this one, and clean things up to my > taste. Ok, thanks! --- If eliminating is_power_of_2() and using the ternary operator is fine, I'd write it like this: unsigned nlz =3D clz64(value - 1); return !value ? 1 : (nlz ? 1ULL << (64 - nlz) : 0); If we don't believe that the compiler can optimize, and after applying all I know about QEMU coding style: int nlz; if (!value) { return 1; } nlz =3D clz64(value - 1); return n ? 1ull << (64 - n) : 0;