Re: Use compiler intrinsics for bit ops in hash

On Sat, 29 Feb 2020 at 04:13, David Fetter <david(at)fetter(dot)org> wrote:
>
> On Thu, Feb 27, 2020 at 02:41:49PM +0800, John Naylor wrote:
> > In 0002, the pg_bitutils functions have a test (input > 0), and the
> > new callers ceil_log2_* and next_power_of_2_* have asserts. That seems
> > backward to me.
>
> To me, too, now that you mention it. My thinking was a little fuzzed
> by trying to accommodate platforms with intrinsics where clz is
> defined for 0 inputs.

Wouldn't it be better just to leave the existing definitions of the
pg_leftmost_one_pos* function alone? It seems to me you're hacking
away at those just so you can support passing 1 to the new functions,
and that's giving you trouble now because you're doing num-1 to handle
the case where the number is already a power of 2. Which is
troublesome because 1-1 is 0, which you're trying to code around.

Isn't it better just to put in a run-time check for numbers that are
already a power of 2 and then get rid of the num - 1? Something like:

/*
* pg_nextpow2_32
* Returns the next highest power of 2 of 'num', or 'num', if
it's already a
* power of 2. 'num' mustn't be 0 or be above UINT_MAX / 2.
*/
static inline uint32
pg_nextpow2_32(uint32 num)
{
Assert(num > 0 && num <= UINT_MAX / 2);
/* use some bitmasking tricks to see if only 1 bit is on */
return (num & (num - 1)) == 0 ? num : ((uint32) 1) <<
(pg_leftmost_one_pos32(num) + 1);
}

I think you'll also want to mention the issue about numbers greater
than UINT_MAX / 2, as I've done above and also align your naming
conversion to what else is in that file.

I don't think Jesse's proposed solution is that great due to the
additional function call overhead for pg_count_leading_zeros_32(). The
(num & (num - 1)) == 0 I imagine will perform better, but I didn't
test it.

Also, wondering if you've looked at any of the other places where we
do "*= 2;" or "<<= 1;" inside a loop? There's quite a number that look
like candidates for using the new function.