Re: A population of population counts

On Sat, May 7, 2016 at 4:26 PM, Tom Lane <tgl(at)sss(dot)pgh(dot)pa(dot)us> wrote:
> David Rowley <david(dot)rowley(at)2ndquadrant(dot)com> writes:
>> I'd like to see us using those functions, when they're available and
>> falling back on the array when they're not. Sounds like that would
>> just be a new configure test. Perhaps a good home for some shared code
>> would be numutils.c.
>
> Meh --- numutils.c is about numbers. Maybe "bitutils.c"?
>
> Another point here is that there might easily be a use-case for such
> functionality in frontend code, so I'd lean towards putting the support in
> src/common if we do this.

I played around with this a bit on the weekend (see rough sketch
attached). The trouble with __builtin_popcount and the POPCNT
instruction is that you only get them if you ask for -msse4.2 or
-mpopcnt, and then you get an illegal instruction trap instead of
sensible fallback behaviour on ancient hardware, so no packager would
be able to do that. So I guess we'd have to use a runtime test like
we do for CRC32 hardware support (the test may actually be identical
since both depend on the SSE4.2 instruction set) and maybe inline
assembler rather the GCC builtin, and that seems a bit over the top
unless someone can show that it's worth it.

My aim with this thread was mainly reducing code duplication and
needless code: perhaps at least the other ideas in the attached
sketch, namely using ffs instead of the rightmost_one_pos table loop
and consolidation of popcount into a reusable API (without trying to
get hardware support) could be worth polishing for the next CF?
Annoyingly, it seems Windows doesn't have POSIX/SUSv2 ffs, though
apparently it can reach that instruction with MSVC intrinsic
_BitScanReverse or MingW __builtin_ffs.

--
Thomas Munro
http://www.enterprisedb.com