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

Commit1cff1b9

Browse files
committed
Represent Lists as expansible arrays, not chains of cons-cells.
Originally, Postgres Lists were a more or less exact reimplementation ofLisp lists, which consist of chains of separately-allocated cons cells,each having a value and a next-cell link. We'd hacked that once before(commitd0b4399) to add a separate List header, but the data was stillin cons cells. That makes some operations -- notably list_nth() -- O(N),and it's bulky because of the next-cell pointers and per-cell pallocoverhead, and it's very cache-unfriendly if the cons cells end upscattered around rather than being adjacent.In this rewrite, we still have List headers, but the data is in aresizable array of values, with no next-cell links. Now we need atmost two palloc's per List, and often only one, since we can allocatesome values in the same palloc call as the List header. (Of course,extending an existing List may require repalloc's to enlarge the array.But this involves just O(log N) allocations not O(N).)Of course this is not without downsides. The key difficulty is thataddition or deletion of a list entry may now cause other entries tomove, which it did not before.For example, that breaks foreach() and sister macros, which historicallyused a pointer to the current cons-cell as loop state. We can repairthose macros transparently by making their actual loop state be aninteger list index; the exposed "ListCell *" pointer is no longer statecarried across loop iterations, but is just a derived value. (Inpractice, modern compilers can optimize things back to having just oneloop state value, at least for simple cases with inline loop bodies.)In principle, this is a semantics change for cases where the loop bodyinserts or deletes list entries ahead of the current loop index; butI found no such cases in the Postgres code.The change is not at all transparent for code that doesn't use foreach()but chases lists "by hand" using lnext(). The largest share of suchcode in the backend is in loops that were maintaining "prev" and "next"variables in addition to the current-cell pointer, in order to deletelist cells efficiently using list_delete_cell(). However, we no longerneed a previous-cell pointer to delete a list cell efficiently. Keepinga next-cell pointer doesn't work, as explained above, but we can improvematters by changing such code to use a regular foreach() loop and thenusing the new macro foreach_delete_current() to delete the current cell.(This macro knows how to update the associated foreach loop's state sothat no cells will be missed in the traversal.)There remains a nontrivial risk of code assuming that a ListCell *pointer will remain good over an operation that could now move the listcontents. To help catch such errors, list.c can be compiled with a newdefine symbol DEBUG_LIST_MEMORY_USAGE that forcibly moves list contentswhenever that could possibly happen. This makes list operationssignificantly more expensive so it's not normally turned on (though itis on by default if USE_VALGRIND is on).There are two notable API differences from the previous code:* lnext() now requires the List's header pointer in addition to thecurrent cell's address.* list_delete_cell() no longer requires a previous-cell argument.These changes are somewhat unfortunate, but on the other hand code usingeither function needs inspection to see if it is assuming anythingit shouldn't, so it's not all bad.Programmers should be aware of these significant performance changes:* list_nth() and related functions are now O(1); so there's nomajor access-speed difference between a list and an array.* Inserting or deleting a list element now takes time proportional tothe distance to the end of the list, due to moving the array elements.(However, it typically *doesn't* require palloc or pfree, so except inlong lists it's probably still faster than before.) Notably, lcons()used to be about the same cost as lappend(), but that's no longer trueif the list is long. Code that uses lcons() and list_delete_first()to maintain a stack might usefully be rewritten to push and pop at theend of the list rather than the beginning.* There are now list_insert_nth...() and list_delete_nth...() functionsthat add or remove a list cell identified by index. These have thedata-movement penalty explained above, but there's no search penalty.* list_concat() and variants now copy the second list's data intostorage belonging to the first list, so there is no longer anysharing of cells between the input lists. The second argument isnow declared "const List *" to reflect that it isn't changed.This patch just does the minimum needed to get the new implementationin place and fix bugs exposed by the regression tests. As suggestedby the foregoing, there's a fair amount of followup work remaining todo.Also, the ENABLE_LIST_COMPAT macros are finally removed in thiscommit. Code using those should have been gone a dozen years ago.Patch by me; thanks to David Rowley, Jesper Pedersen, and othersfor review.Discussion:https://postgr.es/m/11587.1550975080@sss.pgh.pa.us
1 parent67b9b3c commit1cff1b9

File tree

86 files changed

+1248
-1115
lines changed

Some content is hidden

Large Commits have some content hidden by default. Use the searchbox below for content that may be hidden.

86 files changed

+1248
-1115
lines changed

‎contrib/file_fdw/file_fdw.c

