From: Daniel Colascione <dancol@dancol.org>
To: Dmitry Antipov <dmantipov@yandex.ru>
Cc: Emacs development discussions <emacs-devel@gnu.org>
Subject: Re: Set operations on bool-vectors
Date: Fri, 20 Sep 2013 19:49:00 -0700 [thread overview]
Message-ID: <523D091C.6010200@dancol.org> (raw)
In-Reply-To: <523D03BF.2090901@yandex.ru>
[-- Attachment #1: Type: text/plain, Size: 1889 bytes --]
On 9/20/13 7:26 PM, Dmitry Antipov wrote:
> On 09/21/2013 02:59 AM, Daniel Colascione wrote:
>
>> I've implemented built-in set operations on bool vectors.
>
> [...]
>
>> +/* 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
>
> 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 == 64
>> + count = __builtin_popcountll (val);
>> +#elif defined __GNUC__ && BITS_PER_SIZE_T == 32
>> + count = __builtin_popcount (val);
>> +#elif defined __MSC_VER && BITS_PER_SIZE_T == 64
>> +# pragma intrinsic __popcnt64
>> + count = __popcnt64 (val);
>> +#elif defined __MSC_VER && BITS_PER_SIZE_T == 32
>> +# pragma intrinsic __popcnt
>> + count = __popcnt (val);
>> +#else
>> + {
>> + EMACS_INT j;
>> + count = 0;
>> + for (j = 0; j < BITS_PER_SIZE_T; ++j)
>> + count += !!((((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 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.
[-- Attachment #2: OpenPGP digital signature --]
[-- Type: application/pgp-signature, Size: 833 bytes --]
next prev parent reply other threads:[~2013-09-21 2:49 UTC|newest]
Thread overview: 12+ messages / expand[flat|nested] mbox.gz Atom feed top
2013-09-20 22:59 Set operations on bool-vectors Daniel Colascione
2013-09-21 1:57 ` Stefan Monnier
2013-09-21 2:44 ` Daniel Colascione
2013-09-21 15:51 ` Stefan Monnier
2013-09-21 2:26 ` Dmitry Antipov
2013-09-21 2:49 ` Daniel Colascione [this message]
2013-09-21 7:16 ` Eli Zaretskii
2013-09-21 7:43 ` Daniel Colascione
2013-09-21 7:36 ` Andreas Schwab
2013-09-21 7:38 ` Daniel Colascione
2013-09-21 8:35 ` Andreas Schwab
2013-09-21 8:49 ` Daniel Colascione
Reply instructions:
You may reply publicly to this message via plain-text email
using any one of the following methods:
* Save the following mbox file, import it into your mail client,
and reply-to-all from there: mbox
Avoid top-posting and favor interleaved quoting:
https://en.wikipedia.org/wiki/Posting_style#Interleaved_style
* Reply using the --to, --cc, and --in-reply-to
switches of git-send-email(1):
git send-email \
--in-reply-to=523D091C.6010200@dancol.org \
--to=dancol@dancol.org \
--cc=dmantipov@yandex.ru \
--cc=emacs-devel@gnu.org \
/path/to/YOUR_REPLY
https://kernel.org/pub/software/scm/git/docs/git-send-email.html
* If your mail client supports setting the In-Reply-To header
via mailto: links, try the mailto: link
Be sure your reply has a Subject: header at the top and a blank line
before the message body.
Code repositories for project(s) associated with this external index
https://git.savannah.gnu.org/cgit/emacs.git
https://git.savannah.gnu.org/cgit/emacs/org-mode.git
This is an external index of several public inboxes,
see mirroring instructions on how to clone and mirror
all data and code used by this external index.