From mboxrd@z Thu Jan 1 00:00:00 1970 Path: news.gmane.org!not-for-mail From: Daniel Colascione Newsgroups: gmane.emacs.devel Subject: Re: Set operations on bool-vectors Date: Sat, 21 Sep 2013 00:43:10 -0700 Message-ID: <523D4E0E.9050500@dancol.org> References: <523CD363.6020400@dancol.org> <523D03BF.2090901@yandex.ru> <523D091C.6010200@dancol.org> <83txhek5ku.fsf@gnu.org> NNTP-Posting-Host: plane.gmane.org Mime-Version: 1.0 Content-Type: multipart/signed; micalg=pgp-sha1; protocol="application/pgp-signature"; boundary="iWPJBkVldu48Tn0qBg3eHaOqFK4JiepDj" X-Trace: ger.gmane.org 1379749466 25474 80.91.229.3 (21 Sep 2013 07:44:26 GMT) X-Complaints-To: usenet@ger.gmane.org NNTP-Posting-Date: Sat, 21 Sep 2013 07:44:26 +0000 (UTC) Cc: dmantipov@yandex.ru, emacs-devel@gnu.org To: Eli Zaretskii Original-X-From: emacs-devel-bounces+ged-emacs-devel=m.gmane.org@gnu.org Sat Sep 21 09:44:30 2013 Return-path: Envelope-to: ged-emacs-devel@m.gmane.org Original-Received: from lists.gnu.org ([208.118.235.17]) by plane.gmane.org with esmtp (Exim 4.69) (envelope-from ) id 1VNHrf-0004ZQ-Df for ged-emacs-devel@m.gmane.org; Sat, 21 Sep 2013 09:44:27 +0200 Original-Received: from localhost ([::1]:58872 helo=lists.gnu.org) by lists.gnu.org with esmtp (Exim 4.71) (envelope-from ) id 1VNHrf-0006m6-2T for ged-emacs-devel@m.gmane.org; Sat, 21 Sep 2013 03:44:27 -0400 Original-Received: from eggs.gnu.org ([2001:4830:134:3::10]:59388) by lists.gnu.org with esmtp (Exim 4.71) (envelope-from ) id 1VNHrX-0006l8-Mt for emacs-devel@gnu.org; Sat, 21 Sep 2013 03:44:24 -0400 Original-Received: from Debian-exim by eggs.gnu.org with spam-scanned (Exim 4.71) (envelope-from ) id 1VNHrT-0006aI-B7 for emacs-devel@gnu.org; Sat, 21 Sep 2013 03:44:19 -0400 Original-Received: from dancol.org ([2600:3c01::f03c:91ff:fedf:adf3]:46041) by eggs.gnu.org with esmtp (Exim 4.71) (envelope-from ) id 1VNHrT-0006Zz-4s for emacs-devel@gnu.org; Sat, 21 Sep 2013 03:44:15 -0400 Original-Received: from c-76-22-66-162.hsd1.wa.comcast.net ([76.22.66.162] helo=[192.168.1.52]) by dancol.org with esmtpsa (TLS1.0:DHE_RSA_CAMELLIA_256_CBC_SHA1:256) (Exim 4.80) (envelope-from ) id 1VNHrR-0003Ng-Fr; Sat, 21 Sep 2013 00:44:13 -0700 User-Agent: Mozilla/5.0 (Macintosh; Intel Mac OS X 10.6; rv:17.0) Gecko/20130801 Thunderbird/17.0.8 In-Reply-To: <83txhek5ku.fsf@gnu.org> X-Enigmail-Version: 1.5.2 X-detected-operating-system: by eggs.gnu.org: Error: Malformed IPv6 address (bad octet value). X-Received-From: 2600:3c01::f03c:91ff:fedf:adf3 X-BeenThere: emacs-devel@gnu.org X-Mailman-Version: 2.1.14 Precedence: list List-Id: "Emacs development discussions." List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , Errors-To: emacs-devel-bounces+ged-emacs-devel=m.gmane.org@gnu.org Original-Sender: emacs-devel-bounces+ged-emacs-devel=m.gmane.org@gnu.org Xref: news.gmane.org gmane.emacs.devel:163530 Archived-At: This is an OpenPGP/MIME signed message (RFC 4880 and 3156) --iWPJBkVldu48Tn0qBg3eHaOqFK4JiepDj Content-Type: text/plain; charset=UTF-8 Content-Transfer-Encoding: quoted-printable On 9/21/13 12:16 AM, Eli Zaretskii wrote: >> Date: Fri, 20 Sep 2013 19:49:00 -0700 >> From: Daniel Colascione >> Cc: Emacs development discussions >> >>>> +static inline >>>> +EMACS_INT >>>> +popcount_size_t(size_t val) >>>> +{ >>>> + EMACS_INT count; >>>> + >>>> +#if defined __GNUC__ && BITS_PER_SIZE_T =3D=3D 64 >>>> + count =3D __builtin_popcountll (val); >>>> +#elif defined __GNUC__ && BITS_PER_SIZE_T =3D=3D 32 >>>> + count =3D __builtin_popcount (val); >>>> +#elif defined __MSC_VER && BITS_PER_SIZE_T =3D=3D 64 >>>> +# pragma intrinsic __popcnt64 >>>> + count =3D __popcnt64 (val); >>>> +#elif defined __MSC_VER && BITS_PER_SIZE_T =3D=3D 32 >>>> +# pragma intrinsic __popcnt >>>> + count =3D __popcnt (val); >>>> +#else >>>> + { >>>> + EMACS_INT j; >>>> + count =3D 0; >>>> + for (j =3D 0; j < BITS_PER_SIZE_T; ++j) >>>> + count +=3D !!((((size_t) 1) << j) & val); >>>> + } >>>> +#endif >>> >>> Why loop? See http://en.wikipedia.org/wiki/Hamming_weight. >> >> I didn't want to put a lot of effort into a code path we'll probably >> never use. Recall that if we're using icc or gcc or Visual C++ or >> Clang, we'll be using a compiler intrinsic, which will probably compil= e >> down to a single machine instruction. >> >> By the way: can someone test that the Visual C++ alternate actually >> works? I don't have access to a Windows machine at the moment. >=20 > I don't see why it won't work, per documentation on this page: >=20 > http://msdn.microsoft.com/en-us/library/bb385231%28v=3Dvs.90%29.aspx >=20 > However, I think you will need to make usage of these intrinsics > compiler version dependent. GCC supports them starting from 3.4, > whereas MSVC seems to support them since Studio 2008, i.e. _MSC_VER =3D= > 1500 or higher. Fair enough. > It is also not clear to me what will the MSVC intrinsic do if the > binary ever runs on a CPU that doesn't support SSE4, the MSDN > documentation seems to say that the results are unpredictable, > i.e. that there's no fallback, like GCC has in libgcc. So perhaps we > should also guard that with a Windows version (assuming that old > machines will only ever run Windows 9x). Good point. SSE4 is much too recent to require. Making the cpuid check shouldn't be too hard. I have no way to actually test the fallback, though. (It's easy to test the fallback code, but not that easy to test falling back to it.) --iWPJBkVldu48Tn0qBg3eHaOqFK4JiepDj Content-Type: application/pgp-signature; name="signature.asc" Content-Description: OpenPGP digital signature Content-Disposition: attachment; filename="signature.asc" -----BEGIN PGP SIGNATURE----- Version: GnuPG v1.4.14 (Darwin) iQIcBAEBAgAGBQJSPU4OAAoJEMAaIROpHW7IZ1UP/1sNLV0tGVVjVI7hUbBc8/he 9NFCwn+QZFDxMP9DON2hhcTqwnqRXp2VgMlbs7fJflorQJfryxK8eUJPTkYX36hn TqCGMe1P0cFpvs9t5qm5/bisMzvfZouYeu0yOifHQifg9X/odv2df2ay4qIVvvma tR73FttOZR4akfK1K1oF8rrscGjLOFR4NpN1lLUI38UMWv5om+3VecP+32YaXD6U oAK8XqxI1n5CnzRM+Neyqcbs1sIV5FbMNlyZf5k2z/bV4zsJX8MnGln1PliqDEpe gsnIS8wOj5+cogXfEbAjBbyyV8bySILP1GqnqoqdiP5xVdfDncTq4RQ12jcqqkkW C5RQ+bFVUDdRskLjnnN6l7ZB2zyjUE8h/3Z7jGkMhfCmHqQpNlRmsvsO49jbu1aL hYyaWPar7aswBSjOLQwDubo5HTfJq3atXBSR9U3RLv21r9l2OnjkSzLQ2oi8Wzzg HAaCRtoay/yq3EMxNIfRApC/R+IJk2oga1fvzasmjsi3EUlphsAlm38qYpTwfxDq a0vRxAbXYYEGJ7HefFz5ip5ARy07xbZofU/bVxvoMvVB9VGPULErqgONRGBpLjLS zJXW7tqOBERssBEAcZCZzEs/kMzXuhEc9rTyVO8YGYeJfgNAJ+tWxSRMlwEsuZkg S/6C/5KWSEhEm5bUcTzn =y1w1 -----END PGP SIGNATURE----- --iWPJBkVldu48Tn0qBg3eHaOqFK4JiepDj--