X-Original-To: pgsql-performance-postgresql.org@localhost.postgresql.org Received: from localhost (av.hub.org [200.46.204.144]) by postgresql.org (Postfix) with ESMTP id BD2CF9DC813 for ; Thu, 16 Feb 2006 07:35:20 -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 63485-10 for ; Thu, 16 Feb 2006 07:35:22 -0400 (AST) X-Greylist: from auto-whitelisted by SQLgrey- Received: from cassarossa.samfundet.no (cassarossa.samfundet.no [129.241.93.19]) by postgresql.org (Postfix) with ESMTP id BAA4D9DC80D for ; Thu, 16 Feb 2006 07:35:17 -0400 (AST) Received: from trofast.ipv6.sesse.net ([2001:700:300:dc03:20e:cff:fe36:a766] helo=trofast.sesse.net) by cassarossa.samfundet.no with esmtp (Exim 4.50) id 1F9hPq-00047b-ON for pgsql-performance@postgresql.org; Thu, 16 Feb 2006 12:35:19 +0100 Received: from sesse by trofast.sesse.net with local (Exim 3.36 #1 (Debian)) id 1F9hPu-0000vG-00 for ; Thu, 16 Feb 2006 12:35:22 +0100 Date: Thu, 16 Feb 2006 12:35:22 +0100 From: "Steinar H. Gunderson" To: pgsql-performance@postgresql.org Subject: Re: qsort again (was Re: Strange Create Index Message-ID: <20060216113522.GA3461@uio.no> Mail-Followup-To: pgsql-performance@postgresql.org 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> MIME-Version: 1.0 Content-Type: text/plain; charset=utf-8 Content-Disposition: inline In-Reply-To: <7.0.1.0.2.20060215223710.03a7c618@earthlink.net> X-Operating-System: Linux 2.6.14.3 on a x86_64 X-Message-Flag: Outlook? --> http://www.mozilla.org/products/thunderbird/ User-Agent: Mutt/1.5.11+cvs20060126 X-Virus-Scanned: by amavisd-new at hub.org X-Spam-Status: No, score=0.078 required=5 tests=[AWL=0.078] X-Spam-Score: 0.078 X-Spam-Level: X-Archive-Number: 200602/240 X-Sequence-Number: 17226 On Wed, Feb 15, 2006 at 11:30:54PM -0500, Ron wrote: > Even better (and more easily scaled as the number of GPR's in the CPU > changes) is to use > the set {L; L+1; L+2; t>>1; R-2; R-1; R} > This means that instead of 7 random memory accesses, we have 3; two > of which result in a > burst access for three elements each. Isn't that improvement going to disappear competely if you choose a bad pivot? > SIDE NOTE: IIRC glibc's qsort is actually merge sort. Merge sort > performance is insensitive to all inputs, and there are way to > optimize it as well. 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. /* Steinar */ -- Homepage: http://www.sesse.net/