Subject: Proposal for Updating CRC32C with AVX-512 Algorithm.

From: "Amonson, Paul D" <[email-masked]>
Date: Wed, 1 May 2024 15:56:08 +0000

Hi,

Comparing the current SSE4.2 implementation of the CRC32C algorithm in Postgres, to an optimized AVX-512 algorithm [0] we observed significant gains. The result was a ~6.6X average multiplier of increased performance measured on 3 different Intel products. Details below. The AVX-512 algorithm in C is a port of the ISA-L library [1] assembler code.

Workload call size distribution details (write heavy):
   * Average was approximately around 1,010 bytes per call
   * ~80% of the calls were under 256 bytes
   * ~20% of the calls were greater than or equal to 256 bytes up to the max buffer size of 8192

The 256 bytes is important because if the buffer is smaller, it makes sense fallback to the existing implementation. This is because the AVX-512 algorithm needs a minimum of 256 bytes to operate.

Using the above workload data distribution, 
at 0%    calls < 256 bytes, a 841% improvement on average for crc32c functionality was observed.
at 50%   calls < 256 bytes, a 758% improvement on average for crc32c functionality was observed.
at 90%   calls < 256 bytes, a 44% improvement on average for crc32c functionality was observed. 
at 97.6% calls < 256 bytes, the workload's crc32c performance breaks-even.
at 100%  calls < 256 bytes, a 14% regression is seen when using AVX-512 implementation. 

The results above are averages over 3 machines, and were measured on: Intel Saphire Rapids bare metal, and using EC2 on AWS cloud: Intel Saphire Rapids (m7i.2xlarge) and Intel Ice Lake (m6i.2xlarge).

Summary Data (Saphire Rapids bare metal, AWS m7i-2xl, and AWS m6i-2xl):
+---------------------+-------------------+-------------------+-------------------+--------------------+
| Rates in Bytes/us   |     Bare Metal    |    AWS m6i-2xl    |   AWS m7i-2xl     |                    |
| (Larger is Better)  +---------+---------+---------+---------+---------+---------+ Overall Multiplier |
|                     | SSE 4.2 | AVX-512 | SSE 4.2 | AVX-512 | SSE 4.2 | AVX-512 |                    |
+---------------------+---------+---------+---------+---------+---------+---------+--------------------+
| Numbers 256-8192    |  12,046 |  83,196 |   7,471 |  39,965 |  11,867 |  84,589 |        6.62        |
+---------------------+---------+---------+---------+---------+---------+---------+--------------------+
| Numbers 64 - 255    |  16,865 |  15,909 |   9,209 |   7,363 |  12,496 |  10,046 |        0.86        |
+---------------------+---------+---------+---------+---------+---------+---------+--------------------+
                                                    |  Weighted Multiplier [*]    |        1.44        |
                                                    +-----------------------------+--------------------+
There was no evidence of AVX-512 frequency throttling from perf data, which stayed steady during the test.

Feedback on this proposed improvement is appreciated. Some questions: 
1) This AVX-512 ISA-L derived code uses BSD-3 license [2]. Is this compatible with the PostgreSQL License [3]? They both appear to be very permissive licenses, but I am not an expert on licenses. 
2) Is there a preferred benchmark I should run to test this change? 

If licensing is a non-issue, I can post the initial patch along with my Postgres benchmark function patch for further review.

Thanks,
Paul

[0] https://www.researchgate.net/publication/263424619_Fast_CRC_computation#full-text
[1] https://github.com/intel/isa-l
[2] https://opensource.org/license/bsd-3-clause
[3] https://opensource.org/license/postgresql
                      
[*] Weights used were 90% of requests less than 256 bytes, 10% greater than or equal to 256 bytes.

---

From: "Amonson, Paul D" <[email-masked]>
Date: Fri, 17 May 2024 16:21:19 +0000

Hi, forgive the top-post but I have not seen any response to this post?

Thanks,
Paul

