Horton

Re: Popcount optimization using AVX512

David Rowley <dgrowleyml@gmail.com>

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

Attachments

On Sat, 16 Mar 2024 at 04:06, Nathan Bossart <nathandbossart@gmail.com> wrote:
> I ran John Naylor's test_popcount module [0] with the following command on
> an i7-1195G7:
>
>         time psql postgres -c 'select drive_popcount(10000000, 1024)'
>
> Without your patches, this seems to take somewhere around 8.8 seconds.
> With your patches, it takes 0.6 seconds.  (I re-compiled and re-ran the
> tests a couple of times because I had a difficult time believing the amount
> of improvement.)
>
> [0] https://postgr.es/m/CAFBsxsE7otwnfA36Ly44zZO%2Bb7AEWHRFANxR1h1kxveEV%3DghLQ%40mail.gmail.com

I think most of that will come from getting rid of the indirect
function that currently exists in pg_popcount().

Using the attached quick hack, the performance using John's test
module goes from:

-- master
postgres=# select drive_popcount(10000000, 1024);
Time: 9832.845 ms (00:09.833)
Time: 9844.460 ms (00:09.844)
Time: 9858.608 ms (00:09.859)

-- with attached hacky and untested patch
postgres=# select drive_popcount(10000000, 1024);
Time: 2539.029 ms (00:02.539)
Time: 2598.223 ms (00:02.598)
Time: 2611.435 ms (00:02.611)

--- and with the avx512 patch on an AMD 7945HX CPU:
postgres=# select drive_popcount(10000000, 1024);
Time: 564.982 ms
Time: 556.540 ms
Time: 554.032 ms

The following comment seems like it could do with some improvements.

 * Use AVX-512 Intrinsics for supported Intel CPUs or fall back the the software
 * loop in pg_bunutils.c and use the best 32 or 64 bit fast methods. If no fast
 * methods are used this will fall back to __builtin_* or pure software.

There's nothing much specific to Intel here.  AMD Zen4 has AVX512.
Plus "pg_bunutils.c" should be "pg_bitutils.c" and "the the"

How about just:

 * Use AVX-512 Intrinsics on supported CPUs. Fall back the software loop in
 * pg_popcount_slow() when AVX-512 is unavailable.

Maybe it's worth exploring something along the lines of the attached
before doing the AVX512 stuff.  It seems like a pretty good speed-up
and will apply for CPUs without AVX512 support.

David