Lines changed: 3 additions & 6 deletions
Original file line numberDiff line numberDiff line change
@@ -360,8 +360,7 @@ fileGetOptions(Oid foreigntableid,
360360
ForeignServer*server;
361361
ForeignDataWrapper*wrapper;
362362
List*options;
363-
ListCell*lc,
364-
*prev;
363+
ListCell*lc;
365364

366365
/*
367366
* Extract options from FDW objects. We ignore user mappings because
@@ -387,25 +386,23 @@ fileGetOptions(Oid foreigntableid,
387386
*/
388387
*filename=NULL;
389388
*is_program= false;
390-
prev=NULL;
391389
foreach(lc,options)
392390
{
393391
DefElem*def= (DefElem*)lfirst(lc);
394392

395393
if (strcmp(def->defname,"filename")==0)
396394
{
397395
*filename=defGetString(def);
398-
options=list_delete_cell(options,lc,prev);
396+
options=foreach_delete_current(options,lc);
399397
break;
400398
}
401399
elseif (strcmp(def->defname,"program")==0)
402400
{
403401
*filename=defGetString(def);
404402
*is_program= true;
405-
options=list_delete_cell(options,lc,prev);
403+
options=foreach_delete_current(options,lc);
406404
break;
407405
}
408-
prev=lc;
409406
}
410407

411408
/*

‎contrib/pg_trgm/trgm_regexp.c

Lines changed: 4 additions & 14 deletions
Original file line numberDiff line numberDiff line change
@@ -1013,9 +1013,7 @@ addKey(TrgmNFA *trgmNFA, TrgmState *state, TrgmStateKey *key)
10131013
{
10141014
regex_arc_t*arcs;
10151015
TrgmStateKeydestKey;
1016-
ListCell*cell,
1017-
*prev,
1018-
*next;
1016+
ListCell*cell;
10191017
inti,
10201018
arcsCount;
10211019

@@ -1030,13 +1028,10 @@ addKey(TrgmNFA *trgmNFA, TrgmState *state, TrgmStateKey *key)
10301028
* redundancy. We can drop either old key(s) or the new key if we find
10311029
* redundancy.
10321030
*/
1033-
prev=NULL;
1034-
cell=list_head(state->enterKeys);
1035-
while (cell)
1031+
foreach(cell,state->enterKeys)
10361032
{
10371033
TrgmStateKey*existingKey= (TrgmStateKey*)lfirst(cell);
10381034

1039-
next=lnext(cell);
10401035
if (existingKey->nstate==key->nstate)
10411036
{
10421037
if (prefixContains(&existingKey->prefix,&key->prefix))
@@ -1050,15 +1045,10 @@ addKey(TrgmNFA *trgmNFA, TrgmState *state, TrgmStateKey *key)
10501045
* The new key covers this old key. Remove the old key, it's
10511046
* no longer needed once we add this key to the list.
10521047
*/
1053-
state->enterKeys=list_delete_cell(state->enterKeys,
1054-
cell,prev);
1048+
state->enterKeys=foreach_delete_current(state->enterKeys,
1049+
cell);
10551050
}
1056-
else
1057-
prev=cell;
10581051
}
1059-
else
1060-
prev=cell;
1061-
cell=next;
10621052
}
10631053

10641054
/* No redundancy, so add this key to the state's list */

‎contrib/postgres_fdw/deparse.c

