Re: use CLZ instruction in AllocSetFreeIndex()

On Fri, Dec 27, 2019 at 9:54 AM Tom Lane <tgl(at)sss(dot)pgh(dot)pa(dot)us> wrote:
>
> Anyway, getting back to the presented patch, I find myself a bit
> dissatisfied with it because it seems like it's leaving something
> on the table. Specifically, looking at the generated assembly
> code on a couple of architectures, the setup logic generated by
>
> tsize = (size - 1) >> ALLOC_MINBITS;
>
> looks like it costs as much or more as the clz proper. I'm not
> sure we can get rid of the subtract-one step,

As I understand it, the desired outcome is ceil(log2(size)), which can
be computed by clz(size - 1) + 1.

> but couldn't the
> right shift be elided in favor of changing the constant we
> subtract clz's result from? Shifting off those bits separately
> made sense in the old implementation, but assuming that CLZ is
> more or less constant-time, it doesn't with CLZ.

That makes sense -- I'll look into doing that.

--
John Naylor https://www.2ndQuadrant.com/
PostgreSQL Development, 24x7 Support, Remote DBA, Training & Services