> -----Original Message-----
> From: Amonson, Paul D
> Sent: Wednesday, May 1, 2024 8:56 AM
> To: [email-masked]
> Cc: Nathan Bossart <[email-masked]>; Shankaran, Akash
> <[email-masked]>
> Subject: Proposal for Updating CRC32C with AVX-512 Algorithm.
> 
> Hi,
> 
> Comparing the current SSE4.2 implementation of the CRC32C algorithm in
> Postgres, to an optimized AVX-512 algorithm [0] we observed significant
> gains. The result was a ~6.6X average multiplier of increased performance
> measured on 3 different Intel products. Details below. The AVX-512 algorithm
> in C is a port of the ISA-L library [1] assembler code.
> 
> The 256 bytes is important because if the buffer is smaller, it makes sense
> fallback to the existing implementation. This is because the AVX-512 algorithm
> needs a minimum of 256 bytes to operate.
> 
> The results above are averages over 3 machines, and were measured on: Intel
> Saphire Rapids bare metal, and using EC2 on AWS cloud: Intel Saphire Rapids
> (m7i.2xlarge) and Intel Ice Lake (m6i.2xlarge).
> 
> 1) This AVX-512 ISA-L derived code uses BSD-3 license [2]. Is this compatible
> with the PostgreSQL License [3]? They both appear to be very permissive
> licenses, but I am not an expert on licenses.
> If licensing is a non-issue, I can post the initial patch along with my Postgres
> benchmark function patch for further review.
> 
> Thanks,
> Paul
> 
> [0]
> https://www.researchgate.net/publication/263424619_Fast_CRC_computati
> on#full-text

---

From: Daniel Gustafsson <[email-masked]>
Date: Mon, 20 May 2024 10:03:20 +0200

> On 17 May 2024, at 18:21, Amonson, Paul D <[email-masked]> wrote:

> Hi, forgive the top-post but I have not seen any response to this post?

The project is currently in feature-freeze in preparation for the next major
release so new development and ideas are not the top priority right now.
Additionally there is a large developer meeting shortly which many are busy
preparing for.  Excercise some patience, and I'm sure there will be follow-ups
to this once development of postgres v18 picks up.

--
Daniel Gustafsson

---

From: "Amonson, Paul D" <[email-masked]>
Date: Wed, 12 Jun 2024 16:43:41 +0000

> to this once development of postgres v18 picks up.

Thanks, understood.

I had our OSS internal team, who are experts in OSS licensing, review possible conflicts between the PostgreSQL license and the BSD-Clause 3-like license for the CRC32C AVX-512 code, and they found no issues. Therefore, including the new license into the PostgreSQL codebase should be acceptable.

I am attaching the first official patches. The second patch is a simple test function in PostgreSQL SQL, which I used for testing and benchmarking. It will not be merged.

Code Structure Question: While working on this code, I noticed overlaps with runtime CPU checks done in the previous POPCNT merged code. I was considering that these checks should perhaps be formalized and consolidated into a single source/header file pair. If this is desirable, where should I place these files? Should it be in "src/port" where they are used, or in "src/common" where they are available to all (not just the "src/port" tree)?

Thanks,
Paul

---

From: Tom Lane <[email-masked]>
Date: Wed, 12 Jun 2024 14:08:02 -0400

> I had our OSS internal team, who are experts in OSS licensing, review possible conflicts between the PostgreSQL license and the BSD-Clause 3-like license for the CRC32C AVX-512 code, and they found…

Maybe you should get some actual lawyers to answer this type of
question.  The Chromium license this code cites is 3-clause-BSD
style, which is NOT compatible: the "advertising" clause is
significant.

In any case, writing copyright notices that are pointers to
external web pages is not how it's done around here.  We generally
operate on the assumption that the Postgres source code will
outlive any specific web site.  Dead links to incidental material
might be okay, but legally relevant stuff not so much.

			regards, tom lane

---

From: Andres Freund <[email-masked]>
Date: Wed, 12 Jun 2024 12:37:46 -0700

Hi,

I'm wonder if this isn't going in the wrong direction. We're using CRCs for
something they're not well suited for in my understanding - and are paying a
reasonably high price for it, given that even hardware accelerated CRCs aren't
blazingly fast.

CRCs are used for things like ethernet, iSCSI because they are good at
detecting the kinds of errors encountered, namely short bursts of
bitflips. And the covered data is limited to a fairly small limit.

