From: Scott Carey <scott@richrelevance.com>
To: Claudio Freire <klaussfreire@gmail.com>
Cc: Greg Smith <greg@2ndquadrant.com>
Cc: Glyn Astill <glynastill@yahoo.co.uk>
Cc: Kevin Grittner <Kevin.Grittner@wicourts.gov>
Cc: david@lang.hm <david@lang.hm>
Cc: Steve Clark <sclark@netwolves.com>
Cc: Joshua D. Drake <jd@commandprompt.com>
Cc: Scott Marlowe <scott.marlowe@gmail.com>
Cc: pgsql-performance@postgresql.org <pgsql-performance@postgresql.org>
Subject: Re: Linux: more cores = less concurrency.
Date: Thu, 14 Apr 2011 15:42:46 -0700
Message-ID: <C9CCC426.30A29%scott@richrelevance.com> (raw)
In-Reply-To: <BANLkTinJZQ+uT1LADUD-BHYciuWX6JWNvg@mail.gmail.com>
On 4/14/11 1:19 PM, "Claudio Freire" <klaussfreire@gmail.com> wrote:
>On Thu, Apr 14, 2011 at 10:05 PM, Scott Carey <scott@richrelevance.com>
>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.
Reply instructions:
You may reply publicly to this message via plain-text email
using any one of the following methods:
* Reply to all the recipients using the --to and --cc options:
reply via email
To: pgsql-performance@postgresql.org
Cc: scott@richrelevance.com, klaussfreire@gmail.com, greg@2ndquadrant.com, glynastill@yahoo.co.uk, Kevin.Grittner@wicourts.gov, david@lang.hm, sclark@netwolves.com, jd@commandprompt.com, scott.marlowe@gmail.com
Subject: Re: Linux: more cores = less concurrency.
In-Reply-To: <C9CCC426.30A29%scott@richrelevance.com>
* Save the following mbox file, import it into your mail client,
and reply-to-all from there: mbox
This inbox is served by DDX for PostgreSQL; see mirroring instructions
for how to clone and mirror all data and code used for this inbox