| From: | Greg Stark <stark(at)mit(dot)edu> |
|---|---|
| To: | Peter Geoghegan <pg(at)heroku(dot)com> |
| Cc: | PostgreSQL-development <pgsql-hackers(at)postgresql(dot)org>, Jeff Janes <jeff(dot)janes(at)gmail(dot)com>, Simon Riggs <simon(at)2ndquadrant(dot)com>, Heikki Linnakangas <hlinnaka(at)iki(dot)fi>, Robert Haas <robertmhaas(at)gmail(dot)com> |
| Subject: | Re: Using quicksort for every external sort run |
| Date: | 2015-12-09 03:12:23 |
| Message-ID: | CAM-w4HMxSY-5ZLWS=RVaK2YDwA9U-eEQzDCRrUbG7je65Q=enA@mail.gmail.com |
| Views: | Raw Message | Whole Thread | Download mbox | Resend email |
| Thread: | |
| Lists: | pgsql-hackers |
On 9 Dec 2015 02:44, "Peter Geoghegan" <pg(at)heroku(dot)com> wrote:
>
> I guess you mean insertion sort. What's the theoretical justification
> for the change?
Er, right. Insertion sort.
The sort networks I used here are optimal both in number of comparisons and
depth. I suspect modern CPUs actually manage to do some of the comparisons
in parallel even.
I was experimenting with using SIMD registers and did a non SIMD
implementation like this first and noticed it was doing 15% fewer
comparisons than insertion sort and ran faster. That was for sets of 8, I'm
not sure there's as much saving on smaller sets.
| From | Date | Subject | |
|---|---|---|---|
| Next Message | Peter Geoghegan | 2015-12-09 03:15:18 | Re: Using quicksort for every external sort run |
| Previous Message | Peter Geoghegan | 2015-12-09 03:09:04 | Re: Using quicksort for every external sort run |