| From: | John Naylor <john(dot)naylor(at)enterprisedb(dot)com> |
|---|---|
| To: | Peter Geoghegan <pg(at)bowt(dot)ie> |
| Cc: | pgsql-hackers <pgsql-hackers(at)postgresql(dot)org> |
| Subject: | Re: some aspects of our qsort might not be ideal |
| Date: | 2022-06-03 04:24:20 |
| Message-ID: | CAFBsxsHAU-1S7Ltx0XjvXOys4WhYUbh0NOfqH95ZGe2o+wJwSQ@mail.gmail.com |
| Views: | Raw Message | Whole Thread | Download mbox | Resend email |
| Thread: | |
| Lists: | pgsql-hackers |
On Fri, Jun 3, 2022 at 10:44 AM Peter Geoghegan <pg(at)bowt(dot)ie> wrote:
>
> 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.
I had heard of it but not looked into it deeply. I did read that Java
7 uses dual pivot quicksort for primitives and timsort for objects. I
wasn't sure if dual pivot was not good for objects (which could have
possibly-complex comparators) or if timsort was just simply good for
Java's use cases. It seems accessible to try doing, so I'll look into
that.
--
John Naylor
EDB: http://www.enterprisedb.com
| From | Date | Subject | |
|---|---|---|---|
| Next Message | Peter Geoghegan | 2022-06-03 04:35:34 | Re: some aspects of our qsort might not be ideal |
| Previous Message | John Naylor | 2022-06-03 04:02:51 | Re: PG15 beta1 sort performance regression due to Generation context change |