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

Commita2ff18e

Browse files
committed
Improve sift up/down code in binaryheap.c and logtape.c.
Borrow the logic that's long been used in tuplesort.c: insteadof physically swapping the data in two heap entries, keep thevalue that's being sifted up or down in a local variable, andjust move the other values as necessary. This makes the codeshorter as well as faster. It's not clear that any currentcallers are really time-critical enough to notice, but wemight as well code heap maintenance the same way everywhere.Ma Liangzhu and Tom LaneDiscussion:https://postgr.es/m/17336-fc4e522d26a750fd@postgresql.org
1 parent2de3c10 commita2ff18e

File tree

2 files changed

+63
-61
lines changed

2 files changed

+63
-61
lines changed

‎src/backend/lib/binaryheap.c

Lines changed: 40 additions & 30 deletions
Original file line numberDiff line numberDiff line change
@@ -19,7 +19,6 @@
1919

2020
staticvoidsift_down(binaryheap*heap,intnode_off);
2121
staticvoidsift_up(binaryheap*heap,intnode_off);
22-
staticinlinevoidswap_nodes(binaryheap*heap,inta,intb);
2322

2423
/*
2524
* binaryheap_allocate
@@ -173,24 +172,28 @@ binaryheap_first(binaryheap *heap)
173172
Datum
174173
binaryheap_remove_first(binaryheap*heap)
175174
{
175+
Datumresult;
176+
176177
Assert(!binaryheap_empty(heap)&&heap->bh_has_heap_property);
177178

179+
/* extract the root node, which will be the result */
180+
result=heap->bh_nodes[0];
181+
182+
/* easy if heap contains one element */
178183
if (heap->bh_size==1)
179184
{
180185
heap->bh_size--;
181-
returnheap->bh_nodes[0];
186+
returnresult;
182187
}
183188

184189
/*
185-
* Swap the root and last nodes, decrease the size of the heap (i.e.
186-
* remove the former root node) and sift the new root node down to its
187-
* correct position.
190+
* Remove the last node, placing it in the vacated root entry, and sift
191+
* the new root node down to its correct position.
188192
*/
189-
swap_nodes(heap,0,heap->bh_size-1);
190-
heap->bh_size--;
193+
heap->bh_nodes[0]=heap->bh_nodes[--heap->bh_size];
191194
sift_down(heap,0);
192195

193-
returnheap->bh_nodes[heap->bh_size];
196+
returnresult;
194197
}
195198

