Re: optimize lookups in snapshot [sub]xip arrays

On Mon, Aug 08, 2022 at 12:56:28PM +0530, Bharath Rupireddy wrote:
> 1) pg_lfind32 - why just uint32? If it's not possible to define
> functions for char, unsigned char, int16, uint16, int32, int64, uint64
> and so on, can we add a few comments around that? Also, the comments
> can talk about if the base type or element data type of array or data
> type of key matters to use pg_lfind32.

I figured that we'd add functions for other types when needed. I
considered making the new function generic by adding an argument for the
element size. Then, we could branch to optimized routines based on the
element size (e.g., pg_lfind() would call pg_lfind32() if the element size
was 4 bytes). However, that seemed like more complexity than is required,
and it's probably nice to avoid the extra branching.

> 2) I think this is not just for the remaining elements but also for
> non-USE_SSE2 cases. Also, please specify in which cases we reach here
> for USE_SSE2 cases.
> + /* Process the remaining elements the slow way. */

Well, in the non-SSE2 case, all of the elements are remaining at this
point. :)

> 3) Can pg_lfind32 return the index of the key found, for instance to
> use it for setting/resetting the found element in the array?

As discussed upthread, only returning whether the element is present in the
array is slightly faster. If we ever needed a version that returned the
address of the matching element, we could reevaluate whether this small
boost was worth creating a separate function or if we should just modify
pg_lfind32() to be a tad slower. I don't think we need to address that
now, though.

> 4) Can we, right away, use this API to replace linear search, say, in
> SimpleLruReadPage_ReadOnly(), ATExecAttachPartitionIdx(),
> AfterTriggerSetState()? I'm sure I might be missing other places, but
> can we replace the possible found areas with the new function?

I had found a few eligible linear searches earlier [0], but I haven't done
any performance analysis that proved such changes were worthwhile. While
substituting linear searches with pg_lfind32() is probably an improvement
in most cases, I think we ought to demonstrate the benefits for each one.

[0] https://postgr.es/m/20220802221301.GA742739%40nathanxps13

--
Nathan Bossart
Amazon Web Services: https://aws.amazon.com