git.postgresql.org Git - postgresql.git/commit

git projects / postgresql.git / commit

summary | shortlog | log | commit | commitdiff | tree
(parent: 570b726) | patch

Improve performance of our private version of qsort. Per recent testing,

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.

RSS Atom