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