From: | Peter Geoghegan <pg(at)bowt(dot)ie> |
---|---|
To: | John Naylor <john(dot)naylor(at)enterprisedb(dot)com> |
Cc: | pgsql-hackers <pgsql-hackers(at)postgresql(dot)org> |
Subject: | Re: some aspects of our qsort might not be ideal |
Date: | 2022-06-03 03:44:21 |
Message-ID: | CAH2-WznjtM12wy+Mx7EhMKTCwtxGKvUz6TabUy8B18P1y2EUMg@mail.gmail.com |
Views: | Raw Message | Whole Thread | Download mbox | Resend email |
Thread: | |
Lists: | pgsql-hackers |
On Thu, Jun 2, 2022 at 8:33 PM John Naylor <john(dot)naylor(at)enterprisedb(dot)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
From | Date | Subject | |
---|---|---|---|
Next Message | Andres Freund | 2022-06-03 03:50:12 | Re: pg_upgrade test writes to source directory |
Previous Message | John Naylor | 2022-06-03 03:33:16 | Re: some aspects of our qsort might not be ideal |