On 4/14/11 1:19 PM, "Claudio Freire" <klaussfreire@xxxxxxxxx> wrote: >On Thu, Apr 14, 2011 at 10:05 PM, Scott Carey <scott@xxxxxxxxxxxxxxxxx> >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. -- Sent via pgsql-performance mailing list (pgsql-performance@xxxxxxxxxxxxxx) To make changes to your subscription: http://www.postgresql.org/mailpref/pgsql-performance
