Re: optimize lookups in snapshot [sub]xip arrays

From: Nathan Bossart <nathandbossart(at)gmail(dot)com>
To: John Naylor <john(dot)naylor(at)enterprisedb(dot)com>
Cc: Andres Freund <andres(at)anarazel(dot)de>, John Naylor <jcnaylor(at)gmail(dot)com>, pgsql-hackers <pgsql-hackers(at)postgresql(dot)org>
Subject: Re: optimize lookups in snapshot [sub]xip arrays
Date: 2022-08-05 20:25:10
Message-ID: 20220805202510.GA1208450@nathanxps13
Views: Raw Message | Whole Thread | Download mbox | Resend email
Lists: pgsql-hackers

On Fri, Aug 05, 2022 at 11:02:15AM +0700, John Naylor wrote:
> That is a good point. Maybe potential helpers in simd.h should only deal
> specifically with vector registers, with it's users providing C fallbacks.
> I don't have any good ideas of where to put the new function, though.

I moved it to src/include/port for now since that's where files like
pg_bswap.h live.

> Hmm, I didn't know about those. lfind() is similar enough that it would
> make sense to have pg_lfind32() etc in src/include/port/pg_lsearch.h, at
> least for the v4 version that returns the pointer. We already declare
> bsearch_arg() in src/include/port.h and that's another kind of array
> search. Returning bool is different enough to have a different name.
> pg_lfind32_ispresent()? *_noptr()? Meh.
> Having said all that, the man page under BUGS [1] says "The naming is
> unfortunate."

I went ahead and renamed it to pg_lfind32() and switched it back to
returning the pointer. That felt the cleanest from the naming perspective,
but as Andres noted, it might not be as fast as just looking for the
presence of the element. I modified my small testing program to perform
many searches on small arrays, and I wasn't able to identify any impact, so
perhaps thіs is good enough.


Nathan Bossart
Amazon Web Services:

Attachment Content-Type Size
v7-0001-Introduce-optimized-routine-for-linear-searches-t.patch text/x-diff 3.1 KB
v7-0002-Optimize-linear-searches-in-XidInMVCCSnapshot.patch text/x-diff 2.8 KB

In response to


Browse pgsql-hackers by date

  From Date Subject
Next Message Alvaro Herrera 2022-08-05 20:29:40 Re: standby recovery fails (tablespace related) (tentative patch and discussion)
Previous Message Peter Geoghegan 2022-08-05 20:10:47 Re: BTMaxItemSize seems to be subtly incorrect