From: "Amonson, Paul D" <paul.d.amonson@intel.com>
To: "pgsql-hackers@lists.postgresql.org" <pgsql-hackers@lists.postgresql.org>
CC: Nathan Bossart <nathandbossart@gmail.com>, "Shankaran, Akash"
	<akash.shankaran@intel.com>
Subject: Proposal for Updating CRC32C with AVX-512 Algorithm.
Thread-Topic: Proposal for Updating CRC32C with AVX-512 Algorithm.
Thread-Index: Adqb27jiuXmC5sH1QzmzETmUIqng2A==
Date: Wed, 1 May 2024 15:56:08 +0000
Message-ID: <BL1PR11MB530401FA7E9B1CA432CF9DC3DC192@BL1PR11MB5304.namprd11.prod.outlook.com>
Accept-Language: en-US
Content-Language: en-US
x-ms-exchange-antispam-messagedata-chunkcount: 1
x-ms-exchange-antispam-messagedata-0: =?us-ascii?Q?BJhq+2IV1FBH+lqLLZx+zS5LzvikLMDVRTzpuQ7YoS1SGoQZVa3NvxfEGTvv?=
 =?us-ascii?Q?VFY/ulKKg5GzbXAL+6CvkO6LAbmdruzrWe+1IHRiZDyekYw+bN4oPiucHScc?=
 =?us-ascii?Q?QzA3bhZmniOqeQw2AKlwuwKf8En1xCPDxq3JjyAwlsFXXvWwDYrkspd3LIPX?=
 =?us-ascii?Q?q013Ngf70fx7jmkfGDi+gXIOxQGUCZbkoKzVrnNyZgj+0BzGDHRxLSmwjcc6?=
 =?us-ascii?Q?f22cg177UsQNDflbasxl10c2EXrw0zTC5reMRNXUEfWYWzIYKLcr9diF3aOn?=
 =?us-ascii?Q?rGRwHYa9cT5fpmv0cUH5Iu7DFSn7hxGdMr3x+jAykTqsAsM7KUAX22RfFOIH?=
 =?us-ascii?Q?YstQXUmHXcgD7BZzFxRDPwBJVB5J2UwhO8pHrEnRyylonmoMEqs0tiNGWUuK?=
 =?us-ascii?Q?IBYiJm/UzeESydAr702aoYyGZoldUw6efx9Se8S8jKa1mRX6gAbYUS9uo0NQ?=
 =?us-ascii?Q?TDXgdmowRP7xHB4hJxF5D2w3zh/TbvJt4F0LONHqtrxBfY9QJaFU7v2aCWex?=
 =?us-ascii?Q?uGW+HruwfLWZkqbxq8vtjpDGwN3FMhlaXFHJN52RFVXKLf9gOBnbXo9aKK+a?=
 =?us-ascii?Q?Nwm3MdbIOreKWivTKZvMbeJV+lLD9YcPYGYF1mz4xscd3z3bZ9ZC7wT5wdtN?=
 =?us-ascii?Q?3HNpm9vbzfT4hiZm3wYnxO3SU2dKgYoJs3nZg3TaFZ4i4+zZ8GIDXEPc2Lka?=
 =?us-ascii?Q?kQ4TLES5a66+ogYo8hY7ayVAnKtmph6SCv2aJbubqqS6x7ChXqZBKxwpwgpl?=
 =?us-ascii?Q?8Pf4JMucCC8yHLJ4RHYQLcDjE+2RP/5aP5LLrtTSoJ54PzMGLK5hjF+PGf1z?=
 =?us-ascii?Q?+2X5cwCi3KzBJek31wKVYqpu2347A1OuNkwTAZzP9Cg2sEqU9257+pD1UqgJ?=
 =?us-ascii?Q?oGKX632aZA8ftL8xpq3DP6NPOgzbvJC3pzIBi6G5vkxxDH7+mGcGuJqIIjgC?=
 =?us-ascii?Q?fK+GX7IXCTG28bY8eCTyMcDrDSX7TPJg5AYrEbPdK+/2E44ZP3teKef6UQsc?=
 =?us-ascii?Q?MHOgV+ZOA7auniDe3zbFKQWGy6GzWl9VEgtmrgh2e366D/6pDof+uj+/X0Qr?=
 =?us-ascii?Q?EXXSkD4Cd4duZ0dGrFSh2Z7c1b7w9xma9b1bZoRKUexlOlEkOAGnecXwcCBv?=
 =?us-ascii?Q?FqZvCHd00tIwSoMz9TiwSjd0WJ9BlB4hBL28aeG96QoCWZk6k5utHP3zg+NF?=
 =?us-ascii?Q?rWuOFvL78HubTJ6M86Ummg4aXjtZYJ5rIgqR1nfa0AlJeiv0GY757IPAMZQ3?=
 =?us-ascii?Q?PWO64cRF486KfK8f+FyXdBTctTZA8McbzMZQEQSLWGPn4QLgex9nAxTIKsl5?=
 =?us-ascii?Q?b/CVI1Dw76GTCi3zFrSy7Xn67jLp2/qU8grEFYeefLJ1i4OWZKojRIfdmM4I?=
 =?us-ascii?Q?MncUURxwr9UlraBTfxud0/dzV0/LMkdE12meBC1O6vT5w22TpdEGtOKZ6rP7?=
 =?us-ascii?Q?W0ACRAA/yO9iRFN4gzM301p+fi+Qm6N61h2u8zf6bdZ8fvQM2Kng5DUQDRHU?=
 =?us-ascii?Q?iYt+StMd9wo92n2EfY2J9o7Dbcsn5bwB7RjFJoZia0sIDgYUj1S0VwFXgLf/?=
 =?us-ascii?Q?urES4v1WiKTZ9bwe9qLYO8p676tixMQCUicThuE/?=
