From: "Amonson, Paul D" <paul.d.amonson@intel.com>
To: Nathan Bossart <nathandbossart@gmail.com>
CC: 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>
Subject: RE: Popcount optimization using AVX512
Thread-Topic: Popcount optimization using AVX512
Thread-Index: AdoNliAXaie8RHrzTICrAiLVKKiYCgAsQKyAALaJTAAAAQ7nAAAAxSWAAAGNHgAAA/mZgAAeFdGAAZKQbBAAAw6egA3NuLcAAAvVM4ACbQuxsAAhlXkAAHPWMbAAAkOrAACYCUjgAAMc3wABvefW4AD8TV6wADf+AoAAmWkVgACOpocAAAl+RwAAJXNxYAAA1VoAAABadxAAZi2hAAAIeekAAMiJepAACPYvAAAbpMKQAJeTLYAAAHbzAA==
Date: Fri, 15 Mar 2024 15:31:17 +0000
Message-ID: <BL1PR11MB530473FB4E9CBD68C28896F7DC282@BL1PR11MB5304.namprd11.prod.outlook.com>
References: <BL1PR11MB5304BFE26BAC25624508CFD2DC232@BL1PR11MB5304.namprd11.prod.outlook.com>
 <20240304222118.GB3367383@nathanxps13>
 <BL1PR11MB53047C28DDBA6A2E77B9420ADC222@BL1PR11MB5304.namprd11.prod.outlook.com>
 <20240305163730.GA3479896@nathanxps13>
 <BL1PR11MB530444AEE08A91242ABA1915DC222@BL1PR11MB5304.namprd11.prod.outlook.com>
 <20240307173318.GA455851@nathanxps13> <20240307213600.GA563369@nathanxps13>
 <BL1PR11MB5304165E7A81E0107E70B069DC242@BL1PR11MB5304.namprd11.prod.outlook.com>
 <20240312013436.GA1787866@nathanxps13>
 <BL1PR11MB53042473B7B53B96E43648A7DC292@BL1PR11MB5304.namprd11.prod.outlook.com>
 <20240315150611.GA3495582@nathanxps13>
