X-Original-To: pgsql-hackers-postgresql.org@localhost.postgresql.org Received: from localhost (av.hub.org [200.46.204.144]) by postgresql.org (Postfix) with ESMTP id B6EFC9DCACD; Thu, 16 Feb 2006 08:11:01 -0400 (AST) Received: from postgresql.org ([200.46.204.71]) by localhost (av.hub.org [200.46.204.144]) (amavisd-new, port 10024) with ESMTP id 73062-03; Thu, 16 Feb 2006 08:11:04 -0400 (AST) X-Greylist: from auto-whitelisted by SQLgrey- X-Greylist: from auto-whitelisted by SQLgrey- Received: from mail.enyo.de (mail.enyo.de [212.9.189.167]) by postgresql.org (Postfix) with ESMTP id 7A5A79DC9F1; Thu, 16 Feb 2006 08:10:59 -0400 (AST) Received: from deneb.vpn.enyo.de ([212.9.189.177] helo=deneb.enyo.de) by mail.enyo.de with esmtp id 1F9hyG-00073L-J4; Thu, 16 Feb 2006 13:10:52 +0100 Received: from fw by deneb.enyo.de with local (Exim 4.60) (envelope-from ) id 1F9hyC-0001SK-Mq; Thu, 16 Feb 2006 13:10:48 +0100 From: Florian Weimer To: Neil Conway Cc: Tom Lane , Gary Doades , pgsql-performance@postgresql.org, pgsql-hackers@postgresql.org Subject: Re: qsort again References: <43F38867.6010701@gpdnet.co.uk> <19510.1140036968@sss.pgh.pa.us> <19779.1140038874@sss.pgh.pa.us> <43F39E53.1020009@gpdnet.co.uk> <20781.1140046109@sss.pgh.pa.us> <1140055972.31672.42.camel@localhost.localdomain> Date: Thu, 16 Feb 2006 13:10:48 +0100 In-Reply-To: <1140055972.31672.42.camel@localhost.localdomain> (Neil Conway's message of "Wed, 15 Feb 2006 21:12:52 -0500") Message-ID: <873bijsdvb.fsf@mid.deneb.enyo.de> MIME-Version: 1.0 Content-Type: text/plain; charset=us-ascii X-Virus-Scanned: by amavisd-new at hub.org X-Spam-Status: No, score=0.101 required=5 tests=[AWL=0.101] X-Spam-Score: 0.101 X-Spam-Level: X-Archive-Number: 200602/614 X-Sequence-Number: 79752 * 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.