Which imo makes CRCs a bad choice for WAL. For one, we don't actually expect a
short burst of bitflips, the most likely case is all bits after some point
changing (because only one part of the record made it to disk). For another,
WAL records are *not* limited to a small size, and if anything error detection
becomes more important with longer records (they're likely to be span more
pages / segments).

It's hard to understand, but a nonetheless helpful page is
https://users.ece.cmu.edu/~koopman/crc/crc32.html which lists properties for
crc32c:
https://users.ece.cmu.edu/~koopman/crc/c32/0x8f6e37a0_len.txt
which lists
(0x8f6e37a0; 0x11edc6f41) <=> (0x82f63b78; 0x105ec76f1) {2147483615,2147483615,5243,5243,177,177,47,47,20,20,8,8,6,6,1,1} | gold | (*op) iSCSI; CRC-32C; CRC-32/4

This cryptic notion AFAIU indicates that for our polynomial we can detect 2bit
errors up to a length of 2147483615 bytes, 3 bit errors up to 2147483615, 3
and 4 bit errors up to 5243, 5 and 6 bit errors up to 177, 7/8 bit errors up
to 47.

IMO for our purposes just about all errors are going to be at least at sector
boundaries, i.e. 512 bytes and thus are at least 8 bit large. At that point we
are only guaranteed to find a single-byte error (it'll be common to have
much more) up to a lenght of 47bits. Which isn't a useful guarantee.

With that I perhaps have established that CRC guarantees aren't useful for us.
But not yet why we should use something else: Given that we already aren't
relying on hard guarantees, we could instead just use a fast hash like xxh3.
https://github.com/Cyan4973/xxHash which is fast both for large and small
amounts of data.

Greetings,

Andres Freund

---

From: Andres Freund <[email-masked]>
Date: Wed, 12 Jun 2024 13:11:35 -0700

Hi,

>    * ~20% of the calls were greater than or equal to 256 bytes up to the max buffer size of 8192

This is extremely workload dependent, it's not hard to find workloads with
lots of very small record and very few big ones...  What you observed might
have "just" been the warmup behaviour where more full page writes have to be
written.

There a very frequent call computing COMP_CRC32C over just 20 bytes, while
holding a crucial lock.  If we were to do introduce something like this
AVX-512 algorithm, it'd probably be worth to dispatch differently in case of
compile-time known small lengths.

How does the latency of the AVX-512 algorithm compare to just using the CRC32C
instruction?

FWIW, I tried the v2 patch on my Xeon Gold 5215 workstation, and dies early on
with SIGILL:

Program terminated with signal SIGILL, Illegal instruction.
#0  0x0000000000d5946c in _mm512_clmulepi64_epi128 (__A=..., __B=..., __C=0)
    at /home/andres/build/gcc/master/install/lib/gcc/x86_64-pc-linux-gnu/15/include/vpclmulqdqintrin.h:42
