Date: Mon, 25 Jul 2022 12:04:19 -0700
From: Nathan Bossart <nathandbossart@gmail.com>
To: Andres Freund <andres@anarazel.de>
Cc: John Naylor <jcnaylor@gmail.com>, pgsql-hackers@postgresql.org
Subject: Re: optimize lookups in snapshot [sub]xip arrays
Message-ID: <20220725190419.GA4095199@nathanxps13>
References: <20220713170950.GA3116318@nathanxps13>
 <20220715200857.nm2gc4weixwlwbnx@awork3.anarazel.de>
 <20220717035957.GA3631071@nathanxps13>
MIME-Version: 1.0
Content-Type: text/plain; charset=us-ascii
Content-Disposition: inline
In-Reply-To: <20220717035957.GA3631071@nathanxps13>
Archived-At: 
 <https://www.postgresql.org/message-id/20220725190419.GA4095199%40nathanxps13>
Precedence: bulk

On Sat, Jul 16, 2022 at 08:59:57PM -0700, Nathan Bossart wrote:
> On Fri, Jul 15, 2022 at 01:08:57PM -0700, Andres Freund wrote:
>> I wonder if we additionally / alternatively could use a faster method of
>> searching the array linearly, e.g. using SIMD.
> 
> I looked into using SIMD.  The patch is attached, but it is only intended
> for benchmarking purposes and isn't anywhere close to being worth serious
> review.  There may be a simpler/better way to implement the linear search,
> but this seemed to work well.  Overall, SIMD provided a decent improvement.
> I had to increase the number of writers quite a bit in order to demonstrate
> where the hash tables began winning.  Here are the numbers:
> 
>     writers head simd hash
>     256     663  632  694
>     512     530  618  637
>     768     489  544  573
>     1024    364  508  562
>     2048    185  306  485
>     4096    146  197  441
> 
> While it is unsurprising that the hash tables perform the best, there are a
> couple of advantages to SIMD that might make that approach worth
> considering.  For one, there's really no overhead (i.e., you don't need to
> sort the array or build a hash table), so we can avoid picking an arbitrary
> threshold and just have one code path.  Also, a SIMD implementation for a
> linear search through an array of integers could likely be easily reused
> elsewhere.

From the discussion thus far, it seems there is interest in optimizing
[sub]xip lookups, so I'd like to spend some time moving it forward.  I
think the biggest open question is which approach to take.  Both the SIMD
and hash table approaches seem viable, but I think I prefer the SIMD
approach at the moment (see the last paragraph of quoted text for the
reasons).  What do folks think?

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