Re: Set operations on bool-vectors

[Daniel Colascione <dancol@dancol.org>]

[-- 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 --]