From: Nathan Bossart <nathandbossart@gmail.com>
To: Andres Freund <andres@anarazel.de>
Cc: John Naylor <jcnaylor@gmail.com>
Cc: pgsql-hackers@postgresql.org
Subject: Re: optimize lookups in snapshot [sub]xip arrays
Date: Mon, 25 Jul 2022 12:04:19 -0700
Message-ID: <20220725190419.GA4095199@nathanxps13> (raw)
In-Reply-To: <20220717035957.GA3631071@nathanxps13>
References: <20220713170950.GA3116318@nathanxps13>
<20220715200857.nm2gc4weixwlwbnx@awork3.anarazel.de>
<20220717035957.GA3631071@nathanxps13>
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
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, andres@anarazel.de, jcnaylor@gmail.com
Subject: Re: optimize lookups in snapshot [sub]xip arrays
In-Reply-To: <20220725190419.GA4095199@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