Re: qsort (was Re: Solaris)

In article <19660(dot)1051676560(at)sss(dot)pgh(dot)pa(dot)us>,
Tom Lane <tgl(at)sss(dot)pgh(dot)pa(dot)us> wrote:
>dalgoda(at)ix(dot)netcom(dot)com (Mike Castle) writes:
>> What about --with-pg-qsort (that defaults to use for currently known
>> systems) with a test program people could run if they want?
>
>I'd lean to "--with-pg-qsort" forcing the BSD qsort, "--without-pg-qsort"
>forcing the native qsort, and if you don't say either then you get a
>choice based on which OS you are running. (Not sure how hard this is
>to do in the autoconf structure, but if we can do it, it seems like the
>right user interface.)

It's fairly easy, actually.

Something like:

AC_ARG_WITH([pg-qsort],
AC_HELP_STRING([--with-pg-qsort],
[use internal qsort (default is system
dependent)]),
case $withval
yes) force internal;;
no) force system;;
*) tell user to don't do that (--with-pg-qsort=blah);;
esac,
case OS
*Solaris*) force internal;;
*) force system;;
esac
)

>> In that case, would counting the calls to the compare function be the
>> appropriate measurement (I'd think either wall or system time would vary
>> too widely).
>
>I'd trust overall time measurements way more than call counts.
>Obviously it's up to the user to hold overall system load and suchlike
>outside factors constant while conducting the tests --- but measuring
>any single component like comparison-function calls is just asking to be
>misled.

I'm not certain.

I ran the tests posted to this lists with a few mods and got some very
interesting results.

First I added a counter to the compare function, and the most cases, the
glibc implementation was called significantly less often than the BSD
compare function.

In a simple test function, like comparing two ints, then yes, the BSD
implementation was faster. But in a more complex function, say comparing
strings, often times the glibc version was faster. Why? Because the
time spent in the compare function became the overwhelming factor.

So, I ask you this: in places where qsort is used in PG, is it more likely
to be used for simple comparisons or for complex comparisons that involve a
mixture of strings and ints? And, is it more likely to be called with
datasets that are partially sorted or not?

BSD prevailed on trivial comparisons and on sets that had any type of
sorting to them. Glibc prevailed on random order with heavier comparisons.

mrc
--
Mike Castle dalgoda(at)ix(dot)netcom(dot)com www.netcom.com/~dalgoda/
We are all of us living in the shadow of Manhattan. -- Watchmen
fatal ("You are in a maze of twisty compiler features, all different"); -- gcc