public inbox for [email protected]help / color / mirror / Atom feed
[PATCH v13 06/18] More refactoring 3+ messages / 2 participants [nested] [flat]
* [PATCH v13 06/18] More refactoring @ 2020-11-01 19:46 Justin Pryzby <[email protected]> 0 siblings, 0 replies; 3+ messages in thread From: Justin Pryzby @ 2020-11-01 19:46 UTC (permalink / raw) --- src/backend/commands/indexcmds.c | 201 ++++++++++----------- src/test/regress/expected/create_index.out | 4 +- 2 files changed, 93 insertions(+), 112 deletions(-) diff --git a/src/backend/commands/indexcmds.c b/src/backend/commands/indexcmds.c index f5fea14ff4..5c5596cd28 100644 --- a/src/backend/commands/indexcmds.c +++ b/src/backend/commands/indexcmds.c @@ -102,8 +102,8 @@ static void ReindexMultipleInternal(List *relids, ReindexParams *params); static bool ReindexRelationConcurrently(Oid relationOid, ReindexParams *params); -static List *ReindexIndexesConcurrently(List *indexIds, List *heapRelationIds, - ReindexParams *params, MemoryContext private_context); +static List *ReindexIndexesConcurrently(List *indexIds, ReindexParams *params, + MemoryContext private_context); static void update_relispartition(Oid relationId, bool newval); static inline void set_indexsafe_procflags(void); @@ -2652,8 +2652,8 @@ ReindexIndex(RangeVar *indexRelation, ReindexParams *params, bool isTopLevel) .indexId = indOid, /* other fields set later */ }; + ReindexIndexesConcurrently(list_make1(&idxinfo), - list_make1_oid(IndexGetRelation(indOid, false)), params, CurrentMemoryContext); } else @@ -3023,12 +3023,11 @@ reindex_error_callback(void *arg) /* - * Given a list of index oids, return a list of leaf partitions by removing - * any intermediate parents. heaprels is populated with the corresponding - * tables. + * Given a list of index oids, return a new list of leaf partitions by + * excluding any intermediate parents. */ static List * -leaf_indexes(List *inhoids, int options, List **heaprels) +leaf_indexes(List *inhoids, int options) { List *partitions = NIL; ListCell *lc; @@ -3060,7 +3059,6 @@ leaf_indexes(List *inhoids, int options, List **heaprels) /* Save partition OID in current MemoryContext */ partitions = lappend_oid(partitions, partoid); - *heaprels = lappend_oid(*heaprels, tableoid); } return partitions; @@ -3072,13 +3070,11 @@ leaf_indexes(List *inhoids, int options, List **heaprels) * * Reindex a set of partitions, per the partitioned index or table given * by the caller. - * XXX: should be further refactored with logic from ReindexRelationConcurrently */ static void ReindexPartitions(Oid relid, ReindexParams *params, bool isTopLevel) { - List *partitions = NIL, - *heaprels = NIL; + List *partitions = NIL; char relkind = get_rel_relkind(relid); char *relname = get_rel_name(relid); char *relnamespace = get_namespace_name(get_rel_namespace(relid)); @@ -3132,7 +3128,7 @@ ReindexPartitions(Oid relid, ReindexParams *params, bool isTopLevel) if (relkind == RELKIND_PARTITIONED_INDEX) { old_context = MemoryContextSwitchTo(reindex_context); - partitions = leaf_indexes(inhoids, params->options, &heaprels); + partitions = leaf_indexes(inhoids, params->options); MemoryContextSwitchTo(old_context); } else { /* Loop over parent tables */ @@ -3145,7 +3141,7 @@ ReindexPartitions(Oid relid, ReindexParams *params, bool isTopLevel) parttable = table_open(partoid, ShareLock); old_context = MemoryContextSwitchTo(reindex_context); partindexes = RelationGetIndexList(parttable); - partindexes = leaf_indexes(partindexes, params->options, &heaprels); + partindexes = leaf_indexes(partindexes, params->options); partitions = list_concat(partitions, partindexes); MemoryContextSwitchTo(old_context); @@ -3154,10 +3150,9 @@ ReindexPartitions(Oid relid, ReindexParams *params, bool isTopLevel) } if ((params->options & REINDEXOPT_CONCURRENTLY) != 0 && - relkind == RELKIND_PARTITIONED_INDEX && get_rel_persistence(relid) != RELPERSISTENCE_TEMP) { - List *idxinfos = NIL; + List *idxinfos = NIL; ReindexIndexInfo *idxinfo; old_context = MemoryContextSwitchTo(reindex_context); @@ -3172,7 +3167,7 @@ ReindexPartitions(Oid relid, ReindexParams *params, bool isTopLevel) MemoryContextSwitchTo(old_context); /* Process all indexes in a single loop */ - ReindexIndexesConcurrently(idxinfos, heaprels, params, reindex_context); + ReindexIndexesConcurrently(idxinfos, params, reindex_context); } else { /* * Process each partition listed in a separate transaction. Note that @@ -3342,7 +3337,6 @@ ReindexMultipleInternal(List *relids, ReindexParams *params) static bool ReindexRelationConcurrently(Oid relationOid, ReindexParams *params) { - List *heapRelationIds = NIL; List *indexIds = NIL; List *newIndexIds = NIL; ListCell *lc, @@ -3395,14 +3389,6 @@ ReindexRelationConcurrently(Oid relationOid, ReindexParams *params) */ Relation heapRelation; - /* Save the list of relation OIDs in private context */ - oldcontext = MemoryContextSwitchTo(private_context); - - /* Track this relation for session locks */ - heapRelationIds = lappend_oid(heapRelationIds, relationOid); - - MemoryContextSwitchTo(oldcontext); - if (IsCatalogRelationOid(relationOid)) ereport(ERROR, (errcode(ERRCODE_FEATURE_NOT_SUPPORTED), @@ -3415,7 +3401,7 @@ ReindexRelationConcurrently(Oid relationOid, ReindexParams *params) ShareUpdateExclusiveLock); /* leave if relation does not exist */ if (!heapRelation) - break; + break; // XXX: lremove } else heapRelation = table_open(relationOid, @@ -3473,14 +3459,6 @@ ReindexRelationConcurrently(Oid relationOid, ReindexParams *params) Relation toastRelation = table_open(toastOid, ShareUpdateExclusiveLock); - /* Save the list of relation OIDs in private context */ - oldcontext = MemoryContextSwitchTo(private_context); - - /* Track this relation for session locks */ - heapRelationIds = lappend_oid(heapRelationIds, toastOid); - - MemoryContextSwitchTo(oldcontext); - foreach(lc2, RelationGetIndexList(toastRelation)) { Oid cellOid = lfirst_oid(lc2); @@ -3521,78 +3499,6 @@ ReindexRelationConcurrently(Oid relationOid, ReindexParams *params) break; } case RELKIND_INDEX: - { - Oid heapId = IndexGetRelation(relationOid, - (params->options & REINDEXOPT_MISSING_OK) != 0); - Relation heapRelation; - ReindexIndexInfo *idx; - - /* if relation is missing, leave */ - if (!OidIsValid(heapId)) - break; - - if (IsCatalogRelationOid(heapId)) - ereport(ERROR, - (errcode(ERRCODE_FEATURE_NOT_SUPPORTED), - errmsg("cannot reindex system catalogs concurrently"))); - - /* - * Don't allow reindex for an invalid index on TOAST table, as - * if rebuilt it would not be possible to drop it. Match - * error message in reindex_index(). - */ - if (IsToastNamespace(get_rel_namespace(relationOid)) && - !get_index_isvalid(relationOid)) - ereport(ERROR, - (errcode(ERRCODE_FEATURE_NOT_SUPPORTED), - errmsg("cannot reindex invalid index on TOAST table"))); - - /* - * Check if parent relation can be locked and if it exists, - * this needs to be done at this stage as the list of indexes - * to rebuild is not complete yet, and REINDEXOPT_MISSING_OK - * should not be used once all the session locks are taken. - */ - if ((params->options & REINDEXOPT_MISSING_OK) != 0) - { - heapRelation = try_table_open(heapId, - ShareUpdateExclusiveLock); - /* leave if relation does not exist */ - if (!heapRelation) - break; - } - else - heapRelation = table_open(heapId, - ShareUpdateExclusiveLock); - - if (OidIsValid(params->tablespaceOid) && - IsSystemRelation(heapRelation)) - ereport(ERROR, - (errcode(ERRCODE_FEATURE_NOT_SUPPORTED), - errmsg("cannot move system relation \"%s\"", - get_rel_name(relationOid)))); - - table_close(heapRelation, NoLock); - - /* Save the list of relation OIDs in private context */ - oldcontext = MemoryContextSwitchTo(private_context); - - /* Track the heap relation of this index for session locks */ - heapRelationIds = list_make1_oid(heapId); - - /* - * Save the list of relation OIDs in private context. Note - * that invalid indexes are allowed here. - */ - idx = palloc(sizeof(ReindexIndexInfo)); - idx->indexId = relationOid; - indexIds = lappend(indexIds, idx); - /* other fields set later */ - - MemoryContextSwitchTo(oldcontext); - break; - } - case RELKIND_PARTITIONED_TABLE: case RELKIND_PARTITIONED_INDEX: default: @@ -3623,10 +3529,10 @@ ReindexRelationConcurrently(Oid relationOid, ReindexParams *params) errmsg("cannot move non-shared relation to tablespace \"%s\"", get_tablespace_name(params->tablespaceOid)))); - Assert(heapRelationIds != NIL); + // Assert(heapRelationIds != NIL); /* Do the work */ - newIndexIds = ReindexIndexesConcurrently(indexIds, heapRelationIds, params, private_context); + newIndexIds = ReindexIndexesConcurrently(indexIds, params, private_context); /* Log what we did */ if ((params->options & REINDEXOPT_VERBOSE) != 0) @@ -3668,9 +3574,10 @@ ReindexRelationConcurrently(Oid relationOid, ReindexParams *params) * This is called by ReindexRelationConcurrently and */ static List * -ReindexIndexesConcurrently(List *indexIds, List *heapRelationIds, - ReindexParams *params, MemoryContext private_context) +ReindexIndexesConcurrently(List *indexIds, ReindexParams *params, + MemoryContext private_context) { + List *heapRelationIds = NIL; List *newIndexIds = NIL; List *relationLocks = NIL; List *lockTags = NIL; @@ -3688,6 +3595,80 @@ ReindexIndexesConcurrently(List *indexIds, List *heapRelationIds, }; int64 progress_vals[4]; + /* It's not a shared catalog, so refuse to move it to shared tablespace */ + if (params->tablespaceOid == GLOBALTABLESPACE_OID && false) + ereport(ERROR, + (errcode(ERRCODE_FEATURE_NOT_SUPPORTED), + errmsg("cannot move non-shared relation to tablespace \"%s\"", + get_tablespace_name(params->tablespaceOid)))); + + foreach(lc, indexIds) + { + ReindexIndexInfo *idx = lfirst(lc); + Oid indexrelid = idx->indexId; + Oid heapId = IndexGetRelation(indexrelid, + (params->options & REINDEXOPT_MISSING_OK) != 0); + Relation heapRelation; + + /* if relation is missing, leave */ + if (!OidIsValid(heapId)) + break; // XXX: ldelete? + + if (IsCatalogRelationOid(heapId)) + ereport(ERROR, + (errcode(ERRCODE_FEATURE_NOT_SUPPORTED), + errmsg("cannot reindex system catalogs concurrently"))); + + /* + * Don't allow reindex for an invalid index on TOAST table, as + * if rebuilt it would not be possible to drop it. Match + * error message in reindex_index(). + */ + if (IsToastNamespace(get_rel_namespace(indexrelid)) && + !get_index_isvalid(indexrelid)) + ereport(ERROR, + (errcode(ERRCODE_FEATURE_NOT_SUPPORTED), + errmsg("cannot reindex invalid index on TOAST table"))); + + if (OidIsValid(params->tablespaceOid) && + IsCatalogRelationOid(indexrelid)) + ereport(ERROR, + (errcode(ERRCODE_FEATURE_NOT_SUPPORTED), + errmsg("cannot move system relation \"%s\"", + get_rel_name(indexrelid)))); + + /* + * Check if parent relation can be locked and if it exists, + * this needs to be done at this stage as the list of indexes + * to rebuild is not complete yet, and REINDEXOPT_MISSING_OK + * should not be used once all the session locks are taken. + */ + if ((params->options & REINDEXOPT_MISSING_OK) != 0) + { + heapRelation = try_table_open(heapId, + ShareUpdateExclusiveLock); + /* leave if relation does not exist */ + if (!heapRelation) + break; // ldelete + } + else + heapRelation = table_open(heapId, + ShareUpdateExclusiveLock); + table_close(heapRelation, NoLock); + + /* Save the list of relation OIDs in private context */ + oldcontext = MemoryContextSwitchTo(private_context); + + /* Track the heap relation of this index for session locks */ + heapRelationIds = lappend_oid(heapRelationIds, heapId); + // heapRelationIds = list_make1_oid(heapId); + + /* Note that invalid indexes are allowed here. */ + + MemoryContextSwitchTo(oldcontext); + // break; + } + /*----- * Now we have all the indexes we want to process in indexIds. * diff --git a/src/test/regress/expected/create_index.out b/src/test/regress/expected/create_index.out index 6f41adf736..830fdddf24 100644 --- a/src/test/regress/expected/create_index.out +++ b/src/test/regress/expected/create_index.out @@ -2470,12 +2470,12 @@ COMMIT; REINDEX TABLE CONCURRENTLY pg_class; -- no catalog relation ERROR: cannot reindex system catalogs concurrently REINDEX INDEX CONCURRENTLY pg_class_oid_index; -- no catalog index -ERROR: concurrent index creation on system catalog tables is not supported +ERROR: cannot reindex system catalogs concurrently -- These are the toast table and index of pg_authid. REINDEX TABLE CONCURRENTLY pg_toast.pg_toast_1260; -- no catalog toast table ERROR: cannot reindex system catalogs concurrently REINDEX INDEX CONCURRENTLY pg_toast.pg_toast_1260_index; -- no catalog toast index -ERROR: concurrent index creation on system catalog tables is not supported +ERROR: cannot reindex system catalogs concurrently REINDEX SYSTEM CONCURRENTLY postgres; -- not allowed for SYSTEM ERROR: cannot reindex system catalogs concurrently -- Warns about catalog relations -- 2.17.0 --QTprm0S8XgL7H0Dt-- ^ permalink raw reply [nested|flat] 3+ messages in thread
* Improve CRC32C performance on SSE4.2 @ 2025-02-05 20:48 Devulapalli, Raghuveer <[email protected]> 0 siblings, 1 reply; 3+ messages in thread From: Devulapalli, Raghuveer @ 2025-02-05 20:48 UTC (permalink / raw) To: [email protected] <[email protected]>; +Cc: Shankaran, Akash <[email protected]>; Devulapalli, Raghuveer <[email protected]> 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 ^ permalink raw reply [nested|flat] 3+ messages in thread
* RE: Improve CRC32C performance on SSE4.2 @ 2025-02-11 00:24 Devulapalli, Raghuveer <[email protected]> parent: Devulapalli, Raghuveer <[email protected]> 0 siblings, 0 replies; 3+ messages in thread From: Devulapalli, Raghuveer @ 2025-02-11 00:24 UTC (permalink / raw) To: [email protected] <[email protected]>; John Naylor <[email protected]>; +Cc: Shankaran, Akash <[email protected]>; Devulapalli, Raghuveer <[email protected]> Hi John, > I'm highly suspicious of these numbers because they show this version > is about 20x faster than "scalar", so relatively speaking 3x faster > than the AVX-512 proposal? Apologies for this. I was suspicious of this too and looks like I had unintentionally set the scalar version I wrote for testing CRC32C correctness (which computes crc one byte at time). The code for microbenchmarking is all here: https://github.com/r-devulap/crc32c and this commit https://github.com/r-devulap/crc32c/commit/ca4d1b24fd8af87aab544fb1634523b6657325a0 fixes that. Rerunning the benchmarks gives me more sensible numbers: Comparing scalar_crc32c to sse42_crc32c (from ./bench) Benchmark Time CPU Time Old Time New CPU Old CPU New ------------------------------------------------------------------------------------------------------------------------------------ [scalar_crc32c vs. sse42_crc32c]/64 -0.0972 -0.0971 5 4 5 4 [scalar_crc32c vs. sse42_crc32c]/128 -0.3048 -0.3048 8 6 8 6 [scalar_crc32c vs. sse42_crc32c]/256 -0.4610 -0.4610 19 10 19 10 [scalar_crc32c vs. sse42_crc32c]/512 -0.6432 -0.6432 50 18 50 18 [scalar_crc32c vs. sse42_crc32c]/1024 -0.7192 -0.7192 121 34 121 34 [scalar_crc32c vs. sse42_crc32c]/2048 -0.7275 -0.7276 259 70 259 70 > Luckily, that's easily fixable: It turns out the implementation > in the paper (and chromium) has a very inefficient finalization step, > using more carryless multiplications and plenty of other operations. > After the main loop, and at the end, it's much more efficient to > convert the 128-bit intermediate result directly into a CRC in the > usual way. Thank you for pointing this out and also fixing it! This improves over the chromium version by 10-25% especially for with smaller byte size 64 - 512 bytes: Comparing sse42_crc32c to corsix_crc32c (from ./bench) Benchmark Time CPU Time Old Time New CPU Old CPU New ------------------------------------------------------------------------------------------------------------------------------------ [sse42_crc32c vs. corsix_crc32c]/64 -0.2696 -0.2696 4 3 4 3 [sse42_crc32c vs. corsix_crc32c]/128 -0.1551 -0.1552 6 5 6 5 [sse42_crc32c vs. corsix_crc32c]/256 -0.1787 -0.1787 10 8 10 8 [sse42_crc32c vs. corsix_crc32c]/512 -0.1351 -0.1351 18 15 18 15 [sse42_crc32c vs. corsix_crc32c]/1024 -0.0972 -0.0972 34 31 34 31 [sse42_crc32c vs. corsix_crc32c]/2048 -0.0763 -0.0763 69 64 69 64 OVERALL_GEOMEAN -0.1544 -0.1544 0 0 0 0 > I generated a similar function for v2-0004 and this benchmark shows it's faster than master on 128 bytes and above. I ran the same benchmark drive_crc32c with the postgres infrastructure and found that your v2 sse42 version from corsix is slower than pg_comp_crc32c_sse42 in master branch when buffer is < 128 bytes. I think the reason is that postgres is not using -O3 flag build the crc32c source files and the compiler generates less than optimal code. Adding that flag fixes the regression for buffers with 64 bytes - 128 bytes. Could you confirm that behavior on your end too? --- src/port/pg_crc32c_sse42.c | 1 + 1 file changed, 1 insertion(+) diff --git a/src/port/pg_crc32c_sse42.c b/src/port/pg_crc32c_sse42.c index a8c1e5609b..a350b1b93a 100644 --- a/src/port/pg_crc32c_sse42.c +++ b/src/port/pg_crc32c_sse42.c @@ -81,6 +81,7 @@ pg_comp_crc32c_sse42_tail(pg_crc32c crc, const void *data, size_t len) #define clmul_lo(a, b) (_mm_clmulepi64_si128((a), (b), 0)) #define clmul_hi(a, b) (_mm_clmulepi64_si128((a), (b), 17)) pg_attribute_no_sanitize_alignment() +__attribute__((optimize("-O3"))) pg_attribute_target("sse4.2,pclmul") pg_crc32c pg_comp_crc32c_sse42(pg_crc32c crc0, const void *data, size_t len) -- You could also just build with export CFLAGS="-O3" instead of adding the function attribute. > I did the benchmarks on my older machine, which I believe has a latency of 7 cycles for this instruction. May I ask which processor does you older machine have? I am benchmarking on a Tigerlake processor. > It's probably okay to fold these together in the same compile-time > check, since both are fairly old by now, but for those following > along, pclmul is not in SSE 4.2 and is a bit newer. So this would > cause machines building on Nehalem (2008) to fail the check and go > back to slicing-by-8 with it written this way. Technically, the current version of the patch does not have a runtime cpuid check for pclmul and so would cause it to crash with segill on Nehalam (currently we only check for sse4.2). This needs to be fixed by adding an additional cpuid check for pcmul but it would fall back to slicing by 8 on Nehalem and use the latest version on Westmere and above. If you care about keeping the performance on Nehalem, then I am happy to update the choose function to pick the right pointer accordingly. Let me know which one you would prefer. Raghuveer From: Devulapalli, Raghuveer <[email protected]> Sent: Wednesday, February 5, 2025 12:49 PM To: [email protected] Cc: Shankaran, Akash <[email protected]>; Devulapalli, Raghuveer <[email protected]> Subject: Improve CRC32C performance on SSE4.2 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 ^ permalink raw reply [nested|flat] 3+ messages in thread
end of thread, other threads:[~2025-02-11 00:24 UTC | newest] Thread overview: 3+ messages (download: mbox mbox.gz follow: Atom feed) -- links below jump to the message on this page -- 2020-11-01 19:46 [PATCH v13 06/18] More refactoring Justin Pryzby <[email protected]> 2025-02-05 20:48 Improve CRC32C performance on SSE4.2 Devulapalli, Raghuveer <[email protected]> 2025-02-11 00:24 ` RE: Improve CRC32C performance on SSE4.2 Devulapalli, Raghuveer <[email protected]>
This inbox is served by agora; see mirroring instructions for how to clone and mirror all data and code used for this inbox