public inbox for [email protected]
help / color / mirror / Atom feedFrom: Devulapalli, Raghuveer <[email protected]>
To: [email protected] <[email protected]>
Cc: Shankaran, Akash <[email protected]>
Cc: Devulapalli, Raghuveer <[email protected]>
Subject: Improve CRC32C performance on SSE4.2
Date: Wed, 5 Feb 2025 20:48:56 +0000
Message-ID: <PH8PR11MB82869FF741DFA4E9A029FF13FBF72@PH8PR11MB8286.namprd11.prod.outlook.com> (raw)
This patch improves the performance of SSE42 CRC32C algorithm. The current SSE4.2 implementation of CRC32C relies on the native crc32 instruction and processes 8 bytes at a time in a loop. The technique in this paper uses the pclmulqdq instruction and processing 64 bytes at time. The algorithm is based on sse42 version of crc32 computation from Chromium's copy of zlib with modified constants for crc32c computation. See:
https://chromium.googlesource.com/chromium/src/+/refs/heads/main/third_party/zlib/crc32_simd.c
Microbenchmarks (generated with google benchmark using a standalone version of the same algorithms):
Comparing scalar_crc32c to sse42_crc32c (for various buffer sizes: 64, 128, 256, 512, 1024, 2048 bytes)
Benchmark Time CPU Time Old Time New CPU Old CPU New
------------------------------------------------------------------------------------------------------------------------------------
[scalar_crc32c vs. sse42_crc32c]/64 -0.8147 -0.8148 33 6 33 6
[scalar_crc32c vs. sse42_crc32c]/128 -0.8962 -0.8962 88 9 88 9
[scalar_crc32c vs. sse42_crc32c]/256 -0.9200 -0.9200 211 17 211 17
[scalar_crc32c vs. sse42_crc32c]/512 -0.9389 -0.9389 486 30 486 30
[scalar_crc32c vs. sse42_crc32c]/1024 -0.9452 -0.9452 1037 57 1037 57
[scalar_crc32c vs. sse42_crc32c]/2048 -0.9456 -0.9456 2140 116 2140 116
Raghuveer
Attachments:
[application/octet-stream] v1-0001-Add-more-test-coverage-for-crc32c.patch (3.4K, ../PH8PR11MB82869FF741DFA4E9A029FF13FBF72@PH8PR11MB8286.namprd11.prod.outlook.com/3-v1-0001-Add-more-test-coverage-for-crc32c.patch)
download | inline diff:
From 2aa9c6e28bbc956e0d4cc7aea5e1d1871b876a6d Mon Sep 17 00:00:00 2001
From: Raghuveer Devulapalli <[email protected]>
Date: Tue, 4 Feb 2025 12:56:00 -0800
Subject: [PATCH v1 1/2] Add more test coverage for crc32c
---
src/test/regress/expected/crc32c.out | 42 ++++++++++++++++++++++++++++
src/test/regress/parallel_schedule | 2 ++
src/test/regress/sql/crc32c.sql | 12 ++++++++
3 files changed, 56 insertions(+)
create mode 100644 src/test/regress/expected/crc32c.out
create mode 100644 src/test/regress/sql/crc32c.sql
diff --git a/src/test/regress/expected/crc32c.out b/src/test/regress/expected/crc32c.out
new file mode 100644
index 0000000000..f25965df4a
--- /dev/null
+++ b/src/test/regress/expected/crc32c.out
@@ -0,0 +1,42 @@
+--
+-- CRC32C
+-- Testing CRC32C SSE4.2 algorithm.
+-- The new algorithm has various code paths that needs test coverage.
+-- We achieve that by computing CRC32C of text of various sizes: 15, 64, 128, 144, 159 and 256 bytes.
+--
+SELECT crc32c('');
+ crc32c
+--------
+ 0
+(1 row)
+
+SELECT crc32c('Hello 15 bytes!');
+ crc32c
+------------
+ 3405757121
+(1 row)
+
+SELECT crc32c('This is a 64 byte piece of text to run through the main loop ...');
+ crc32c
+-----------
+ 721494841
+(1 row)
+
+SELECT crc32c('This is a carefully constructed text that needs to be exactly 128 bytes long for testing purposes. Let me add more words to ....');
+ crc32c
+------------
+ 1602016964
+(1 row)
+
+SELECT crc32c('This is a text that needs to be exactly 144 bytes long for testing purposes. I will add more words to reach that specific length. Now we are ...');
+ crc32c
+------------
+ 1912862944
+(1 row)
+
+SELECT crc32c('This is a precisely crafted message that needs to be exactly 159 bytes in length for testing purposes. I will continue adding more text until we reach that ...');
+ crc32c
+------------
+ 1245879782
+(1 row)
+
diff --git a/src/test/regress/parallel_schedule b/src/test/regress/parallel_schedule
index 1edd9e45eb..7c9dbf65db 100644
--- a/src/test/regress/parallel_schedule
+++ b/src/test/regress/parallel_schedule
@@ -56,6 +56,8 @@ test: create_aggregate create_function_sql create_cast constraints triggers sele
# ----------
test: sanity_check
+test: crc32c
+
# ----------
# Another group of parallel tests
# aggregates depends on create_aggregate
diff --git a/src/test/regress/sql/crc32c.sql b/src/test/regress/sql/crc32c.sql
new file mode 100644
index 0000000000..5e481eab6f
--- /dev/null
+++ b/src/test/regress/sql/crc32c.sql
@@ -0,0 +1,12 @@
+--
+-- CRC32C
+-- Testing CRC32C SSE4.2 algorithm.
+-- The new algorithm has various code paths that needs test coverage.
+-- We achieve that by computing CRC32C of text of various sizes: 15, 64, 128, 144, 159 and 256 bytes.
+--
+SELECT crc32c('');
+SELECT crc32c('Hello 15 bytes!');
+SELECT crc32c('This is a 64 byte piece of text to run through the main loop ...');
+SELECT crc32c('This is a carefully constructed text that needs to be exactly 128 bytes long for testing purposes. Let me add more words to ....');
+SELECT crc32c('This is a text that needs to be exactly 144 bytes long for testing purposes. I will add more words to reach that specific length. Now we are ...');
+SELECT crc32c('This is a precisely crafted message that needs to be exactly 159 bytes in length for testing purposes. I will continue adding more text until we reach that ...');
--
2.43.0
[application/octet-stream] v1-0002-Improve-CRC32C-performance-on-SSE4.2.patch (9.8K, ../PH8PR11MB82869FF741DFA4E9A029FF13FBF72@PH8PR11MB8286.namprd11.prod.outlook.com/4-v1-0002-Improve-CRC32C-performance-on-SSE4.2.patch)
download | inline diff:
From 661d6a7ae5ba02f963561513bea4a003d789cdda Mon Sep 17 00:00:00 2001
From: Raghuveer Devulapalli <[email protected]>
Date: Tue, 4 Feb 2025 15:20:13 -0800
Subject: [PATCH v1 2/2] Improve CRC32C performance on SSE4.2
The current SSE4.2 implementation of CRC32C relies on the native crc32
instruction and processes 8 bytes at a time in a loop. The technique in
this paper uses the pclmulqdq instruction and processing 64 bytes at
time.
Based on: "Fast CRC Computation for Generic Polynomials Using PCLMULQDQ Instruction"
V. Gopal, E. Ozturk, et al., 2009
The algorithm is based on crc32_sse42_simd from chromimum's copy of zlib. See:
from https://chromium.googlesource.com/chromium/src/+/refs/heads/main/third_party/zlib/crc32_simd.c
Microbenchmarks: (generated with google benchmark using a standalone
version of the same algorithms).
Comparing scalar_crc32c (current version) to sse42_crc32c (proposed new
version):
|----------------------------------+---------------------+---------------+---------------|
| Benchmark | Buffer size (bytes) | Time Old (ns) | Time New (ns) |
|----------------------------------+---------------------+---------------+---------------|
| [scalar_crc32c vs. sse42_crc32c] | 64 | 33 | 6 |
| [scalar_crc32c vs. sse42_crc32c] | 128 | 88 | 9 |
| [scalar_crc32c vs. sse42_crc32c] | 256 | 211 | 17 |
| [scalar_crc32c vs. sse42_crc32c] | 512 | 486 | 30 |
| [scalar_crc32c vs. sse42_crc32c] | 1024 | 1037 | 57 |
| [scalar_crc32c vs. sse42_crc32c] | 2048 | 2140 | 116 |
|----------------------------------+---------------------+---------------+---------------|
---
config/c-compiler.m4 | 7 +-
configure | 7 +-
meson.build | 7 +-
src/port/pg_crc32c_sse42.c | 127 ++++++++++++++++++++++++++++++++++++-
4 files changed, 141 insertions(+), 7 deletions(-)
diff --git a/config/c-compiler.m4 b/config/c-compiler.m4
index 8534cc54c1..8b255b5cc8 100644
--- a/config/c-compiler.m4
+++ b/config/c-compiler.m4
@@ -557,14 +557,19 @@ AC_DEFUN([PGAC_SSE42_CRC32_INTRINSICS],
[define([Ac_cachevar], [AS_TR_SH([pgac_cv_sse42_crc32_intrinsics])])dnl
AC_CACHE_CHECK([for _mm_crc32_u8 and _mm_crc32_u32], [Ac_cachevar],
[AC_LINK_IFELSE([AC_LANG_PROGRAM([#include <nmmintrin.h>
+ #include <wmmintrin.h>
#if defined(__has_attribute) && __has_attribute (target)
- __attribute__((target("sse4.2")))
+ __attribute__((target("sse4.2,pclmul")))
#endif
static int crc32_sse42_test(void)
+
{
+ __m128i x1 = _mm_set1_epi32(1);
unsigned int crc = 0;
crc = _mm_crc32_u8(crc, 0);
crc = _mm_crc32_u32(crc, 0);
+ x1 = _mm_clmulepi64_si128(x1, x1, 0x00); // pclmul
+ crc = crc + _mm_extract_epi32(x1, 1);
/* return computed value, to prevent the above being optimized away */
return crc == 0;
}],
diff --git a/configure b/configure
index ceeef9b091..f457e3d3bc 100755
--- a/configure
+++ b/configure
@@ -17178,14 +17178,19 @@ else
cat confdefs.h - <<_ACEOF >conftest.$ac_ext
/* end confdefs.h. */
#include <nmmintrin.h>
+ #include <wmmintrin.h>
#if defined(__has_attribute) && __has_attribute (target)
- __attribute__((target("sse4.2")))
+ __attribute__((target("sse4.2,pclmul")))
#endif
static int crc32_sse42_test(void)
+
{
+ __m128i x1 = _mm_set1_epi32(1);
unsigned int crc = 0;
crc = _mm_crc32_u8(crc, 0);
crc = _mm_crc32_u32(crc, 0);
+ x1 = _mm_clmulepi64_si128(x1, x1, 0x00);
+ crc = crc + _mm_extract_epi32(x1, 1);
/* return computed value, to prevent the above being optimized away */
return crc == 0;
}
diff --git a/meson.build b/meson.build
index 8e128f4982..070f51a440 100644
--- a/meson.build
+++ b/meson.build
@@ -2227,15 +2227,18 @@ if host_cpu == 'x86' or host_cpu == 'x86_64'
prog = '''
#include <nmmintrin.h>
-
+#include <wmmintrin.h>
#if defined(__has_attribute) && __has_attribute (target)
-__attribute__((target("sse4.2")))
+__attribute__((target("sse4.2,pclmul")))
#endif
int main(void)
{
+ __m128i x1 = _mm_set1_epi32(1);
unsigned int crc = 0;
crc = _mm_crc32_u8(crc, 0);
crc = _mm_crc32_u32(crc, 0);
+ x1 = _mm_clmulepi64_si128(x1, x1, 0x00); // pclmul
+ crc = crc + _mm_extract_epi32(x1, 1);
/* return computed value, to prevent the above being optimized away */
return crc == 0;
}
diff --git a/src/port/pg_crc32c_sse42.c b/src/port/pg_crc32c_sse42.c
index 22c2137df3..69f8917c7d 100644
--- a/src/port/pg_crc32c_sse42.c
+++ b/src/port/pg_crc32c_sse42.c
@@ -15,13 +15,13 @@
#include "c.h"
#include <nmmintrin.h>
-
+#include <wmmintrin.h>
#include "port/pg_crc32c.h"
pg_attribute_no_sanitize_alignment()
pg_attribute_target("sse4.2")
-pg_crc32c
-pg_comp_crc32c_sse42(pg_crc32c crc, const void *data, size_t len)
+static pg_crc32c
+pg_comp_crc32c_sse42_tail(pg_crc32c crc, const void *data, size_t len)
{
const unsigned char *p = data;
const unsigned char *pend = p + len;
@@ -68,3 +68,124 @@ pg_comp_crc32c_sse42(pg_crc32c crc, const void *data, size_t len)
return crc;
}
+
+/*
+ * Based on: "Fast CRC Computation for Generic Polynomials Using PCLMULQDQ
+ * Instruction" V. Gopal, E. Ozturk, et al., 2009
+ *
+ * The algorithm is based on crc32_sse42_simd from chromimum's copy of zlib.
+ * See:
+ * https://chromium.googlesource.com/chromium/src/+/refs/heads/main/third_party/zlib/crc32_simd.c
+ */
+
+pg_attribute_no_sanitize_alignment()
+pg_attribute_target("sse4.2,pclmul")
+pg_crc32c
+pg_comp_crc32c_sse42(pg_crc32c crc, const void *data, size_t length)
+{
+ ssize_t len = (ssize_t) length;
+ const unsigned char *buf = data;
+ /*
+ * Definitions of the bit-reflected domain constants k1,k2,k3, etc and
+ * the CRC32+Barrett polynomials given at the end of the paper.
+ */
+ static const uint64_t pg_attribute_aligned(16) k1k2[] = { 0x740eef02, 0x9e4addf8 };
+ static const uint64_t pg_attribute_aligned(16) k3k4[] = { 0xf20c0dfe, 0x14cd00bd6 };
+ static const uint64_t pg_attribute_aligned(16) k5k0[] = { 0xdd45aab8, 0x000000000 };
+ static const uint64_t pg_attribute_aligned(16) poly[] = { 0x105ec76f1, 0xdea713f1 };
+ if (len >= 64) {
+ __m128i x0, x1, x2, x3, x4, x5, x6, x7, x8, y5, y6, y7, y8;
+ /*
+ * There's at least one block of 64.
+ */
+ x1 = _mm_loadu_si128((__m128i *)(buf + 0x00));
+ x2 = _mm_loadu_si128((__m128i *)(buf + 0x10));
+ x3 = _mm_loadu_si128((__m128i *)(buf + 0x20));
+ x4 = _mm_loadu_si128((__m128i *)(buf + 0x30));
+ x1 = _mm_xor_si128(x1, _mm_cvtsi32_si128(crc));
+ x0 = _mm_load_si128((__m128i *)k1k2);
+ buf += 64;
+ len -= 64;
+ /*
+ * Parallel fold blocks of 64, if any.
+ */
+ while (len >= 64)
+ {
+ x5 = _mm_clmulepi64_si128(x1, x0, 0x00);
+ x6 = _mm_clmulepi64_si128(x2, x0, 0x00);
+ x7 = _mm_clmulepi64_si128(x3, x0, 0x00);
+ x8 = _mm_clmulepi64_si128(x4, x0, 0x00);
+ x1 = _mm_clmulepi64_si128(x1, x0, 0x11);
+ x2 = _mm_clmulepi64_si128(x2, x0, 0x11);
+ x3 = _mm_clmulepi64_si128(x3, x0, 0x11);
+ x4 = _mm_clmulepi64_si128(x4, x0, 0x11);
+ y5 = _mm_loadu_si128((__m128i *)(buf + 0x00));
+ y6 = _mm_loadu_si128((__m128i *)(buf + 0x10));
+ y7 = _mm_loadu_si128((__m128i *)(buf + 0x20));
+ y8 = _mm_loadu_si128((__m128i *)(buf + 0x30));
+ x1 = _mm_xor_si128(x1, x5);
+ x2 = _mm_xor_si128(x2, x6);
+ x3 = _mm_xor_si128(x3, x7);
+ x4 = _mm_xor_si128(x4, x8);
+ x1 = _mm_xor_si128(x1, y5);
+ x2 = _mm_xor_si128(x2, y6);
+ x3 = _mm_xor_si128(x3, y7);
+ x4 = _mm_xor_si128(x4, y8);
+ buf += 64;
+ len -= 64;
+ }
+ /*
+ * Fold into 128-bits.
+ */
+ x0 = _mm_load_si128((__m128i *)k3k4);
+ x5 = _mm_clmulepi64_si128(x1, x0, 0x00);
+ x1 = _mm_clmulepi64_si128(x1, x0, 0x11);
+ x1 = _mm_xor_si128(x1, x2);
+ x1 = _mm_xor_si128(x1, x5);
+ x5 = _mm_clmulepi64_si128(x1, x0, 0x00);
+ x1 = _mm_clmulepi64_si128(x1, x0, 0x11);
+ x1 = _mm_xor_si128(x1, x3);
+ x1 = _mm_xor_si128(x1, x5);
+ x5 = _mm_clmulepi64_si128(x1, x0, 0x00);
+ x1 = _mm_clmulepi64_si128(x1, x0, 0x11);
+ x1 = _mm_xor_si128(x1, x4);
+ x1 = _mm_xor_si128(x1, x5);
+ /*
+ * Single fold blocks of 16, if any.
+ */
+ while (len >= 16)
+ {
+ x2 = _mm_loadu_si128((__m128i *)buf);
+ x5 = _mm_clmulepi64_si128(x1, x0, 0x00);
+ x1 = _mm_clmulepi64_si128(x1, x0, 0x11);
+ x1 = _mm_xor_si128(x1, x2);
+ x1 = _mm_xor_si128(x1, x5);
+ buf += 16;
+ len -= 16;
+ }
+ /*
+ * Fold 128-bits to 64-bits.
+ */
+ x2 = _mm_clmulepi64_si128(x1, x0, 0x10);
+ x3 = _mm_setr_epi32(~0, 0, ~0, 0);
+ x1 = _mm_srli_si128(x1, 8);
+ x1 = _mm_xor_si128(x1, x2);
+ x0 = _mm_loadl_epi64((__m128i*)k5k0);
+ x2 = _mm_srli_si128(x1, 4);
+ x1 = _mm_and_si128(x1, x3);
+ x1 = _mm_clmulepi64_si128(x1, x0, 0x00);
+ x1 = _mm_xor_si128(x1, x2);
+ /*
+ * Barret reduce to 32-bits.
+ */
+ x0 = _mm_load_si128((__m128i*)poly);
+ x2 = _mm_and_si128(x1, x3);
+ x2 = _mm_clmulepi64_si128(x2, x0, 0x10);
+ x2 = _mm_and_si128(x2, x3);
+ x2 = _mm_clmulepi64_si128(x2, x0, 0x00);
+ x1 = _mm_xor_si128(x1, x2);
+ crc = _mm_extract_epi32(x1, 1);
+ }
+
+ return pg_comp_crc32c_sse42_tail(crc, buf, len);
+}
--
2.43.0
view thread (3+ messages) latest in thread
reply
Reply instructions:
You may reply publicly to this message via plain-text email
using any one of the following methods:
* Reply to all the recipients using the --to and --cc options:
reply via email
To: [email protected]
Cc: [email protected], [email protected], [email protected]
Subject: Re: Improve CRC32C performance on SSE4.2
In-Reply-To: <PH8PR11MB82869FF741DFA4E9A029FF13FBF72@PH8PR11MB8286.namprd11.prod.outlook.com>
* Save the following mbox file, import it into your mail client,
and reply-to-all from there: mbox
This inbox is served by agora; see mirroring instructions
for how to clone and mirror all data and code used for this inbox