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 E987C9DC9B8; Thu, 16 Feb 2006 15:13:14 -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 59288-10; Thu, 16 Feb 2006 15:13:14 -0400 (AST) X-Greylist: from auto-whitelisted by SQLgrey- X-Greylist: from auto-whitelisted by SQLgrey- Received: from mailbox.samurai.com (mailbox.samurai.com [205.207.28.82]) by postgresql.org (Postfix) with ESMTP id 380F29DC83D; Thu, 16 Feb 2006 15:13:11 -0400 (AST) Received: from localhost (mailbox.samurai.com [205.207.28.82]) by mailbox.samurai.com (Postfix) with ESMTP id D062E239461; Thu, 16 Feb 2006 14:13:12 -0500 (EST) Received: from mailbox.samurai.com ([205.207.28.82]) by localhost (mailbox.samurai.com [205.207.28.82]) (amavisd-new, port 10024) with LMTP id 71135-02-7; Thu, 16 Feb 2006 14:13:10 -0500 (EST) Received: from [192.168.1.102] (d226-82-205.home.cgocable.net [24.226.82.205]) by mailbox.samurai.com (Postfix) with ESMTP id 41A2B239456; Thu, 16 Feb 2006 14:13:10 -0500 (EST) Subject: Re: qsort again (was Re: [PERFORM] Strange Create Index From: Neil Conway To: "Steinar H. Gunderson" Cc: pgsql-performance@postgresql.org, PostgreSQL-development In-Reply-To: <20060216113522.GA3461@uio.no> 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> <7.0.1.0.2.20060215194635.03b55da0@earthlink.net> <21615.1140052893@sss.pgh.pa.us> <7.0.1.0.2.20060215223710.03a7c618@earthlink.net> <20060216113522.GA3461@uio.no> Content-Type: text/plain Date: Thu, 16 Feb 2006 14:14:03 -0500 Message-Id: <1140117243.31672.54.camel@localhost.localdomain> Mime-Version: 1.0 X-Mailer: Evolution 2.4.1 Content-Transfer-Encoding: 7bit X-Virus-Scanned: by amavisd-new at mailbox.samurai.com X-Virus-Scanned: by amavisd-new at hub.org X-Spam-Status: No, score=0.067 required=5 tests=[AWL=0.067] X-Spam-Score: 0.067 X-Spam-Level: X-Archive-Number: 200602/636 X-Sequence-Number: 79774 On Thu, 2006-02-16 at 12:35 +0100, Steinar H. Gunderson wrote: > glibc-2.3.5/stdlib/qsort.c: > > /* Order size using quicksort. This implementation incorporates > four optimizations discussed in Sedgewick: > > I can't see any references to merge sort in there at all. stdlib/qsort.c defines _quicksort(), not qsort(), which is defined by msort.c. On looking closer, it seems glibc actually tries to determine the physical memory in the machine -- if it is sorting a single array that exceeds 1/4 of the machine's physical memory, it uses quick sort, otherwise it uses merge sort. -Neil