Horton

Re: Popcount optimization using AVX512

Nathan Bossart <nathandbossart@gmail.com>

View thread
From: Nathan Bossart <nathandbossart@gmail.com>
To: Alvaro Herrera <alvherre@alvh.no-ip.org>
Cc: "Amonson, Paul D" <paul.d.amonson@intel.com>, Tom Lane <tgl@sss.pgh.pa.us>, David Rowley <dgrowleyml@gmail.com>, Andres Freund <andres@anarazel.de>, "Shankaran, Akash" <akash.shankaran@intel.com>, Noah Misch <noah@leadboat.com>, Matthias van de Meent <boekewurm+postgres@gmail.com>, "pgsql-hackers@lists.postgresql.org" <pgsql-hackers@lists.postgresql.org>
Date: 2024-04-01T15:53:38Z
Lists: pgsql-hackers

Commits

Same data as JSON: GET /api/v1/messages/:b64id/commits the thread's linked commits as JSON, with link sources. API reference →

  1. Fix __attribute__((target(...))) usage.

  2. Use __attribute__((target(...))) for AVX-512 support.

  3. Fix code for probing availability of AVX-512.

  4. Optimize visibilitymap_count() with AVX-512 instructions.

  5. Optimize pg_popcount() with AVX-512 instructions.

  6. Inline pg_popcount() for small buffers.

  7. Avoid function call overhead of pg_popcount() in syslogger.c.

  8. Refactor code for setting pg_popcount* function pointers.

  9. Inline pg_popcount{32,64} into pg_popcount().

  10. Remove MSVC scripts

  11. Use ARMv8 CRC instructions where available.

  12. Use Intel SSE 4.2 CRC instructions where available.

On Mon, Apr 01, 2024 at 01:06:12PM +0200, Alvaro Herrera wrote:
> On 2024-Mar-31, Nathan Bossart wrote:
>> +	popcnt = _mm512_reduce_add_epi64(accum);
>> +	return popcnt + pg_popcount_fast(buf, bytes);
> 
> Hmm, doesn't this arrangement cause an extra function call to
> pg_popcount_fast to be used here?  Given the level of micro-optimization
> being used by this code, I would have thought that you'd have tried to
> avoid that.  (At least, maybe avoid the call if bytes is 0, no?)

Yes, it does.  I did another benchmark on very small arrays and can see the
overhead.  This is the time in milliseconds to run pg_popcount() on an
array 1 billion times:

    size (bytes)  HEAD      AVX512-POPCNT
    1             1707.685  3480.424
    2             1926.694  4606.182
    4             3210.412  5284.506
    8             1920.703  3640.968
    16            2936.91   4045.586
    32            3627.956  5538.418
    64            5347.213  3748.212

I suspect that anything below 64 bytes will see this regression, as that is
the earliest point where there are enough bytes for ZMM registers.

We could avoid the call if there are no remaining bytes, but the numbers
for the smallest arrays probably wouldn't improve much, and that might
actually add some overhead due to branching.  The other option to avoid
this overhead is to put most of pg_bitutils.c into its header file so that
we can inline the call.

Reviewing the current callers of pg_popcount(), IIUC the only ones that are
passing very small arrays are the bit_count() implementations and a call in
the syslogger for a single byte.  I don't know how much to worry about the
overhead for bit_count() since there's presumably a bunch of other
overhead, and the syslogger one could probably be fixed via an inline
function that pulled the value from pg_number_of_ones (which would probably
be an improvement over the status quo, anyway).  But this is all to save a
couple of nanoseconds...

-- 
Nathan Bossart
Amazon Web Services: https://aws.amazon.com