Feedback-ID: i0fe9450f:Fastmail
Date: Wed, 21 Sep 2022 14:40:13 +0900
From: Michael Paquier <michael@paquier.xyz>
To: Nathan Bossart <nathandbossart@gmail.com>
Cc: Richard Guo <guofenglinux@gmail.com>,
	PostgreSQL-development <pgsql-hackers@postgresql.org>
Subject: Re: make additional use of optimized linear search routines
Message-ID: <YyqjvS3HumArAxwq@paquier.xyz>
References: <20220901185153.GA783106@nathanxps13>
 <CAMbWs4-aZr_SiAbKsoOjAN2v5OQ4+eWb7LSXHpHksK_Yr+-t3A@mail.gmail.com>
 <20220902221611.GC1261322@nathanxps13>
 <YxKosqGmCeagEtRi@paquier.xyz>
MIME-Version: 1.0
Content-Type: multipart/signed; micalg=pgp-sha512;
	protocol="application/pgp-signature"; boundary="7Kp+ZadZUM+x/etc"
Content-Disposition: inline
In-Reply-To: <YxKosqGmCeagEtRi@paquier.xyz>
Archived-At: 
 <https://www.postgresql.org/message-id/YyqjvS3HumArAxwq%40paquier.xyz>
Precedence: bulk


--7Kp+ZadZUM+x/etc
Content-Type: text/plain; charset=us-ascii
Content-Disposition: inline
Content-Transfer-Encoding: quoted-printable

On Sat, Sep 03, 2022 at 10:06:58AM +0900, Michael Paquier wrote:
> Ohoh.  This sounds like a good idea to me, close to what John has
> applied lately.  I'll take a closer look..

So, the two code paths patched here are rather isolated.  The one in
TransactionIdIsInProgress() requires an overflowed set of subxids
still running, something similar to what the isolation test
subxid-overflow does.  XidIsConcurrent() is also kind of hard to
reason about with a benchmark.

Anyway, I did not know about the work done with SIMD instructions in
pg_lfind.h and after playing the API I have run some micro benchmarks
with on pg_lfind32() and I can see some improvements.  With a range of
100~10k elements in a fixed number of repeated calls with a for loop
and lfind(), I could not get up to the 40% speedup.  That was somewhat
closer to 15%~20% on x86 and 20%~25% with arm64.  There is a trend=20
where things got better with a higher number of elements with
lfind().

In short, switching those code paths to use the linear search routines
looks like a good thing in the long-term, so I would like to apply
this patch.  If you have any comments or objections, please feel
free.
--
Michael

--7Kp+ZadZUM+x/etc
Content-Type: application/pgp-signature; name="signature.asc"

-----BEGIN PGP SIGNATURE-----

iQIzBAABCgAdFiEEG72nH6vTowiyblFKnvQgOdbyQH0FAmMqo70ACgkQnvQgOdby
QH3IQBAAnCWj9FCLXIvC4pZqos3F+Ip8mXsVxiD/WKbMCfhH8DhvCj5YpZ2phQIo
7Se8TpiN3NPaaVhUXjj13KDg+w52jWC6Lg6F2a5Z2dZR6yKn5f8uON8LilKLzKub
COJXsTE2jJIUzuVhzLR0EJDvdmsJjJWYzxwCJ6EHaCmnECYKLyeRbkJfKgzGj4f9
2Ybvj+OK0G6hubuJ5dws7EG1jedgbk+zjVhAVfJyGt9vxxaBy8p0Nfam+H8E7AHs
CS1qHpdVVbetyAT+cODFyOGdm4vbLfwcNOXwCRgDt1opXzzr7pl0rfVbHwfInhVU
GsaZW85nHjJwRQVYzLgPSUfeEOLYcOQzee8VxwvytfghJyKLGh0uz1lMXSfGCY6D
LxwEMfH1WG95Nf3hmHtWiN2JO6Kjykwsu7KSH9bHeOa+Wf+xMob9LriKK4wk7srw
sHQaxRcXwGWi3AOmCkKWKfsqYqobLbd0qrtBcu/rPk00LJ3OIYgDjenjzvOwECCj
xzJ4L2CtyyrA69Q2lU656S/ExOH4oIRZD1fns1DQ63/J3N/284xfXRGH7Fx5t9PP
NwFIC/0AtBfb3iIEuMCNuUCi/lRtOBlJz4Bb7IS7lXQK/SOCgguNMQAF6qyjorhv
xch80PR5xQbOThAY/iVhI2ChwWlpyMxH6H/7V015aCTKGHxc5nc=
=kX6v
-----END PGP SIGNATURE-----

--7Kp+ZadZUM+x/etc--