| From: | Peter Geoghegan <pg(at)heroku(dot)com> |
|---|---|
| To: | Greg Stark <stark(at)mit(dot)edu> |
| Cc: | Jeff Janes <jeff(dot)janes(at)gmail(dot)com>, Robert Haas <robertmhaas(at)gmail(dot)com>, Pg Hackers <pgsql-hackers(at)postgresql(dot)org>, Heikki Linnakangas <hlinnaka(at)iki(dot)fi>, Simon Riggs <simon(at)2ndquadrant(dot)com> |
| Subject: | Re: Using quicksort for every external sort run |
| Date: | 2015-12-11 23:20:11 |
| Message-ID: | CAM3SWZQQwtyFY3h65m+Wmju_pEgu6qys9idd4_98ZTTyYVLHzQ@mail.gmail.com |
| Views: | Raw Message | Whole Thread | Download mbox | Resend email |
| Thread: | |
| Lists: | pgsql-hackers |
On Fri, Dec 11, 2015 at 2:41 PM, Greg Stark <stark(at)mit(dot)edu> wrote:
> However the number of comparisons is significantly higher. And in the
> non-"abbreviated keys" case where the compare is going to be a
> function pointer call the number of comparisons is probably more
> important than the actual time spent when benchmarking comparing
> int64s. In that case insertion sort does seem to be better than using
> the sort networks.
Back when I wrote a prototype of Timsort, pre-abbreviated keys, it
required significantly fewer text comparisons [1] in fair and
representative cases (i.e. not particularly tickling our quicksort's
precheck thing), and yet was significantly slower.
[1] http://www.postgresql.org/message-id/CAEYLb_W++UhrcWprzG9TyBVF7Sn-c1s9oLbABvAvPGdeP2DFSQ@mail.gmail.com
--
Peter Geoghegan
| From | Date | Subject | |
|---|---|---|---|
| Next Message | Mark Dilger | 2015-12-11 23:30:04 | Re: Bootstrap DATA is a pita |
| Previous Message | Tom Lane | 2015-12-11 23:12:16 | Re: Bootstrap DATA is a pita |