Date: Thu, 4 Aug 2022 15:15:51 -0700
From: Nathan Bossart <nathandbossart@gmail.com>
To: John Naylor <john.naylor@enterprisedb.com>
Cc: Andres Freund <andres@anarazel.de>, John Naylor <jcnaylor@gmail.com>,
	pgsql-hackers <pgsql-hackers@postgresql.org>
Subject: Re: optimize lookups in snapshot [sub]xip arrays
Message-ID: <20220804221551.GA1090071@nathanxps13>
References: <20220726181906.7l4ulzjdblnanclm@alap3.anarazel.de>
 <20220728213423.GA408719@nathanxps13>
 <CAFBsxsE14aHKR6gr+rEeFJKaBq8sgXctonwpWw3G7twaePHkVA@mail.gmail.com>
 <20220730053811.GA417958@nathanxps13>
 <20220802221301.GA742739@nathanxps13>
 <20220802225539.nm7bgkwvkpzgib5x@awork3.anarazel.de>
 <20220802234357.GA802740@nathanxps13>
 <20220803180658.3ofq6v34wxchg4wc@awork3.anarazel.de>
 <20220803202540.GA1088968@nathanxps13>
 <CAFBsxsH51bBtyr3rf13x7YMNkFfuzZPSQxxbfUepBj8m4=ck=Q@mail.gmail.com>
MIME-Version: 1.0
Content-Type: text/plain; charset=us-ascii
Content-Disposition: inline
In-Reply-To: 
 <CAFBsxsH51bBtyr3rf13x7YMNkFfuzZPSQxxbfUepBj8m4=ck=Q@mail.gmail.com>
Archived-At: 
 <https://www.postgresql.org/message-id/20220804221551.GA1090071%40nathanxps13>
Precedence: bulk

On Thu, Aug 04, 2022 at 02:58:14PM +0700, John Naylor wrote:
> Were you considering adding the new function to simd.h now that that's
> committed? It's a bit up in the air what should go in there, but this new
> function is low-level and generic enough to be a candidate...

I don't have a strong opinion.  I went with a separate file because I
envisioned a variety of possible linear search functions (e.g., char,
uint16, uint32), and some might not use SIMD instructions.  Futhermore, it
seemed less obvious to look in simd.h for linear search functions.  That
being said, it might make sense to just add it here for now.

> I wonder if the "pg_" prefix is appropriate here, as that is most often
> used for things that hide specific details *and* where the base name would
> clash, like OS calls or C library functions. I'm not quite sure where the
> line is drawn, but I mean that "linearsearch" is a generic algorithm and
> not a specific API we are implementing, if that makes sense.

Yeah, I was concerned about clashing with lsearch() and lfind().  I will
drop the prefix.

> The suffix "_uint32" might be more succinct as "32" (cf pg_bswap32(),
> pg_popcount32, etc). We'll likely want to search bytes sometime, so
> something to keep in mind as far as naming ("_int" vs "_byte"?).

How about something like lsearch32 or linearsearch32?

> I'm not a fan of "its" as a variable name, and I'm curious what it's
> intended to convey.

It's short for "iterations."  I'll spell it out completely to avoid this
kind of confusion.

> All the __m128i vars could technically be declared const, although I think
> it doesn't matter -- it's just a hint to the reader.

Will do.

> Out of curiosity do we know how much we get by loading four registers
> rather than two?

The small program I've been using for testing takes about 40% more time
with the two register approach.  The majority of this test involves
searching for elements that either don't exist in the array or that live
near the end of the array, so this is probably close to the worst case.

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