In-Reply-To: <20240315150611.GA3495582@nathanxps13>
Accept-Language: en-US
Content-Language: en-US
x-ms-exchange-antispam-messagedata-chunkcount: 1
x-ms-exchange-antispam-messagedata-0: =?us-ascii?Q?4BYjaSGEtZjLE4Nl/k6w99DAXkgLefxrqqt6EMkIfWhIoFJH/mMYFoHoPu5U?=
 =?us-ascii?Q?bfIDXMbylKHxTlTmcsZiWZPEgxG4Y4isukzX4PIuR+jhRXyWdhjUN1bitZGk?=
 =?us-ascii?Q?XJ2C6PuP1gtLdJHD+Y7CIZydguIuh9u/W/5QQRiIKhhYzVFApHOTR9BDx2/0?=
 =?us-ascii?Q?pkbtqFLKPGD4uCKxfuxxNjRgB4O0EIzKM4hP0Lc5xfPEzVRfk0s/NIcqCx6I?=
 =?us-ascii?Q?k76hJ3Tu2/ClpcXqijhEsyffr1J7iNjs/kwyGmcO3GKnfjmEIAkjX0EX3I6M?=
 =?us-ascii?Q?nPFcvD2qx/TfokeM0pvIBq4u3k9W4EweDRheez/pspjF+fYmTho7ogaM+vLC?=
 =?us-ascii?Q?gYQm7aSxPcuXV9ReoGXke5oSHoST87yVEP4bsEEQk1AhTUDLSeT5k22sqLWe?=
 =?us-ascii?Q?0qbwyF1+y5Z41LFgUErUOcK+wP6PeiTUMEYBvq0e9pfIGzUtDQ7ue/D32DYF?=
 =?us-ascii?Q?bqqGXVXSdyk9jpoOFoWpFbTnHvABb2JbcnMTrCapTs13RCfCAnp9PK1WjzH+?=
 =?us-ascii?Q?HUl64Trs+FSySKkupjjINJ/jErZ8tFGRgoQ7KSCbReSrriGNHICVifgJnYYp?=
 =?us-ascii?Q?chg+oumgggsnKRaV1J/Se6Zx0R4EKcd8prUy2YoF4tPF9+U8qw/niqtlZ+XI?=
 =?us-ascii?Q?VZiDQrwAhii97YqYGskh5wYkB/SK3OdDPUKQvD6ATGAaClgc++vdLTlG51iq?=
 =?us-ascii?Q?O0zu0XK+DZWdbY44Z40Z74uDMyFlaBcH0YdOfemf6uSXJUxJw7sRoDwAPQCM?=
 =?us-ascii?Q?Th0gQ+SbK/R/MlUn6iGZwFV6Qepsb/+FA9JgvKBkV63/iRLLGNbr55Ldr5zM?=
 =?us-ascii?Q?hk0CWZTgE62vLai08mKCQYwGFJcBBdzuRn/BaO9rEp+acXRF6/jDKh0NufgU?=
 =?us-ascii?Q?Un1XH9thRQ/9BPTXOvbJaBm3v0bPcgDqkEfuD0DytsyWJfIn4Mf0LUry6Mku?=
 =?us-ascii?Q?4lABCaO6K708QdFWdEO5mRewHOqgZfuEJIUkqHihhFbkY1YH9ic6V4A8Q8rC?=
 =?us-ascii?Q?4n1iOSX+QZUYdcJBA+KzJTNyY4MPFzwnpN/QG04RVpyhIVwmA4cLEJfRbMms?=
 =?us-ascii?Q?cc7oHIbKdvYYm0hrDRjh3w4UNp9EGU+35YlK3oLy1De9nn/2+QL8liys5IwI?=
 =?us-ascii?Q?tJ6+DwanRRGpwnFfPJrJfPNZdP600ADg8DEfYXjUogXcW4gtDmI6PXfU5rlq?=
 =?us-ascii?Q?GwVXuUbWKU0Xd4L8vNhGtSiD+VPTIxQnWxrpXKiZo4OVzk/vuvExv5VkSSOp?=
 =?us-ascii?Q?/qTcfJA79aRfzMEPG7VXFcSID1wP+B+Az45W84olBKktTECoXN9g4JKUeEsC?=
 =?us-ascii?Q?EwIDrIawrNLkOhkIC8yOVlGIg7SAntagJhwFBtkTvMIMxzE0F0uQbRhUp2bs?=
 =?us-ascii?Q?EP4w6RlGWn3+7X7sJc69kItL1DP1wnKEDtzeQI78C/QPSVesWBHzFNONp3sC?=
 =?us-ascii?Q?dKfY0IN4Uqzh36FHxAORqX2285otxPVuY5l4BOTXGQ6re3U/UZWFwYpm69jx?=
 =?us-ascii?Q?cpGaE1+/vYQ69Bzc4HDjQvY8u1v7slKAIwdgpm4fmRP1OR4o1QUnX3t+q6vt?=
 =?us-ascii?Q?egsd26Wg6xJ3qyjk++lju7jYOB2s5SBxsq6if8gu?=
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: 6201bc07-bb7e-46c0-481a-08dc4504f52a
X-MS-Exchange-CrossTenant-originalarrivaltime: 15 Mar 2024 15:31:17.4905
 (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: a7OBJFMoGD5jyoLK9fQL4TI/74/3BEz2D0k4Ota7oap0k5iM2W0+bXi4+xN0WBeV2fibr+Tg9A72S8UTk7pPlue1RNbjSlQKJ4FxWKbvFcA=
X-MS-Exchange-Transport-CrossTenantHeadersStamped: IA1PR11MB6265
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/BL1PR11MB530473FB4E9CBD68C28896F7DC282%40BL1PR11MB5304.namprd11.prod.outlook.com>
Precedence: bulk

> -----Original Message-----
> From: Nathan Bossart <nathandbossart@gmail.com>
> Sent: Friday, March 15, 2024 8:06 AM
> To: Amonson, Paul D <paul.d.amonson@intel.com>
> Cc: 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
> Subject: Re: Popcount optimization using AVX512
>=20
> Which test suite did you run?  Those numbers seem potentially
> indistinguishable from noise, which probably isn't great for such a large=
 patch
> set.

I ran...
	psql -c "select bitcount(column) from table;"
...in a loop with "column" widths of 84, 4096, 8192, and 16384 containing r=
andom data. There DB has 1 million rows.  In the loop before calling the se=
lect I have code to clear all system caches. If I omit the code to clear sy=
stem caches the margin of error remains the same but the improvement percen=
t changes from 1.2% to 14.6% (much less I/O when cached data is available).

> I ran John Naylor's test_popcount module [0] with the following command o=
n
> an i7-1195G7:
>=20
> 	time psql postgres -c 'select drive_popcount(10000000, 1024)'
>=20
> 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 t=
ests a
> couple of times because I had a difficult time believing the amount of
> improvement.)

When I tested the code outside postgres in a micro benchmark I got 200-300%=
 improvements. Your results are interesting, as it implies more than 300% i=
mprovement. Let me do some research on the benchmark you referenced. Howeve=
r, in all cases it seems that there is no regression so should we move forw=
ard on merging while I run some more local tests?

Thanks,
Paul