Received: from maia.hub.org (maia-2.hub.org [200.46.204.251]) by mail.postgresql.org (Postfix) with ESMTP id B0E771337B83 for ; Thu, 14 Apr 2011 19:43:02 -0300 (ADT) Received: from mail.postgresql.org ([200.46.204.86]) by maia.hub.org (mx1.hub.org [200.46.204.251]) (amavisd-maia, port 10024) with ESMTP id 06604-04 for ; Thu, 14 Apr 2011 22:42:45 +0000 (UTC) X-Greylist: from auto-whitelisted by SQLgrey-1.7.6 Received: from EXHUB018-1.exch018.msoutlookonline.net (exhub018-1.exch018.msoutlookonline.net [64.78.17.16]) by mail.postgresql.org (Postfix) with ESMTP id CCDC21337B6E for ; Thu, 14 Apr 2011 19:42:44 -0300 (ADT) Received: from EXVMBX018-1.exch018.msoutlookonline.net ([64.78.17.47]) by EXHUB018-1.exch018.msoutlookonline.net ([64.78.17.16]) with mapi; Thu, 14 Apr 2011 15:42:44 -0700 From: Scott Carey To: Claudio Freire CC: Greg Smith , Glyn Astill , Kevin Grittner , "david@lang.hm" , Steve Clark , "Joshua D. Drake" , Scott Marlowe , "pgsql-performance@postgresql.org" Date: Thu, 14 Apr 2011 15:42:46 -0700 Subject: Re: Linux: more cores = less concurrency. Thread-Topic: [PERFORM] Linux: more cores = less concurrency. Thread-Index: Acv69UT+Ma0XHODLQL+ZHERWj84Wsw== Message-ID: In-Reply-To: Accept-Language: en-US Content-Language: en-US X-MS-Has-Attach: X-MS-TNEF-Correlator: user-agent: Microsoft-MacOutlook/14.10.0.110310 acceptlanguage: en-US Content-Type: text/plain; charset="us-ascii" Content-Transfer-Encoding: quoted-printable MIME-Version: 1.0 X-Virus-Scanned: Maia Mailguard 1.0.1 X-Spam-Status: No, hits=-1.9 tagged_above=-10 required=5 tests=BAYES_00=-1.9 X-Spam-Level: X-Archive-Number: 201104/218 X-Sequence-Number: 43280 On 4/14/11 1:19 PM, "Claudio Freire" wrote: >On Thu, Apr 14, 2011 at 10:05 PM, Scott Carey >wrote: >> Huge Pages helps caches. >> Dual-Pivot quicksort is more cache friendly and is _always_ equal to or >> faster than traditional quicksort (its a provably improved algorithm). > >If you want a cache-friendly sorting algorithm, you need mergesort. > >I don't know any algorithm as friendly to caches as mergesort. > >Quicksort could be better only when the sorting buffer is guaranteed >to fit on the CPU's cache, and that's usually just a few 4kb pages. Of mergesort variants, Timsort is a recent general purpose variant favored by many since it is sub- O(n log(n)) on partially sorted data. Which work best under which circumstances depends a lot on the size of the data, size of the elements, cost of the compare function, whether you're sorting the data directly or sorting pointers, and other factors. Mergesort may be more cache friendly (?) but might use more memory bandwidth. I'm not sure. I do know that dual-pivot quicksort provably causes fewer swaps (but the same # of compares) as the usual single-pivot quicksort. And swaps are a lot slower than you would expect due to the effects on processor caches. Therefore it might help with multiprocessor scalability by reducing memory/cache pressure.