]> granicus.if.org Git - postgresql/commit
Improve performance of our private version of qsort. Per recent testing,
authorTom Lane <tgl@sss.pgh.pa.us>
Tue, 21 Mar 2006 19:49:19 +0000 (19:49 +0000)
committerTom Lane <tgl@sss.pgh.pa.us>
Tue, 21 Mar 2006 19:49:19 +0000 (19:49 +0000)
commita155814e373fde80e7fae7d240bd100370c3b2b3
tree50e8c7ec3ad5364f1ef118f8d8b72abc37e54e64
parent85fa81f65bb2394b455036bb658403577f85e766
Improve performance of our private version of qsort.  Per recent testing,
the logic it contained to switch to insertion sort for near-sorted input was
in fact a big loss, because it could fairly easily be fooled into applying
insertion sort to large subfiles that weren't all that well ordered.  Remove
that, and instead add a simple check for already-perfectly-sorted input, as
per suggestion from Dann Corbit.  This adds at worst O(N*lgN) overhead, and
usually far less, while sometimes allowing a subfile sort to finish in O(N)
time.  Preliminary testing says this is an improvement over the basic
Bentley & McIlroy code for many nonrandom inputs, and it costs almost
nothing when the input is random.
src/port/qsort.c