From: | Tom Lane <tgl(at)sss(dot)pgh(dot)pa(dot)us> |
---|---|
To: | Marko Kreen <markokr(at)gmail(dot)com> |
Cc: | Bruce Momjian <pgman(at)candle(dot)pha(dot)pa(dot)us>, Qingqing Zhou <zhouqq(at)cs(dot)toronto(dot)edu>, pgsql-hackers(at)postgresql(dot)org |
Subject: | Re: Which qsort is used |
Date: | 2005-12-13 15:29:50 |
Message-ID: | 6495.1134487790@sss.pgh.pa.us |
Views: | Raw Message | Whole Thread | Download mbox | Resend email |
Thread: | |
Lists: | pgsql-hackers |
Marko Kreen <markokr(at)gmail(dot)com> writes:
> http://sourceware.org/ml/libc-alpha/2000-03/msg00139.html
> Seems glibc guys once tested some implementation of quicksort vs. merge sort
> and found out that
> "For small sets and smaller data types (arrays of ints and
> arrays of doubles) mergesort is definitly faster and behaves better."
> If the qsort in Postgres is called usually on wide data - on full rows
> not on pointers to rows, then indeed it would be wise to use out own
> sort.
But I can assure you that it is never called on any such thing. Since
qsort only works on fixed-size items, it'd be essentially impossible
to use it directly on rows; we *always* use it on pointers instead.
(We could only do the other if we had a separate code path for rows
containing only fixed-width-never-null columns, which we do not, and
it'd be pretty silly to add one in view of the increased data-copying
work that would result.)
The referenced message is pretty interesting for this discussion,
particularly its pointer to someone's sort test routines --- wonder
if those are still available? It was also eye-opening to read that
glibc actually contains two separate algorithms to use depending on
the size of the target array. If that's still true then it throws a
lot of the testing so far into doubt.
regards, tom lane
From | Date | Subject | |
---|---|---|---|
Next Message | Tom Lane | 2005-12-13 15:35:47 | Re: Deadlock with ShareLocks? |
Previous Message | Tom Lane | 2005-12-13 15:21:54 | Re: Anyone for adding -fwrapv to our standard CFLAGS? |