Content-Type: text/plain; charset="us-ascii"
Content-Transfer-Encoding: quoted-printable
MIME-Version: 1.0
X-MS-Exchange-CrossTenant-AuthAs: Internal
X-MS-Exchange-CrossTenant-AuthSource: BL1PR11MB5304.namprd11.prod.outlook.com
X-MS-Exchange-CrossTenant-Network-Message-Id: ac2a3eb5-c8e0-4c51-7bc6-08dc69f73799
X-MS-Exchange-CrossTenant-originalarrivaltime: 01 May 2024 15:56:09.0154
 (UTC)
X-MS-Exchange-CrossTenant-fromentityheader: Hosted
X-MS-Exchange-CrossTenant-id: 46c98d88-e344-4ed4-8496-4ed7712e255d
X-MS-Exchange-CrossTenant-mailboxtype: HOSTED
X-MS-Exchange-CrossTenant-userprincipalname: LYtO87srJqh0vsirVaOLILRT3REyDVqi5qyKthlfZWspg8/mvJnDrnSYMSUFCpxyIPgz6mQQw7q4+BBUyRRcMs4HoYDvCN1SDY4iaX7ua4Y=
X-MS-Exchange-Transport-CrossTenantHeadersStamped: IA1PR11MB7680
X-OriginatorOrg: intel.com
List-Id: <pgsql-hackers.lists.postgresql.org>
List-Help: <https://lists.postgresql.org/manage/>
List-Subscribe: <https://lists.postgresql.org/manage/>
List-Post: <mailto:pgsql-hackers@lists.postgresql.org>
List-Owner: <mailto:pgsql-hackers-owner@lists.postgresql.org>
List-Archive: <https://www.postgresql.org/list/pgsql-hackers>
Archived-At: <https://www.postgresql.org/message-id/BL1PR11MB530401FA7E9B1CA432CF9DC3DC192%40BL1PR11MB5304.namprd11.prod.outlook.com>
Precedence: bulk

Hi,

Comparing the current SSE4.2 implementation of the CRC32C algorithm in Post=
gres, 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 i=
s 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 ma=
x 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 algor=
ithm needs a minimum of 256 bytes to operate.

Using the above workload data distribution,=20
at 0%    calls < 256 bytes, a 841% improvement on average for crc32c functi=
onality was observed.
at 50%   calls < 256 bytes, a 758% improvement on average for crc32c functi=
onality was observed.
at 90%   calls < 256 bytes, a 44% improvement on average for crc32c functio=
nality was observed.=20
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 imp=
lementation.=20

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 Rapid=
s (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-2=
xl     |                    |
| (Larger is Better)  +---------+---------+---------+---------+---------+--=
-------+ Overall Multiplier |
|                     | SSE 4.2 | AVX-512 | SSE 4.2 | AVX-512 | SSE 4.2 | A=
VX-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:=20
1) This AVX-512 ISA-L derived code uses BSD-3 license [2]. Is this compatib=
le with the PostgreSQL License [3]? They both appear to be very permissive =
licenses, but I am not an expert on licenses.=20
2) Is there a preferred benchmark I should run to test this change?=20

If licensing is a non-issue, I can post the initial patch along with my Pos=
tgres 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
                     =20
[*] Weights used were 90% of requests less than 256 bytes, 10% greater than=
 or equal to 256 bytes.