From: Nathan Bossart <nathandbossart@gmail.com>
To: John Naylor <john.naylor@enterprisedb.com>
Cc: Andres Freund <andres@anarazel.de>
Cc: John Naylor <jcnaylor@gmail.com>
Cc: pgsql-hackers <pgsql-hackers@postgresql.org>
Subject: Re: optimize lookups in snapshot [sub]xip arrays
Date: Thu, 4 Aug 2022 15:15:51 -0700
Message-ID: <20220804221551.GA1090071@nathanxps13> (raw)
In-Reply-To: <CAFBsxsH51bBtyr3rf13x7YMNkFfuzZPSQxxbfUepBj8m4=ck=Q@mail.gmail.com>
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>
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
Reply instructions:
You may reply publicly to this message via plain-text email
using any one of the following methods:
* Reply to all the recipients using the --to and --cc options:
reply via email
To: pgsql-hackers@postgresql.org
Cc: nathandbossart@gmail.com, john.naylor@enterprisedb.com, andres@anarazel.de, jcnaylor@gmail.com
Subject: Re: optimize lookups in snapshot [sub]xip arrays
In-Reply-To: <20220804221551.GA1090071@nathanxps13>
* Save the following mbox file, import it into your mail client,
and reply-to-all from there: mbox
This inbox is served by DDX for PostgreSQL; see mirroring instructions
for how to clone and mirror all data and code used for this inbox