Re: qsort again (was Re: [PERFORM] Strange Create Index behaviour)

From: Tom Lane
Subject: Re: qsort again (was Re: [PERFORM] Strange Create Index behaviour)
Date: ,
Msg-id: 19570.1142971720@sss.pgh.pa.us
(view: Whole thread, Raw)
In response to: qsort again (was Re: [PERFORM] Strange Create Index behaviour)  (Tom Lane)
List: pgsql-hackers

Tree view

qsort again (was Re: [PERFORM] Strange Create Index behaviour)  (Tom Lane, )
 Re: qsort again (was Re: [PERFORM] Strange Create Index behaviour)  (Gary Doades, )
  Re: qsort again (was Re: [PERFORM] Strange Create Index behaviour)  (Tom Lane, )
  Re: qsort again (was Re: [PERFORM] Strange Create Index behaviour)  (Tom Lane, )
   Re: qsort again (was Re: [PERFORM] Strange Create Index behaviour)  (Tom Lane, )
    Re: qsort again (was Re: [PERFORM] Strange Create Index  (Simon Riggs, )
  Re: qsort again (was Re: [PERFORM] Strange Create Index behaviour)  (Christopher Kings-Lynne, )
 Re: qsort again (was Re: [PERFORM] Strange Create Index  (Ron, )
  Re: qsort again (was Re: [PERFORM] Strange Create Index behaviour)  (Tom Lane, )
   Re: qsort again (was Re: [PERFORM] Strange Create Index  (Ron, )
 Re: qsort again (was Re: [PERFORM] Strange Create Index behaviour)  ("Dann Corbit", )
  Re: qsort again (was Re: [PERFORM] Strange Create  (Ron, )
  Re: qsort again (was Re: [PERFORM] Strange Create Index behaviour)  (Bruce Momjian, )
   Re: qsort again (was Re: [PERFORM] Strange Create Index behaviour)  ("Jonah H. Harris", )
 Re: qsort again (was Re: [PERFORM] Strange Create Index  (Neil Conway, )
  Re: qsort again  (Florian Weimer, )
   Re: qsort again  (Martijn van Oosterhout, )
    Re: [PERFORM] qsort again  (Sven Geisler, )
   Re: [PERFORM] qsort again  (Ron, )
 Re: qsort again (was Re: [PERFORM] Strange Create Index behaviour)  ("Qingqing Zhou", )
  Re: qsort again (was Re: [PERFORM] Strange Create Index behaviour)  (Tom Lane, )
 Re: qsort again (was Re: [PERFORM] Strange Create Index behaviour)  ("Qingqing Zhou", )
  Re: qsort again (was Re: [PERFORM] Strange Create Index behaviour)  (Tom Lane, )
 Re: qsort again (was Re: [PERFORM] Strange Create Index behaviour)  ("Qingqing Zhou", )
 Re: qsort again (was Re: [PERFORM] Strange Create Index  (Ron, )
  Re: qsort again (was Re: [PERFORM] Strange Create Index  (Markus Schaber, )
   Re: qsort again (was Re: [PERFORM] Strange Create Index  ("Jonah H. Harris", )
   Re: qsort again (was Re: [PERFORM] Strange Create Index  ("Craig A. James", )
    Re: qsort again (was Re: [PERFORM] Strange Create Index  (Tom Lane, )
     Re: qsort again (was Re: [PERFORM] Strange Create Index  (Mark Lewis, )
      Re: qsort again (was Re: [PERFORM] Strange Create Index  (Markus Schaber, )
       Re: qsort again (was Re: [PERFORM] Strange Create Index  (Greg Stark, )
        Re: qsort again (was Re: [PERFORM] Strange Create Index  (Mark Lewis, )
         Re: qsort again (was Re: [PERFORM] Strange Create Index  (David Lang, )
          Re: qsort again (was Re: [PERFORM] Strange Create Index  (Markus Schaber, )
          Re: qsort again (was Re: [PERFORM] Strange Create Index  (Mark Lewis, )
           Re: qsort again (was Re: [PERFORM] Strange Create Index  (Tom Lane, )
      Re: qsort again (was Re: [PERFORM] Strange Create Index  (Martijn van Oosterhout, )
      Re: qsort again (was Re: [PERFORM] Strange Create Index  (Scott Lamb, )
       Re: qsort again (was Re: [PERFORM] Strange Create Index  (Martijn van Oosterhout, )
  Re: qsort again (was Re: [PERFORM] Strange Create Index  (Martijn van Oosterhout, )
   Re: qsort again (was Re: [PERFORM] Strange Create  (Ron, )
    Re: qsort again (was Re: [PERFORM] Strange Create  (Tom Lane, )
    Re: qsort again (was Re: [PERFORM] Strange Create  (Ron, )
     Re: qsort again (was Re: [PERFORM] Strange Create  (Martijn van Oosterhout, )
     Re: qsort again (was Re: [PERFORM] Strange Create  (Scott Lamb, )
      Re: qsort again (was Re: [PERFORM] Strange Create  (Ron, )
       Re: qsort again (was Re: [PERFORM] Strange Create  (Ron, )
        Re: qsort again (was Re: [PERFORM] Strange Create  (Markus Schaber, )
         Re: qsort again (was Re: [PERFORM] Strange Create  (Ron, )
          Re: qsort again (was Re: [PERFORM] Strange Create  (Martijn van Oosterhout, )
           Re: qsort again (was Re: [PERFORM] Strange Create  (Ron, )
 Re: qsort again (was Re: [PERFORM] Strange Create Index  (Neil Conway, )
 Re: qsort again (was Re: [PERFORM] Strange Create  (Ron, )
  Re: qsort again (was Re: [PERFORM] Strange Create  (Ragnar, )
   Re: qsort again (was Re: [PERFORM] Strange Create  ("Gregory Maxwell", )
 Re: qsort again (was Re: [PERFORM] Strange Create Index behaviour)  (Tom Lane, )

Last month I wrote:
> It seems clear that our qsort.c is doing a pretty awful job of picking
> qsort pivots, while glibc is mostly managing not to make that mistake.

I re-ran Gary's test script using the just-committed improvements to
qsort.c, and got pretty nice numbers (attached --- compare to
http://archives.postgresql.org/pgsql-performance/2006-02/msg00227.php).
So it was wrong to blame his problems on the pivot selection --- the
culprit was that ill-considered switch to insertion sort.

            regards, tom lane

100 runtimes for latest port/qsort.c, sorted ascending:

Time: 335.481 ms
Time: 335.606 ms
Time: 335.932 ms
Time: 336.039 ms
Time: 336.182 ms
Time: 336.231 ms
Time: 336.711 ms
Time: 336.721 ms
Time: 336.971 ms
Time: 336.982 ms
Time: 337.036 ms
Time: 337.190 ms
Time: 337.223 ms
Time: 337.312 ms
Time: 337.350 ms
Time: 337.423 ms
Time: 337.523 ms
Time: 337.528 ms
Time: 337.565 ms
Time: 337.566 ms
Time: 337.732 ms
Time: 337.741 ms
Time: 337.744 ms
Time: 337.786 ms
Time: 337.790 ms
Time: 337.898 ms
Time: 337.905 ms
Time: 337.952 ms
Time: 337.976 ms
Time: 338.017 ms
Time: 338.123 ms
Time: 338.206 ms
Time: 338.306 ms
Time: 338.514 ms
Time: 338.594 ms
Time: 338.597 ms
Time: 338.683 ms
Time: 338.705 ms
Time: 338.729 ms
Time: 338.748 ms
Time: 338.816 ms
Time: 338.958 ms
Time: 338.963 ms
Time: 338.997 ms
Time: 339.074 ms
Time: 339.106 ms
Time: 339.134 ms
Time: 339.159 ms
Time: 339.226 ms
Time: 339.260 ms
Time: 339.289 ms
Time: 339.341 ms
Time: 339.500 ms
Time: 339.585 ms
Time: 339.595 ms
Time: 339.774 ms
Time: 339.897 ms
Time: 339.927 ms
Time: 340.064 ms
Time: 340.133 ms
Time: 340.172 ms
Time: 340.219 ms
Time: 340.261 ms
Time: 340.323 ms
Time: 340.708 ms
Time: 340.761 ms
Time: 340.785 ms
Time: 340.900 ms
Time: 340.986 ms
Time: 341.339 ms
Time: 341.564 ms
Time: 341.707 ms
Time: 342.155 ms
Time: 342.213 ms
Time: 342.452 ms
Time: 342.515 ms
Time: 342.540 ms
Time: 342.928 ms
Time: 343.548 ms
Time: 343.663 ms
Time: 344.192 ms
Time: 344.952 ms
Time: 345.152 ms
Time: 345.174 ms
Time: 345.444 ms
Time: 346.848 ms
Time: 348.144 ms
Time: 348.842 ms
Time: 354.550 ms
Time: 356.877 ms
Time: 357.475 ms
Time: 358.487 ms
Time: 364.178 ms
Time: 370.730 ms
Time: 493.098 ms
Time: 648.009 ms
Time: 849.345 ms
Time: 860.616 ms
Time: 936.800 ms
Time: 1727.085 ms


pgsql-hackers by date:

From: "Andrew Dunstan"
Date:
Subject: Re: [GENERAL] A real currency type
From: Trent Shipley
Date:
Subject: Modular Type Libraries: was A real currency type