| From: | Peter Geoghegan <pg(at)bowt(dot)ie> |
|---|---|
| To: | Thomas Munro <thomas(dot)munro(at)gmail(dot)com> |
| Cc: | Andres Freund <andres(at)anarazel(dot)de>, Justin Pryzby <pryzby(at)telsasoft(dot)com>, John Naylor <john(dot)naylor(at)enterprisedb(dot)com>, pgsql-hackers <pgsql-hackers(at)postgresql(dot)org>, Robert Haas <rhaas(at)postgresql(dot)org>, David Rowley <dgrowleyml(at)gmail(dot)com> |
| Subject: | Re: A qsort template |
| Date: | 2022-04-10 21:54:44 |
| Message-ID: | CAH2-Wz==X6rxnFNBn2yH=xmNdCAvQxFMnDdMoTgn2V5guQEB-A@mail.gmail.com |
| Views: | Raw Message | Whole Thread | Download mbox | Resend email |
| Thread: | |
| Lists: | pgsql-hackers |
On Sun, Apr 10, 2022 at 2:44 PM Thomas Munro <thomas(dot)munro(at)gmail(dot)com> wrote:
> David Rowley privately reported a performance regression when sorting
> single ints with a lot of duplicates, in a case that previously hit
> qsort_ssup() but now hits qsort_tuple_int32() and then has to call the
> tiebreaker comparator.
That's not good.
The B&M quicksort implementation that we adopted is generally
extremely fast for that case, since it uses 3 way partitioning (based
on the Dutch National Flag algorithm). This essentially makes sorting
large groups of duplicates take only linear time (not linearithmic
time).
--
Peter Geoghegan
| From | Date | Subject | |
|---|---|---|---|
| Next Message | Peter Geoghegan | 2022-04-10 22:03:36 | Re: Improving btree performance through specializing by key shape, take 2 |
| Previous Message | Peter Geoghegan | 2022-04-10 21:44:35 | Re: Improving btree performance through specializing by key shape, take 2 |