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: Fri, 20 Sep 2013 19:49:00 -0700 Message-ID: <523D091C.6010200@dancol.org> References: <523CD363.6020400@dancol.org> <523D03BF.2090901@yandex.ru> NNTP-Posting-Host: plane.gmane.org Mime-Version: 1.0 Content-Type: multipart/signed; micalg=pgp-sha1; protocol="application/pgp-signature"; boundary="cpx0rS9nVNiI6suN7vbKX4kMoqeVkBmTF" X-Trace: ger.gmane.org 1379731816 8475 80.91.229.3 (21 Sep 2013 02:50:16 GMT) X-Complaints-To: usenet@ger.gmane.org NNTP-Posting-Date: Sat, 21 Sep 2013 02:50:16 +0000 (UTC) Cc: Emacs development discussions To: Dmitry Antipov Original-X-From: emacs-devel-bounces+ged-emacs-devel=m.gmane.org@gnu.org Sat Sep 21 04:50:20 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 1VNDH0-0007c5-KX for ged-emacs-devel@m.gmane.org; Sat, 21 Sep 2013 04:50:18 +0200 Original-Received: from localhost ([::1]:58414 helo=lists.gnu.org) by lists.gnu.org with esmtp (Exim 4.71) (envelope-from ) id 1VNDH0-00033y-1X for ged-emacs-devel@m.gmane.org; Fri, 20 Sep 2013 22:50:18 -0400 Original-Received: from eggs.gnu.org ([2001:4830:134:3::10]:57289) by lists.gnu.org with esmtp (Exim 4.71) (envelope-from ) id 1VNDGs-00033p-Jo for emacs-devel@gnu.org; Fri, 20 Sep 2013 22:50:16 -0400 Original-Received: from Debian-exim by eggs.gnu.org with spam-scanned (Exim 4.71) (envelope-from ) id 1VNDGm-00061V-IC for emacs-devel@gnu.org; Fri, 20 Sep 2013 22:50:10 -0400 Original-Received: from dancol.org ([2600:3c01::f03c:91ff:fedf:adf3]:44998) by eggs.gnu.org with esmtp (Exim 4.71) (envelope-from ) id 1VNDGm-0005yo-CT for emacs-devel@gnu.org; Fri, 20 Sep 2013 22:50:04 -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 1VNDGl-0002rO-Fh; Fri, 20 Sep 2013 19:50:03 -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: <523D03BF.2090901@yandex.ru> 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:163526 Archived-At: This is an OpenPGP/MIME signed message (RFC 4880 and 3156) --cpx0rS9nVNiI6suN7vbKX4kMoqeVkBmTF Content-Type: text/plain; charset=UTF-8 Content-Transfer-Encoding: quoted-printable On 9/20/13 7:26 PM, Dmitry Antipov wrote: > On 09/21/2013 02:59 AM, Daniel Colascione wrote: >=20 >> I've implemented built-in set operations on bool vectors. >=20 > [...] >=20 >> +/* Because we round up the BOOL_VECTOR allocate size to word_size >> + units, we can safely read past the "end" of the vector in the >> + operations below. These extra bits are always zero. Also, we >> + always BOOL_VECTORS with at least one size_t of storage so that we= >> + don't have to special-case empty bit vectors. */ >> + >> +#if (SIZE_MAX >> 32) & 1 >> +# define BITS_PER_SIZE_T 64 >> +#else >> +# define BITS_PER_SIZE_T 32 >> +#endif >=20 > IIUC this should go to the well-known place in lisp.h. Sure. >> +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 >=20 > 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 compile 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. --cpx0rS9nVNiI6suN7vbKX4kMoqeVkBmTF 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) iQIcBAEBAgAGBQJSPQkdAAoJEMAaIROpHW7IIHwQALXOBJuMZRwxM9DFkxdrVisT EQK5Oa6eI1Yn905qSNx7xu2pmVTaH1fMkC7EwpuiK4MKya4VcIOWuD8n1o+Y9qFh bQEgUV7md3dgPhjzZ4HFLBtrBAQTC2IjWVBd3qfr8W019ffDV87103YbirUmAX0A yx3JWVJMJqyvzR87nUwsdLnCtbXxM2vVugtB9MgVZy514en2S7OUE4FWZ2sF1+S/ uPm7psQp9O88cqYDyg/q2yuvtDOsDu94U5oiCKiwXiz8Xao6IzxiPVqpn9uwSHcu +tSxAcGY8pkwYH0HD4If3F2Vn3cUXazJ8nJhkMP8uyoQnUndkuk2pu86/X2B7p/c QtOXasTTaEY3pDhACxOiBLIW8znYMPBRqR63DiKwydJZ5oZ+HXUrG7lLGLO4Anmy LKsDrF5xZCMi+ff4NB8m1WZUk1LIsklbrIZOp+vAnWpP6IcZxAQifQUK7zvU2RGo vh2nclGzTodM8PSn6PyCiPu+ZXveQowMAnOpgR5XpcgMuiRfGH0XH215g3umMjiP 3nI2F2IUtpwzbj5uPommWy0elzgI9vASRIT3V7lApNKBoe3/j9lo7ODdQHioTLrP LNylfP4cOocAb3+XwJDfTNaBCYZc4xdTczmPYWOk++WAjK02LXBN9UFkn8+k/yBg QJm6hFTJ955RLcM42ED6 =Tiek -----END PGP SIGNATURE----- --cpx0rS9nVNiI6suN7vbKX4kMoqeVkBmTF--