Thread: Re: branch-free tuplesort partitioning

On Mon, Nov 25, 2024 at 7:14 AM John Naylor <johncnaylorls@gmail.com> wrote:
> To evaluate this technique further, it'll need some work to handle
> duplicates well.

I suggest using a test program for this that Tom wrote nearly 20 years
ago to validate changes that were made to the Bentley & McIlroy qsort,
available from here:

https://www.postgresql.org/message-id/18732.1142967137@sss.pgh.pa.us

It generates most of the standardized inputs described by the B&M
paper. For example, it will generate "Sawtooth" inputs. (Though I
don't see "organ pipe" input -- that one was a more adversarial case,
described by their paper, which might also be interesting.)

--
Peter Geoghegan

On Mon, Nov 25, 2024 at 10:20 PM Peter Geoghegan <pg@bowt.ie> wrote:
>
> I suggest using a test program for this that Tom wrote nearly 20 years
> ago to validate changes that were made to the Bentley & McIlroy qsort,
> available from here:
>
> https://www.postgresql.org/message-id/18732.1142967137@sss.pgh.pa.us
>
> It generates most of the standardized inputs described by the B&M
> paper. For example, it will generate "Sawtooth" inputs. (Though I
> don't see "organ pipe" input -- that one was a more adversarial case,
> described by their paper, which might also be interesting.)

Thanks for that reference, that will be useful!

--
John Naylor
Amazon Web Services