Re: some aspects of our qsort might not be ideal - Mailing list pgsql-hackers

From Peter Geoghegan
Subject Re: some aspects of our qsort might not be ideal
Date
Msg-id CAH2-WznjtM12wy+Mx7EhMKTCwtxGKvUz6TabUy8B18P1y2EUMg@mail.gmail.com
Whole thread Raw
In response to Re: some aspects of our qsort might not be ideal  (John Naylor <john.naylor@enterprisedb.com>)
Responses Re: some aspects of our qsort might not be ideal
Re: some aspects of our qsort might not be ideal
List pgsql-hackers
On Thu, Jun 2, 2022 at 8:33 PM John Naylor <john.naylor@enterprisedb.com> wrote:
> Attached is a draft series that implements some but not all features
> of pattern-defeating quicksort, namely the ones I thought were
> interesting for us. Recently this quicksort variant got committed for
> the next release of the Go language 1.19 [1] (which in turn was based
> on that of Rust [2]), and that implementation was a helpful additional
> example. The bottom line is that replacing the partitioning scheme
> this way is likely not worth doing because of our particular use
> cases, but along the way I found some other things that might be worth
> doing, so some good may come out of this.

What about dual-pivot quicksort, which is used in Java 7+? That is the
defacto successor to Bentley & McIlroy. In fact, Jon Bentley himself
collaborated with its author, and provided benchmarking input. The
underlying philosophy is essentially the same as the original -- it
is supposed to be an "industrial strength" quicksort, with various
adversarial cases considered directly.

See:

https://www.wild-inter.net/publications/wild-2018b.pdf

https://codeblab.com/wp-content/uploads/2009/09/DualPivotQuicksort.pdf

At one point quite a few years back I planned on investigating it
myself, but never followed through.

--
Peter Geoghegan



pgsql-hackers by date:

Previous
From: John Naylor
Date:
Subject: Re: some aspects of our qsort might not be ideal
Next
From: Andres Freund
Date:
Subject: Re: pg_upgrade test writes to source directory