42	  return (__m512i) __builtin_ia32_vpclmulqdq_v8di ((__v8di)__A,
(gdb) bt
#0  0x0000000000d5946c in _mm512_clmulepi64_epi128 (__A=..., __B=..., __C=0)
    at /home/andres/build/gcc/master/install/lib/gcc/x86_64-pc-linux-gnu/15/include/vpclmulqdqintrin.h:42
#1  pg_comp_crc32c_avx512 (crc=<optimized out>, data=<optimized out>, length=<optimized out>)
    at ../../../../../home/andres/src/postgresql/src/port/pg_crc32c_avx512.c:163
#2  0x0000000000819343 in ReadControlFile () at ../../../../../home/andres/src/postgresql/src/backend/access/transam/xlog.c:4375
#3  0x000000000081c4ac in LocalProcessControlFile (reset=<optimized out>) at ../../../../../home/andres/src/postgresql/src/backend/access/transam/xlog.c:4817
#4  0x0000000000a8131d in PostmasterMain (argc=argc@entry=85, argv=argv@entry=0x341b08f0)
    at ../../../../../home/andres/src/postgresql/src/backend/postmaster/postmaster.c:902
#5  0x00000000009b53fe in main (argc=85, argv=0x341b08f0) at ../../../../../home/andres/src/postgresql/src/backend/main/main.c:197

Cascade lake doesn't have vpclmulqdq, so we shouldn't be getting here...

This is on an optimied build with meson, with -march=native included in
c_flags.

Relevant configure output:

Checking if "XSAVE intrinsics without -mxsave" : links: NO (cached)
Checking if "XSAVE intrinsics with -mxsave" : links: YES (cached)
Checking if "AVX-512 popcount without -mavx512vpopcntdq -mavx512bw" : links: NO (cached)
Checking if "AVX-512 popcount with -mavx512vpopcntdq -mavx512bw" : links: YES (cached)
Checking if "_mm512_clmulepi64_epi128 ... with -msse4.2 -mavx512vl -mvpclmulqdq" : links: YES
Checking if "x86_64: popcntq instruction" compiles: YES (cached)

Greetings,

Andres Freund

---

From: "Amonson, Paul D" <[email-masked]>
Date: Mon, 17 Jun 2024 22:42:54 +0000

> have "just" been the warmup behaviour where more full page writes have to
> be written.

Can you tell me how to avoid capturing this "warm-up" so that the numbers are more accurate?
 
> compile-time known small lengths.

So are you suggesting that we be able to directly call into the 64/32 bit based algorithm directly from these known small byte cases in the code? I think that we can do that with a separate API being exposed.

> How does the latency of the AVX-512 algorithm compare to just using the
> CRC32C instruction?

I think I need more information on this one as I am not sure I understand the use case? The same function pointer indirect methods are used with or without the AVX-512 algorithm?

Paul

---

From: Nathan Bossart <[email-masked]>
Date: Thu, 8 Aug 2024 14:28:31 -0500

> reasonably high price for it, given that even hardware accelerated CRCs aren't

I tend to agree, especially that we should be more concerned about all
bytes after a certain point being garbage than bit flips.  (I think we
should also care about bit flips, but I hope those are much less common
than half-written WAL records.)

> https://github.com/Cyan4973/xxHash which is fast both for large and small

Would it be out of the question to reuse the page checksum code (i.e., an
FNV-1a derivative)?  The chart in your link claims that xxh3 is
substantially faster than "FNV64", but I wonder if the latter was
vectorized.  I don't know how our CRC-32C implementations (and proposed
implementations) compare, either.

-- 
nathan

---

From: John Naylor <[email-masked]>
Date: Wed, 4 Dec 2024 13:40:37 +0700

> have "just" been the warmup behaviour where more full page writes have to be

Sorry for going back so far, but this thread was pointed out to me,
and this aspect of the design could use some more discussion:

+ * pg_crc32c_avx512(): compute the crc32c of the buffer, where the
+ * buffer length must be at least 256, and a multiple of 64. Based

There is another technique that computes CRC on 3 separate chunks and
combines them at the end, so about 3x faster on large-enough chunks.
That's the way used for the Arm proposal [0], coincidentally also
citing a white paper from Intel, but as Dimitry pointed out in that
thread, its link has apparently disappeared. Raghuveer, do you know
about this, and is there another link available?

http://www.intel.com/content/dam/www/public/us/en/documents/white-papers/crc-iscsi-polynomial-crc32-instruction-paper.pdf

The cut off point in one implementation is only 144 bytes [1] , which
is maybe not as small as we'd like, but is quite a bit smaller than
256. That seems better suited to our workloads, and more portable. I
have a *brand-new* laptop with an Intel chip, and IIUC it doesn't
support AVX-512 because it uses a big-little architecture. I also
understand that Sierra Forrest (a server product line) will be all
little cores with no AVX-512 support, so I'm not sure why the proposal
here requires AVX-512.

> compile-time known small lengths.

I know you've read an earlier version of the patch and realized that
it wouldn't help here, but we could probably dispatch differently
regardless, although it may only be worth it if we can inline the
instructions. Since we technically only need to wait for xl_prev, I
believe we could push the computation of the other 12 bytes to before
acquiring the lock, then only execute a single instruction on xl_prev
to complete the CRC computation. Is there any reason why we couldn't
do that, assuming we have a clean way to make that portable? That
would mean that the CRCs between major versions would be different,
but I think we don't guarantee that anyway.