196199
/*
@@ -211,49 +214,47 @@ binaryheap_replace_first(binaryheap *heap, Datum d)
211214
sift_down(heap,0);
212215
}
213216

214-
/*
215-
* Swap the contents of two nodes.
216-
*/
217-
staticinlinevoid
218-
swap_nodes(binaryheap*heap,inta,intb)
219-
{
220-
Datumswap;
221-
222-
swap=heap->bh_nodes[a];
223-
heap->bh_nodes[a]=heap->bh_nodes[b];
224-
heap->bh_nodes[b]=swap;
225-
}
226-
227217
/*
228218
* Sift a node up to the highest position it can hold according to the
229219
* comparator.
230220
*/
231221
staticvoid
232222
sift_up(binaryheap*heap,intnode_off)
233223
{
224+
Datumnode_val=heap->bh_nodes[node_off];
225+
226+
/*
227+
* Within the loop, the node_off'th array entry is a "hole" that
228+
* notionally holds node_val, but we don't actually store node_val there
229+
* till the end, saving some unnecessary data copying steps.
230+
*/
234231
while (node_off!=0)
235232
{
236233
intcmp;
237234
intparent_off;
235+
Datumparent_val;
238236

239237
/*
240238
* If this node is smaller than its parent, the heap condition is
241239
* satisfied, and we're done.
242240
*/
243241
parent_off=parent_offset(node_off);
244-
cmp=heap->bh_compare(heap->bh_nodes[node_off],
245-
heap->bh_nodes[parent_off],
242+
parent_val=heap->bh_nodes[parent_off];
243+
cmp=heap->bh_compare(node_val,
244+
parent_val,
246245
heap->bh_arg);
247246
if (cmp <=0)
248247
break;
249248

250249
/*
251-
* Otherwise, swap thenode and its parentand go on to check the
252-
* node's new parent.
250+
* Otherwise, swap theparent value with the hole,and go on to check
251+
*thenode's new parent.
253252
*/
254-
swap_nodes(heap,node_off,parent_off);
253+
heap->bh_nodes[node_off]=parent_val;
255254
node_off=parent_off;
256255
}
256+
/* Re-fill the hole */
257+
heap->bh_nodes[node_off]=node_val;
257258
}
258259

259260
/*
@@ -263,6 +264,13 @@ sift_up(binaryheap *heap, int node_off)
263264
staticvoid
264265
sift_down(binaryheap*heap,intnode_off)
265266
{
267+
Datumnode_val=heap->bh_nodes[node_off];
268+
269+
/*
270+
* Within the loop, the node_off'th array entry is a "hole" that
271+
* notionally holds node_val, but we don't actually store node_val there
272+
* till the end, saving some unnecessary data copying steps.
273+
*/
266274
while (true)
267275
{
268276
intleft_off=left_offset(node_off);
@@ -271,14 +279,14 @@ sift_down(binaryheap *heap, int node_off)
271279

272280
/* Is the left child larger than the parent? */
273281
if (left_off<heap->bh_size&&
274-
heap->bh_compare(heap->bh_nodes[node_off],
282+
heap->bh_compare(node_val,
275283
heap->bh_nodes[left_off],
276284
heap->bh_arg)<0)
277285
swap_off=left_off;
278286

279287
/* Is the right child larger than the parent? */
280288
if (right_off<heap->bh_size&&
281-
heap->bh_compare(heap->bh_nodes[node_off],
289+
heap->bh_compare(node_val,
282290
heap->bh_nodes[right_off],
283291
heap->bh_arg)<0)
284292
{
@@ -298,10 +306,12 @@ sift_down(binaryheap *heap, int node_off)
298306
break;
299307

300308
/*
301-
* Otherwise, swap thenode with the child that violates the heap
309+
* Otherwise, swap thehole with the child that violates the heap
302310
* property; then go on to check its children.
303311
*/
304-
swap_nodes(heap,swap_off,node_off);
312+
heap->bh_nodes[node_off]=heap->bh_nodes[swap_off];
305313
node_off=swap_off;
306314
}
315+
/* Re-fill the hole */
316+
heap->bh_nodes[node_off]=node_val;
307317
}

‎src/backend/utils/sort/logtape.c

Lines changed: 23 additions & 31 deletions
Original file line numberDiff line numberDiff line change
@@ -340,16 +340,6 @@ ltsReadFillBuffer(LogicalTape *lt)
340340
return (lt->nbytes>0);
341341
}
342342

343-
staticinlinevoid
344-
swap_nodes(long*heap,unsigned longa,unsigned longb)
345-
{
346-
longswap;
347-
348-
swap=heap[a];
349-
heap[a]=heap[b];
350-
heap[b]=swap;
351-
}
352-
353343
staticinlineunsigned long
354344
left_offset(unsigned longi)
355345
{
@@ -390,31 +380,33 @@ ltsGetFreeBlock(LogicalTapeSet *lts)
390380
long*heap=lts->freeBlocks;
391381
longblocknum;
392382
intheapsize;
393-
unsigned longpos;
383+
longholeval;
384+
unsigned longholepos;
394385

395386
/* freelist empty; allocate a new block */
396387
if (lts->nFreeBlocks==0)
397388
returnlts->nBlocksAllocated++;
398389

390+
/* easy if heap contains one element */
399391
if (lts->nFreeBlocks==1)
400392
{
401393
lts->nFreeBlocks--;
402394
returnlts->freeBlocks[0];
403395
}
404396

405-
/*take top of minheap */
397+
/*remove top of minheap */
406398
blocknum=heap[0];
407399

408-
/* replace with end of minheap array */
409-
heap[0]=heap[--lts->nFreeBlocks];
400+
/*we'llreplace it with end of minheap array */
401+
holeval=heap[--lts->nFreeBlocks];
410402

411403
/* sift down */
412-
pos=0;
404+
holepos=0;/* holepos is where the "hole" is */
413405
heapsize=lts->nFreeBlocks;
414406
while (true)
415407
{
416-
unsigned longleft=left_offset(pos);
417-
unsigned longright=right_offset(pos);
408+
unsigned longleft=left_offset(holepos);
409+
unsigned longright=right_offset(holepos);
418410
unsigned longmin_child;
419411

420412
if (left<heapsize&&right<heapsize)
@@ -426,12 +418,13 @@ ltsGetFreeBlock(LogicalTapeSet *lts)
426418
else
427419
break;
428420

429-
if (heap[min_child] >=heap[pos])
421+
if (heap[min_child] >=holeval)
430422
break;
431423

432-
swap_nodes(heap,min_child,pos);
433-
pos=min_child;
424+
heap[holepos]=heap[min_child];
425+
holepos=min_child;
434426
}
427+
heap[holepos]=holeval;
435428

436429
returnblocknum;
437430
}
@@ -483,7 +476,7 @@ static void
483476
ltsReleaseBlock(LogicalTapeSet*lts,longblocknum)
484477
{
485478
long*heap;
486-
unsigned longpos;
479+
unsigned longholepos;
487480

488481
/*
489482
* Do nothing if we're no longer interested in remembering free space.
@@ -508,24 +501,23 @@ ltsReleaseBlock(LogicalTapeSet *lts, long blocknum)
508501
lts->freeBlocksLen*sizeof(long));
509502
}
510503

504+
/* create a "hole" at end of minheap array */
511505
heap=lts->freeBlocks;
512-
pos=lts->nFreeBlocks;
513-
514-
/* place entry at end of minheap array */
515-
heap[pos]=blocknum;
506+
holepos=lts->nFreeBlocks;
516507
lts->nFreeBlocks++;
517508

518-
/* sift up */
519-
while (pos!=0)
509+
/* sift upto insert blocknum*/
510+
while (holepos!=0)
520511
{
521-
unsigned longparent=parent_offset(pos);
512+
unsigned longparent=parent_offset(holepos);
522513

523-
if (heap[parent]<heap[pos])
514+
if (heap[parent]<blocknum)
524515
break;
525516

526-
swap_nodes(heap,parent,pos);
527-
pos=parent;
517+
heap[holepos]=heap[parent];
518+
holepos=parent;
528519
}
520+
heap[holepos]=blocknum;
529521
}
530522

531523
/*

0 commit comments

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