Movatterモバイル変換

[0]ホーム
URL:

Skip to content

Navigation Menu

Sign in
Appearance settings

Search code, repositories, users, issues, pull requests...

Provide feedback

We read every piece of feedback, and take your input very seriously.

Saved searches

Use saved searches to filter your results more quickly

 Sign up
Appearance settings

Commita3f0b3d

Browse files
committed
Improve performance of our private version of qsort. Per recent testing,
the logic it contained to switch to insertion sort for near-sorted input wasin fact a big loss, because it could fairly easily be fooled into applyinginsertion sort to large subfiles that weren't all that well ordered. Removethat, and instead add a simple check for already-perfectly-sorted input, asper suggestion from Dann Corbit. This adds at worst O(N*lgN) overhead, andusually far less, while sometimes allowing a subfile sort to finish in O(N)time. Preliminary testing says this is an improvement over the basicBentley & McIlroy code for many nonrandom inputs, and it costs almostnothing when the input is random.
1 parent570b726 commita3f0b3d

File tree

1 file changed

+20
-17
lines changed

1 file changed

+20
-17
lines changed

‎src/port/qsort.c

Lines changed: 20 additions & 17 deletions
Original file line numberDiff line numberDiff line change
@@ -2,8 +2,10 @@
22
*Modifications from vanilla NetBSD source:
33
* Add do ... while() macro fix
44
* Remove __inline, _DIAGASSERTs, __P
5+
* Remove ill-considered "swap_cnt" switch to insertion sort,
6+
* in favor of a simple check for presorted input.
57
*
6-
*$PostgreSQL: pgsql/src/port/qsort.c,v 1.8 2005/10/15 02:49:51 momjian Exp $
8+
*$PostgreSQL: pgsql/src/port/qsort.c,v 1.9 2006/03/21 19:49:15 tgl Exp $
79
*/
810

911
/*$NetBSD: qsort.c,v 1.13 2003/08/07 16:43:42 agc Exp $*/
@@ -47,7 +49,11 @@ static void swapfunc(char *, char *, size_t, int);
4749
#definemin(a,b)((a) < (b) ? (a) : (b))
4850

4951
/*
50-
* Qsort routine from Bentley & McIlroy's "Engineering a Sort Function".
52+
* Qsort routine based on J. L. Bentley and M. D. McIlroy,
53+
* "Engineering a sort function",
54+
* Software--Practice and Experience 23 (1993) 1249-1265.
55+
* We have modified their original by adding a check for already-sorted input,
56+
* which seems to be a win per discussions on pgsql-hackers around 2006-03-21.
5157
*/
5258
#defineswapcode(TYPE,parmi,parmj,n) \
5359
do {\
@@ -116,10 +122,9 @@ int(*cmp) (const void *, const void *);
116122
intd,
117123
r,
118124
swaptype,
119-
swap_cnt;
125+
presorted;
120126

121127
loop:SWAPINIT(a,es);
122-
swap_cnt=0;
123128
if (n<7)
124129
{
125130
for (pm= (char*)a+es;pm< (char*)a+n*es;pm+=es)
@@ -128,6 +133,17 @@ loop:SWAPINIT(a, es);
128133
swap(pl,pl-es);
129134
return;
130135
}
136+
presorted=1;
137+
for (pm= (char*)a+es;pm< (char*)a+n*es;pm+=es)
138+
{
139+
if (cmp(pm-es,pm)>0)
140+
{
141+
presorted=0;
142+
break;
143+
}
144+
}
145+
if (presorted)
146+
return;
131147
pm= (char*)a+ (n /2)*es;
132148
if (n>7)
133149
{
@@ -144,15 +160,13 @@ loop:SWAPINIT(a, es);
144160
}
145161
swap(a,pm);
146162
pa=pb= (char*)a+es;
147-
148163
pc=pd= (char*)a+ (n-1)*es;
149164
for (;;)
150165
{
151166
while (pb <=pc&& (r=cmp(pb,a)) <=0)
152167
{
153168
if (r==0)
154169
{
155-
swap_cnt=1;
156170
swap(pa,pb);
157171
pa+=es;
158172
}
@@ -162,7 +176,6 @@ loop:SWAPINIT(a, es);
162176
{
163177
if (r==0)
164178
{
165-
swap_cnt=1;
166179
swap(pc,pd);
167180
pd-=es;
168181
}
@@ -171,19 +184,9 @@ loop:SWAPINIT(a, es);
171184
if (pb>pc)
172185
break;
173186
swap(pb,pc);
174-
swap_cnt=1;
175187
pb+=es;
176188
pc-=es;
177189
}
178-
if (swap_cnt==0)
179-
{/* Switch to insertion sort */
180-
for (pm= (char*)a+es;pm< (char*)a+n*es;pm+=es)
181-
for (pl=pm;pl> (char*)a&&cmp(pl-es,pl)>0;
182-
pl-=es)
183-
swap(pl,pl-es);
184-
return;
185-
}
186-
187190
pn= (char*)a+n*es;
188191
r=min(pa- (char*)a,pb-pa);
189192
vecswap(a,pb-r,r);

0 commit comments

Comments
 (0)
[8]ページ先頭
©2009-2025 Movatter.jp