[0] https://commitfest.postgresql.org/50/4620/
[1] https://github.com/komrad36/CRC/blob/master/CRC/golden_intel.cpp#L138C27-L138C42

--
John Naylor
Amazon Web Services

---

From: "Devulapalli, Raghuveer" <[email-masked]>
Date: Sat, 7 Dec 2024 15:16:05 +0000

> Sorry for going back so far, but this thread was pointed out to me, and this aspect
> of the design could use some more discussion:
> 
> That's the way used for the Arm proposal [0], coincidentally also citing a white
> paper from Intel, but as Dimitry pointed out in that thread, its link has apparently
> disappeared. Raghuveer, do you know about this, and is there another link
> available?
> 
> http://www.intel.com/content/dam/www/public/us/en/documents/white-
> papers/crc-iscsi-polynomial-crc32-instruction-paper.pdf

 I am not aware of this paper. Let me poke a few people internally and get back to you on this. 

> The cut off point in one implementation is only 144 bytes [1] , which is maybe not
> as small as we'd like, but is quite a bit smaller than 256. That seems better suited
> to our workloads, and more portable. I have a *brand-new* laptop with an Intel
> chip, and IIUC it doesn't support AVX-512 because it uses a big-little architecture.
> I also understand that Sierra Forrest (a server product line) will be all little cores
> with no AVX-512 support, so I'm not sure why the proposal here requires AVX-
> 512.

AVX-512 is present all of Intel main P-core based Xeon and AMD's Zen4 and Zen5. Sierra Forest contains the SSE and AVX/AVX2 family ISA but AFAIK AVX/AVX2 does not contain any CRC32C specific instructions. See:

1) https://www.intel.com/content/www/us/en/docs/intrinsics-guide/index.html#text=pclmul&ig_expand=754&techs=AVX_ALL
2) https://www.intel.com/content/www/us/en/docs/intrinsics-guide/index.html#ig_expand=754&techs=AVX_ALL&text=crc32

> 
> > There a very frequent call computing COMP_CRC32C over just 20 bytes,
> > while holding a crucial lock.  If we were to do introduce something
> > like this
> > AVX-512 algorithm, it'd probably be worth to dispatch differently in
> > case of compile-time known small lengths.
> 
> I know you've read an earlier version of the patch and realized that it wouldn't
> help here, but we could probably dispatch differently regardless, although it may
> only be worth it if we can inline the instructions. Since we technically only need to
> wait for xl_prev, I believe we could push the computation of the other 12 bytes to
> before acquiring the lock, then only execute a single instruction on xl_prev to
> complete the CRC computation. Is there any reason why we couldn't do that,
> assuming we have a clean way to make that portable? That would mean that the
> CRCs between major versions would be different, but I think we don't guarantee
> that anyway.

Not sure about that. This is not my expertise and I might need a little time to figure this out. Unfortunately, I am on travel with limited internet connection for the next 6 weeks. I will only be able to address this when I get back. Is this a blocker for the patch or is this something we can address as a revision? 
 
Raghuveer

---

From: John Naylor <[email-masked]>
Date: Sat, 14 Dec 2024 12:08:57 +0700

> and 4 bit errors up to 5243, 5 and 6 bit errors up to 177, 7/8 bit errors up

One aspect of that cryptic notation that you seemed to have missed is
"(*op)" -- explained as:

*p - primitive polynomial. This has optimal length for HD=3, and good
HD=2 performance above that length.
*o - odd bit errors detected. This has a factor of (x+1) and detects
all odd bit errors (implying that even number of bit errors have an
elevated undetected error rate)
*op - odd bit errors detected plus primitive. This is a primitive
polynomial times (x+1). It has optimal length for HD=4, and detects
all odd bit errors.

This means it's not really a 32-bit checksum -- it's a 1-bit checksum
plus a 31-bit checksum. The 1-bit checksum can detect any odd number
of bit-flips. Do we really want to throw that property away?

Sure, for an even number bitflips beyond a small number, we're left
with the luck ordinary collisions, and CRC is not particularly great,
but for two messages of the same length, I'm also not sure it's all
that bad, either

-- 
John Naylor
Amazon Web Services