[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]
Re: Set operations on bool-vectors
From: |
Daniel Colascione |
Subject: |
Re: Set operations on bool-vectors |
Date: |
Fri, 20 Sep 2013 19:49:00 -0700 |
User-agent: |
Mozilla/5.0 (Macintosh; Intel Mac OS X 10.6; rv:17.0) Gecko/20130801 Thunderbird/17.0.8 |
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.
signature.asc
Description: OpenPGP digital signature