[RFC] Generic population count function

[Jung-uk Kim]

-----BEGIN PGP SIGNED MESSAGE-----
Hash: SHA1

On 2012-11-15 03:32:50 -0500, Bruce Evans wrote:
> On Wed, 14 Nov 2012, Jung-uk Kim wrote:
> 
>> I implemented generic population count function.  Please see the 
>> attachment.  It is also available from here:
>> 
>> http://people.freebsd.org/~jkim/bitcount.diff
>> 
>> The idea is to make use of CPU-supported population count
>> instructions if available and the compiler supports them (i.e.,
>> clang), especially for larger than 32-bit data.  The patch also
>> has use cases for the new function (i.e., counting number of bits
>> in IPv6 address[*]).
>> 
>> Any objection?
> 
> This is rather over-engineered for something that is used once or
> twice, but it is good to move the functions out of sys/systm.h
> where they weren't even usable outside the kernel.

There's little history behind it, actually.  When I wrote the
following patch, I was looking for fast population count function
available in FreeBSD:

http://svnweb.freebsd.org/ports/head/java/openjdk6/files/patch-set?annotate=306138#l5437

I searched everywhere and found this:

http://www.dalkescientific.com/writings/diary/archive/2011/11/02/faster_popcount_update.html

but I ended up (ab)using count() method for bitset in C++ because
there's no portable way to do so.  The GCC-supplied bitset header uses
__builtin_popcount(), naturally. :-)

BTW, I intent to add CPU_COUNT() macro to sys/cpuset.h with this
bitcount() function.

[Snip ffs() issues]

> I only noticed the following in your version: - including
> <sys/cdefs.h> is a style bug because sys/types.h includes it

Will fix, thanks!

> - you removed the silly special inline for bitcount16() but still 
> implement bitcount16(), presumably for compatibiltiy.

Precisely.  I don't want to see angry kib at . ;-)

> But it is incompatible since the old version has the bogus return
> type uint16_t.

Yes, I noticed that, too.  I believe kib@ added it to make Linux ->
FreeBSD conversion easier, i.e.,

http://lxr.linux.no/#linux+v3.6.6/drivers/gpu/drm/i915/intel_sdvo.c#L1279
http://lxr.linux.no/#linux+v3.6.6/drivers/gpu/drm/i915/intel_sdvo.c#L1913

BTW, I found Linux has very simple ("naive") population count (aka,
Hamming weight) macros:

http://lxr.linux.no/#linux+v3.6.6/include/asm-generic/bitops/const_hweight.h

__builtin_popcount() family should do much better than this. ;-)

> It seems to be used just twice: in intel_sdvo.c, it is blindly
> converted to bool in 1 place and to unsigned int in 1 place.  Both
> of these uses are for device initialization so their efficiency is
> especially
uniportant.

Correct.

> - bitcount32() is also incompatible since the old version has the
> slightly less bogus return type uint32_t.  At least the args have
> correct type, unlike the ffs() family.

Yes, it is little incompatible but *intentional*.  I looked through
entire source code and found no problem.  The return value is always
<= 32 anyway. :-)

Thanks for the review,

Jung-uk Kim
-----BEGIN PGP SIGNATURE-----
Version: GnuPG v2.0.19 (FreeBSD)
Comment: Using GnuPG with Mozilla - http://www.enigmail.net/

iEYEARECAAYFAlClQtAACgkQmlay1b9qnVMZUwCfQhimEbrL87o+KOITt27nNgNS
pWAAniWs9Jzf6W2CkiIyozSSfLqW1YJK
=DOpK
-----END PGP SIGNATURE-----