Lines changed: 3 additions & 3 deletions
Original file line numberDiff line numberDiff line change
@@ -2610,7 +2610,7 @@ deparseSubscriptingRef(SubscriptingRef *node, deparse_expr_cxt *context)
26102610
{
26112611
deparseExpr(lfirst(lowlist_item),context);
26122612
appendStringInfoChar(buf,':');
2613-
lowlist_item=lnext(lowlist_item);
2613+
lowlist_item=lnext(node->reflowerindexpr,lowlist_item);
26142614
}
26152615
deparseExpr(lfirst(uplist_item),context);
26162616
appendStringInfoChar(buf,']');
@@ -2673,7 +2673,7 @@ deparseFuncExpr(FuncExpr *node, deparse_expr_cxt *context)
26732673
{
26742674
if (!first)
26752675
appendStringInfoString(buf,", ");
2676-
if (use_variadic&&lnext(arg)==NULL)
2676+
if (use_variadic&&lnext(node->args,arg)==NULL)
26772677
appendStringInfoString(buf,"VARIADIC ");
26782678
deparseExpr((Expr*)lfirst(arg),context);
26792679
first= false;
@@ -3001,7 +3001,7 @@ deparseAggref(Aggref *node, deparse_expr_cxt *context)
30013001
first= false;
30023002

30033003
/* Add VARIADIC */
3004-
if (use_variadic&&lnext(arg)==NULL)
3004+
if (use_variadic&&lnext(node->args,arg)==NULL)
30053005
appendStringInfoString(buf,"VARIADIC ");
30063006

30073007
deparseExpr((Expr*)n,context);

‎contrib/sepgsql/label.c

Lines changed: 2 additions & 9 deletions
Original file line numberDiff line numberDiff line change
@@ -207,23 +207,16 @@ sepgsql_subxact_callback(SubXactEvent event, SubTransactionId mySubid,
207207
SubTransactionIdparentSubid,void*arg)
208208
{
209209
ListCell*cell;
210-
ListCell*prev;
211-
ListCell*next;
212210

213211
if (event==SUBXACT_EVENT_ABORT_SUB)
214212
{
215-
prev=NULL;
216-
for (cell=list_head(client_label_pending);cell;cell=next)
213+
foreach(cell,client_label_pending)
217214
{
218215
pending_label*plabel=lfirst(cell);
219216

220-
next=lnext(cell);
221-
222217
if (plabel->subid==mySubid)
223218
client_label_pending
224-
=list_delete_cell(client_label_pending,cell,prev);
225-
else
226-
prev=cell;
219+
=foreach_delete_current(client_label_pending,cell);
227220
}
228221
}
229222
}

‎contrib/sepgsql/uavc.c

Lines changed: 2 additions & 7 deletions
Original file line numberDiff line numberDiff line change
@@ -93,24 +93,20 @@ static void
9393
sepgsql_avc_reclaim(void)
9494
{
9595
ListCell*cell;
96-
ListCell*next;
97-
ListCell*prev;
9896
intindex;
9997

10098
while (avc_num_caches >=avc_threshold-AVC_NUM_RECLAIM)
10199
{
102100
index=avc_lru_hint;
103101

104-
prev=NULL;
105-
for (cell=list_head(avc_slots[index]);cell;cell=next)
102+
foreach(cell,avc_slots[index])
106103
{
107104
avc_cache*cache=lfirst(cell);
108105

109-
next=lnext(cell);
110106
if (!cache->hot_cache)
111107
{
112108
avc_slots[index]
113-
=list_delete_cell(avc_slots[index],cell,prev);
109+
=foreach_delete_current(avc_slots[index],cell);
114110

115111
pfree(cache->scontext);
116112
pfree(cache->tcontext);
@@ -123,7 +119,6 @@ sepgsql_avc_reclaim(void)
123119
else
124120
{
125121
cache->hot_cache= false;
126-
prev=cell;
127122
}
128123
}
129124
avc_lru_hint= (avc_lru_hint+1) %AVC_NUM_SLOTS;

‎src/backend/access/common/printtup.c

Lines changed: 2 additions & 2 deletions
Original file line numberDiff line numberDiff line change
@@ -262,14 +262,14 @@ SendRowDescriptionCols_3(StringInfo buf, TupleDesc typeinfo, List *targetlist, i
262262
/* Do we have a non-resjunk tlist item? */
263263
while (tlist_item&&
264264
((TargetEntry*)lfirst(tlist_item))->resjunk)
265-
tlist_item=lnext(tlist_item);
265+
tlist_item=lnext(targetlist,tlist_item);
266266
if (tlist_item)
267267
{
268268
TargetEntry*tle= (TargetEntry*)lfirst(tlist_item);
269269

270270
resorigtbl=tle->resorigtbl;
271271
resorigcol=tle->resorigcol;
272-
tlist_item=lnext(tlist_item);
272+
tlist_item=lnext(targetlist,tlist_item);
273273
}
274274
else
275275
{

‎src/backend/catalog/heap.c

Lines changed: 1 addition & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -3420,7 +3420,7 @@ insert_ordered_unique_oid(List *list, Oid datum)
34203420
prev=list_head(list);
34213421
for (;;)
34223422
{
3423-
ListCell*curr=lnext(prev);
3423+
ListCell*curr=lnext(list,prev);
34243424

34253425
if (curr==NULL||datum<lfirst_oid(curr))
34263426
break;/* it belongs after 'prev', before 'curr' */

‎src/backend/catalog/index.c

Lines changed: 3 additions & 3 deletions
Original file line numberDiff line numberDiff line change
@@ -347,7 +347,7 @@ ConstructTupleDescriptor(Relation heapRelation,
347347
if (indexpr_item==NULL)/* shouldn't happen */
348348
elog(ERROR,"too few entries in indexprs list");
349349
indexkey= (Node*)lfirst(indexpr_item);
350-
indexpr_item=lnext(indexpr_item);
350+
indexpr_item=lnext(indexInfo->ii_Expressions,indexpr_item);
351351

352352
/*
353353
* Lookup the expression type in pg_type for the type length etc.
@@ -397,7 +397,7 @@ ConstructTupleDescriptor(Relation heapRelation,
397397
if (colnames_item==NULL)/* shouldn't happen */
398398
elog(ERROR,"too few entries in colnames list");
399399
namestrcpy(&to->attname, (constchar*)lfirst(colnames_item));
400-
colnames_item=lnext(colnames_item);
400+
colnames_item=lnext(indexColNames,colnames_item);
401401

402402
/*
403403
* Check the opclass and index AM to see if either provides a keytype
@@ -2465,7 +2465,7 @@ FormIndexDatum(IndexInfo *indexInfo,
24652465
iDatum=ExecEvalExprSwitchContext((ExprState*)lfirst(indexpr_item),
24662466
GetPerTupleExprContext(estate),
24672467
&isNull);
2468-
indexpr_item=lnext(indexpr_item);
2468+
indexpr_item=lnext(indexInfo->ii_ExpressionsState,indexpr_item);
24692469
}
24702470
values[i]=iDatum;
24712471
isnull[i]=isNull;

‎src/backend/catalog/namespace.c

Lines changed: 3 additions & 3 deletions
Original file line numberDiff line numberDiff line change
@@ -3402,15 +3402,15 @@ OverrideSearchPathMatchesCurrent(OverrideSearchPath *path)
34023402
if (path->addTemp)
34033403
{
34043404
if (lc&&lfirst_oid(lc)==myTempNamespace)
3405-
lc=lnext(lc);
3405+
lc=lnext(activeSearchPath,lc);
34063406
else
34073407
return false;
34083408
}
34093409
/* If path->addCatalog, next item should be pg_catalog. */
34103410
if (path->addCatalog)
34113411
{
34123412
if (lc&&lfirst_oid(lc)==PG_CATALOG_NAMESPACE)
3413-
lc=lnext(lc);
3413+
lc=lnext(activeSearchPath,lc);
34143414
else
34153415
return false;
34163416
}
@@ -3421,7 +3421,7 @@ OverrideSearchPathMatchesCurrent(OverrideSearchPath *path)
34213421
foreach(lcp,path->schemas)
34223422
{
34233423
if (lc&&lfirst_oid(lc)==lfirst_oid(lcp))
3424-
lc=lnext(lc);
3424+
lc=lnext(activeSearchPath,lc);
34253425
else
34263426
return false;
34273427
}

‎src/backend/catalog/partition.c

Lines changed: 1 addition & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -275,7 +275,7 @@ has_partition_attrs(Relation rel, Bitmapset *attnums, bool *used_in_expr)
275275

276276
/* Find all attributes referenced */
277277
pull_varattnos(expr,1,&expr_attrs);
278-
partexprs_item=lnext(partexprs_item);
278+
partexprs_item=lnext(partexprs,partexprs_item);
279279

280280
if (bms_overlap(attnums,expr_attrs))
281281
{

‎src/backend/catalog/pg_inherits.c

Lines changed: 10 additions & 4 deletions
Original file line numberDiff line numberDiff line change
@@ -37,7 +37,7 @@
3737
typedefstructSeenRelsEntry
3838
{
3939
Oidrel_id;/* relation oid */
40-
ListCell*numparents_cell;/*corresponding list cell */
40+
intlist_index;/*its position in output list(s) */
4141
}SeenRelsEntry;
4242

4343
/*
@@ -186,7 +186,9 @@ find_all_inheritors(Oid parentrelId, LOCKMODE lockmode, List **numparents)
186186
* indirect children. We can use a single list as both the record of
187187
* already-found rels and the agenda of rels yet to be scanned for more
188188
* children. This is a bit tricky but works because the foreach() macro
189-
* doesn't fetch the next list element until the bottom of the loop.
189+
* doesn't fetch the next list element until the bottom of the loop. Note
190+
* that we can't keep pointers into the output lists; but an index is
191+
* sufficient.
190192
*/
191193
rels_list=list_make1_oid(parentrelId);
192194
rel_numparents=list_make1_int(0);
@@ -217,14 +219,18 @@ find_all_inheritors(Oid parentrelId, LOCKMODE lockmode, List **numparents)
217219
if (found)
218220
{
219221
/* if the rel is already there, bump number-of-parents counter */
220-
lfirst_int(hash_entry->numparents_cell)++;
222+
ListCell*numparents_cell;
223+
224+
numparents_cell=list_nth_cell(rel_numparents,
225+
hash_entry->list_index);
226+
lfirst_int(numparents_cell)++;
221227
}
222228
else
223229
{
224230
/* if it's not there, add it. expect 1 parent, initially. */
231+
hash_entry->list_index=list_length(rels_list);
225232
rels_list=lappend_oid(rels_list,child_oid);
226233
rel_numparents=lappend_int(rel_numparents,1);
227-
hash_entry->numparents_cell=rel_numparents->tail;
228234
}
229235
}
230236
}

‎src/backend/catalog/pg_proc.c

Lines changed: 4 additions & 6 deletions
Original file line numberDiff line numberDiff line change
@@ -538,11 +538,9 @@ ProcedureCreate(const char *procedureName,
538538
Assert(list_length(oldDefaults)==oldproc->pronargdefaults);
539539

540540
/* new list can have more defaults than old, advance over 'em */
541-
newlc=list_head(parameterDefaults);
542-
for (i=list_length(parameterDefaults)-oldproc->pronargdefaults;
543-
i>0;
544-
i--)
545-
newlc=lnext(newlc);
541+
newlc=list_nth_cell(parameterDefaults,
542+
list_length(parameterDefaults)-
543+
oldproc->pronargdefaults);
546544

547545
foreach(oldlc,oldDefaults)
548546
{
@@ -557,7 +555,7 @@ ProcedureCreate(const char *procedureName,
557555
errhint("Use %s %s first.",
558556
dropcmd,
559557
format_procedure(oldproc->oid))));
560-
newlc=lnext(newlc);
558+
newlc=lnext(parameterDefaults,newlc);
561559
}
562560
}
563561

‎src/backend/catalog/pg_publication.c

Lines changed: 4 additions & 8 deletions
Original file line numberDiff line numberDiff line change
@@ -481,7 +481,6 @@ pg_get_publication_tables(PG_FUNCTION_ARGS)
481481
char*pubname=text_to_cstring(PG_GETARG_TEXT_PP(0));
482482
Publication*publication;
483483
List*tables;
484-
ListCell**lcp;
485484

486485
/* stuff done only on the first call of the function */
487486
if (SRF_IS_FIRSTCALL())
@@ -499,22 +498,19 @@ pg_get_publication_tables(PG_FUNCTION_ARGS)
499498
tables=GetAllTablesPublicationRelations();
500499
else
501500
tables=GetPublicationRelations(publication->oid);
502-
lcp= (ListCell**)palloc(sizeof(ListCell*));
503-
*lcp=list_head(tables);
504-
funcctx->user_fctx= (void*)lcp;
501+
funcctx->user_fctx= (void*)tables;
505502

506503
MemoryContextSwitchTo(oldcontext);
507504
}
508505

509506
/* stuff done on every call of the function */
510507
funcctx=SRF_PERCALL_SETUP();
511-
lcp= (ListCell**)funcctx->user_fctx;
508+
tables= (List*)funcctx->user_fctx;
512509

513-
while (*lcp!=NULL)
510+
if (funcctx->call_cntr<list_length(tables))
514511
{
515-
Oidrelid=lfirst_oid(*lcp);
512+
Oidrelid=list_nth_oid(tables,funcctx->call_cntr);
516513

517-
*lcp=lnext(*lcp);
518514
SRF_RETURN_NEXT(funcctx,ObjectIdGetDatum(relid));
519515
}
520516

‎src/backend/commands/analyze.c

Lines changed: 2 additions & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -455,7 +455,8 @@ do_analyze_rel(Relation onerel, VacuumParams *params,
455455
if (indexpr_item==NULL)/* shouldn't happen */
456456
elog(ERROR,"too few entries in indexprs list");
457457
indexkey= (Node*)lfirst(indexpr_item);
458-
indexpr_item=lnext(indexpr_item);
458+
indexpr_item=lnext(indexInfo->ii_Expressions,
459+
indexpr_item);
459460
thisdata->vacattrstats[tcnt]=
460461
examine_attribute(Irel[ind],i+1,indexkey);
461462
if (thisdata->vacattrstats[tcnt]!=NULL)

0 commit comments

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