From owner-freebsd-arch@FreeBSD.ORG Thu Mar 15 18:21:37 2007 Return-Path: X-Original-To: freebsd-arch@freebsd.org Delivered-To: freebsd-arch@freebsd.org Received: from mx1.freebsd.org (mx1.freebsd.org [69.147.83.52]) by hub.freebsd.org (Postfix) with ESMTP id 2A55C16A402; Thu, 15 Mar 2007 18:21:37 +0000 (UTC) (envelope-from gergely.czuczy@harmless.hu) Received: from marvin.harmless.hu (marvin.harmless.hu [195.56.55.204]) by mx1.freebsd.org (Postfix) with ESMTP id 8E9A413C4B9; Thu, 15 Mar 2007 18:21:36 +0000 (UTC) (envelope-from gergely.czuczy@harmless.hu) Received: from localhost (marvin-mail [192.168.0.2]) by marvin.harmless.hu (Postfix) with ESMTP id 70D117BFF20; Thu, 15 Mar 2007 18:49:48 +0100 (CET) X-Virus-Scanned: by amavisd-new-2.4.2 (20060627) (Debian) at harmless.hu Received: from marvin.harmless.hu ([192.168.0.2]) by localhost (marvin.harmless.hu [192.168.0.2]) (amavisd-new, port 10024) with ESMTP id 9WLi6L+l4vwJ; Thu, 15 Mar 2007 18:49:48 +0100 (CET) Received: from marvin.harmless.hu (localhost [127.0.0.1]) by marvin.harmless.hu (Postfix) with ESMTP id DB5A47BFD14; Thu, 15 Mar 2007 18:49:47 +0100 (CET) Date: Thu, 15 Mar 2007 18:49:47 +0100 From: Gergely CZUCZY To: Max Laier Message-ID: <20070315174947.GA4674@harmless.hu> References: <45F906ED.8070100@aueb.gr> <200703151827.39963.max@love2party.net> MIME-Version: 1.0 Content-Type: multipart/signed; micalg=x-unknown; protocol="application/pgp-signature"; boundary="h31gzZEtNLTqOjlF" Content-Disposition: inline In-Reply-To: <200703151827.39963.max@love2party.net> User-Agent: mutt-ng/devel-r804 (FreeBSD) Cc: freebsd-threads@freebsd.org, freebsd-arch@freebsd.org Subject: Re: Multithreaded qsort(3) X-BeenThere: freebsd-arch@freebsd.org X-Mailman-Version: 2.1.5 Precedence: list List-Id: Discussion related to FreeBSD architecture List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , X-List-Received-Date: Thu, 15 Mar 2007 18:21:37 -0000 --h31gzZEtNLTqOjlF Content-Type: text/plain; charset=utf-8 Content-Disposition: inline Content-Transfer-Encoding: quoted-printable 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 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). >=20 > I'd suggest to name it qsort() and put it in a separate library (not=20 > necessarily named libc_mt, as I don't believe there are that many=20 > functions in libc, that can actually gain from multithreading). >=20 > This approach, would allow LD_PRELOAD'ing the _mt version without the nee= d=20 > to recompile. >=20 > That said, I'm not sure this really belongs in the base system. As=20 > qsort_mt it's way too obscure and unportable for any real application to= =20 > use it. As a replacement for qsort it won't work (as you pointed out=20 > yourself). I do think that we need efforts like this, but they should be= =20 > 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 performa= nce 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@harmless.hu --=20 Weenies test. Geniuses solve problems that arise. --h31gzZEtNLTqOjlF Content-Type: application/pgp-signature Content-Disposition: inline -----BEGIN PGP SIGNATURE----- Version: GnuPG v1.4.5 (FreeBSD) owF1Vz1sHEUUNoloVlCYinIkCtvJ3fl8cexwxobEDlGEE1uJEUIUYXZ39m7i3Zn1 zOydNxIICQkoKBANSBQgqJEogJKehoKGlhaElIKKju/N7J3vYnBh383u+/u+7703 /uTZiwsXFn/57vu3Ln/86RdPffvMr/GlonJODdoFNyOp2mvd7lp7fWNzvb3R7vXW 1wXnm+tJ91p3fe3azX8+3NrVygnl2kd1KfrMiVO3WuZcqi2WDLmxwm1XLmtfiybv 7Ulbaiud1KrPpMqlEtNnR4YrmwnTvqkSnUo16LOTSjuRtksjleNxLqLoQLGjYdVi d7hha1dbrNftbjLuWHej39vsX+kd3mGXu8ia3jhl+1wKw8YGXvrRDgvGxqa8hjH5 SIbBQ/fF/nqvxfakLmQqLbtfIrM8x6ep8Q67ZYRwyMu26Ks/ur00EoynqUhZUeVu aARPma3KUhvHnGa6MuzE0hdZlLkoUCen4juMvakrlnDFrBDelRsKhroFVfPS0Lmy v7paCg2rTobAsU072gxW301Tu+pdPihcJ9lhXCGiLoKTUphMm4KrRLBMDiojLPkj 3wLv6QwfUZQouMyRw21WGg1CBOWKMpikrL0nyjyXceLfUgIF1nSkAQzyt0wr7xXE ICRPRMsnwnMLR6pGJQUVa70vWLICmA850GoMqVTvG/X7g0znuR4DXpYKKweKpRIe LAXrT/Fe67C7vKCXfLQRyuCxzKWr/eP2//6Ex+ygJPThZq3P7glIFTgFfsbSDQM4 80x5w0vs0Gjbp98DwwvLBtD4HNhkrivna7cAKmnIRBuogdjyXnhsneGJz2BZVUUM bYIRUJAIiyTsaqKJMAtPecpiQnckrYTwW+xhZeHdTqWye/g6I/1KJxIHnpk2QMwe s9TI0QwvK00Bu4QjJE/UqKwC5SRYGSQLdsumtK3pJ2bESSXhGV16DMi9Iw9TGaws CcRwU8/YjIekJrBfclhmlQrlAlalSYdk5x1ZnhFqec5inB1PGZ7hqNcnsgWJciL4 eTYO9q/PhKZmcpUKako4PPMEgNIkIXnjVBqv5DlEDp+s9jx7wGQs2EjqnDsxy2Kg VSFHW5KSSp1XE834R3fqpsF43kfrnNWlnqjLy7ngx/6wkXVOLDIe0BLAk6I3iLNl 6k0YrnSine1eN6JRRJNngHT95JmLsLziA5QQKI7I6394BEHBkxKkR25kXns3KWuC occtOjbVaslBnrkUI482UCO23RCjBu1QBzcT8i0FJA+t8AbxBPwqMFSHRsqMLmbl CMbO6jqinuQlcOTJsMXGvjc4zQq2v/fg8N7N/YPre0ueZPBOWI6EobEx7Uk6B+/b URo8Ah0jSKISs/UsDFKzXKYtIFl4tdrKFyVJGz5ZlKwx/qke8hlzSN3W1okCk+y6 DY6mlEq3hH5AwzmNRRDbhNwRDZWi9eAJxvzwI4MCUJG5TPzUgc12FPxRq0rnA4A2 E4YWjSdv3CwXzC9PylibY7YMlmjklpqmAKZ+1RBLE9yKPFvxgzelnkBrB1bGIkx5 kcGto9Y+DsW3WBwwrM8G0yS3AqOD3FtJfzP2KhbVjft7LaZJFWNpRTAcN4oBydi4 qCirckJxIJQwPO9EBHmYcBMf9JYJSyWFzHJaPAO/6GZxsgAzxRglgNAAUchaI1MS ZFEHDCi1kRRjuJs/oL+kxhngm2CIHU22JSGO4J0oarbVWE9qAL3T59ALiuMzQ0+F scMO7ndw9xB+CobtJV30RGO6cByM+LQrPTdISfm2iX27FrwkVg1mC1Kl6R15q3Pg UMNVYVlNwZtdWsjxnE3UqAHwUQ+EXYxw8I/oXl9+fsxvD5L5MlUytxi3I0SJmoVv UQW4psVl0d3REc68TJCGh+Y8CKnMcB8kqTdwNBOET4Z+A0pEGwpZcIpOIqI2Dasq zB3KjHLQUG/omHBChJAKlJh4KuQpObL+9akWbDN2vLz8HanDbtTBAUpvhQZsljbK rKNGHyjDX3rIW3NR8Vct62842MTO6HxmUjaC8eA22AahtJqGpEtpwGg85JOF6u0Q scWGmIr4nMPhcNWIyjegf8U/i2g6t5orI8omGjyvQ0BgEUTi1oiHMYgJ2sZOxI4I 1aDFmomBy1wciopp3eDNaFo+wmOyeA/NzdPSKnK4zSHcjVq0ouiWMAOBgbr7qEoe 1RHdRp3uYxz4407ij19BDxc5NlFnWEVRu00j5w0hlMQVySFsh93CF6SGG5POATJE gZla2EYkBuOnE3308sWnF+hflcm/OYsXHn298NVnOx/c/funhz/+cPWFK+/vvP3e 4vOf/77w5Wt/Re/8+dv65Y3dk+ce//x48Y/TC9/8Cw== =nogL -----END PGP SIGNATURE----- --h31gzZEtNLTqOjlF--