Multithreaded qsort(3)

[Gergely CZUCZY]

On Thu, Mar 15, 2007 at 06:27:32PM +0100, Max Laier wrote:
> On Thursday 15 March 2007 09:42, Diomidis Spinellis wrote:
> > Greetings,
> >
> > I've added multhread support to our qsort implementation.  You can see
> > the code at <http://people.freebsd.org/~dds/qsort_mt.c> and some
> > performance figures at the end of this email.  I propose to add it to
> > our libc.  I need your opinions on the interface, and also any comments
> > you may have on the code.  I see the following design dimensions:
> >
> > 1. Naming and availability
> > --------------------------
> > - Option 1.1: Replace qsort with this implementation
> > * Pros: Programs gain performance without any source code change;
> > abstraction (number of processors/cores should be invisible, just as
> > the CPU architecture or disk drive interface)
> > * Cons: May confuse multithreaded programs; programs require linking
> > with pthreads library; programs whose compare function is not thread
> > safe will break
> >
> > - Option 1.2: Name it qsort_mt
> > * Pros: POLA; programs can tune the call according to their need
> > * Cons: Programs require source code changes; we violate abstraction;
> > namespace polution
> >
> > My proposal: option 1.2: name it qsort_mt and make it available in a
> > separate library (libc_mt).
> 
> I'd suggest to name it qsort() and put it in a separate library (not 
> necessarily named libc_mt, as I don't believe there are that many 
> functions in libc, that can actually gain from multithreading).
> 
> This approach, would allow LD_PRELOAD'ing the _mt version without the need 
> to recompile.
> 
> That said, I'm not sure this really belongs in the base system.  As 
> qsort_mt it's way too obscure and unportable for any real application to 
> use it.  As a replacement for qsort it won't work (as you pointed out 
> yourself).  I do think that we need efforts like this, but they should be 
> made outside of FreeBSD, otherwise they won't be much useful in general.
I'm just a FreeBSD user, and developing some applications under it. I'd
like to share my point of view, a point of view of an application developer,
of this placing.

I see two useful ways placing such a function into the OS. One is naming it
qsort() and putting it into a library that even can be libmaped or preloaded
into some applications, thus gaining some performance on some applications
that were not designed to be work in a multithreaded way (and gain performance
on the several CPUs).

The other one is putting it into a different library, that a program can be
linked against along with libc, and the old qsort and this new one can be
mixed as the developers would like it to. By this way, it would be very
useful to have the ability to assign control functions to the multihreaded
qsort, like telling it what threads to use, how to lunch/reuse threads, how
many, and so on.

To be honest, i find both ways quite useful. I think maybe the best way
would be to do both at the same time.

Bye,

Gergely Czuczy
mailto: gergely.czuczy at harmless.hu

-- 
Weenies test. Geniuses solve problems that arise.
-------------- next part --------------
A non-text attachment was scrubbed...
Name: not available
Type: application/pgp-signature
Size: 2482 bytes
Desc: not available
Url : http://lists.freebsd.org/pipermail/freebsd-threads/attachments/20070315/2de83e2d/attachment.pgp