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

Commit4b31063

Browse files
committed
Fix broken Bitmapset optimization in DiscreteKnapsack()
Some code in DiscreteKnapsack() attempted to zero all words in aBitmapset by performing bms_del_members() to delete all the members fromitself before replacing those members with members from another set.When that code was written, this was a valid way to manipulate the setin such a way to save from palloc having to be called to allocate a newBitmapset. However,00b4146 modified Bitmapsets so that an empty set is*always* represented as NULL and this breaks the optimization as theBitmapset code will always pfree the memory when the set becomes empty.Since DiscreteKnapsack() has been coded to avoid as many unneededallocations as possible, it seems risky to not fix this. Here we addbms_replace_members() to effectively perform an in-place copy of anotherset, reusing the memory of the existing set, when possible.This got broken in v16, but no backpatch for now as there've been nocomplaints.Reviewed-by: Richard GuoDiscussion:https://postgr.es/m/CAApHDvoTCBkBU2PJghNOFUiO0q=QP4WAWHi5sJP6_4=b2WodrA@mail.gmail.com
1 parent57b440e commit4b31063

File tree

3 files changed

+46
-4
lines changed

3 files changed

+46
-4
lines changed

‎src/backend/lib/knapsack.c

Lines changed: 1 addition & 4 deletions
Original file line numberDiff line numberDiff line change
@@ -89,10 +89,7 @@ DiscreteKnapsack(int max_weight, int num_items,
8989
{
9090
/* copy sets[ow] to sets[j] without realloc */
9191
if (j!=ow)
92-
{
93-
sets[j]=bms_del_members(sets[j],sets[j]);
94-
sets[j]=bms_add_members(sets[j],sets[ow]);
95-
}
92+
sets[j]=bms_replace_members(sets[j],sets[ow]);
9693

9794
sets[j]=bms_add_member(sets[j],i);
9895

‎src/backend/nodes/bitmapset.c

Lines changed: 44 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -976,6 +976,50 @@ bms_add_members(Bitmapset *a, const Bitmapset *b)
976976
returnresult;
977977
}
978978

979+
/*
980+
* bms_replace_members
981+
*Remove all existing members from 'a' and repopulate the set with members
982+
*from 'b', recycling 'a', when possible.
983+
*/
984+
Bitmapset*
985+
bms_replace_members(Bitmapset*a,constBitmapset*b)
986+
{
987+
inti;
988+
989+
Assert(bms_is_valid_set(a));
990+
Assert(bms_is_valid_set(b));
991+
992+
if (a==NULL)
993+
returnbms_copy(b);
994+
if (b==NULL)
995+
{
996+
pfree(a);
997+
returnNULL;
998+
}
999+
1000+
if (a->nwords<b->nwords)
1001+
a= (Bitmapset*)repalloc(a,BITMAPSET_SIZE(b->nwords));
1002+
1003+
i=0;
1004+
do
1005+
{
1006+
a->words[i]=b->words[i];
1007+
}while (++i<b->nwords);
1008+
1009+
a->nwords=b->nwords;
1010+
1011+
#ifdefREALLOCATE_BITMAPSETS
1012+
1013+
/*
1014+
* There's no guarantee that the repalloc returned a new pointer, so copy
1015+
* and free unconditionally here.
1016+
*/
1017+
a=bms_copy_and_free(a);
1018+
#endif
1019+
1020+
returna;
1021+
}
1022+
9791023
/*
9801024
* bms_add_range
9811025
*Add members in the range of 'lower' to 'upper' to the set.

‎src/include/nodes/bitmapset.h

Lines changed: 1 addition & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -109,6 +109,7 @@ extern BMS_Membership bms_membership(const Bitmapset *a);
109109
externBitmapset*bms_add_member(Bitmapset*a,intx);
110110
externBitmapset*bms_del_member(Bitmapset*a,intx);
111111
externBitmapset*bms_add_members(Bitmapset*a,constBitmapset*b);
112+
externBitmapset*bms_replace_members(Bitmapset*a,constBitmapset*b);
112113
externBitmapset*bms_add_range(Bitmapset*a,intlower,intupper);
113114
externBitmapset*bms_int_members(Bitmapset*a,constBitmapset*b);
114115
externBitmapset*bms_del_members(Bitmapset*a,constBitmapset*b);

0 commit comments

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