Re: use CLZ instruction in AllocSetFreeIndex()

On 2019-Dec-26, John Naylor wrote:

> In commit ab5b4e2f9ed, we optimized AllocSetFreeIndex() using a lookup
> table. At the time, using CLZ was rejected because compiler/platform
> support was not widespread enough to justify it. For other reasons, we
> recently added bitutils.h which uses __builtin_clz() where available,
> so it makes sense to revisit this. I modified the test in [1] (C files
> attached), using two separate functions to test CLZ versus the
> open-coded algorithm of pg_leftmost_one_pos32().
>
> These are typical results on a recent Intel platform:
>
> HEAD 5.55s
> clz 4.51s
> open-coded 9.67s

I can confirm these results on my Intel laptop. I ran it with a
repetition of 20, averages of 4 runs:

clz 1,614
bitutils 3,714
current 2,088
(stddevs are under 0,031).

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