| From: | Florian Weimer <fw(at)deneb(dot)enyo(dot)de> |
|---|---|
| To: | Neil Conway <neilc(at)samurai(dot)com> |
| Cc: | Tom Lane <tgl(at)sss(dot)pgh(dot)pa(dot)us>, Gary Doades <gpd(at)gpdnet(dot)co(dot)uk>, pgsql-performance(at)postgresql(dot)org, pgsql-hackers(at)postgresql(dot)org |
| Subject: | Re: qsort again |
| Date: | 2006-02-16 12:10:48 |
| Message-ID: | 873bijsdvb.fsf@mid.deneb.enyo.de |
| Views: | Raw Message | Whole Thread | Download mbox | Resend email |
| Thread: | |
| Lists: | pgsql-hackers pgsql-performance |
* Neil Conway:
> On Wed, 2006-02-15 at 18:28 -0500, Tom Lane wrote:
>> It seems clear that our qsort.c is doing a pretty awful job of picking
>> qsort pivots, while glibc is mostly managing not to make that mistake.
>> I haven't looked at the glibc code yet to see what they are doing
>> differently.
>
> glibc qsort is actually merge sort, so I'm not surprised it avoids this
> problem.
qsort also performs twice as many key comparisons as the theoretical
minimum. If key comparison is not very cheap, other schemes (like
heapsort, for example) are more attractive.
| From | Date | Subject | |
|---|---|---|---|
| Next Message | Robert Treat | 2006-02-16 12:17:51 | Re: [HACKERS] Patch Submission Guidelines |
| Previous Message | Steinar H. Gunderson | 2006-02-16 11:35:22 | Re: qsort again (was Re: Strange Create Index |
| From | Date | Subject | |
|---|---|---|---|
| Next Message | Martijn van Oosterhout | 2006-02-16 12:49:18 | Re: qsort again |
| Previous Message | Steinar H. Gunderson | 2006-02-16 11:35:22 | Re: qsort again (was Re: Strange Create Index |