Making empty Bitmapsets always be NULL
When I designed the Bitmapset module, I set things up so that an empty
Bitmapset could be represented either by a NULL pointer, or by an
allocated object all of whose bits are zero. I've recently come to
the conclusion that that was a bad idea and we should instead have
a convention like the longstanding invariant for Lists: an empty
list is represented by NIL and nothing else.
To do this, we need to fix bms_intersect, bms_difference, and a couple
of other functions to check for having produced an empty result; but
then we can replace bms_is_empty() by a simple NULL test. I originally
guessed that that would be a bad tradeoff, but now I think it likely
is a win performance-wise, because we call bms_is_empty() many more
times than those other functions put together.
However, any performance gain would likely be marginal; the real
reason why I'm pushing this is that we have various places that have
hand-implemented a rule about "this Bitmapset variable must be exactly
NULL if empty", so that they can use checks-for-null in place of
bms_is_empty() calls in particularly hot code paths. That is a really
fragile, mistake-prone way to do things, and I'm surprised that we've
seldom been bitten by it. It's not well documented at all which
variables have this property, so you can't readily tell which code
might be violating those conventions.
So basically I'd like to establish that convention everywhere and
get rid of these ad-hoc reduce-to-NULL checks. I put together the
attached draft patch to do so. I've not done any hard performance
testing on it --- I did do one benchmark that showed maybe 0.8%
speedup, but I'd regard that as below the noise.
I found just a few places that have issues with this idea. One thing
that is problematic is bms_first_member(): assuming you allow it to
loop to completion, it ends with the passed Bitmapset being empty,
which is now an invariant violation. I made it pfree the argument
at that point, and fixed a couple of callers that would be broken
thereby; but I wonder if it wouldn't be better to get rid of that
function entirely and convert all its callers to use bms_next_member.
There are only about half a dozen.
I also discovered that nodeAppend.c is relying on bms_del_members
not reducing a non-empty set to NULL, because it uses the nullness
of appendstate->as_valid_subplans as a state boolean. That was
probably acceptable when it was written, but whoever added
classify_matching_subplans made a hash of the state invariants here,
because that can set as_valid_subplans to empty. I added a separate
boolean as an easy way out, but maybe that code could do with a more
thorough revisit.
I'll add this to the about-to-start CF.
regards, tom lane
Attachments:
v1-make-empty-bitmapsets-always-be-NULL.patchtext/x-diff; charset=us-ascii; name=v1-make-empty-bitmapsets-always-be-NULL.patchDownload
diff --git a/src/backend/access/heap/heapam.c b/src/backend/access/heap/heapam.c
index 7eb79cee58..a5d74cc462 100644
--- a/src/backend/access/heap/heapam.c
+++ b/src/backend/access/heap/heapam.c
@@ -3046,6 +3046,7 @@ heap_update(Relation relation, ItemPointer otid, HeapTuple newtup,
modified_attrs = HeapDetermineColumnsInfo(relation, interesting_attrs,
id_attrs, &oldtup,
newtup, &id_has_external);
+ interesting_attrs = NULL; /* don't try to free it again */
/*
* If we're not updating any "key" column, we can grab a weaker lock type.
@@ -3860,8 +3861,9 @@ heap_attr_equals(TupleDesc tupdesc, int attrnum, Datum value1, Datum value2,
* listed as interesting) of the old tuple is a member of external_cols and is
* stored externally.
*
- * The input interesting_cols bitmapset is destructively modified; that is OK
- * since this is invoked at most once in heap_update.
+ * The input interesting_cols bitmapset is destructively modified, and freed
+ * before we return; that is OK since this is invoked at most once in
+ * heap_update.
*/
static Bitmapset *
HeapDetermineColumnsInfo(Relation relation,
diff --git a/src/backend/executor/execUtils.c b/src/backend/executor/execUtils.c
index c33a3c0bec..cfa95a07e4 100644
--- a/src/backend/executor/execUtils.c
+++ b/src/backend/executor/execUtils.c
@@ -877,15 +877,7 @@ UpdateChangedParamSet(PlanState *node, Bitmapset *newchg)
* include anything else into its chgParam set.
*/
parmset = bms_intersect(node->plan->allParam, newchg);
-
- /*
- * Keep node->chgParam == NULL if there's not actually any members; this
- * allows the simplest possible tests in executor node files.
- */
- if (!bms_is_empty(parmset))
- node->chgParam = bms_join(node->chgParam, parmset);
- else
- bms_free(parmset);
+ node->chgParam = bms_join(node->chgParam, parmset);
}
/*
diff --git a/src/backend/executor/nodeAgg.c b/src/backend/executor/nodeAgg.c
index 20d23696a5..51a30ddf65 100644
--- a/src/backend/executor/nodeAgg.c
+++ b/src/backend/executor/nodeAgg.c
@@ -1642,7 +1642,7 @@ find_hash_columns(AggState *aggstate)
perhash->hashGrpColIdxHash[i] = i + 1;
perhash->numhashGrpCols++;
/* delete already mapped columns */
- bms_del_member(colnos, grpColIdx[i]);
+ colnos = bms_del_member(colnos, grpColIdx[i]);
}
/* and add the remaining columns */
@@ -1673,7 +1673,6 @@ find_hash_columns(AggState *aggstate)
&TTSOpsMinimalTuple);
list_free(hashTlist);
- bms_free(colnos);
}
bms_free(base_colnos);
diff --git a/src/backend/executor/nodeAppend.c b/src/backend/executor/nodeAppend.c
index cb25499b3f..c185b11c67 100644
--- a/src/backend/executor/nodeAppend.c
+++ b/src/backend/executor/nodeAppend.c
@@ -157,7 +157,10 @@ ExecInitAppend(Append *node, EState *estate, int eflags)
* later calls to ExecFindMatchingSubPlans.
*/
if (!prunestate->do_exec_prune && nplans > 0)
+ {
appendstate->as_valid_subplans = bms_add_range(NULL, 0, nplans - 1);
+ appendstate->as_valid_subplans_identified = true;
+ }
}
else
{
@@ -170,6 +173,7 @@ ExecInitAppend(Append *node, EState *estate, int eflags)
Assert(nplans > 0);
appendstate->as_valid_subplans = validsubplans =
bms_add_range(NULL, 0, nplans - 1);
+ appendstate->as_valid_subplans_identified = true;
appendstate->as_prune_state = NULL;
}
@@ -259,7 +263,7 @@ ExecInitAppend(Append *node, EState *estate, int eflags)
appendstate->as_asyncresults = (TupleTableSlot **)
palloc0(nasyncplans * sizeof(TupleTableSlot *));
- if (appendstate->as_valid_subplans != NULL)
+ if (appendstate->as_valid_subplans_identified)
classify_matching_subplans(appendstate);
}
@@ -414,13 +418,11 @@ ExecReScanAppend(AppendState *node)
bms_overlap(node->ps.chgParam,
node->as_prune_state->execparamids))
{
+ node->as_valid_subplans_identified = false;
bms_free(node->as_valid_subplans);
node->as_valid_subplans = NULL;
- if (nasyncplans > 0)
- {
- bms_free(node->as_valid_asyncplans);
- node->as_valid_asyncplans = NULL;
- }
+ bms_free(node->as_valid_asyncplans);
+ node->as_valid_asyncplans = NULL;
}
for (i = 0; i < node->as_nplans; i++)
@@ -574,11 +576,14 @@ choose_next_subplan_locally(AppendState *node)
if (node->as_nasyncplans > 0)
{
/* We'd have filled as_valid_subplans already */
- Assert(node->as_valid_subplans);
+ Assert(node->as_valid_subplans_identified);
}
- else if (node->as_valid_subplans == NULL)
+ else if (!node->as_valid_subplans_identified)
+ {
node->as_valid_subplans =
ExecFindMatchingSubPlans(node->as_prune_state, false);
+ node->as_valid_subplans_identified = true;
+ }
whichplan = -1;
}
@@ -640,10 +645,11 @@ choose_next_subplan_for_leader(AppendState *node)
* run-time pruning is disabled then the valid subplans will always be
* set to all subplans.
*/
- if (node->as_valid_subplans == NULL)
+ if (!node->as_valid_subplans_identified)
{
node->as_valid_subplans =
ExecFindMatchingSubPlans(node->as_prune_state, false);
+ node->as_valid_subplans_identified = true;
/*
* Mark each invalid plan as finished to allow the loop below to
@@ -715,10 +721,12 @@ choose_next_subplan_for_worker(AppendState *node)
* run-time pruning is disabled then the valid subplans will always be set
* to all subplans.
*/
- else if (node->as_valid_subplans == NULL)
+ else if (!node->as_valid_subplans_identified)
{
node->as_valid_subplans =
ExecFindMatchingSubPlans(node->as_prune_state, false);
+ node->as_valid_subplans_identified = true;
+
mark_invalid_subplans_as_finished(node);
}
@@ -866,10 +874,11 @@ ExecAppendAsyncBegin(AppendState *node)
Assert(node->as_nasyncplans > 0);
/* If we've yet to determine the valid subplans then do so now. */
- if (node->as_valid_subplans == NULL)
+ if (!node->as_valid_subplans_identified)
{
node->as_valid_subplans =
ExecFindMatchingSubPlans(node->as_prune_state, false);
+ node->as_valid_subplans_identified = true;
classify_matching_subplans(node);
}
@@ -1143,6 +1152,7 @@ classify_matching_subplans(AppendState *node)
{
Bitmapset *valid_asyncplans;
+ Assert(node->as_valid_subplans_identified);
Assert(node->as_valid_asyncplans == NULL);
/* Nothing to do if there are no valid subplans. */
@@ -1161,9 +1171,8 @@ classify_matching_subplans(AppendState *node)
}
/* Get valid async subplans. */
- valid_asyncplans = bms_copy(node->as_asyncplans);
- valid_asyncplans = bms_int_members(valid_asyncplans,
- node->as_valid_subplans);
+ valid_asyncplans = bms_intersect(node->as_asyncplans,
+ node->as_valid_subplans);
/* Adjust the valid subplans to contain sync subplans only. */
node->as_valid_subplans = bms_del_members(node->as_valid_subplans,
diff --git a/src/backend/nodes/bitmapset.c b/src/backend/nodes/bitmapset.c
index 98660524ad..af62a85980 100644
--- a/src/backend/nodes/bitmapset.c
+++ b/src/backend/nodes/bitmapset.c
@@ -5,10 +5,8 @@
*
* A bitmap set can represent any set of nonnegative integers, although
* it is mainly intended for sets where the maximum value is not large,
- * say at most a few hundred. By convention, a NULL pointer is always
- * accepted by all operations to represent the empty set. (But beware
- * that this is not the only representation of the empty set. Use
- * bms_is_empty() in preference to testing for NULL.)
+ * say at most a few hundred. By convention, we always represent the
+ * empty set by a NULL pointer.
*
*
* Copyright (c) 2003-2023, PostgreSQL Global Development Group
@@ -66,6 +64,8 @@
#error "invalid BITS_PER_BITMAPWORD"
#endif
+static bool bms_is_empty_internal(const Bitmapset *a);
+
/*
* bms_copy - make a palloc'd copy of a bitmapset
@@ -104,10 +104,10 @@ bms_equal(const Bitmapset *a, const Bitmapset *b)
{
if (b == NULL)
return true;
- return bms_is_empty(b);
+ return false;
}
else if (b == NULL)
- return bms_is_empty(a);
+ return false;
/* Identify shorter and longer input */
if (a->nwords <= b->nwords)
{
@@ -151,9 +151,9 @@ bms_compare(const Bitmapset *a, const Bitmapset *b)
/* Handle cases where either input is NULL */
if (a == NULL)
- return bms_is_empty(b) ? 0 : -1;
+ return (b == NULL) ? 0 : -1;
else if (b == NULL)
- return bms_is_empty(a) ? 0 : +1;
+ return +1;
/* Handle cases where one input is longer than the other */
shortlen = Min(a->nwords, b->nwords);
for (i = shortlen; i < a->nwords; i++)
@@ -282,6 +282,12 @@ bms_intersect(const Bitmapset *a, const Bitmapset *b)
resultlen = result->nwords;
for (i = 0; i < resultlen; i++)
result->words[i] &= other->words[i];
+ /* If we computed an empty result, we must return NULL */
+ if (bms_is_empty_internal(result))
+ {
+ pfree(result);
+ return NULL;
+ }
return result;
}
@@ -300,12 +306,22 @@ bms_difference(const Bitmapset *a, const Bitmapset *b)
return NULL;
if (b == NULL)
return bms_copy(a);
+
+ /*
+ * In Postgres' usage, an empty result is a very common case, so it's
+ * worth optimizing for that by testing bms_nonempty_difference(). This
+ * saves us a palloc/pfree cycle compared to checking after-the-fact.
+ */
+ if (!bms_nonempty_difference(a, b))
+ return NULL;
+
/* Copy the left input */
result = bms_copy(a);
/* And remove b's bits from result */
shortlen = Min(a->nwords, b->nwords);
for (i = 0; i < shortlen; i++)
result->words[i] &= ~b->words[i];
+ /* Need not check for empty result, since we handled that case above */
return result;
}
@@ -323,7 +339,7 @@ bms_is_subset(const Bitmapset *a, const Bitmapset *b)
if (a == NULL)
return true; /* empty set is a subset of anything */
if (b == NULL)
- return bms_is_empty(a);
+ return false;
/* Check common words */
shortlen = Min(a->nwords, b->nwords);
for (i = 0; i < shortlen; i++)
@@ -362,10 +378,10 @@ bms_subset_compare(const Bitmapset *a, const Bitmapset *b)
{
if (b == NULL)
return BMS_EQUAL;
- return bms_is_empty(b) ? BMS_EQUAL : BMS_SUBSET1;
+ return BMS_SUBSET1;
}
if (b == NULL)
- return bms_is_empty(a) ? BMS_EQUAL : BMS_SUBSET2;
+ return BMS_SUBSET2;
/* Check common words */
result = BMS_EQUAL; /* status so far */
shortlen = Min(a->nwords, b->nwords);
@@ -554,7 +570,7 @@ bms_nonempty_difference(const Bitmapset *a, const Bitmapset *b)
if (a == NULL)
return false;
if (b == NULL)
- return !bms_is_empty(a);
+ return true;
/* Check words in common */
shortlen = Min(a->nwords, b->nwords);
for (i = 0; i < shortlen; i++)
@@ -696,12 +712,13 @@ bms_membership(const Bitmapset *a)
}
/*
- * bms_is_empty - is a set empty?
+ * bms_is_empty_internal - is a set empty?
*
- * This is even faster than bms_membership().
+ * This is now used only locally, to detect cases where a function has
+ * computed an empty set that we must now get rid of.
*/
-bool
-bms_is_empty(const Bitmapset *a)
+static bool
+bms_is_empty_internal(const Bitmapset *a)
{
int nwords;
int wordnum;
@@ -786,6 +803,12 @@ bms_del_member(Bitmapset *a, int x)
bitnum = BITNUM(x);
if (wordnum < a->nwords)
a->words[wordnum] &= ~((bitmapword) 1 << bitnum);
+ /* If we computed an empty result, we must return NULL */
+ if (bms_is_empty_internal(a))
+ {
+ pfree(a);
+ return NULL;
+ }
return a;
}
@@ -922,6 +945,12 @@ bms_int_members(Bitmapset *a, const Bitmapset *b)
a->words[i] &= b->words[i];
for (; i < a->nwords; i++)
a->words[i] = 0;
+ /* If we computed an empty result, we must return NULL */
+ if (bms_is_empty_internal(a))
+ {
+ pfree(a);
+ return NULL;
+ }
return a;
}
@@ -943,6 +972,12 @@ bms_del_members(Bitmapset *a, const Bitmapset *b)
shortlen = Min(a->nwords, b->nwords);
for (i = 0; i < shortlen; i++)
a->words[i] &= ~b->words[i];
+ /* If we computed an empty result, we must return NULL */
+ if (bms_is_empty_internal(a))
+ {
+ pfree(a);
+ return NULL;
+ }
return a;
}
@@ -985,7 +1020,8 @@ bms_join(Bitmapset *a, Bitmapset *b)
/*
* bms_first_member - find and remove first member of a set
*
- * Returns -1 if set is empty. NB: set is destructively modified!
+ * Returns -1 if set is empty.
+ * NB: set is destructively modified, and will be freed once empty!
*
* This is intended as support for iterating through the members of a set.
* The typical pattern is
@@ -1021,6 +1057,8 @@ bms_first_member(Bitmapset *a)
return result;
}
}
+ /* Set is now empty, so it violates the empty-set invariant */
+ pfree(a);
return -1;
}
diff --git a/src/backend/optimizer/path/indxpath.c b/src/backend/optimizer/path/indxpath.c
index 011a0337da..9f4698f2a2 100644
--- a/src/backend/optimizer/path/indxpath.c
+++ b/src/backend/optimizer/path/indxpath.c
@@ -949,9 +949,6 @@ build_index_paths(PlannerInfo *root, RelOptInfo *rel,
/* We do not want the index's rel itself listed in outer_relids */
outer_relids = bms_del_member(outer_relids, rel->relid);
- /* Enforce convention that outer_relids is exactly NULL if empty */
- if (bms_is_empty(outer_relids))
- outer_relids = NULL;
/* Compute loop_count for cost estimation purposes */
loop_count = get_loop_count(root, rel->relid, outer_relids);
diff --git a/src/backend/optimizer/plan/subselect.c b/src/backend/optimizer/plan/subselect.c
index 04eda4798e..0956a33952 100644
--- a/src/backend/optimizer/plan/subselect.c
+++ b/src/backend/optimizer/plan/subselect.c
@@ -1486,7 +1486,6 @@ convert_EXISTS_sublink_to_join(PlannerInfo *root, SubLink *sublink,
if (varno <= rtoffset)
upper_varnos = bms_add_member(upper_varnos, varno);
}
- bms_free(clause_varnos);
Assert(!bms_is_empty(upper_varnos));
/*
@@ -2824,15 +2823,6 @@ finalize_plan(PlannerInfo *root, Plan *plan,
/* but not any initplan setParams */
plan->extParam = bms_del_members(plan->extParam, initSetParam);
- /*
- * For speed at execution time, make sure extParam/allParam are actually
- * NULL if they are empty sets.
- */
- if (bms_is_empty(plan->extParam))
- plan->extParam = NULL;
- if (bms_is_empty(plan->allParam))
- plan->allParam = NULL;
-
return plan->allParam;
}
diff --git a/src/backend/optimizer/util/pathnode.c b/src/backend/optimizer/util/pathnode.c
index d749b50578..e8e06397a9 100644
--- a/src/backend/optimizer/util/pathnode.c
+++ b/src/backend/optimizer/util/pathnode.c
@@ -2372,12 +2372,6 @@ calc_nestloop_required_outer(Relids outerrelids,
/* ... and remove any mention of now-satisfied outer rels */
required_outer = bms_del_members(required_outer,
outerrelids);
- /* maintain invariant that required_outer is exactly NULL if empty */
- if (bms_is_empty(required_outer))
- {
- bms_free(required_outer);
- required_outer = NULL;
- }
return required_outer;
}
diff --git a/src/backend/optimizer/util/placeholder.c b/src/backend/optimizer/util/placeholder.c
index 9c6cb5eba7..b1723578e6 100644
--- a/src/backend/optimizer/util/placeholder.c
+++ b/src/backend/optimizer/util/placeholder.c
@@ -125,8 +125,6 @@ find_placeholder_info(PlannerInfo *root, PlaceHolderVar *phv)
*/
rels_used = pull_varnos(root, (Node *) phv->phexpr);
phinfo->ph_lateral = bms_difference(rels_used, phv->phrels);
- if (bms_is_empty(phinfo->ph_lateral))
- phinfo->ph_lateral = NULL; /* make it exactly NULL if empty */
phinfo->ph_eval_at = bms_int_members(rels_used, phv->phrels);
/* If no contained vars, force evaluation at syntactic location */
if (bms_is_empty(phinfo->ph_eval_at))
diff --git a/src/backend/optimizer/util/relnode.c b/src/backend/optimizer/util/relnode.c
index 9ad44a0508..68fd033595 100644
--- a/src/backend/optimizer/util/relnode.c
+++ b/src/backend/optimizer/util/relnode.c
@@ -772,8 +772,6 @@ build_join_rel(PlannerInfo *root,
*/
joinrel->direct_lateral_relids =
bms_del_members(joinrel->direct_lateral_relids, joinrel->relids);
- if (bms_is_empty(joinrel->direct_lateral_relids))
- joinrel->direct_lateral_relids = NULL;
/*
* Construct restrict and join clause lists for the new joinrel. (The
@@ -1024,11 +1022,6 @@ min_join_parameterization(PlannerInfo *root,
*/
result = bms_union(outer_rel->lateral_relids, inner_rel->lateral_relids);
result = bms_del_members(result, joinrelids);
-
- /* Maintain invariant that result is exactly NULL if empty */
- if (bms_is_empty(result))
- result = NULL;
-
return result;
}
diff --git a/src/backend/replication/logical/relation.c b/src/backend/replication/logical/relation.c
index 9f139c64db..7e32eee77e 100644
--- a/src/backend/replication/logical/relation.c
+++ b/src/backend/replication/logical/relation.c
@@ -214,6 +214,8 @@ logicalrep_rel_att_by_name(LogicalRepRelation *remoterel, const char *attname)
/*
* Report error with names of the missing local relation column(s), if any.
+ *
+ * Note that missingatts will be freed before we return.
*/
static void
logicalrep_report_missing_attrs(LogicalRepRelation *remoterel,
@@ -429,9 +431,6 @@ logicalrep_rel_open(LogicalRepRelId remoteid, LOCKMODE lockmode)
logicalrep_report_missing_attrs(remoterel, missingatts);
- /* be tidy */
- bms_free(missingatts);
-
/*
* Set if the table's replica identity is enough to apply
* update/delete.
diff --git a/src/backend/rewrite/rewriteManip.c b/src/backend/rewrite/rewriteManip.c
index 04718f66c0..d28d0da621 100644
--- a/src/backend/rewrite/rewriteManip.c
+++ b/src/backend/rewrite/rewriteManip.c
@@ -1247,16 +1247,11 @@ remove_nulling_relids_mutator(Node *node,
!bms_is_member(var->varno, context->except_relids) &&
bms_overlap(var->varnullingrels, context->removable_relids))
{
- Relids newnullingrels = bms_difference(var->varnullingrels,
- context->removable_relids);
-
- /* Micro-optimization: ensure nullingrels is NULL if empty */
- if (bms_is_empty(newnullingrels))
- newnullingrels = NULL;
/* Copy the Var ... */
var = copyObject(var);
/* ... and replace the copy's varnullingrels field */
- var->varnullingrels = newnullingrels;
+ var->varnullingrels = bms_difference(var->varnullingrels,
+ context->removable_relids);
return (Node *) var;
}
/* Otherwise fall through to copy the Var normally */
@@ -1268,26 +1263,20 @@ remove_nulling_relids_mutator(Node *node,
if (phv->phlevelsup == context->sublevels_up &&
!bms_overlap(phv->phrels, context->except_relids))
{
- Relids newnullingrels = bms_difference(phv->phnullingrels,
- context->removable_relids);
-
/*
- * Micro-optimization: ensure nullingrels is NULL if empty.
- *
* Note: it might seem desirable to remove the PHV altogether if
* phnullingrels goes to empty. Currently we dare not do that
* because we use PHVs in some cases to enforce separate identity
* of subexpressions; see wrap_non_vars usages in prepjointree.c.
*/
- if (bms_is_empty(newnullingrels))
- newnullingrels = NULL;
/* Copy the PlaceHolderVar and mutate what's below ... */
phv = (PlaceHolderVar *)
expression_tree_mutator(node,
remove_nulling_relids_mutator,
(void *) context);
/* ... and replace the copy's phnullingrels field */
- phv->phnullingrels = newnullingrels;
+ phv->phnullingrels = bms_difference(phv->phnullingrels,
+ context->removable_relids);
/* We must also update phrels, if it contains a removable RTI */
phv->phrels = bms_difference(phv->phrels,
context->removable_relids);
diff --git a/src/include/nodes/bitmapset.h b/src/include/nodes/bitmapset.h
index 3d2225e1ae..e1d6cabeba 100644
--- a/src/include/nodes/bitmapset.h
+++ b/src/include/nodes/bitmapset.h
@@ -5,10 +5,8 @@
*
* A bitmap set can represent any set of nonnegative integers, although
* it is mainly intended for sets where the maximum value is not large,
- * say at most a few hundred. By convention, a NULL pointer is always
- * accepted by all operations to represent the empty set. (But beware
- * that this is not the only representation of the empty set. Use
- * bms_is_empty() in preference to testing for NULL.)
+ * say at most a few hundred. By convention, we always represent the
+ * empty set by a NULL pointer.
*
*
* Copyright (c) 2003-2023, PostgreSQL Global Development Group
@@ -102,7 +100,9 @@ extern int bms_num_members(const Bitmapset *a);
/* optimized tests when we don't need to know exact membership count: */
extern BMS_Membership bms_membership(const Bitmapset *a);
-extern bool bms_is_empty(const Bitmapset *a);
+
+/* NULL is now the only allowed representation of an empty bitmapset */
+#define bms_is_empty(a) ((a) == NULL)
/* these routines recycle (modify or free) their non-const inputs: */
diff --git a/src/include/nodes/execnodes.h b/src/include/nodes/execnodes.h
index 20f4c8b35f..e7eb1e666f 100644
--- a/src/include/nodes/execnodes.h
+++ b/src/include/nodes/execnodes.h
@@ -1350,6 +1350,7 @@ struct AppendState
ParallelAppendState *as_pstate; /* parallel coordination info */
Size pstate_len; /* size of parallel coordination info */
struct PartitionPruneState *as_prune_state;
+ bool as_valid_subplans_identified; /* is as_valid_subplans valid? */
Bitmapset *as_valid_subplans;
Bitmapset *as_valid_asyncplans; /* valid asynchronous plans indexes */
bool (*choose_next_subplan) (AppendState *);
diff --git a/src/pl/plpgsql/src/pl_exec.c b/src/pl/plpgsql/src/pl_exec.c
index ffd6d2e3bc..b0a2cac227 100644
--- a/src/pl/plpgsql/src/pl_exec.c
+++ b/src/pl/plpgsql/src/pl_exec.c
@@ -6240,12 +6240,9 @@ setup_param_list(PLpgSQL_execstate *estate, PLpgSQL_expr *expr)
Assert(expr->plan != NULL);
/*
- * We only need a ParamListInfo if the expression has parameters. In
- * principle we should test with bms_is_empty(), but we use a not-null
- * test because it's faster. In current usage bits are never removed from
- * expr->paramnos, only added, so this test is correct anyway.
+ * We only need a ParamListInfo if the expression has parameters.
*/
- if (expr->paramnos)
+ if (!bms_is_empty(expr->paramnos))
{
/* Use the common ParamListInfo */
paramLI = estate->paramLI;
On Tue, Feb 28, 2023 at 04:59:48PM -0500, Tom Lane wrote:
When I designed the Bitmapset module, I set things up so that an empty
Bitmapset could be represented either by a NULL pointer, or by an
allocated object all of whose bits are zero. I've recently come to
the conclusion that that was a bad idea and we should instead have
a convention like the longstanding invariant for Lists: an empty
list is represented by NIL and nothing else.
+1
I found just a few places that have issues with this idea. One thing
that is problematic is bms_first_member(): assuming you allow it to
loop to completion, it ends with the passed Bitmapset being empty,
which is now an invariant violation. I made it pfree the argument
at that point, and fixed a couple of callers that would be broken
thereby; but I wonder if it wouldn't be better to get rid of that
function entirely and convert all its callers to use bms_next_member.
There are only about half a dozen.
Unless there is a way to avoid the invariant violation that doesn't involve
scanning the rest of the words before bms_first_member returns, +1 to
removing it. Perhaps we could add a num_members variable to the struct so
that we know right away when the set becomes empty. But maintaining that
might be more trouble than it's worth.
I also discovered that nodeAppend.c is relying on bms_del_members
not reducing a non-empty set to NULL, because it uses the nullness
of appendstate->as_valid_subplans as a state boolean. That was
probably acceptable when it was written, but whoever added
classify_matching_subplans made a hash of the state invariants here,
because that can set as_valid_subplans to empty. I added a separate
boolean as an easy way out, but maybe that code could do with a more
thorough revisit.
The separate boolean certainly seems less fragile. That might even be
worthwhile independent of the rest of the patch.
--
Nathan Bossart
Amazon Web Services: https://aws.amazon.com
On Tue, Feb 28, 2023 at 1:59 PM Tom Lane <tgl@sss.pgh.pa.us> wrote:
I also discovered that nodeAppend.c is relying on bms_del_members
not reducing a non-empty set to NULL, because it uses the nullness
of appendstate->as_valid_subplans as a state boolean.
I seem to recall that Deep and I tripped into this during the zedstore
column projection work. I think we started out using NULL as a
sentinel value for our bitmaps, too, and it looked like it worked,
until it didn't... so +1 to the simplification.
--Jacob
Nathan Bossart <nathandbossart@gmail.com> writes:
On Tue, Feb 28, 2023 at 04:59:48PM -0500, Tom Lane wrote:
When I designed the Bitmapset module, I set things up so that an empty
Bitmapset could be represented either by a NULL pointer, or by an
allocated object all of whose bits are zero. I've recently come to
the conclusion that that was a bad idea and we should instead have
a convention like the longstanding invariant for Lists: an empty
list is represented by NIL and nothing else.
+1
Thanks for looking at this.
Unless there is a way to avoid the invariant violation that doesn't involve
scanning the rest of the words before bms_first_member returns, +1 to
removing it. Perhaps we could add a num_members variable to the struct so
that we know right away when the set becomes empty. But maintaining that
might be more trouble than it's worth.
bms_first_member is definitely legacy code, so let's just get
rid of it. Done like that in 0001 below. (This was slightly more
complex than I foresaw, because some of the callers were modifying
the result variables. But they're probably cleaner this way anyway.)
I also discovered that nodeAppend.c is relying on bms_del_members
not reducing a non-empty set to NULL, because it uses the nullness
of appendstate->as_valid_subplans as a state boolean.
The separate boolean certainly seems less fragile. That might even be
worthwhile independent of the rest of the patch.
Yeah. I split out those executor fixes as 0002; 0003 is the changes
to bitmapsets proper, and then 0004 removes now-dead code.
regards, tom lane
Attachments:
v2-0001-Remove-bms_first_member.patchtext/x-diff; charset=us-ascii; name=v2-0001-Remove-bms_first_member.patchDownload
From b60df906e9894d061f3f37025b92c6b258e9c8fc Mon Sep 17 00:00:00 2001
From: Tom Lane <tgl@sss.pgh.pa.us>
Date: Wed, 1 Mar 2023 17:02:30 -0500
Subject: [PATCH v2 1/4] Remove bms_first_member().
This function has been semi-deprecated ever since we invented
bms_next_member(). Its habit of scribbling on the input bitmapset
isn't great, plus for sufficiently large bitmapsets it would take
O(N^2) time to complete a loop. Now we have the additional problem
that reducing the input to empty while leaving it still accessible
would violate a proposed invariant. So let's just get rid of it,
after updating the few extant callers to use bms_next_member().
Discussion: https://postgr.es/m/1159933.1677621588@sss.pgh.pa.us
---
contrib/file_fdw/file_fdw.c | 9 ++---
contrib/sepgsql/dml.c | 3 +-
src/backend/access/heap/heapam.c | 27 +++++---------
src/backend/executor/nodeAgg.c | 3 +-
src/backend/nodes/bitmapset.c | 42 ----------------------
src/backend/optimizer/plan/subselect.c | 3 +-
src/backend/parser/parse_expr.c | 2 +-
src/backend/replication/logical/relation.c | 3 +-
src/include/nodes/bitmapset.h | 1 -
9 files changed, 23 insertions(+), 70 deletions(-)
diff --git a/contrib/file_fdw/file_fdw.c b/contrib/file_fdw/file_fdw.c
index 8ccc167548..2d2b0b6a6b 100644
--- a/contrib/file_fdw/file_fdw.c
+++ b/contrib/file_fdw/file_fdw.c
@@ -858,7 +858,7 @@ check_selective_binary_conversion(RelOptInfo *baserel,
ListCell *lc;
Relation rel;
TupleDesc tupleDesc;
- AttrNumber attnum;
+ int attidx;
Bitmapset *attrs_used = NULL;
bool has_wholerow = false;
int numattrs;
@@ -901,10 +901,11 @@ check_selective_binary_conversion(RelOptInfo *baserel,
rel = table_open(foreigntableid, AccessShareLock);
tupleDesc = RelationGetDescr(rel);
- while ((attnum = bms_first_member(attrs_used)) >= 0)
+ attidx = -1;
+ while ((attidx = bms_next_member(attrs_used, attidx)) >= 0)
{
- /* Adjust for system attributes. */
- attnum += FirstLowInvalidHeapAttributeNumber;
+ /* attidx is zero-based, attnum is the normal attribute number */
+ AttrNumber attnum = attidx + FirstLowInvalidHeapAttributeNumber;
if (attnum == 0)
{
diff --git a/contrib/sepgsql/dml.c b/contrib/sepgsql/dml.c
index 3cc927c79e..8c8f6f1e3a 100644
--- a/contrib/sepgsql/dml.c
+++ b/contrib/sepgsql/dml.c
@@ -231,7 +231,8 @@ check_relation_privileges(Oid relOid,
updated = fixup_whole_row_references(relOid, updated);
columns = bms_union(selected, bms_union(inserted, updated));
- while ((index = bms_first_member(columns)) >= 0)
+ index = -1;
+ while ((index = bms_next_member(columns, index)) >= 0)
{
AttrNumber attnum;
uint32 column_perms = 0;
diff --git a/src/backend/access/heap/heapam.c b/src/backend/access/heap/heapam.c
index 7eb79cee58..a84290c434 100644
--- a/src/backend/access/heap/heapam.c
+++ b/src/backend/access/heap/heapam.c
@@ -3859,9 +3859,6 @@ heap_attr_equals(TupleDesc tupdesc, int attrnum, Datum value1, Datum value2,
* has_external indicates if any of the unmodified attributes (from those
* listed as interesting) of the old tuple is a member of external_cols and is
* stored externally.
- *
- * The input interesting_cols bitmapset is destructively modified; that is OK
- * since this is invoked at most once in heap_update.
*/
static Bitmapset *
HeapDetermineColumnsInfo(Relation relation,
@@ -3870,19 +3867,20 @@ HeapDetermineColumnsInfo(Relation relation,
HeapTuple oldtup, HeapTuple newtup,
bool *has_external)
{
- int attrnum;
+ int attidx;
Bitmapset *modified = NULL;
TupleDesc tupdesc = RelationGetDescr(relation);
- while ((attrnum = bms_first_member(interesting_cols)) >= 0)
+ attidx = -1;
+ while ((attidx = bms_next_member(interesting_cols, attidx)) >= 0)
{
+ /* attidx is zero-based, attrnum is the normal attribute number */
+ int attrnum = attidx + FirstLowInvalidHeapAttributeNumber;
Datum value1,
value2;
bool isnull1,
isnull2;
- attrnum += FirstLowInvalidHeapAttributeNumber;
-
/*
* If it's a whole-tuple reference, say "not equal". It's not really
* worth supporting this case, since it could only succeed after a
@@ -3890,9 +3888,7 @@ HeapDetermineColumnsInfo(Relation relation,
*/
if (attrnum == 0)
{
- modified = bms_add_member(modified,
- attrnum -
- FirstLowInvalidHeapAttributeNumber);
+ modified = bms_add_member(modified, attidx);
continue;
}
@@ -3905,9 +3901,7 @@ HeapDetermineColumnsInfo(Relation relation,
{
if (attrnum != TableOidAttributeNumber)
{
- modified = bms_add_member(modified,
- attrnum -
- FirstLowInvalidHeapAttributeNumber);
+ modified = bms_add_member(modified, attidx);
continue;
}
}
@@ -3924,9 +3918,7 @@ HeapDetermineColumnsInfo(Relation relation,
if (!heap_attr_equals(tupdesc, attrnum, value1,
value2, isnull1, isnull2))
{
- modified = bms_add_member(modified,
- attrnum -
- FirstLowInvalidHeapAttributeNumber);
+ modified = bms_add_member(modified, attidx);
continue;
}
@@ -3943,8 +3935,7 @@ HeapDetermineColumnsInfo(Relation relation,
* member of external_cols.
*/
if (VARATT_IS_EXTERNAL((struct varlena *) DatumGetPointer(value1)) &&
- bms_is_member(attrnum - FirstLowInvalidHeapAttributeNumber,
- external_cols))
+ bms_is_member(attidx, external_cols))
*has_external = true;
}
diff --git a/src/backend/executor/nodeAgg.c b/src/backend/executor/nodeAgg.c
index 20d23696a5..5960e4a6c1 100644
--- a/src/backend/executor/nodeAgg.c
+++ b/src/backend/executor/nodeAgg.c
@@ -1646,7 +1646,8 @@ find_hash_columns(AggState *aggstate)
}
/* and add the remaining columns */
- while ((i = bms_first_member(colnos)) >= 0)
+ i = -1;
+ while ((i = bms_next_member(colnos, i)) >= 0)
{
perhash->hashGrpColIdxInput[perhash->numhashGrpCols] = i;
perhash->numhashGrpCols++;
diff --git a/src/backend/nodes/bitmapset.c b/src/backend/nodes/bitmapset.c
index 98660524ad..10dbbdddf5 100644
--- a/src/backend/nodes/bitmapset.c
+++ b/src/backend/nodes/bitmapset.c
@@ -982,48 +982,6 @@ bms_join(Bitmapset *a, Bitmapset *b)
return result;
}
-/*
- * bms_first_member - find and remove first member of a set
- *
- * Returns -1 if set is empty. NB: set is destructively modified!
- *
- * This is intended as support for iterating through the members of a set.
- * The typical pattern is
- *
- * while ((x = bms_first_member(inputset)) >= 0)
- * process member x;
- *
- * CAUTION: this destroys the content of "inputset". If the set must
- * not be modified, use bms_next_member instead.
- */
-int
-bms_first_member(Bitmapset *a)
-{
- int nwords;
- int wordnum;
-
- if (a == NULL)
- return -1;
- nwords = a->nwords;
- for (wordnum = 0; wordnum < nwords; wordnum++)
- {
- bitmapword w = a->words[wordnum];
-
- if (w != 0)
- {
- int result;
-
- w = RIGHTMOST_ONE(w);
- a->words[wordnum] &= ~w;
-
- result = wordnum * BITS_PER_BITMAPWORD;
- result += bmw_rightmost_one_pos(w);
- return result;
- }
- }
- return -1;
-}
-
/*
* bms_next_member - find next member of a set
*
diff --git a/src/backend/optimizer/plan/subselect.c b/src/backend/optimizer/plan/subselect.c
index 04eda4798e..22ffe4ca42 100644
--- a/src/backend/optimizer/plan/subselect.c
+++ b/src/backend/optimizer/plan/subselect.c
@@ -1481,7 +1481,8 @@ convert_EXISTS_sublink_to_join(PlannerInfo *root, SubLink *sublink,
*/
clause_varnos = pull_varnos(root, whereClause);
upper_varnos = NULL;
- while ((varno = bms_first_member(clause_varnos)) >= 0)
+ varno = -1;
+ while ((varno = bms_next_member(clause_varnos, varno)) >= 0)
{
if (varno <= rtoffset)
upper_varnos = bms_add_member(upper_varnos, varno);
diff --git a/src/backend/parser/parse_expr.c b/src/backend/parser/parse_expr.c
index 7ff41acb84..78221d2e0f 100644
--- a/src/backend/parser/parse_expr.c
+++ b/src/backend/parser/parse_expr.c
@@ -2759,7 +2759,7 @@ make_row_comparison_op(ParseState *pstate, List *opname,
* them ... this coding arbitrarily picks the lowest btree strategy
* number.
*/
- i = bms_first_member(strats);
+ i = bms_next_member(strats, -1);
if (i < 0)
{
/* No common interpretation, so fail */
diff --git a/src/backend/replication/logical/relation.c b/src/backend/replication/logical/relation.c
index 9f139c64db..55bfa07871 100644
--- a/src/backend/replication/logical/relation.c
+++ b/src/backend/replication/logical/relation.c
@@ -227,7 +227,8 @@ logicalrep_report_missing_attrs(LogicalRepRelation *remoterel,
initStringInfo(&missingattsbuf);
- while ((i = bms_first_member(missingatts)) >= 0)
+ i = -1;
+ while ((i = bms_next_member(missingatts, i)) >= 0)
{
missingattcnt++;
if (missingattcnt == 1)
diff --git a/src/include/nodes/bitmapset.h b/src/include/nodes/bitmapset.h
index 3d2225e1ae..c344ac04be 100644
--- a/src/include/nodes/bitmapset.h
+++ b/src/include/nodes/bitmapset.h
@@ -115,7 +115,6 @@ extern Bitmapset *bms_del_members(Bitmapset *a, const Bitmapset *b);
extern Bitmapset *bms_join(Bitmapset *a, Bitmapset *b);
/* support for iterating through the integer elements of a set: */
-extern int bms_first_member(Bitmapset *a);
extern int bms_next_member(const Bitmapset *a, int prevbit);
extern int bms_prev_member(const Bitmapset *a, int prevbit);
--
2.31.1
v2-0002-Mop-up-some-undue-familiarity-with-the-innards-of.patchtext/x-diff; charset=us-ascii; name*0=v2-0002-Mop-up-some-undue-familiarity-with-the-innards-of.p; name*1=atchDownload
From 8a5e732157f5faaac234ea037998ac278721edef Mon Sep 17 00:00:00 2001
From: Tom Lane <tgl@sss.pgh.pa.us>
Date: Wed, 1 Mar 2023 17:27:34 -0500
Subject: [PATCH v2 2/4] Mop up some undue familiarity with the innards of
Bitmapsets.
nodeAppend.c used non-nullness of appendstate->as_valid_subplans as
a state flag to indicate whether it'd done ExecFindMatchingSubPlans
(or some sufficient approximation to that). This was pretty
questionable even in the beginning, since it wouldn't really work
right if there are no valid subplans. It got more questionable
after commit 27e1f1456 added logic that could reduce as_valid_subplans
to an empty set: at that point we were depending on unspecified
behavior of bms_del_members, namely that it'd not return an empty
set as NULL. It's about to start doing that, which breaks this
logic entirely. Hence, add a separate boolean flag to signal
whether as_valid_subplans has been computed.
Also fix a previously-cosmetic bug in nodeAgg.c, wherein it ignored
the return value of bms_del_member instead of updating its pointer.
Discussion: https://postgr.es/m/1159933.1677621588@sss.pgh.pa.us
---
src/backend/executor/nodeAgg.c | 2 +-
src/backend/executor/nodeAppend.c | 37 +++++++++++++++++++------------
src/include/nodes/execnodes.h | 1 +
3 files changed, 25 insertions(+), 15 deletions(-)
diff --git a/src/backend/executor/nodeAgg.c b/src/backend/executor/nodeAgg.c
index 5960e4a6c1..19342a420c 100644
--- a/src/backend/executor/nodeAgg.c
+++ b/src/backend/executor/nodeAgg.c
@@ -1642,7 +1642,7 @@ find_hash_columns(AggState *aggstate)
perhash->hashGrpColIdxHash[i] = i + 1;
perhash->numhashGrpCols++;
/* delete already mapped columns */
- bms_del_member(colnos, grpColIdx[i]);
+ colnos = bms_del_member(colnos, grpColIdx[i]);
}
/* and add the remaining columns */
diff --git a/src/backend/executor/nodeAppend.c b/src/backend/executor/nodeAppend.c
index cb25499b3f..c185b11c67 100644
--- a/src/backend/executor/nodeAppend.c
+++ b/src/backend/executor/nodeAppend.c
@@ -157,7 +157,10 @@ ExecInitAppend(Append *node, EState *estate, int eflags)
* later calls to ExecFindMatchingSubPlans.
*/
if (!prunestate->do_exec_prune && nplans > 0)
+ {
appendstate->as_valid_subplans = bms_add_range(NULL, 0, nplans - 1);
+ appendstate->as_valid_subplans_identified = true;
+ }
}
else
{
@@ -170,6 +173,7 @@ ExecInitAppend(Append *node, EState *estate, int eflags)
Assert(nplans > 0);
appendstate->as_valid_subplans = validsubplans =
bms_add_range(NULL, 0, nplans - 1);
+ appendstate->as_valid_subplans_identified = true;
appendstate->as_prune_state = NULL;
}
@@ -259,7 +263,7 @@ ExecInitAppend(Append *node, EState *estate, int eflags)
appendstate->as_asyncresults = (TupleTableSlot **)
palloc0(nasyncplans * sizeof(TupleTableSlot *));
- if (appendstate->as_valid_subplans != NULL)
+ if (appendstate->as_valid_subplans_identified)
classify_matching_subplans(appendstate);
}
@@ -414,13 +418,11 @@ ExecReScanAppend(AppendState *node)
bms_overlap(node->ps.chgParam,
node->as_prune_state->execparamids))
{
+ node->as_valid_subplans_identified = false;
bms_free(node->as_valid_subplans);
node->as_valid_subplans = NULL;
- if (nasyncplans > 0)
- {
- bms_free(node->as_valid_asyncplans);
- node->as_valid_asyncplans = NULL;
- }
+ bms_free(node->as_valid_asyncplans);
+ node->as_valid_asyncplans = NULL;
}
for (i = 0; i < node->as_nplans; i++)
@@ -574,11 +576,14 @@ choose_next_subplan_locally(AppendState *node)
if (node->as_nasyncplans > 0)
{
/* We'd have filled as_valid_subplans already */
- Assert(node->as_valid_subplans);
+ Assert(node->as_valid_subplans_identified);
}
- else if (node->as_valid_subplans == NULL)
+ else if (!node->as_valid_subplans_identified)
+ {
node->as_valid_subplans =
ExecFindMatchingSubPlans(node->as_prune_state, false);
+ node->as_valid_subplans_identified = true;
+ }
whichplan = -1;
}
@@ -640,10 +645,11 @@ choose_next_subplan_for_leader(AppendState *node)
* run-time pruning is disabled then the valid subplans will always be
* set to all subplans.
*/
- if (node->as_valid_subplans == NULL)
+ if (!node->as_valid_subplans_identified)
{
node->as_valid_subplans =
ExecFindMatchingSubPlans(node->as_prune_state, false);
+ node->as_valid_subplans_identified = true;
/*
* Mark each invalid plan as finished to allow the loop below to
@@ -715,10 +721,12 @@ choose_next_subplan_for_worker(AppendState *node)
* run-time pruning is disabled then the valid subplans will always be set
* to all subplans.
*/
- else if (node->as_valid_subplans == NULL)
+ else if (!node->as_valid_subplans_identified)
{
node->as_valid_subplans =
ExecFindMatchingSubPlans(node->as_prune_state, false);
+ node->as_valid_subplans_identified = true;
+
mark_invalid_subplans_as_finished(node);
}
@@ -866,10 +874,11 @@ ExecAppendAsyncBegin(AppendState *node)
Assert(node->as_nasyncplans > 0);
/* If we've yet to determine the valid subplans then do so now. */
- if (node->as_valid_subplans == NULL)
+ if (!node->as_valid_subplans_identified)
{
node->as_valid_subplans =
ExecFindMatchingSubPlans(node->as_prune_state, false);
+ node->as_valid_subplans_identified = true;
classify_matching_subplans(node);
}
@@ -1143,6 +1152,7 @@ classify_matching_subplans(AppendState *node)
{
Bitmapset *valid_asyncplans;
+ Assert(node->as_valid_subplans_identified);
Assert(node->as_valid_asyncplans == NULL);
/* Nothing to do if there are no valid subplans. */
@@ -1161,9 +1171,8 @@ classify_matching_subplans(AppendState *node)
}
/* Get valid async subplans. */
- valid_asyncplans = bms_copy(node->as_asyncplans);
- valid_asyncplans = bms_int_members(valid_asyncplans,
- node->as_valid_subplans);
+ valid_asyncplans = bms_intersect(node->as_asyncplans,
+ node->as_valid_subplans);
/* Adjust the valid subplans to contain sync subplans only. */
node->as_valid_subplans = bms_del_members(node->as_valid_subplans,
diff --git a/src/include/nodes/execnodes.h b/src/include/nodes/execnodes.h
index 20f4c8b35f..e7eb1e666f 100644
--- a/src/include/nodes/execnodes.h
+++ b/src/include/nodes/execnodes.h
@@ -1350,6 +1350,7 @@ struct AppendState
ParallelAppendState *as_pstate; /* parallel coordination info */
Size pstate_len; /* size of parallel coordination info */
struct PartitionPruneState *as_prune_state;
+ bool as_valid_subplans_identified; /* is as_valid_subplans valid? */
Bitmapset *as_valid_subplans;
Bitmapset *as_valid_asyncplans; /* valid asynchronous plans indexes */
bool (*choose_next_subplan) (AppendState *);
--
2.31.1
v2-0003-Require-empty-Bitmapsets-to-be-represented-as-NUL.patchtext/x-diff; charset=us-ascii; name*0=v2-0003-Require-empty-Bitmapsets-to-be-represented-as-NUL.p; name*1=atchDownload
From 54644de166623238b2411c8710cd4bab9f97bfdc Mon Sep 17 00:00:00 2001
From: Tom Lane <tgl@sss.pgh.pa.us>
Date: Wed, 1 Mar 2023 17:44:06 -0500
Subject: [PATCH v2 3/4] Require empty Bitmapsets to be represented as NULL.
When I designed the Bitmapset module, I set things up so that an empty
Bitmapset could be represented either by a NULL pointer, or by an
allocated object all of whose bits are zero. I've recently come to
the conclusion that that was a bad idea and we should instead have a
convention like the longstanding invariant for Lists, whereby an empty
list is represented by NIL and nothing else.
To do this, we need to fix bms_intersect, bms_difference, and a couple
of other functions to check for having produced an empty result; but
then we can replace bms_is_empty(a) by a simple "a == NULL" test.
This is very likely a (marginal) win performance-wise, because we
call bms_is_empty many more times than those other functions put
together. However, the real reason to do it is that we have various
places that have hand-implemented a rule about "this Bitmapset
variable must be exactly NULL if empty", so that they can use
checks-for-null in place of bms_is_empty calls in particularly hot
code paths. That is a really fragile, mistake-prone way to do things,
and I'm surprised that we've seldom been bitten by it. It's not well
documented at all which variables have this property, so you can't
readily tell which code might be violating those conventions. By
making the convention universal, we can eliminate a subtle source of
bugs.
Discussion: https://postgr.es/m/1159933.1677621588@sss.pgh.pa.us
---
src/backend/nodes/bitmapset.c | 67 ++++++++++++++++++++++++++---------
src/include/nodes/bitmapset.h | 10 +++---
2 files changed, 56 insertions(+), 21 deletions(-)
diff --git a/src/backend/nodes/bitmapset.c b/src/backend/nodes/bitmapset.c
index 10dbbdddf5..c43de74cdf 100644
--- a/src/backend/nodes/bitmapset.c
+++ b/src/backend/nodes/bitmapset.c
@@ -5,10 +5,8 @@
*
* A bitmap set can represent any set of nonnegative integers, although
* it is mainly intended for sets where the maximum value is not large,
- * say at most a few hundred. By convention, a NULL pointer is always
- * accepted by all operations to represent the empty set. (But beware
- * that this is not the only representation of the empty set. Use
- * bms_is_empty() in preference to testing for NULL.)
+ * say at most a few hundred. By convention, we always represent the
+ * empty set by a NULL pointer.
*
*
* Copyright (c) 2003-2023, PostgreSQL Global Development Group
@@ -66,6 +64,8 @@
#error "invalid BITS_PER_BITMAPWORD"
#endif
+static bool bms_is_empty_internal(const Bitmapset *a);
+
/*
* bms_copy - make a palloc'd copy of a bitmapset
@@ -104,10 +104,10 @@ bms_equal(const Bitmapset *a, const Bitmapset *b)
{
if (b == NULL)
return true;
- return bms_is_empty(b);
+ return false;
}
else if (b == NULL)
- return bms_is_empty(a);
+ return false;
/* Identify shorter and longer input */
if (a->nwords <= b->nwords)
{
@@ -151,9 +151,9 @@ bms_compare(const Bitmapset *a, const Bitmapset *b)
/* Handle cases where either input is NULL */
if (a == NULL)
- return bms_is_empty(b) ? 0 : -1;
+ return (b == NULL) ? 0 : -1;
else if (b == NULL)
- return bms_is_empty(a) ? 0 : +1;
+ return +1;
/* Handle cases where one input is longer than the other */
shortlen = Min(a->nwords, b->nwords);
for (i = shortlen; i < a->nwords; i++)
@@ -282,6 +282,12 @@ bms_intersect(const Bitmapset *a, const Bitmapset *b)
resultlen = result->nwords;
for (i = 0; i < resultlen; i++)
result->words[i] &= other->words[i];
+ /* If we computed an empty result, we must return NULL */
+ if (bms_is_empty_internal(result))
+ {
+ pfree(result);
+ return NULL;
+ }
return result;
}
@@ -300,12 +306,22 @@ bms_difference(const Bitmapset *a, const Bitmapset *b)
return NULL;
if (b == NULL)
return bms_copy(a);
+
+ /*
+ * In Postgres' usage, an empty result is a very common case, so it's
+ * worth optimizing for that by testing bms_nonempty_difference(). This
+ * saves us a palloc/pfree cycle compared to checking after-the-fact.
+ */
+ if (!bms_nonempty_difference(a, b))
+ return NULL;
+
/* Copy the left input */
result = bms_copy(a);
/* And remove b's bits from result */
shortlen = Min(a->nwords, b->nwords);
for (i = 0; i < shortlen; i++)
result->words[i] &= ~b->words[i];
+ /* Need not check for empty result, since we handled that case above */
return result;
}
@@ -323,7 +339,7 @@ bms_is_subset(const Bitmapset *a, const Bitmapset *b)
if (a == NULL)
return true; /* empty set is a subset of anything */
if (b == NULL)
- return bms_is_empty(a);
+ return false;
/* Check common words */
shortlen = Min(a->nwords, b->nwords);
for (i = 0; i < shortlen; i++)
@@ -362,10 +378,10 @@ bms_subset_compare(const Bitmapset *a, const Bitmapset *b)
{
if (b == NULL)
return BMS_EQUAL;
- return bms_is_empty(b) ? BMS_EQUAL : BMS_SUBSET1;
+ return BMS_SUBSET1;
}
if (b == NULL)
- return bms_is_empty(a) ? BMS_EQUAL : BMS_SUBSET2;
+ return BMS_SUBSET2;
/* Check common words */
result = BMS_EQUAL; /* status so far */
shortlen = Min(a->nwords, b->nwords);
@@ -554,7 +570,7 @@ bms_nonempty_difference(const Bitmapset *a, const Bitmapset *b)
if (a == NULL)
return false;
if (b == NULL)
- return !bms_is_empty(a);
+ return true;
/* Check words in common */
shortlen = Min(a->nwords, b->nwords);
for (i = 0; i < shortlen; i++)
@@ -696,12 +712,13 @@ bms_membership(const Bitmapset *a)
}
/*
- * bms_is_empty - is a set empty?
+ * bms_is_empty_internal - is a set empty?
*
- * This is even faster than bms_membership().
+ * This is now used only locally, to detect cases where a function has
+ * computed an empty set that we must now get rid of.
*/
-bool
-bms_is_empty(const Bitmapset *a)
+static bool
+bms_is_empty_internal(const Bitmapset *a)
{
int nwords;
int wordnum;
@@ -786,6 +803,12 @@ bms_del_member(Bitmapset *a, int x)
bitnum = BITNUM(x);
if (wordnum < a->nwords)
a->words[wordnum] &= ~((bitmapword) 1 << bitnum);
+ /* If we computed an empty result, we must return NULL */
+ if (bms_is_empty_internal(a))
+ {
+ pfree(a);
+ return NULL;
+ }
return a;
}
@@ -922,6 +945,12 @@ bms_int_members(Bitmapset *a, const Bitmapset *b)
a->words[i] &= b->words[i];
for (; i < a->nwords; i++)
a->words[i] = 0;
+ /* If we computed an empty result, we must return NULL */
+ if (bms_is_empty_internal(a))
+ {
+ pfree(a);
+ return NULL;
+ }
return a;
}
@@ -943,6 +972,12 @@ bms_del_members(Bitmapset *a, const Bitmapset *b)
shortlen = Min(a->nwords, b->nwords);
for (i = 0; i < shortlen; i++)
a->words[i] &= ~b->words[i];
+ /* If we computed an empty result, we must return NULL */
+ if (bms_is_empty_internal(a))
+ {
+ pfree(a);
+ return NULL;
+ }
return a;
}
diff --git a/src/include/nodes/bitmapset.h b/src/include/nodes/bitmapset.h
index c344ac04be..14de6a9ff1 100644
--- a/src/include/nodes/bitmapset.h
+++ b/src/include/nodes/bitmapset.h
@@ -5,10 +5,8 @@
*
* A bitmap set can represent any set of nonnegative integers, although
* it is mainly intended for sets where the maximum value is not large,
- * say at most a few hundred. By convention, a NULL pointer is always
- * accepted by all operations to represent the empty set. (But beware
- * that this is not the only representation of the empty set. Use
- * bms_is_empty() in preference to testing for NULL.)
+ * say at most a few hundred. By convention, we always represent the
+ * empty set by a NULL pointer.
*
*
* Copyright (c) 2003-2023, PostgreSQL Global Development Group
@@ -102,7 +100,9 @@ extern int bms_num_members(const Bitmapset *a);
/* optimized tests when we don't need to know exact membership count: */
extern BMS_Membership bms_membership(const Bitmapset *a);
-extern bool bms_is_empty(const Bitmapset *a);
+
+/* NULL is now the only allowed representation of an empty bitmapset */
+#define bms_is_empty(a) ((a) == NULL)
/* these routines recycle (modify or free) their non-const inputs: */
--
2.31.1
v2-0004-Remove-local-optimizations-of-empty-Bitmapsets-in.patchtext/x-diff; charset=us-ascii; name*0=v2-0004-Remove-local-optimizations-of-empty-Bitmapsets-in.p; name*1=atchDownload
From ae52bce53b203fdee7427963613bf00e42dcddea Mon Sep 17 00:00:00 2001
From: Tom Lane <tgl@sss.pgh.pa.us>
Date: Wed, 1 Mar 2023 17:52:25 -0500
Subject: [PATCH v2 4/4] Remove local optimizations of empty Bitmapsets into
null pointers.
These are all dead code now that it's done centrally.
Discussion: https://postgr.es/m/1159933.1677621588@sss.pgh.pa.us
---
src/backend/executor/execUtils.c | 10 +---------
src/backend/optimizer/path/indxpath.c | 3 ---
src/backend/optimizer/plan/subselect.c | 9 ---------
src/backend/optimizer/util/pathnode.c | 6 ------
src/backend/optimizer/util/placeholder.c | 2 --
src/backend/optimizer/util/relnode.c | 7 -------
src/backend/rewrite/rewriteManip.c | 19 ++++---------------
src/pl/plpgsql/src/pl_exec.c | 7 ++-----
8 files changed, 7 insertions(+), 56 deletions(-)
diff --git a/src/backend/executor/execUtils.c b/src/backend/executor/execUtils.c
index c33a3c0bec..cfa95a07e4 100644
--- a/src/backend/executor/execUtils.c
+++ b/src/backend/executor/execUtils.c
@@ -877,15 +877,7 @@ UpdateChangedParamSet(PlanState *node, Bitmapset *newchg)
* include anything else into its chgParam set.
*/
parmset = bms_intersect(node->plan->allParam, newchg);
-
- /*
- * Keep node->chgParam == NULL if there's not actually any members; this
- * allows the simplest possible tests in executor node files.
- */
- if (!bms_is_empty(parmset))
- node->chgParam = bms_join(node->chgParam, parmset);
- else
- bms_free(parmset);
+ node->chgParam = bms_join(node->chgParam, parmset);
}
/*
diff --git a/src/backend/optimizer/path/indxpath.c b/src/backend/optimizer/path/indxpath.c
index 011a0337da..9f4698f2a2 100644
--- a/src/backend/optimizer/path/indxpath.c
+++ b/src/backend/optimizer/path/indxpath.c
@@ -949,9 +949,6 @@ build_index_paths(PlannerInfo *root, RelOptInfo *rel,
/* We do not want the index's rel itself listed in outer_relids */
outer_relids = bms_del_member(outer_relids, rel->relid);
- /* Enforce convention that outer_relids is exactly NULL if empty */
- if (bms_is_empty(outer_relids))
- outer_relids = NULL;
/* Compute loop_count for cost estimation purposes */
loop_count = get_loop_count(root, rel->relid, outer_relids);
diff --git a/src/backend/optimizer/plan/subselect.c b/src/backend/optimizer/plan/subselect.c
index 22ffe4ca42..052263aea6 100644
--- a/src/backend/optimizer/plan/subselect.c
+++ b/src/backend/optimizer/plan/subselect.c
@@ -2825,15 +2825,6 @@ finalize_plan(PlannerInfo *root, Plan *plan,
/* but not any initplan setParams */
plan->extParam = bms_del_members(plan->extParam, initSetParam);
- /*
- * For speed at execution time, make sure extParam/allParam are actually
- * NULL if they are empty sets.
- */
- if (bms_is_empty(plan->extParam))
- plan->extParam = NULL;
- if (bms_is_empty(plan->allParam))
- plan->allParam = NULL;
-
return plan->allParam;
}
diff --git a/src/backend/optimizer/util/pathnode.c b/src/backend/optimizer/util/pathnode.c
index d749b50578..e8e06397a9 100644
--- a/src/backend/optimizer/util/pathnode.c
+++ b/src/backend/optimizer/util/pathnode.c
@@ -2372,12 +2372,6 @@ calc_nestloop_required_outer(Relids outerrelids,
/* ... and remove any mention of now-satisfied outer rels */
required_outer = bms_del_members(required_outer,
outerrelids);
- /* maintain invariant that required_outer is exactly NULL if empty */
- if (bms_is_empty(required_outer))
- {
- bms_free(required_outer);
- required_outer = NULL;
- }
return required_outer;
}
diff --git a/src/backend/optimizer/util/placeholder.c b/src/backend/optimizer/util/placeholder.c
index 9c6cb5eba7..b1723578e6 100644
--- a/src/backend/optimizer/util/placeholder.c
+++ b/src/backend/optimizer/util/placeholder.c
@@ -125,8 +125,6 @@ find_placeholder_info(PlannerInfo *root, PlaceHolderVar *phv)
*/
rels_used = pull_varnos(root, (Node *) phv->phexpr);
phinfo->ph_lateral = bms_difference(rels_used, phv->phrels);
- if (bms_is_empty(phinfo->ph_lateral))
- phinfo->ph_lateral = NULL; /* make it exactly NULL if empty */
phinfo->ph_eval_at = bms_int_members(rels_used, phv->phrels);
/* If no contained vars, force evaluation at syntactic location */
if (bms_is_empty(phinfo->ph_eval_at))
diff --git a/src/backend/optimizer/util/relnode.c b/src/backend/optimizer/util/relnode.c
index 9ad44a0508..68fd033595 100644
--- a/src/backend/optimizer/util/relnode.c
+++ b/src/backend/optimizer/util/relnode.c
@@ -772,8 +772,6 @@ build_join_rel(PlannerInfo *root,
*/
joinrel->direct_lateral_relids =
bms_del_members(joinrel->direct_lateral_relids, joinrel->relids);
- if (bms_is_empty(joinrel->direct_lateral_relids))
- joinrel->direct_lateral_relids = NULL;
/*
* Construct restrict and join clause lists for the new joinrel. (The
@@ -1024,11 +1022,6 @@ min_join_parameterization(PlannerInfo *root,
*/
result = bms_union(outer_rel->lateral_relids, inner_rel->lateral_relids);
result = bms_del_members(result, joinrelids);
-
- /* Maintain invariant that result is exactly NULL if empty */
- if (bms_is_empty(result))
- result = NULL;
-
return result;
}
diff --git a/src/backend/rewrite/rewriteManip.c b/src/backend/rewrite/rewriteManip.c
index 04718f66c0..d28d0da621 100644
--- a/src/backend/rewrite/rewriteManip.c
+++ b/src/backend/rewrite/rewriteManip.c
@@ -1247,16 +1247,11 @@ remove_nulling_relids_mutator(Node *node,
!bms_is_member(var->varno, context->except_relids) &&
bms_overlap(var->varnullingrels, context->removable_relids))
{
- Relids newnullingrels = bms_difference(var->varnullingrels,
- context->removable_relids);
-
- /* Micro-optimization: ensure nullingrels is NULL if empty */
- if (bms_is_empty(newnullingrels))
- newnullingrels = NULL;
/* Copy the Var ... */
var = copyObject(var);
/* ... and replace the copy's varnullingrels field */
- var->varnullingrels = newnullingrels;
+ var->varnullingrels = bms_difference(var->varnullingrels,
+ context->removable_relids);
return (Node *) var;
}
/* Otherwise fall through to copy the Var normally */
@@ -1268,26 +1263,20 @@ remove_nulling_relids_mutator(Node *node,
if (phv->phlevelsup == context->sublevels_up &&
!bms_overlap(phv->phrels, context->except_relids))
{
- Relids newnullingrels = bms_difference(phv->phnullingrels,
- context->removable_relids);
-
/*
- * Micro-optimization: ensure nullingrels is NULL if empty.
- *
* Note: it might seem desirable to remove the PHV altogether if
* phnullingrels goes to empty. Currently we dare not do that
* because we use PHVs in some cases to enforce separate identity
* of subexpressions; see wrap_non_vars usages in prepjointree.c.
*/
- if (bms_is_empty(newnullingrels))
- newnullingrels = NULL;
/* Copy the PlaceHolderVar and mutate what's below ... */
phv = (PlaceHolderVar *)
expression_tree_mutator(node,
remove_nulling_relids_mutator,
(void *) context);
/* ... and replace the copy's phnullingrels field */
- phv->phnullingrels = newnullingrels;
+ phv->phnullingrels = bms_difference(phv->phnullingrels,
+ context->removable_relids);
/* We must also update phrels, if it contains a removable RTI */
phv->phrels = bms_difference(phv->phrels,
context->removable_relids);
diff --git a/src/pl/plpgsql/src/pl_exec.c b/src/pl/plpgsql/src/pl_exec.c
index ffd6d2e3bc..b0a2cac227 100644
--- a/src/pl/plpgsql/src/pl_exec.c
+++ b/src/pl/plpgsql/src/pl_exec.c
@@ -6240,12 +6240,9 @@ setup_param_list(PLpgSQL_execstate *estate, PLpgSQL_expr *expr)
Assert(expr->plan != NULL);
/*
- * We only need a ParamListInfo if the expression has parameters. In
- * principle we should test with bms_is_empty(), but we use a not-null
- * test because it's faster. In current usage bits are never removed from
- * expr->paramnos, only added, so this test is correct anyway.
+ * We only need a ParamListInfo if the expression has parameters.
*/
- if (expr->paramnos)
+ if (!bms_is_empty(expr->paramnos))
{
/* Use the common ParamListInfo */
paramLI = estate->paramLI;
--
2.31.1
On Wed, Mar 01, 2023 at 05:59:45PM -0500, Tom Lane wrote:
bms_first_member is definitely legacy code, so let's just get
rid of it. Done like that in 0001 below. (This was slightly more
complex than I foresaw, because some of the callers were modifying
the result variables. But they're probably cleaner this way anyway.)
Yeah, it's nice that you don't have to subtract
FirstLowInvalidHeapAttributeNumber in so many places. I think future
changes might end up using attidx when they ought to use attrnum (and vice
versa), but you could just as easily forget to subtract
FirstLowInvalidHeapAttributeNumber today, so it's probably fine.
+ /* attidx is zero-based, attrnum is the normal attribute number */ + int attrnum = attidx + FirstLowInvalidHeapAttributeNumber;
nitpick: Shouldn't this be an AttrNumber?
Yeah. I split out those executor fixes as 0002; 0003 is the changes
to bitmapsets proper, and then 0004 removes now-dead code.
These all looked reasonable to me.
--
Nathan Bossart
Amazon Web Services: https://aws.amazon.com
Nathan Bossart <nathandbossart@gmail.com> writes:
On Wed, Mar 01, 2023 at 05:59:45PM -0500, Tom Lane wrote:
+ /* attidx is zero-based, attrnum is the normal attribute number */ + int attrnum = attidx + FirstLowInvalidHeapAttributeNumber;
nitpick: Shouldn't this be an AttrNumber?
I stuck with the existing type choices for those variables,
but I don't mind changing to AttrNumber here.
regards, tom lane
On Thu, Mar 2, 2023 at 6:59 AM Tom Lane <tgl@sss.pgh.pa.us> wrote:
Yeah. I split out those executor fixes as 0002; 0003 is the changes
to bitmapsets proper, and then 0004 removes now-dead code.
+1 to all these patches. Some minor comments from me.
*0003
It seems that the Bitmapset checked by bms_is_empty_internal cannot be
NULL from how it is computed by a function. So I wonder if we can
remove the check of 'a' being NULL in that function, or reduce it to an
Assert.
- if (a == NULL)
- return true;
+ Assert(a != NULL);
*0004
It seems that in create_lateral_join_info around line 689, the
bms_is_empty check of lateral_relids is not necessary, since we've
checked that lateral_relids cannot be NULL several lines earlier.
@@ -682,12 +682,6 @@ create_lateral_join_info(PlannerInfo *root)
if (lateral_relids == NULL)
continue;
- /*
- * We should not have broken the invariant that lateral_relids is
- * exactly NULL if empty.
- */
- Assert(!bms_is_empty(lateral_relids));
-
Thanks
Richard
Richard Guo <guofenglinux@gmail.com> writes:
It seems that the Bitmapset checked by bms_is_empty_internal cannot be
NULL from how it is computed by a function. So I wonder if we can
remove the check of 'a' being NULL in that function, or reduce it to an
Assert.
Yeah, I think just removing it is sufficient. The subsequent attempts
to dereference the pointer will crash just fine if it's NULL; we don't
need an Assert to help things along.
It seems that in create_lateral_join_info around line 689, the
bms_is_empty check of lateral_relids is not necessary, since we've
checked that lateral_relids cannot be NULL several lines earlier.
Good catch, I missed that one.
Pushed, thanks for reviewing.
regards, tom lane
On Wed, 1 Mar 2023 at 10:59, Tom Lane <tgl@sss.pgh.pa.us> wrote:
When I designed the Bitmapset module, I set things up so that an empty
Bitmapset could be represented either by a NULL pointer, or by an
allocated object all of whose bits are zero. I've recently come to
the conclusion that that was a bad idea and we should instead have
a convention like the longstanding invariant for Lists: an empty
list is represented by NIL and nothing else.
I know I'm late to the party here, but I just wanted to add that I
agree with this and also that I've never been a fan of having to
decide if it was safe to check for NULL when I needed performance or
if I needed to use bms_is_empty() because the set might have all its
words set to 0.
I suggest tightening the rule even further so instead of just empty
sets having to be represented as NULL, the rule should be that sets
should never contain any trailing zero words, which is effectively a
superset of the "empty is NULL" rule that you've just changed.
If we did this, then various functions can shake loose some crufty
code and various other functions become more optimal due to not having
to loop over trailing zero words needlessly. For example.
* bms_equal() and bms_compare() can precheck nwords match before
troubling themselves with looping over each member, and;
* bms_is_subset() can return false early if 'a' has more words than 'b', and;
* bms_subset_compare() becomes more simple as it does not have to look
for trailing 0 words, and;
* bms_nonempty_difference() can return true early if 'a' has more
words than 'b', plus no need to check for trailing zero words at the
end.
We can also chop the set down to size in; bms_intersect(),
bms_difference(), bms_int_members(), bms_del_members() and
bms_intersect() which saves looping needlessly over empty words when
various other BMS operations are performed later on the set, for
example, bms_next_member(), bms_prev_member, bms_copy(), etc.
The only reason I can think of that this would be a bad idea is that
if we want to add members again then we need to do repalloc(). If
we're only increasing the nwords back to what it had been on some
previous occasion then repalloc() is effectively a no-op, so I doubt
this will really be a net negative. I think the effort we'll waste by
carrying around needless trailing zero words in most cases is likely
to outweigh the overhead of any no-op repallocs. Take
bms_int_members(), for example, we'll purposefully 0 out all the
trailing words possibly having to read in new cachelines from RAM to
do so. It would be better to leave having to read those in again
until we actually need to do something more useful with them, like
adding some new members to the set again. We'll have to dirty those
cachelines then anyway and we may have flushed those cachelines out of
the CPU cache by the time we get around to adding the new members
again.
I've coded this up in the attached and followed the lead in list.c and
added a function named check_bitmapset_invariants() which ensures the
above rule is followed. I think the code as it stands today should
really have something like that anyway.
The patch also optimizes sub-optimal newly added code which calls
bms_is_empty_internal() when we have other more optimal means to
determine if the set is empty or not.
David
Attachments:
bms_no_trailing_zero_words.patchapplication/octet-stream; name=bms_no_trailing_zero_words.patchDownload
diff --git a/src/backend/nodes/bitmapset.c b/src/backend/nodes/bitmapset.c
index 7ba3cf635b..6cdc1663d2 100644
--- a/src/backend/nodes/bitmapset.c
+++ b/src/backend/nodes/bitmapset.c
@@ -5,8 +5,10 @@
*
* A bitmap set can represent any set of nonnegative integers, although
* it is mainly intended for sets where the maximum value is not large,
- * say at most a few hundred. By convention, we always represent the
- * empty set by a NULL pointer.
+ * say at most a few hundred. By convention, we always represent a set with
+ * the minimum possible number of words, i.e, there are never any trailing
+ * zero words. Enforcing this requires that an empty set is represented as
+ * NULL.
*
*
* Copyright (c) 2003-2023, PostgreSQL Global Development Group
@@ -66,6 +68,22 @@
static bool bms_is_empty_internal(const Bitmapset *a);
+#ifdef USE_ASSERT_CHECKING
+static void
+check_bitmapset_invariants(const Bitmapset *set)
+{
+ /* Verify that the set does not have any trailing zero words */
+ if (set != NULL)
+ {
+ int wordnum = set->nwords - 1;
+
+ while (set->words[wordnum--] == 0)
+ Assert(false);
+ }
+}
+#else
+#define check_bitmapset_invariants(set) ((void) 0)
+#endif /* USE_ASSERT_CHECKING */
/*
* bms_copy - make a palloc'd copy of a bitmapset
@@ -76,6 +94,8 @@ bms_copy(const Bitmapset *a)
Bitmapset *result;
size_t size;
+ check_bitmapset_invariants(a);
+
if (a == NULL)
return NULL;
size = BITMAPSET_SIZE(a->nwords);
@@ -86,18 +106,12 @@ bms_copy(const Bitmapset *a)
/*
* bms_equal - are two bitmapsets equal?
- *
- * This is logical not physical equality; in particular, a NULL pointer will
- * be reported as equal to a palloc'd value containing no members.
*/
bool
bms_equal(const Bitmapset *a, const Bitmapset *b)
{
- const Bitmapset *shorter;
- const Bitmapset *longer;
- int shortlen;
- int longlen;
- int i;
+ check_bitmapset_invariants(a);
+ check_bitmapset_invariants(b);
/* Handle cases where either input is NULL */
if (a == NULL)
@@ -108,30 +122,18 @@ bms_equal(const Bitmapset *a, const Bitmapset *b)
}
else if (b == NULL)
return false;
- /* Identify shorter and longer input */
- if (a->nwords <= b->nwords)
- {
- shorter = a;
- longer = b;
- }
- else
- {
- shorter = b;
- longer = a;
- }
- /* And process */
- shortlen = shorter->nwords;
- for (i = 0; i < shortlen; i++)
- {
- if (shorter->words[i] != longer->words[i])
- return false;
- }
- longlen = longer->nwords;
- for (; i < longlen; i++)
+
+ /* can't be equal if the word counts don't match */
+ if (a->nwords != b->nwords)
+ return false;
+
+ /* check each word matches */
+ for (int i = 0; i < a->nwords; i++)
{
- if (longer->words[i] != 0)
+ if (a->words[i] != b->words[i])
return false;
}
+
return true;
}
@@ -146,29 +148,24 @@ bms_equal(const Bitmapset *a, const Bitmapset *b)
int
bms_compare(const Bitmapset *a, const Bitmapset *b)
{
- int shortlen;
- int i;
+ int nwords;
+
+ check_bitmapset_invariants(a);
+ check_bitmapset_invariants(b);
/* Handle cases where either input is NULL */
if (a == NULL)
return (b == NULL) ? 0 : -1;
else if (b == NULL)
return +1;
- /* Handle cases where one input is longer than the other */
- shortlen = Min(a->nwords, b->nwords);
- for (i = shortlen; i < a->nwords; i++)
- {
- if (a->words[i] != 0)
- return +1;
- }
- for (i = shortlen; i < b->nwords; i++)
- {
- if (b->words[i] != 0)
- return -1;
- }
- /* Process words in common */
- i = shortlen;
- while (--i >= 0)
+
+ /* the set with the most words must be greater */
+ if (a->nwords != b->nwords)
+ return (a->nwords > b->nwords) ? +1 : -1;
+
+ /* do the actual comparison */
+ nwords = a->nwords;
+ for (int i = 0; i < nwords; i++)
{
bitmapword aw = a->words[i];
bitmapword bw = b->words[i];
@@ -208,6 +205,8 @@ bms_make_singleton(int x)
void
bms_free(Bitmapset *a)
{
+ check_bitmapset_invariants(a);
+
if (a)
pfree(a);
}
@@ -228,7 +227,9 @@ bms_union(const Bitmapset *a, const Bitmapset *b)
Bitmapset *result;
const Bitmapset *other;
int otherlen;
- int i;
+
+ check_bitmapset_invariants(a);
+ check_bitmapset_invariants(b);
/* Handle cases where either input is NULL */
if (a == NULL)
@@ -248,7 +249,7 @@ bms_union(const Bitmapset *a, const Bitmapset *b)
}
/* And union the shorter input into the result */
otherlen = other->nwords;
- for (i = 0; i < otherlen; i++)
+ for (int i = 0; i < otherlen; i++)
result->words[i] |= other->words[i];
return result;
}
@@ -262,7 +263,10 @@ bms_intersect(const Bitmapset *a, const Bitmapset *b)
Bitmapset *result;
const Bitmapset *other;
int resultlen;
- int i;
+ int nonzeroidx;
+
+ check_bitmapset_invariants(a);
+ check_bitmapset_invariants(b);
/* Handle cases where either input is NULL */
if (a == NULL || b == NULL)
@@ -280,14 +284,23 @@ bms_intersect(const Bitmapset *a, const Bitmapset *b)
}
/* And intersect the longer input with the result */
resultlen = result->nwords;
- for (i = 0; i < resultlen; i++)
+ nonzeroidx = -1;
+ for (int i = 0; i < resultlen; i++)
+ {
result->words[i] &= other->words[i];
+
+ if (result->words[i] != 0)
+ nonzeroidx = i;
+ }
/* If we computed an empty result, we must return NULL */
- if (bms_is_empty_internal(result))
+ if (nonzeroidx == -1)
{
pfree(result);
return NULL;
}
+
+ /* get rid of trailing zero words */
+ result->nwords = nonzeroidx + 1;
return result;
}
@@ -299,7 +312,10 @@ bms_difference(const Bitmapset *a, const Bitmapset *b)
{
Bitmapset *result;
int shortlen;
- int i;
+ int nonzeroidx;
+
+ check_bitmapset_invariants(a);
+ check_bitmapset_invariants(b);
/* Handle cases where either input is NULL */
if (a == NULL)
@@ -319,8 +335,19 @@ bms_difference(const Bitmapset *a, const Bitmapset *b)
result = bms_copy(a);
/* And remove b's bits from result */
shortlen = Min(a->nwords, b->nwords);
- for (i = 0; i < shortlen; i++)
+ nonzeroidx = -1;
+ for (int i = 0; i < shortlen; i++)
+ {
result->words[i] &= ~b->words[i];
+
+ if (result->words[i] != 0)
+ nonzeroidx = i;
+ }
+
+ /* get rid of trailing zero words */
+ result->nwords = nonzeroidx + 1;
+ Assert(result->nwords != 0);
+
/* Need not check for empty result, since we handled that case above */
return result;
}
@@ -331,32 +358,25 @@ bms_difference(const Bitmapset *a, const Bitmapset *b)
bool
bms_is_subset(const Bitmapset *a, const Bitmapset *b)
{
- int shortlen;
- int longlen;
- int i;
+ check_bitmapset_invariants(a);
+ check_bitmapset_invariants(b);
/* Handle cases where either input is NULL */
if (a == NULL)
return true; /* empty set is a subset of anything */
if (b == NULL)
return false;
- /* Check common words */
- shortlen = Min(a->nwords, b->nwords);
- for (i = 0; i < shortlen; i++)
+
+ /* 'a' can't be a subset of 'b' if it contains more words */
+ if (a->nwords > b->nwords)
+ return false;
+
+ /* Check all 'a' members are set in 'b' */
+ for (int i = 0; i < a->nwords; i++)
{
if ((a->words[i] & ~b->words[i]) != 0)
return false;
}
- /* Check extra words */
- if (a->nwords > b->nwords)
- {
- longlen = a->nwords;
- for (; i < longlen; i++)
- {
- if (a->words[i] != 0)
- return false;
- }
- }
return true;
}
@@ -370,8 +390,9 @@ bms_subset_compare(const Bitmapset *a, const Bitmapset *b)
{
BMS_Comparison result;
int shortlen;
- int longlen;
- int i;
+
+ check_bitmapset_invariants(a);
+ check_bitmapset_invariants(b);
/* Handle cases where either input is NULL */
if (a == NULL)
@@ -385,7 +406,7 @@ bms_subset_compare(const Bitmapset *a, const Bitmapset *b)
/* Check common words */
result = BMS_EQUAL; /* status so far */
shortlen = Min(a->nwords, b->nwords);
- for (i = 0; i < shortlen; i++)
+ for (int i = 0; i < shortlen; i++)
{
bitmapword aword = a->words[i];
bitmapword bword = b->words[i];
@@ -408,31 +429,17 @@ bms_subset_compare(const Bitmapset *a, const Bitmapset *b)
/* Check extra words */
if (a->nwords > b->nwords)
{
- longlen = a->nwords;
- for (; i < longlen; i++)
- {
- if (a->words[i] != 0)
- {
- /* a is not a subset of b */
- if (result == BMS_SUBSET1)
- return BMS_DIFFERENT;
- result = BMS_SUBSET2;
- }
- }
+ /* if a has more words then a is not a subset of b */
+ if (result == BMS_SUBSET1)
+ return BMS_DIFFERENT;
+ return BMS_SUBSET2;
}
else if (a->nwords < b->nwords)
{
- longlen = b->nwords;
- for (; i < longlen; i++)
- {
- if (b->words[i] != 0)
- {
- /* b is not a subset of a */
- if (result == BMS_SUBSET2)
- return BMS_DIFFERENT;
- result = BMS_SUBSET1;
- }
- }
+ /* if b has more words then b is not a subset of a */
+ if (result == BMS_SUBSET2)
+ return BMS_DIFFERENT;
+ return BMS_SUBSET1;
}
return result;
}
@@ -446,6 +453,8 @@ bms_is_member(int x, const Bitmapset *a)
int wordnum,
bitnum;
+ check_bitmapset_invariants(a);
+
/* XXX better to just return false for x<0 ? */
if (x < 0)
elog(ERROR, "negative bitmapset member not allowed");
@@ -469,12 +478,13 @@ bms_is_member(int x, const Bitmapset *a)
int
bms_member_index(Bitmapset *a, int x)
{
- int i;
int bitnum;
int wordnum;
int result = 0;
bitmapword mask;
+ check_bitmapset_invariants(a);
+
/* return -1 if not a member of the bitmap */
if (!bms_is_member(x, a))
return -1;
@@ -483,7 +493,7 @@ bms_member_index(Bitmapset *a, int x)
bitnum = BITNUM(x);
/* count bits in preceding words */
- for (i = 0; i < wordnum; i++)
+ for (int i = 0; i < wordnum; i++)
{
bitmapword w = a->words[i];
@@ -511,14 +521,16 @@ bool
bms_overlap(const Bitmapset *a, const Bitmapset *b)
{
int shortlen;
- int i;
+
+ check_bitmapset_invariants(a);
+ check_bitmapset_invariants(b);
/* Handle cases where either input is NULL */
if (a == NULL || b == NULL)
return false;
/* Check words in common */
shortlen = Min(a->nwords, b->nwords);
- for (i = 0; i < shortlen; i++)
+ for (int i = 0; i < shortlen; i++)
{
if ((a->words[i] & b->words[i]) != 0)
return true;
@@ -536,6 +548,8 @@ bms_overlap_list(const Bitmapset *a, const List *b)
int wordnum,
bitnum;
+ check_bitmapset_invariants(a);
+
if (a == NULL || b == NIL)
return false;
@@ -563,27 +577,23 @@ bms_overlap_list(const Bitmapset *a, const List *b)
bool
bms_nonempty_difference(const Bitmapset *a, const Bitmapset *b)
{
- int shortlen;
- int i;
+ check_bitmapset_invariants(a);
+ check_bitmapset_invariants(b);
/* Handle cases where either input is NULL */
if (a == NULL)
return false;
if (b == NULL)
return true;
- /* Check words in common */
- shortlen = Min(a->nwords, b->nwords);
- for (i = 0; i < shortlen; i++)
+ /* if a has more words then it must contain additional members */
+ if (a->nwords > b->nwords)
+ return true;
+ /* Check all 'a' members are set in 'b' */
+ for (int i = 0; i < a->nwords; i++)
{
if ((a->words[i] & ~b->words[i]) != 0)
return true;
}
- /* Check extra words in a */
- for (; i < a->nwords; i++)
- {
- if (a->words[i] != 0)
- return true;
- }
return false;
}
@@ -599,6 +609,8 @@ bms_singleton_member(const Bitmapset *a)
int nwords;
int wordnum;
+ check_bitmapset_invariants(a);
+
if (a == NULL)
elog(ERROR, "bitmapset is empty");
nwords = a->nwords;
@@ -637,6 +649,8 @@ bms_get_singleton_member(const Bitmapset *a, int *member)
int nwords;
int wordnum;
+ check_bitmapset_invariants(a);
+
if (a == NULL)
return false;
nwords = a->nwords;
@@ -668,6 +682,8 @@ bms_num_members(const Bitmapset *a)
int nwords;
int wordnum;
+ check_bitmapset_invariants(a);
+
if (a == NULL)
return 0;
nwords = a->nwords;
@@ -690,17 +706,20 @@ bms_num_members(const Bitmapset *a)
BMS_Membership
bms_membership(const Bitmapset *a)
{
- BMS_Membership result = BMS_EMPTY_SET;
- int nwords;
- int wordnum;
+ BMS_Membership result;
+
+ check_bitmapset_invariants(a);
if (a == NULL)
return BMS_EMPTY_SET;
- nwords = a->nwords;
- for (wordnum = 0; wordnum < nwords; wordnum++)
- {
- bitmapword w = a->words[wordnum];
+ /* fast path for common case */
+ if (a->words[0] != 0 && HAS_MULTIPLE_ONES(a->words[0]))
+ return BMS_MULTIPLE;
+ result = BMS_EMPTY_SET;
+ for (int i = 0; i < a->nwords; i++)
+ {
+ bitmapword w = a->words[i];
if (w != 0)
{
if (result != BMS_EMPTY_SET || HAS_MULTIPLE_ONES(w))
@@ -757,6 +776,8 @@ bms_add_member(Bitmapset *a, int x)
int wordnum,
bitnum;
+ check_bitmapset_invariants(a);
+
if (x < 0)
elog(ERROR, "negative bitmapset member not allowed");
if (a == NULL)
@@ -794,6 +815,8 @@ bms_del_member(Bitmapset *a, int x)
int wordnum,
bitnum;
+ check_bitmapset_invariants(a);
+
if (x < 0)
elog(ERROR, "negative bitmapset member not allowed");
if (a == NULL)
@@ -822,6 +845,9 @@ bms_add_members(Bitmapset *a, const Bitmapset *b)
int otherlen;
int i;
+ check_bitmapset_invariants(a);
+ check_bitmapset_invariants(b);
+
/* Handle cases where either input is NULL */
if (a == NULL)
return bms_copy(b);
@@ -864,6 +890,8 @@ bms_add_range(Bitmapset *a, int lower, int upper)
ushiftbits,
wordnum;
+ check_bitmapset_invariants(a);
+
/* do nothing if nothing is called for, without further checking */
if (upper < lower)
return a;
@@ -928,8 +956,12 @@ Bitmapset *
bms_int_members(Bitmapset *a, const Bitmapset *b)
{
int shortlen;
+ int nonzeroidx;
int i;
+ check_bitmapset_invariants(a);
+ check_bitmapset_invariants(b);
+
/* Handle cases where either input is NULL */
if (a == NULL)
return NULL;
@@ -940,16 +972,24 @@ bms_int_members(Bitmapset *a, const Bitmapset *b)
}
/* Intersect b into a; we need never copy */
shortlen = Min(a->nwords, b->nwords);
+ nonzeroidx = -1;
for (i = 0; i < shortlen; i++)
+ {
a->words[i] &= b->words[i];
- for (; i < a->nwords; i++)
- a->words[i] = 0;
+
+ if (a->words[i] != 0)
+ nonzeroidx = i;
+ }
+
/* If we computed an empty result, we must return NULL */
- if (bms_is_empty_internal(a))
+ if (nonzeroidx == -1)
{
pfree(a);
return NULL;
}
+
+ /* get rid of trailing zero words */
+ a->nwords = nonzeroidx + 1;
return a;
}
@@ -961,6 +1001,10 @@ bms_del_members(Bitmapset *a, const Bitmapset *b)
{
int shortlen;
int i;
+ int nonzeroidx;
+
+ check_bitmapset_invariants(a);
+ check_bitmapset_invariants(b);
/* Handle cases where either input is NULL */
if (a == NULL)
@@ -969,14 +1013,25 @@ bms_del_members(Bitmapset *a, const Bitmapset *b)
return a;
/* Remove b's bits from a; we need never copy */
shortlen = Min(a->nwords, b->nwords);
+ nonzeroidx = -1;
for (i = 0; i < shortlen; i++)
+ {
a->words[i] &= ~b->words[i];
+
+ if (a->words[i] != 0)
+ nonzeroidx = i;
+ }
+
/* If we computed an empty result, we must return NULL */
- if (bms_is_empty_internal(a))
+ if (nonzeroidx == -1)
{
pfree(a);
return NULL;
}
+
+ /* get rid of trailing zero words */
+ a->nwords = nonzeroidx + 1;
+
return a;
}
@@ -991,6 +1046,9 @@ bms_join(Bitmapset *a, Bitmapset *b)
int otherlen;
int i;
+ check_bitmapset_invariants(a);
+ check_bitmapset_invariants(b);
+
/* Handle cases where either input is NULL */
if (a == NULL)
return b;
@@ -1042,6 +1100,8 @@ bms_next_member(const Bitmapset *a, int prevbit)
int wordnum;
bitmapword mask;
+ check_bitmapset_invariants(a);
+
if (a == NULL)
return -2;
nwords = a->nwords;
@@ -1101,6 +1161,8 @@ bms_prev_member(const Bitmapset *a, int prevbit)
int ushiftbits;
bitmapword mask;
+ check_bitmapset_invariants(a);
+
/*
* If set is NULL or if there are no more bits to the right then we've
* nothing to do.
@@ -1151,6 +1213,8 @@ bms_hash_value(const Bitmapset *a)
{
int lastword;
+ check_bitmapset_invariants(a);
+
if (a == NULL)
return 0; /* All empty sets hash to 0 */
for (lastword = a->nwords; --lastword >= 0;)
David Rowley <dgrowleyml@gmail.com> writes:
I suggest tightening the rule even further so instead of just empty
sets having to be represented as NULL, the rule should be that sets
should never contain any trailing zero words, which is effectively a
superset of the "empty is NULL" rule that you've just changed.
Hmm, I'm not immediately a fan of that, because it'd mean more
interaction with aset.c to change the allocated size of results.
(Is it worth carrying both "allocated words" and "nonzero words"
fields to avoid useless memory-management effort? Dunno.)
Another point here is that I'm pretty sure that just about all
bitmapsets we deal with are only one or two words, so I'm not
convinced you're going to get any performance win to justify
the added management overhead.
regards, tom lane
On Fri, 3 Mar 2023 at 15:17, Tom Lane <tgl@sss.pgh.pa.us> wrote:
(Is it worth carrying both "allocated words" and "nonzero words"
fields to avoid useless memory-management effort? Dunno.)
It would have been a more appealing thing to do before Bitmapset
became a node type as we'd have had empty space in the struct to have
another 32-bit word on 64-bit builds.
Another point here is that I'm pretty sure that just about all
bitmapsets we deal with are only one or two words, so I'm not
convinced you're going to get any performance win to justify
the added management overhead.
It's true that the majority of Bitmapsets are going to be just 1 word,
but it's important to acknowledge that we do suffer in some more
extreme cases when Bitmapsets become large. Partition with large
numbers of partitions is one such case.
create table lp(a int) partition by list(a);
select 'create table lp'||x||' partition of lp for values
in('||x||');' from generate_series(0,9999)x;
\gexec
# cat bench.sql
select * from lp where a > 1 and a < 3;
$ pgbench -n -T 15 -f bench.sql postgres | grep tps
master:
tps = 28055.619289 (without initial connection time)
tps = 27819.235083 (without initial connection time)
tps = 28486.099808 (without initial connection time)
master + bms_no_trailing_zero_words.patch:
tps = 30840.840266 (without initial connection time)
tps = 29491.519705 (without initial connection time)
tps = 29471.083938 (without initial connection time)
(~6.45% faster)
Of course, it's an extreme case, I'm merely trying to show that
trimming the Bitmapsets down can have an impact in some cases.
David
David Rowley <dgrowleyml@gmail.com> writes:
On Fri, 3 Mar 2023 at 15:17, Tom Lane <tgl@sss.pgh.pa.us> wrote:
Another point here is that I'm pretty sure that just about all
bitmapsets we deal with are only one or two words, so I'm not
convinced you're going to get any performance win to justify
the added management overhead.
It's true that the majority of Bitmapsets are going to be just 1 word,
but it's important to acknowledge that we do suffer in some more
extreme cases when Bitmapsets become large. Partition with large
numbers of partitions is one such case.
Maybe, but optimizing for that while pessimizing every other case
doesn't sound very attractive from here. I think we need some
benchmarks on normal-size bitmapsets before considering doing much
in this area.
Also, if we're going to make any sort of changes here it'd probably
behoove us to make struct Bitmapset private in bitmapset.c, so that
we can have confidence that nobody is playing games with them.
I had a go at that and was pleasantly surprised to find that
actually nobody has; the attached passes check-world. It'd probably
be smart to commit this as a follow-on to 00b41463c, whether or not
we go any further.
Also, given that we do this, I don't think that check_bitmapset_invariants
as you propose it is worth the trouble. The reason we've gone to such
lengths with checking List invariants is that initially we had a large
number of places doing creative and not-too-structured things with Lists,
plus we've made several absolutely fundamental changes to that data
structure. Despite the far larger bug surface, I don't recall that those
invariant checks ever found anything after the initial rounds of changes.
So I don't buy that there's an argument for a similarly expensive set
of checks here. bitmapset.c is small enough that we should be able to
pretty much prove it correct by eyeball.
regards, tom lane
Attachments:
v1-make-struct-Bitmapset-private.patchtext/x-diff; charset=us-ascii; name=v1-make-struct-Bitmapset-private.patchDownload
diff --git a/src/backend/nodes/Makefile b/src/backend/nodes/Makefile
index af12c64878..a6eb2a87bb 100644
--- a/src/backend/nodes/Makefile
+++ b/src/backend/nodes/Makefile
@@ -54,7 +54,6 @@ node_headers = \
commands/trigger.h \
executor/tuptable.h \
foreign/fdwapi.h \
- nodes/bitmapset.h \
nodes/extensible.h \
nodes/lockoptions.h \
nodes/miscnodes.h \
diff --git a/src/backend/nodes/bitmapset.c b/src/backend/nodes/bitmapset.c
index 7ba3cf635b..c11daeb303 100644
--- a/src/backend/nodes/bitmapset.c
+++ b/src/backend/nodes/bitmapset.c
@@ -24,6 +24,34 @@
#include "port/pg_bitutils.h"
+/*
+ * Data representation
+ *
+ * Larger bitmap word sizes generally give better performance, so long as
+ * they're not wider than the processor can handle efficiently. We use
+ * 64-bit words if pointers are that large, else 32-bit words.
+ */
+#if SIZEOF_VOID_P >= 8
+
+#define BITS_PER_BITMAPWORD 64
+typedef uint64 bitmapword; /* must be an unsigned type */
+typedef int64 signedbitmapword; /* must be the matching signed type */
+
+#else
+
+#define BITS_PER_BITMAPWORD 32
+typedef uint32 bitmapword; /* must be an unsigned type */
+typedef int32 signedbitmapword; /* must be the matching signed type */
+
+#endif
+
+struct Bitmapset
+{
+ NodeTag type; /* it's a Node */
+ int nwords; /* number of words in array */
+ bitmapword words[FLEXIBLE_ARRAY_MEMBER]; /* really [nwords] */
+};
+
#define WORDNUM(x) ((x) / BITS_PER_BITMAPWORD)
#define BITNUM(x) ((x) % BITS_PER_BITMAPWORD)
diff --git a/src/backend/nodes/gen_node_support.pl b/src/backend/nodes/gen_node_support.pl
index ecbcadb8bf..fd5d61bfd4 100644
--- a/src/backend/nodes/gen_node_support.pl
+++ b/src/backend/nodes/gen_node_support.pl
@@ -65,7 +65,6 @@ my @all_input_files = qw(
commands/trigger.h
executor/tuptable.h
foreign/fdwapi.h
- nodes/bitmapset.h
nodes/extensible.h
nodes/lockoptions.h
nodes/miscnodes.h
@@ -132,6 +131,19 @@ my @special_read_write;
# node types we don't want any support functions for, just node tags
my @nodetag_only;
+# Nodes with custom copy/equal implementations are skipped from
+# .funcs.c but need case statements in .switch.c.
+my @custom_copy_equal;
+
+# Similarly for custom read/write implementations.
+my @custom_read_write;
+
+# Similarly for custom query jumble implementation.
+my @custom_query_jumble;
+
+# Track node types with manually assigned NodeTag numbers.
+my %manual_nodetag_number;
+
# types that are copied by straight assignment
my @scalar_types = qw(
bits32 bool char double int int8 int16 int32 int64 long uint8 uint16 uint32 uint64
@@ -166,18 +178,12 @@ push @no_equal, qw(List);
push @no_query_jumble, qw(List);
push @special_read_write, qw(List);
-# Nodes with custom copy/equal implementations are skipped from
-# .funcs.c but need case statements in .switch.c.
-my @custom_copy_equal;
-
-# Similarly for custom read/write implementations.
-my @custom_read_write;
-
-# Similarly for custom query jumble implementation.
-my @custom_query_jumble;
-
-# Track node types with manually assigned NodeTag numbers.
-my %manual_nodetag_number;
+# Likewise, Bitmapset is specially handled rather than being parsed
+# out of a header file. This supports making it an opaque struct.
+push @node_types, qw(Bitmapset);
+push @custom_copy_equal, qw(Bitmapset);
+push @no_query_jumble, qw(Bitmapset);
+push @special_read_write, qw(Bitmapset);
# This is a struct, so we can copy it by assignment. Equal support is
# currently not required.
diff --git a/src/backend/nodes/tidbitmap.c b/src/backend/nodes/tidbitmap.c
index 29a1858441..541626e697 100644
--- a/src/backend/nodes/tidbitmap.c
+++ b/src/backend/nodes/tidbitmap.c
@@ -42,7 +42,6 @@
#include "access/htup_details.h"
#include "common/hashfn.h"
-#include "nodes/bitmapset.h"
#include "nodes/tidbitmap.h"
#include "storage/lwlock.h"
#include "utils/dsa.h"
@@ -72,7 +71,14 @@
*/
#define PAGES_PER_CHUNK (BLCKSZ / 32)
-/* We use BITS_PER_BITMAPWORD and typedef bitmapword from nodes/bitmapset.h */
+/* We use the same BITS_PER_BITMAPWORD and typedef bitmapword as bitmapset.c */
+#if SIZEOF_VOID_P >= 8
+#define BITS_PER_BITMAPWORD 64
+typedef uint64 bitmapword; /* must be an unsigned type */
+#else
+#define BITS_PER_BITMAPWORD 32
+typedef uint32 bitmapword; /* must be an unsigned type */
+#endif
#define WORDNUM(x) ((x) / BITS_PER_BITMAPWORD)
#define BITNUM(x) ((x) % BITS_PER_BITMAPWORD)
diff --git a/src/include/nodes/bitmapset.h b/src/include/nodes/bitmapset.h
index 14de6a9ff1..3f5be0b9a3 100644
--- a/src/include/nodes/bitmapset.h
+++ b/src/include/nodes/bitmapset.h
@@ -18,43 +18,14 @@
#ifndef BITMAPSET_H
#define BITMAPSET_H
-#include "nodes/nodes.h"
-
/*
* Forward decl to save including pg_list.h
*/
struct List;
-/*
- * Data representation
- *
- * Larger bitmap word sizes generally give better performance, so long as
- * they're not wider than the processor can handle efficiently. We use
- * 64-bit words if pointers are that large, else 32-bit words.
- */
-#if SIZEOF_VOID_P >= 8
-
-#define BITS_PER_BITMAPWORD 64
-typedef uint64 bitmapword; /* must be an unsigned type */
-typedef int64 signedbitmapword; /* must be the matching signed type */
-
-#else
-
-#define BITS_PER_BITMAPWORD 32
-typedef uint32 bitmapword; /* must be an unsigned type */
-typedef int32 signedbitmapword; /* must be the matching signed type */
-
-#endif
-
-typedef struct Bitmapset
-{
- pg_node_attr(custom_copy_equal, special_read_write, no_query_jumble)
-
- NodeTag type;
- int nwords; /* number of words in array */
- bitmapword words[FLEXIBLE_ARRAY_MEMBER]; /* really [nwords] */
-} Bitmapset;
+/* struct Bitmapset is private in bitmapset.c */
+typedef struct Bitmapset Bitmapset;
/* result of bms_subset_compare */
typedef enum
diff --git a/src/include/nodes/meson.build b/src/include/nodes/meson.build
index efe0834afb..81f1e7a890 100644
--- a/src/include/nodes/meson.build
+++ b/src/include/nodes/meson.build
@@ -15,7 +15,6 @@ node_support_input_i = [
'commands/trigger.h',
'executor/tuptable.h',
'foreign/fdwapi.h',
- 'nodes/bitmapset.h',
'nodes/extensible.h',
'nodes/lockoptions.h',
'nodes/miscnodes.h',
On Sat, 4 Mar 2023 at 11:08, Tom Lane <tgl@sss.pgh.pa.us> wrote:
David Rowley <dgrowleyml@gmail.com> writes:
On Fri, 3 Mar 2023 at 15:17, Tom Lane <tgl@sss.pgh.pa.us> wrote:
It's true that the majority of Bitmapsets are going to be just 1 word,
but it's important to acknowledge that we do suffer in some more
extreme cases when Bitmapsets become large. Partition with large
numbers of partitions is one such case.Maybe, but optimizing for that while pessimizing every other case
doesn't sound very attractive from here. I think we need some
benchmarks on normal-size bitmapsets before considering doing much
in this area.
After thinking about this again and looking at the code, I'm not
really sure where the pessimism has been added. For the changes made
to say bms_equal(), there was already a branch that checked the nwords
column so that we could find the shorter and longer sets out of the
two input sets. That's been replaced with a comparison of both input
set's nwords, which does not really seem any more expensive. For
bms_compare() we needed to do Min(a->nwords, b->nwords) to find the
shortest set, likewise for bms_nonempty_difference() and
bms_is_subset(). That does not seem less expensive than the
replacement code.
I think the times where we have sets that we do manage to trim down
the nword count with that we actually end up having to expand again
are likely fairly rare.
I also wondered if we could shave off a few instructions by utilising
the knowledge that nwords is never 0. That would mean that some of
the loops could be written as:
i = 0; do { <stuff>; } while (++i < set->nwords);
instead of:
for (i = 0; i < set->nwords; i++) { <stuff>; }
if we do assume that the vast majority of sets are nwords==1 sets,
then this reduces the loop condition checks by half for all those.
I see that gcc manages to optimize: for (i = 0; i < set->nwords || i
== 0; i++) { <stuff>; } into the same code as the do while loop. clang
does not seem to manage that.
Also, if we're going to make any sort of changes here it'd probably
behoove us to make struct Bitmapset private in bitmapset.c, so that
we can have confidence that nobody is playing games with them.
I had a go at that and was pleasantly surprised to find that
actually nobody has; the attached passes check-world. It'd probably
be smart to commit this as a follow-on to 00b41463c, whether or not
we go any further.
That seems like a good idea. This will give us extra reassurance that
nobody is making up their own Bitmapsets through some custom function
that don't follow the rules.
Also, given that we do this, I don't think that check_bitmapset_invariants
as you propose it is worth the trouble.
I wondered if maybe just Assert(a == NULL || a->words[a->nwords - 1]
!= 0); would be worthwhile anywhere. However, I don't see any
particular function that is more likely to catch those errors, so it's
maybe not worth doing anywhere if we're not doing it everywhere.
I adjusted the patch to remove the invariant checks and fixed up a
couple of things I'd missed. The 0002 patch changes the for loops
into do while loops. I wanted to see if we could see any performance
gains from doing this.
The performance numbers are nowhere near as stable as I'd like them to
have been, but testing the patch shows:
Test 1:
setup:
create table t1 (a int) partition by list(a);
select 'create table t1_'||x||' partition of t1 for values
in('||x||');' from generate_series(0,9)x;
\gexec
Test 1's sql:
select * from t1 where a > 1 and a < 3;
for i in {1..3}; do pgbench -n -f test1.sql -T 15 postgres | grep tps; done
master (cf96907aad):
tps = 29534.189309
tps = 30465.722545
tps = 30328.290553
master + 0001:
tps = 28915.174536
tps = 29817.950994
tps = 29387.084581
master + 0001 + 0002:
tps = 29438.216512
tps = 29951.905408
tps = 31445.191414
Test 2:
setup:
create table t2 (a int) partition by list(a);
select 'create table t2_'||x||' partition of t2 for values
in('||x||');' from generate_series(0,9999)x;
\gexec
Test 2's sql:
select * from t2 where a > 1 and a < 3;
for i in {1..3}; do pgbench -n -f test2.sql -T 15 postgres | grep tps; done
master (cf96907aad):
tps = 28470.504990
tps = 29175.450905
tps = 28123.699176
master + 0001:
tps = 28056.256805
tps = 28380.401746
tps = 28384.395217
master + 0001 + 0002:
tps = 29365.992219
tps = 28418.374923
tps = 28303.924129
Test 3:
setup:
create table t3a (a int primary key);
create table t3b (a int primary key);
Test 3's sql:
select * from t3a inner join t3b on t3a.a = t3b.a;
for i in {1..3}; do pgbench -n -f test3.sql -T 15 postgres | grep tps; done
master (cf96907aad):
tps = 20458.710550
tps = 20527.898929
tps = 20284.165277
master + 0001:
tps = 20700.340713
tps = 20571.913956
tps = 20541.771589
master + 0001 + 0002:
tps = 20046.674601
tps = 20016.649536
tps = 19487.999853
I've attached a graph of this too. It shows that there might be a
small increase in performance with tests 1 and 2. It seems like test 3
regresses a bit. I suspect this might just be a code arrangement issue
as master + 0001 is faster than 0001 + 0002 for that test.
David
Attachments:
v1-0001-Remove-trailing-zero-words-from-Bitmapsets.patchapplication/octet-stream; name=v1-0001-Remove-trailing-zero-words-from-Bitmapsets.patchDownload
From 056c803c20628e6e7bf0000f217bfcaadcbeae22 Mon Sep 17 00:00:00 2001
From: David Rowley <dgrowley@gmail.com>
Date: Fri, 3 Mar 2023 16:40:29 +1300
Subject: [PATCH v1 1/2] Remove trailing zero words from Bitmapsets
---
src/backend/nodes/bitmapset.c | 207 +++++++++++++++-------------------
1 file changed, 89 insertions(+), 118 deletions(-)
diff --git a/src/backend/nodes/bitmapset.c b/src/backend/nodes/bitmapset.c
index 7ba3cf635b..14fb100087 100644
--- a/src/backend/nodes/bitmapset.c
+++ b/src/backend/nodes/bitmapset.c
@@ -5,8 +5,10 @@
*
* A bitmap set can represent any set of nonnegative integers, although
* it is mainly intended for sets where the maximum value is not large,
- * say at most a few hundred. By convention, we always represent the
- * empty set by a NULL pointer.
+ * say at most a few hundred. By convention, we always represent a set with
+ * the minimum possible number of words, i.e, there are never any trailing
+ * zero words. Enforcing this requires that an empty set is represented as
+ * NULL.
*
*
* Copyright (c) 2003-2023, PostgreSQL Global Development Group
@@ -85,18 +87,11 @@ bms_copy(const Bitmapset *a)
}
/*
- * bms_equal - are two bitmapsets equal?
- *
- * This is logical not physical equality; in particular, a NULL pointer will
- * be reported as equal to a palloc'd value containing no members.
+ * bms_equal - are two bitmapsets equal? or both NULL?
*/
bool
bms_equal(const Bitmapset *a, const Bitmapset *b)
{
- const Bitmapset *shorter;
- const Bitmapset *longer;
- int shortlen;
- int longlen;
int i;
/* Handle cases where either input is NULL */
@@ -108,30 +103,18 @@ bms_equal(const Bitmapset *a, const Bitmapset *b)
}
else if (b == NULL)
return false;
- /* Identify shorter and longer input */
- if (a->nwords <= b->nwords)
- {
- shorter = a;
- longer = b;
- }
- else
- {
- shorter = b;
- longer = a;
- }
- /* And process */
- shortlen = shorter->nwords;
- for (i = 0; i < shortlen; i++)
- {
- if (shorter->words[i] != longer->words[i])
- return false;
- }
- longlen = longer->nwords;
- for (; i < longlen; i++)
+
+ /* can't be equal if the word counts don't match */
+ if (a->nwords != b->nwords)
+ return false;
+
+ /* check each word matches */
+ for (i = 0; i < a->nwords; i++)
{
- if (longer->words[i] != 0)
+ if (a->words[i] != b->words[i])
return false;
}
+
return true;
}
@@ -146,29 +129,18 @@ bms_equal(const Bitmapset *a, const Bitmapset *b)
int
bms_compare(const Bitmapset *a, const Bitmapset *b)
{
- int shortlen;
int i;
-
/* Handle cases where either input is NULL */
if (a == NULL)
return (b == NULL) ? 0 : -1;
else if (b == NULL)
return +1;
- /* Handle cases where one input is longer than the other */
- shortlen = Min(a->nwords, b->nwords);
- for (i = shortlen; i < a->nwords; i++)
- {
- if (a->words[i] != 0)
- return +1;
- }
- for (i = shortlen; i < b->nwords; i++)
- {
- if (b->words[i] != 0)
- return -1;
- }
- /* Process words in common */
- i = shortlen;
- while (--i >= 0)
+
+ /* the set with the most words must be greater */
+ if (a->nwords != b->nwords)
+ return (a->nwords > b->nwords) ? +1 : -1;
+
+ for (i = a->nwords - 1; i >= 0; i--)
{
bitmapword aw = a->words[i];
bitmapword bw = b->words[i];
@@ -261,6 +233,7 @@ bms_intersect(const Bitmapset *a, const Bitmapset *b)
{
Bitmapset *result;
const Bitmapset *other;
+ int lastnonzero;
int resultlen;
int i;
@@ -280,14 +253,23 @@ bms_intersect(const Bitmapset *a, const Bitmapset *b)
}
/* And intersect the longer input with the result */
resultlen = result->nwords;
+ lastnonzero = -1;
for (i = 0; i < resultlen; i++)
+ {
result->words[i] &= other->words[i];
+
+ if (result->words[i] != 0)
+ lastnonzero = i;
+ }
/* If we computed an empty result, we must return NULL */
- if (bms_is_empty_internal(result))
+ if (lastnonzero == -1)
{
pfree(result);
return NULL;
}
+
+ /* get rid of trailing zero words */
+ result->nwords = lastnonzero + 1;
return result;
}
@@ -298,6 +280,7 @@ Bitmapset *
bms_difference(const Bitmapset *a, const Bitmapset *b)
{
Bitmapset *result;
+ int lastnonzero;
int shortlen;
int i;
@@ -319,8 +302,19 @@ bms_difference(const Bitmapset *a, const Bitmapset *b)
result = bms_copy(a);
/* And remove b's bits from result */
shortlen = Min(a->nwords, b->nwords);
+ lastnonzero = -1;
for (i = 0; i < shortlen; i++)
+ {
result->words[i] &= ~b->words[i];
+
+ if (result->words[i] != 0)
+ lastnonzero = i;
+ }
+
+ /* get rid of trailing zero words */
+ result->nwords = lastnonzero + 1;
+ Assert(result->nwords != 0);
+
/* Need not check for empty result, since we handled that case above */
return result;
}
@@ -331,32 +325,23 @@ bms_difference(const Bitmapset *a, const Bitmapset *b)
bool
bms_is_subset(const Bitmapset *a, const Bitmapset *b)
{
- int shortlen;
- int longlen;
int i;
-
/* Handle cases where either input is NULL */
if (a == NULL)
return true; /* empty set is a subset of anything */
if (b == NULL)
return false;
- /* Check common words */
- shortlen = Min(a->nwords, b->nwords);
- for (i = 0; i < shortlen; i++)
+
+ /* 'a' can't be a subset of 'b' if it contains more words */
+ if (a->nwords > b->nwords)
+ return false;
+
+ /* Check all 'a' members are set in 'b' */
+ for (i = 0; i < a->nwords; i++)
{
if ((a->words[i] & ~b->words[i]) != 0)
return false;
}
- /* Check extra words */
- if (a->nwords > b->nwords)
- {
- longlen = a->nwords;
- for (; i < longlen; i++)
- {
- if (a->words[i] != 0)
- return false;
- }
- }
return true;
}
@@ -370,7 +355,6 @@ bms_subset_compare(const Bitmapset *a, const Bitmapset *b)
{
BMS_Comparison result;
int shortlen;
- int longlen;
int i;
/* Handle cases where either input is NULL */
@@ -408,31 +392,17 @@ bms_subset_compare(const Bitmapset *a, const Bitmapset *b)
/* Check extra words */
if (a->nwords > b->nwords)
{
- longlen = a->nwords;
- for (; i < longlen; i++)
- {
- if (a->words[i] != 0)
- {
- /* a is not a subset of b */
- if (result == BMS_SUBSET1)
- return BMS_DIFFERENT;
- result = BMS_SUBSET2;
- }
- }
+ /* if a has more words then a is not a subset of b */
+ if (result == BMS_SUBSET1)
+ return BMS_DIFFERENT;
+ return BMS_SUBSET2;
}
else if (a->nwords < b->nwords)
{
- longlen = b->nwords;
- for (; i < longlen; i++)
- {
- if (b->words[i] != 0)
- {
- /* b is not a subset of a */
- if (result == BMS_SUBSET2)
- return BMS_DIFFERENT;
- result = BMS_SUBSET1;
- }
- }
+ /* if b has more words then b is not a subset of a */
+ if (result == BMS_SUBSET2)
+ return BMS_DIFFERENT;
+ return BMS_SUBSET1;
}
return result;
}
@@ -563,27 +533,21 @@ bms_overlap_list(const Bitmapset *a, const List *b)
bool
bms_nonempty_difference(const Bitmapset *a, const Bitmapset *b)
{
- int shortlen;
int i;
-
/* Handle cases where either input is NULL */
if (a == NULL)
return false;
if (b == NULL)
return true;
- /* Check words in common */
- shortlen = Min(a->nwords, b->nwords);
- for (i = 0; i < shortlen; i++)
+ /* if a has more words then it must contain additional members */
+ if (a->nwords > b->nwords)
+ return true;
+ /* Check all 'a' members are set in 'b' */
+ for (i = 0; i < a->nwords; i++)
{
if ((a->words[i] & ~b->words[i]) != 0)
return true;
}
- /* Check extra words in a */
- for (; i < a->nwords; i++)
- {
- if (a->words[i] != 0)
- return true;
- }
return false;
}
@@ -927,6 +891,7 @@ bms_add_range(Bitmapset *a, int lower, int upper)
Bitmapset *
bms_int_members(Bitmapset *a, const Bitmapset *b)
{
+ int lastnonzero;
int shortlen;
int i;
@@ -940,16 +905,24 @@ bms_int_members(Bitmapset *a, const Bitmapset *b)
}
/* Intersect b into a; we need never copy */
shortlen = Min(a->nwords, b->nwords);
+ lastnonzero = -1;
for (i = 0; i < shortlen; i++)
+ {
a->words[i] &= b->words[i];
- for (; i < a->nwords; i++)
- a->words[i] = 0;
+
+ if (a->words[i] != 0)
+ lastnonzero = i;
+ }
+
/* If we computed an empty result, we must return NULL */
- if (bms_is_empty_internal(a))
+ if (lastnonzero == -1)
{
pfree(a);
return NULL;
}
+
+ /* get rid of trailing zero words */
+ a->nwords = lastnonzero + 1;
return a;
}
@@ -959,6 +932,7 @@ bms_int_members(Bitmapset *a, const Bitmapset *b)
Bitmapset *
bms_del_members(Bitmapset *a, const Bitmapset *b)
{
+ int lastnonzero;
int shortlen;
int i;
@@ -969,14 +943,25 @@ bms_del_members(Bitmapset *a, const Bitmapset *b)
return a;
/* Remove b's bits from a; we need never copy */
shortlen = Min(a->nwords, b->nwords);
+ lastnonzero = -1;
for (i = 0; i < shortlen; i++)
+ {
a->words[i] &= ~b->words[i];
+
+ if (a->words[i] != 0)
+ lastnonzero = i;
+ }
+
/* If we computed an empty result, we must return NULL */
- if (bms_is_empty_internal(a))
+ if (lastnonzero == -1)
{
pfree(a);
return NULL;
}
+
+ /* get rid of trailing zero words */
+ a->nwords = lastnonzero + 1;
+
return a;
}
@@ -1140,28 +1125,14 @@ bms_prev_member(const Bitmapset *a, int prevbit)
/*
* bms_hash_value - compute a hash key for a Bitmapset
- *
- * Note: we must ensure that any two bitmapsets that are bms_equal() will
- * hash to the same value; in practice this means that trailing all-zero
- * words must not affect the result. Hence we strip those before applying
- * hash_any().
*/
uint32
bms_hash_value(const Bitmapset *a)
{
- int lastword;
-
if (a == NULL)
return 0; /* All empty sets hash to 0 */
- for (lastword = a->nwords; --lastword >= 0;)
- {
- if (a->words[lastword] != 0)
- break;
- }
- if (lastword < 0)
- return 0; /* All empty sets hash to 0 */
return DatumGetUInt32(hash_any((const unsigned char *) a->words,
- (lastword + 1) * sizeof(bitmapword)));
+ a->nwords * sizeof(bitmapword)));
}
/*
--
2.37.2
v1-0002-Use-do-while-loops-instead-of-for-loops.patchapplication/octet-stream; name=v1-0002-Use-do-while-loops-instead-of-for-loops.patchDownload
From a9b0f52face6d918738885413da83070ae48a137 Mon Sep 17 00:00:00 2001
From: David Rowley <dgrowley@gmail.com>
Date: Tue, 7 Mar 2023 12:43:26 +1300
Subject: [PATCH v1 2/2] Use do while loops instead of for loops
---
src/backend/nodes/bitmapset.c | 118 +++++++++++++++++++---------------
1 file changed, 67 insertions(+), 51 deletions(-)
diff --git a/src/backend/nodes/bitmapset.c b/src/backend/nodes/bitmapset.c
index 14fb100087..aec7392cff 100644
--- a/src/backend/nodes/bitmapset.c
+++ b/src/backend/nodes/bitmapset.c
@@ -8,7 +8,13 @@
* say at most a few hundred. By convention, we always represent a set with
* the minimum possible number of words, i.e, there are never any trailing
* zero words. Enforcing this requires that an empty set is represented as
- * NULL.
+ * NULL. Because an empty Bitmapset is represented as NULL, a non-NULL
+ * Bitmapset always has at least 1 Bitmapword. We can exploit this fact to
+ * speedup various loops over the Bitmapset's words array by using "do while"
+ * loops instead of "for" loops. This means the code does not waste time
+ * checking the loop condition before the first iteration. For Bitmapsets
+ * containing only a single word (likely the majority of them) this reduces
+ * the loop condition tests by half.
*
*
* Copyright (c) 2003-2023, PostgreSQL Global Development Group
@@ -109,11 +115,11 @@ bms_equal(const Bitmapset *a, const Bitmapset *b)
return false;
/* check each word matches */
- for (i = 0; i < a->nwords; i++)
- {
+ i = 0;
+ do {
if (a->words[i] != b->words[i])
return false;
- }
+ } while (++i < a->nwords);
return true;
}
@@ -140,14 +146,14 @@ bms_compare(const Bitmapset *a, const Bitmapset *b)
if (a->nwords != b->nwords)
return (a->nwords > b->nwords) ? +1 : -1;
- for (i = a->nwords - 1; i >= 0; i--)
- {
+ i = a->nwords - 1;
+ do {
bitmapword aw = a->words[i];
bitmapword bw = b->words[i];
if (aw != bw)
return (aw > bw) ? +1 : -1;
- }
+ } while (--i >= 0);
return 0;
}
@@ -220,8 +226,10 @@ bms_union(const Bitmapset *a, const Bitmapset *b)
}
/* And union the shorter input into the result */
otherlen = other->nwords;
- for (i = 0; i < otherlen; i++)
+ i = 0;
+ do {
result->words[i] |= other->words[i];
+ } while (++i < otherlen);
return result;
}
@@ -254,13 +262,13 @@ bms_intersect(const Bitmapset *a, const Bitmapset *b)
/* And intersect the longer input with the result */
resultlen = result->nwords;
lastnonzero = -1;
- for (i = 0; i < resultlen; i++)
- {
+ i = 0;
+ do {
result->words[i] &= other->words[i];
if (result->words[i] != 0)
lastnonzero = i;
- }
+ } while (++i < resultlen);
/* If we computed an empty result, we must return NULL */
if (lastnonzero == -1)
{
@@ -303,13 +311,13 @@ bms_difference(const Bitmapset *a, const Bitmapset *b)
/* And remove b's bits from result */
shortlen = Min(a->nwords, b->nwords);
lastnonzero = -1;
- for (i = 0; i < shortlen; i++)
- {
+ i = 0;
+ do {
result->words[i] &= ~b->words[i];
if (result->words[i] != 0)
lastnonzero = i;
- }
+ } while (++i < shortlen);
/* get rid of trailing zero words */
result->nwords = lastnonzero + 1;
@@ -337,11 +345,11 @@ bms_is_subset(const Bitmapset *a, const Bitmapset *b)
return false;
/* Check all 'a' members are set in 'b' */
- for (i = 0; i < a->nwords; i++)
- {
+ i = 0;
+ do {
if ((a->words[i] & ~b->words[i]) != 0)
return false;
- }
+ } while (++i < a->nwords);
return true;
}
@@ -369,8 +377,8 @@ bms_subset_compare(const Bitmapset *a, const Bitmapset *b)
/* Check common words */
result = BMS_EQUAL; /* status so far */
shortlen = Min(a->nwords, b->nwords);
- for (i = 0; i < shortlen; i++)
- {
+ i = 0;
+ do {
bitmapword aword = a->words[i];
bitmapword bword = b->words[i];
@@ -388,7 +396,7 @@ bms_subset_compare(const Bitmapset *a, const Bitmapset *b)
return BMS_DIFFERENT;
result = BMS_SUBSET1;
}
- }
+ } while (++i < shortlen);
/* Check extra words */
if (a->nwords > b->nwords)
{
@@ -488,11 +496,11 @@ bms_overlap(const Bitmapset *a, const Bitmapset *b)
return false;
/* Check words in common */
shortlen = Min(a->nwords, b->nwords);
- for (i = 0; i < shortlen; i++)
- {
+ i = 0;
+ do {
if ((a->words[i] & b->words[i]) != 0)
return true;
- }
+ } while (++i < shortlen);
return false;
}
@@ -543,11 +551,11 @@ bms_nonempty_difference(const Bitmapset *a, const Bitmapset *b)
if (a->nwords > b->nwords)
return true;
/* Check all 'a' members are set in 'b' */
- for (i = 0; i < a->nwords; i++)
- {
+ i = 0;
+ do {
if ((a->words[i] & ~b->words[i]) != 0)
return true;
- }
+ } while (++i < a->nwords);
return false;
}
@@ -566,8 +574,8 @@ bms_singleton_member(const Bitmapset *a)
if (a == NULL)
elog(ERROR, "bitmapset is empty");
nwords = a->nwords;
- for (wordnum = 0; wordnum < nwords; wordnum++)
- {
+ wordnum = 0;
+ do {
bitmapword w = a->words[wordnum];
if (w != 0)
@@ -577,7 +585,7 @@ bms_singleton_member(const Bitmapset *a)
result = wordnum * BITS_PER_BITMAPWORD;
result += bmw_rightmost_one_pos(w);
}
- }
+ } while (++wordnum < nwords);
if (result < 0)
elog(ERROR, "bitmapset is empty");
return result;
@@ -604,8 +612,8 @@ bms_get_singleton_member(const Bitmapset *a, int *member)
if (a == NULL)
return false;
nwords = a->nwords;
- for (wordnum = 0; wordnum < nwords; wordnum++)
- {
+ wordnum = 0;
+ do {
bitmapword w = a->words[wordnum];
if (w != 0)
@@ -615,7 +623,7 @@ bms_get_singleton_member(const Bitmapset *a, int *member)
result = wordnum * BITS_PER_BITMAPWORD;
result += bmw_rightmost_one_pos(w);
}
- }
+ } while (++wordnum < nwords);
if (result < 0)
return false;
*member = result;
@@ -635,14 +643,14 @@ bms_num_members(const Bitmapset *a)
if (a == NULL)
return 0;
nwords = a->nwords;
- for (wordnum = 0; wordnum < nwords; wordnum++)
- {
+ wordnum = 0;
+ do {
bitmapword w = a->words[wordnum];
/* No need to count the bits in a zero word */
if (w != 0)
result += bmw_popcount(w);
- }
+ } while (++wordnum < nwords);
return result;
}
@@ -661,8 +669,8 @@ bms_membership(const Bitmapset *a)
if (a == NULL)
return BMS_EMPTY_SET;
nwords = a->nwords;
- for (wordnum = 0; wordnum < nwords; wordnum++)
- {
+ wordnum = 0;
+ do {
bitmapword w = a->words[wordnum];
if (w != 0)
@@ -671,7 +679,7 @@ bms_membership(const Bitmapset *a)
return BMS_MULTIPLE;
result = BMS_SINGLETON;
}
- }
+ } while (++wordnum < nwords);
return result;
}
@@ -689,13 +697,13 @@ bms_is_empty_internal(const Bitmapset *a)
int wordnum;
nwords = a->nwords;
- for (wordnum = 0; wordnum < nwords; wordnum++)
- {
+ wordnum = 0;
+ do {
bitmapword w = a->words[wordnum];
if (w != 0)
return false;
- }
+ } while (++wordnum < nwords);
return true;
}
@@ -737,8 +745,10 @@ bms_add_member(Bitmapset *a, int x)
a = (Bitmapset *) repalloc(a, BITMAPSET_SIZE(wordnum + 1));
a->nwords = wordnum + 1;
/* zero out the enlarged portion */
- for (i = oldnwords; i < a->nwords; i++)
+ i = oldnwords;
+ do {
a->words[i] = 0;
+ } while (++i < a->nwords);
}
a->words[wordnum] |= ((bitmapword) 1 << bitnum);
@@ -804,8 +814,10 @@ bms_add_members(Bitmapset *a, const Bitmapset *b)
}
/* And union the shorter input into the result */
otherlen = other->nwords;
- for (i = 0; i < otherlen; i++)
+ i = 0;
+ do {
result->words[i] |= other->words[i];
+ } while (++i < otherlen);
if (result != a)
pfree(a);
return result;
@@ -851,8 +863,10 @@ bms_add_range(Bitmapset *a, int lower, int upper)
a = (Bitmapset *) repalloc(a, BITMAPSET_SIZE(uwordnum + 1));
a->nwords = uwordnum + 1;
/* zero out the enlarged portion */
- for (i = oldnwords; i < a->nwords; i++)
+ i = oldnwords;
+ do {
a->words[i] = 0;
+ } while (++i < a->nwords);
}
wordnum = lwordnum = WORDNUM(lower);
@@ -906,13 +920,13 @@ bms_int_members(Bitmapset *a, const Bitmapset *b)
/* Intersect b into a; we need never copy */
shortlen = Min(a->nwords, b->nwords);
lastnonzero = -1;
- for (i = 0; i < shortlen; i++)
- {
+ i = 0;
+ do {
a->words[i] &= b->words[i];
if (a->words[i] != 0)
lastnonzero = i;
- }
+ } while (++i < shortlen);
/* If we computed an empty result, we must return NULL */
if (lastnonzero == -1)
@@ -944,13 +958,13 @@ bms_del_members(Bitmapset *a, const Bitmapset *b)
/* Remove b's bits from a; we need never copy */
shortlen = Min(a->nwords, b->nwords);
lastnonzero = -1;
- for (i = 0; i < shortlen; i++)
- {
+ i = 0;
+ do {
a->words[i] &= ~b->words[i];
if (a->words[i] != 0)
lastnonzero = i;
- }
+ } while (++i < shortlen);
/* If we computed an empty result, we must return NULL */
if (lastnonzero == -1)
@@ -994,8 +1008,10 @@ bms_join(Bitmapset *a, Bitmapset *b)
}
/* And union the shorter input into the result */
otherlen = other->nwords;
- for (i = 0; i < otherlen; i++)
+ i = 0;
+ do {
result->words[i] |= other->words[i];
+ } while (++i < otherlen);
if (other != result) /* pure paranoia */
pfree(other);
return result;
--
2.37.2
Hello,
On Tue, Mar 7, 2023 at 1:07 PM David Rowley <dgrowleyml@gmail.com> wrote:
I adjusted the patch to remove the invariant checks and fixed up a
couple of things I'd missed. The 0002 patch changes the for loops
into do while loops. I wanted to see if we could see any performance
gains from doing this.
I noticed that these patches caused significant degradation while
working on improving planning performance in another thread [1]/messages/by-id/CAJ2pMkY10J_PA2jpH5M-VoOo6BvJnTOO_-t_znu_pOaP0q10pA@mail.gmail.com.
In the experiment, I used the query attached to this email. This
workload consists of eight tables, each of which is split into n
partitions. The "query.sql" measures the planning time of a query that
joins these tables. You can quickly reproduce my experiment using the
following commands.
=====
psql -f create-tables.sql
psql -f query.sql
=====
I show the result in the following tables. I refer to David's patches
in [2]/messages/by-id/CAApHDvq9eq0W_aFUGrb6ba28ieuQN4zM5Uwqxy7+LMZjJc+VGg@mail.gmail.com as the "trailing-zero" patch. When n was large, the
trailing-zero patch showed significant degradation. This is due to too
many calls of repalloc(). With this patch, we cannot reuse spaces
after the last non-zero bitmapword, so we need to call repalloc() more
frequently than before. When n is 256, repalloc() was called only 670
times without the patch, while it was called 5694 times with the
patch.
Table 1: Planning time (ms)
-----------------------------------------------------------------
n | Master | Patched (trailing-zero) | Patched (bitwise-OR)
-----------------------------------------------------------------
1 | 37.639 | 37.330 | 36.979
2 | 36.066 | 35.646 | 36.044
4 | 37.958 | 37.349 | 37.842
8 | 42.397 | 42.994 | 39.779
16 | 54.565 | 67.713 | 44.186
32 | 89.220 | 100.828 | 65.542
64 | 227.854 | 269.059 | 150.398
128 | 896.513 | 1279.965 | 577.671
256 | 4241.994 | 8220.508 | 2538.681
-----------------------------------------------------------------
Table 2: Planning time speedup (higher is better)
------------------------------------------------------
n | Patched (trailing-zero) | Patched (bitwise-OR)
------------------------------------------------------
1 | 100.8% | 101.8%
2 | 101.2% | 100.1%
4 | 101.6% | 100.3%
8 | 98.6% | 106.6%
16 | 80.6% | 123.5%
32 | 88.5% | 136.1%
64 | 84.7% | 151.5%
128 | 70.0% | 155.2%
256 | 51.6% | 167.1%
------------------------------------------------------
On Fri, Mar 3, 2023 at 10:52 AM David Rowley <dgrowleyml@gmail.com> wrote:
The patch also optimizes sub-optimal newly added code which calls
bms_is_empty_internal() when we have other more optimal means to
determine if the set is empty or not.
However, I agree with David's opinion regarding the
bms_is_empty_internal() calls, which is quoted above. I have
implemented this optimization in a slightly different way than David.
My patch is attached to this email. The difference between my patch
and David's is in the determination method of whether the result is
empty: David's patch records the last index of non-zero bitmapword to
minimize the Bitmapset. If the index is -1, we can conclude that the
result is empty. In contrast, my patch uses a more lightweight
operation. I show my changes as follows.
=====
@@ -263,6 +261,7 @@ bms_intersect(const Bitmapset *a, const Bitmapset *b)
const Bitmapset *other;
int resultlen;
int i;
+ bitmapword bitwise_or = 0;
/* Handle cases where either input is NULL */
if (a == NULL || b == NULL)
@@ -281,9 +280,17 @@ bms_intersect(const Bitmapset *a, const Bitmapset *b)
/* And intersect the longer input with the result */
resultlen = result->nwords;
for (i = 0; i < resultlen; i++)
- result->words[i] &= other->words[i];
+ {
+ bitmapword w = (result->words[i] &= other->words[i]);
+
+ /*
+ * Compute bitwise OR of all bitmapwords to determine if the result
+ * is empty
+ */
+ bitwise_or |= w;
+ }
/* If we computed an empty result, we must return NULL */
- if (bms_is_empty_internal(result))
+ if (bitwise_or == 0)
{
pfree(result);
return NULL;
@@ -711,30 +718,6 @@ bms_membership(const Bitmapset *a)
return result;
}
=====
My idea is to compute the bitwise OR of all bitmapwords of the result
Bitmapset. The bitwise OR can be represented as a single operation in
the machine code and does not require any conditional branches. If the
bitwise ORed value is zero, we can conclude the result Bitmapset is
empty. The costs related to this operation can be almost negligible;
it is significantly cheaper than calling bms_is_empty_internal() and
less expensive than using a conditional branch such as 'if.'
In the tables above, I called my patch the "bitwise-OR" patch. The
patch is much faster than the master when n is large. Its speed up
reached 167.1%. I think just adopting this optimization is worth
considering.
[1]: /messages/by-id/CAJ2pMkY10J_PA2jpH5M-VoOo6BvJnTOO_-t_znu_pOaP0q10pA@mail.gmail.com
[2]: /messages/by-id/CAApHDvq9eq0W_aFUGrb6ba28ieuQN4zM5Uwqxy7+LMZjJc+VGg@mail.gmail.com
--
Best regards,
Yuya Watari
Attachments:
v1-0001-Remove-bms_is_empty_internal-function-calls.patchapplication/octet-stream; name=v1-0001-Remove-bms_is_empty_internal-function-calls.patchDownload
From e31a67e4b09a20d6c1922cfe9e729c08e50ffad4 Mon Sep 17 00:00:00 2001
From: Yuya Watari <watari.yuya@gmail.com>
Date: Tue, 14 Mar 2023 15:12:18 +0900
Subject: [PATCH v1] Remove bms_is_empty_internal() function calls
Originally, we checked whether the result of the Bitmapset operation
was empty or not by calling the bms_is_empty_internal() function.
However, these calls lead to unnecessary looping over the result
Bitmapset. This commit reduces such redundant calls and improves the
performance.
---
src/backend/nodes/bitmapset.c | 78 ++++++++++++++++++++---------------
1 file changed, 44 insertions(+), 34 deletions(-)
diff --git a/src/backend/nodes/bitmapset.c b/src/backend/nodes/bitmapset.c
index 7ba3cf635b..b8155ae869 100644
--- a/src/backend/nodes/bitmapset.c
+++ b/src/backend/nodes/bitmapset.c
@@ -64,8 +64,6 @@
#error "invalid BITS_PER_BITMAPWORD"
#endif
-static bool bms_is_empty_internal(const Bitmapset *a);
-
/*
* bms_copy - make a palloc'd copy of a bitmapset
@@ -263,6 +261,7 @@ bms_intersect(const Bitmapset *a, const Bitmapset *b)
const Bitmapset *other;
int resultlen;
int i;
+ bitmapword bitwise_or = 0;
/* Handle cases where either input is NULL */
if (a == NULL || b == NULL)
@@ -281,9 +280,17 @@ bms_intersect(const Bitmapset *a, const Bitmapset *b)
/* And intersect the longer input with the result */
resultlen = result->nwords;
for (i = 0; i < resultlen; i++)
- result->words[i] &= other->words[i];
+ {
+ bitmapword w = (result->words[i] &= other->words[i]);
+
+ /*
+ * Compute bitwise OR of all bitmapwords to determine if the result
+ * is empty
+ */
+ bitwise_or |= w;
+ }
/* If we computed an empty result, we must return NULL */
- if (bms_is_empty_internal(result))
+ if (bitwise_or == 0)
{
pfree(result);
return NULL;
@@ -711,30 +718,6 @@ bms_membership(const Bitmapset *a)
return result;
}
-/*
- * bms_is_empty_internal - is a set empty?
- *
- * This is now used only locally, to detect cases where a function has
- * computed an empty set that we must now get rid of. Hence, we can
- * assume the input isn't NULL.
- */
-static bool
-bms_is_empty_internal(const Bitmapset *a)
-{
- int nwords;
- int wordnum;
-
- nwords = a->nwords;
- for (wordnum = 0; wordnum < nwords; wordnum++)
- {
- bitmapword w = a->words[wordnum];
-
- if (w != 0)
- return false;
- }
- return true;
-}
-
/*
* These operations all "recycle" their non-const inputs, ie, either
@@ -793,6 +776,7 @@ bms_del_member(Bitmapset *a, int x)
{
int wordnum,
bitnum;
+ bitmapword bitwise_or = 0;
if (x < 0)
elog(ERROR, "negative bitmapset member not allowed");
@@ -801,9 +785,17 @@ bms_del_member(Bitmapset *a, int x)
wordnum = WORDNUM(x);
bitnum = BITNUM(x);
if (wordnum < a->nwords)
- a->words[wordnum] &= ~((bitmapword) 1 << bitnum);
+ {
+ bitmapword w = (a->words[wordnum] &= ~((bitmapword) 1 << bitnum));
+
+ /*
+ * Compute bitwise OR of all bitmapwords to determine if the result
+ * is empty
+ */
+ bitwise_or |= w;
+ }
/* If we computed an empty result, we must return NULL */
- if (bms_is_empty_internal(a))
+ if (bitwise_or == 0)
{
pfree(a);
return NULL;
@@ -929,6 +921,7 @@ bms_int_members(Bitmapset *a, const Bitmapset *b)
{
int shortlen;
int i;
+ bitmapword bitwise_or = 0;
/* Handle cases where either input is NULL */
if (a == NULL)
@@ -941,11 +934,19 @@ bms_int_members(Bitmapset *a, const Bitmapset *b)
/* Intersect b into a; we need never copy */
shortlen = Min(a->nwords, b->nwords);
for (i = 0; i < shortlen; i++)
- a->words[i] &= b->words[i];
+ {
+ bitmapword w = (a->words[i] &= b->words[i]);
+
+ /*
+ * Compute bitwise OR of all bitmapwords to determine if the result
+ * is empty
+ */
+ bitwise_or |= w;
+ }
for (; i < a->nwords; i++)
a->words[i] = 0;
/* If we computed an empty result, we must return NULL */
- if (bms_is_empty_internal(a))
+ if (bitwise_or == 0)
{
pfree(a);
return NULL;
@@ -961,6 +962,7 @@ bms_del_members(Bitmapset *a, const Bitmapset *b)
{
int shortlen;
int i;
+ bitmapword bitwise_or = 0;
/* Handle cases where either input is NULL */
if (a == NULL)
@@ -970,9 +972,17 @@ bms_del_members(Bitmapset *a, const Bitmapset *b)
/* Remove b's bits from a; we need never copy */
shortlen = Min(a->nwords, b->nwords);
for (i = 0; i < shortlen; i++)
- a->words[i] &= ~b->words[i];
+ {
+ bitmapword w = (a->words[i] &= ~b->words[i]);
+
+ /*
+ * Compute bitwise OR of all bitmapwords to determine if the result
+ * is empty
+ */
+ bitwise_or |= w;
+ }
/* If we computed an empty result, we must return NULL */
- if (bms_is_empty_internal(a))
+ if (bitwise_or == 0)
{
pfree(a);
return NULL;
--
2.39.2.windows.1
Hello,
On Thu, Mar 16, 2023 at 10:30 AM Yuya Watari <watari.yuya@gmail.com> wrote:
My idea is to compute the bitwise OR of all bitmapwords of the result
Bitmapset. The bitwise OR can be represented as a single operation in
the machine code and does not require any conditional branches. If the
bitwise ORed value is zero, we can conclude the result Bitmapset is
empty. The costs related to this operation can be almost negligible;
it is significantly cheaper than calling bms_is_empty_internal() and
less expensive than using a conditional branch such as 'if.'
After posting the patch, I noticed that my patch had some bugs. My
idea above is not applicable to bms_del_member(), and I missed some
additional operations required in bms_del_members(). I have attached
the fixed version to this email. I really apologize for making the
mistakes. Should we add new regression tests to prevent this kind of
bug?
The following tables illustrate the result of a re-run experiment. The
significant improvement was a mistake, but a speedup of about 2% was
still obtained when the number of partitions, namely n, was large.
This result indicates that the optimization regarding
bms_is_empty_internal() is effective on some workloads.
Table 1: Planning time (ms)
(n: the number of partitions of each table)
-----------------------------------------------------------------
n | Master | Patched (trailing-zero) | Patched (bitwise-OR)
-----------------------------------------------------------------
1 | 36.903 | 36.621 | 36.731
2 | 35.842 | 35.031 | 35.704
4 | 37.756 | 37.457 | 37.409
8 | 42.069 | 42.578 | 42.322
16 | 53.670 | 67.792 | 53.618
32 | 88.412 | 100.605 | 89.147
64 | 229.734 | 271.259 | 225.971
128 | 889.367 | 1272.270 | 870.472
256 | 4209.312 | 8223.623 | 4129.594
-----------------------------------------------------------------
Table 2: Planning time speedup (higher is better)
------------------------------------------------------
n | Patched (trailing-zero) | Patched (bitwise-OR)
------------------------------------------------------
1 | 100.8% | 100.5%
2 | 102.3% | 100.4%
4 | 100.8% | 100.9%
8 | 98.8% | 99.4%
16 | 79.2% | 100.1%
32 | 87.9% | 99.2%
64 | 84.7% | 101.7%
128 | 69.9% | 102.2%
256 | 51.2% | 101.9%
------------------------------------------------------
--
Best regards,
Yuya Watari
Attachments:
v2-0001-Remove-bms_is_empty_internal-function-calls.patchapplication/octet-stream; name=v2-0001-Remove-bms_is_empty_internal-function-calls.patchDownload
From 4c404d3074d33e1f56e95abc5037f20816727235 Mon Sep 17 00:00:00 2001
From: Yuya Watari <watari.yuya@gmail.com>
Date: Tue, 14 Mar 2023 15:12:18 +0900
Subject: [PATCH v2] Remove bms_is_empty_internal() function calls
Originally, we checked whether the result of the Bitmapset operation
was empty or not by calling the bms_is_empty_internal() function.
However, these calls lead to unnecessary looping over the result
Bitmapset. This commit reduces such redundant calls and improves the
performance.
---
src/backend/nodes/bitmapset.c | 42 ++++++++++++++++++++++++++++++-----
1 file changed, 36 insertions(+), 6 deletions(-)
diff --git a/src/backend/nodes/bitmapset.c b/src/backend/nodes/bitmapset.c
index 7ba3cf635b..47eec5b63b 100644
--- a/src/backend/nodes/bitmapset.c
+++ b/src/backend/nodes/bitmapset.c
@@ -263,6 +263,7 @@ bms_intersect(const Bitmapset *a, const Bitmapset *b)
const Bitmapset *other;
int resultlen;
int i;
+ bitmapword bitwise_or = 0;
/* Handle cases where either input is NULL */
if (a == NULL || b == NULL)
@@ -281,9 +282,17 @@ bms_intersect(const Bitmapset *a, const Bitmapset *b)
/* And intersect the longer input with the result */
resultlen = result->nwords;
for (i = 0; i < resultlen; i++)
- result->words[i] &= other->words[i];
+ {
+ bitmapword w = (result->words[i] &= other->words[i]);
+
+ /*
+ * Compute bitwise OR of all bitmapwords to determine if the result
+ * is empty
+ */
+ bitwise_or |= w;
+ }
/* If we computed an empty result, we must return NULL */
- if (bms_is_empty_internal(result))
+ if (bitwise_or == 0)
{
pfree(result);
return NULL;
@@ -929,6 +938,7 @@ bms_int_members(Bitmapset *a, const Bitmapset *b)
{
int shortlen;
int i;
+ bitmapword bitwise_or = 0;
/* Handle cases where either input is NULL */
if (a == NULL)
@@ -941,11 +951,19 @@ bms_int_members(Bitmapset *a, const Bitmapset *b)
/* Intersect b into a; we need never copy */
shortlen = Min(a->nwords, b->nwords);
for (i = 0; i < shortlen; i++)
- a->words[i] &= b->words[i];
+ {
+ bitmapword w = (a->words[i] &= b->words[i]);
+
+ /*
+ * Compute bitwise OR of all bitmapwords to determine if the result
+ * is empty
+ */
+ bitwise_or |= w;
+ }
for (; i < a->nwords; i++)
a->words[i] = 0;
/* If we computed an empty result, we must return NULL */
- if (bms_is_empty_internal(a))
+ if (bitwise_or == 0)
{
pfree(a);
return NULL;
@@ -961,6 +979,7 @@ bms_del_members(Bitmapset *a, const Bitmapset *b)
{
int shortlen;
int i;
+ bitmapword bitwise_or = 0;
/* Handle cases where either input is NULL */
if (a == NULL)
@@ -970,9 +989,20 @@ bms_del_members(Bitmapset *a, const Bitmapset *b)
/* Remove b's bits from a; we need never copy */
shortlen = Min(a->nwords, b->nwords);
for (i = 0; i < shortlen; i++)
- a->words[i] &= ~b->words[i];
+ {
+ bitmapword w = (a->words[i] &= ~b->words[i]);
+
+ /*
+ * Compute bitwise OR of all bitmapwords to determine if the result
+ * is empty
+ */
+ bitwise_or |= w;
+ }
+ /* Compute bitwise OR of extra words in a */
+ for (; i < a->nwords; i++)
+ bitwise_or |= a->words[i];
/* If we computed an empty result, we must return NULL */
- if (bms_is_empty_internal(a))
+ if (bitwise_or == 0)
{
pfree(a);
return NULL;
--
2.39.2.windows.1
Hello,
On Tue, Mar 7, 2023 at 1:07 PM David Rowley <dgrowleyml@gmail.com> wrote:
I adjusted the patch to remove the invariant checks and fixed up a
couple of things I'd missed. The 0002 patch changes the for loops
into do while loops. I wanted to see if we could see any performance
gains from doing this.
In March, I reported that David's patch caused a degradation in
planning performance. I have investigated this issue further and found
some bugs in the patch. Due to these bugs, Bitmapset operations in the
original patch computed incorrect results. This incorrect computation
resulted in unexpected behavior, which I observed as performance
degradation. After fixing the bugs, David's patch showed significant
performance improvements. In particular, it is worth noting that the
patch obtained a good speedup even when most Bitmapsets have only one
word.
1.1. Wrong truncation that we should not do (fixed in v2-0003)
The first bug is in bms_difference() and bms_del_members(). At the end
of these functions, the original patch truncated the result Bitmapset
when lastnonzero was -1. However, we must not do this when the result
Bitmapset is longer than the other. In such a case, the last word of
the result was still non-zero, so we cannot shorten nwords. I fixed
this bug in v2-0003.
1.2. Missing truncation that we should do (fixed in v2-0004)
The other bug is in bms_del_member(). As seen from v2-0004-*.patch,
the original patch missed the necessary truncation. I also fixed this
bug.
2. Experiments
I conducted experiments to evaluate the performance of David's patch
with bug fixes. In the experiments, I used two queries attached to
this email. The first query, Query A (query-a.sql), joins three tables
and performs an aggregation. This is quite a simple query. The second
query, Query B (query-b.sql), is more complicated because it joins
eight tables. In both queries, every table is split into n partitions.
I issued these queries with varying n and measured their planning
times. The following tables and attached figure show the results.
Table 1: Planning time and its speedup of Query A
(n: the number of partitions of each table)
(Speedup: higher is better)
---------------------------------------------
n | Master (ms) | Patched (ms) | Speedup
---------------------------------------------
1 | 0.722 | 0.682 | 105.8%
2 | 0.779 | 0.774 | 100.6%
4 | 0.977 | 0.958 | 101.9%
8 | 1.286 | 1.287 | 99.9%
16 | 1.993 | 1.986 | 100.4%
32 | 3.967 | 3.900 | 101.7%
64 | 7.783 | 7.310 | 106.5%
128 | 23.369 | 19.722 | 118.5%
256 | 108.723 | 75.149 | 144.7%
384 | 265.576 | 167.354 | 158.7%
512 | 516.468 | 301.100 | 171.5%
640 | 883.167 | 494.960 | 178.4%
768 | 1423.839 | 755.201 | 188.5%
896 | 2195.935 | 1127.786 | 194.7%
1024 | 3041.131 | 1444.145 | 210.6%
---------------------------------------------
Table 2: Planning time and its speedup of Query B
--------------------------------------------
n | Master (ms) | Patched (ms) | Speedup
--------------------------------------------
1 | 36.038 | 35.455 | 101.6%
2 | 34.831 | 34.178 | 101.9%
4 | 36.537 | 35.998 | 101.5%
8 | 41.234 | 40.333 | 102.2%
16 | 52.427 | 50.596 | 103.6%
32 | 87.064 | 80.013 | 108.8%
64 | 228.050 | 187.762 | 121.5%
128 | 886.140 | 645.731 | 137.2%
256 | 4212.709 | 2853.072 | 147.7%
--------------------------------------------
You can quickly reproduce my experiments by the following commands.
== Query A ==
psql -f create-tables-a.sql
psql -f query-a.sql
=============
== Query B ==
psql -f create-tables-b.sql
psql -f query-b.sql
=============
The above results indicate that David's patch demonstrated outstanding
performance. The speedup reached 210.6% for Query A and 147.7% for
Query B. Even when n is small, the patch reduced planning time. The
main concern about this patch was overheads for Bitmapsets with only
one or two words. My experiments imply that such overheads are
non-existent or negligible because some performance improvements were
obtained even for small sizes.
The results of my experiments strongly support the effectiveness of
David's patch. I think this optimization is worth considering.
I am looking forward to your comments.
--
Best regards,
Yuya Watari
Attachments:
v2-0001-Remove-trailing-zero-words-from-Bitmapsets.patchapplication/octet-stream; name=v2-0001-Remove-trailing-zero-words-from-Bitmapsets.patchDownload
From cbe1d770f5984c1a84b1a7db21c7c83866fd457c Mon Sep 17 00:00:00 2001
From: David Rowley <dgrowley@gmail.com>
Date: Fri, 3 Mar 2023 16:40:29 +1300
Subject: [PATCH v2 1/4] Remove trailing zero words from Bitmapsets
---
src/backend/nodes/bitmapset.c | 207 +++++++++++++++-------------------
1 file changed, 89 insertions(+), 118 deletions(-)
diff --git a/src/backend/nodes/bitmapset.c b/src/backend/nodes/bitmapset.c
index 7ba3cf635b..14fb100087 100644
--- a/src/backend/nodes/bitmapset.c
+++ b/src/backend/nodes/bitmapset.c
@@ -5,8 +5,10 @@
*
* A bitmap set can represent any set of nonnegative integers, although
* it is mainly intended for sets where the maximum value is not large,
- * say at most a few hundred. By convention, we always represent the
- * empty set by a NULL pointer.
+ * say at most a few hundred. By convention, we always represent a set with
+ * the minimum possible number of words, i.e, there are never any trailing
+ * zero words. Enforcing this requires that an empty set is represented as
+ * NULL.
*
*
* Copyright (c) 2003-2023, PostgreSQL Global Development Group
@@ -85,18 +87,11 @@ bms_copy(const Bitmapset *a)
}
/*
- * bms_equal - are two bitmapsets equal?
- *
- * This is logical not physical equality; in particular, a NULL pointer will
- * be reported as equal to a palloc'd value containing no members.
+ * bms_equal - are two bitmapsets equal? or both NULL?
*/
bool
bms_equal(const Bitmapset *a, const Bitmapset *b)
{
- const Bitmapset *shorter;
- const Bitmapset *longer;
- int shortlen;
- int longlen;
int i;
/* Handle cases where either input is NULL */
@@ -108,30 +103,18 @@ bms_equal(const Bitmapset *a, const Bitmapset *b)
}
else if (b == NULL)
return false;
- /* Identify shorter and longer input */
- if (a->nwords <= b->nwords)
- {
- shorter = a;
- longer = b;
- }
- else
- {
- shorter = b;
- longer = a;
- }
- /* And process */
- shortlen = shorter->nwords;
- for (i = 0; i < shortlen; i++)
- {
- if (shorter->words[i] != longer->words[i])
- return false;
- }
- longlen = longer->nwords;
- for (; i < longlen; i++)
+
+ /* can't be equal if the word counts don't match */
+ if (a->nwords != b->nwords)
+ return false;
+
+ /* check each word matches */
+ for (i = 0; i < a->nwords; i++)
{
- if (longer->words[i] != 0)
+ if (a->words[i] != b->words[i])
return false;
}
+
return true;
}
@@ -146,29 +129,18 @@ bms_equal(const Bitmapset *a, const Bitmapset *b)
int
bms_compare(const Bitmapset *a, const Bitmapset *b)
{
- int shortlen;
int i;
-
/* Handle cases where either input is NULL */
if (a == NULL)
return (b == NULL) ? 0 : -1;
else if (b == NULL)
return +1;
- /* Handle cases where one input is longer than the other */
- shortlen = Min(a->nwords, b->nwords);
- for (i = shortlen; i < a->nwords; i++)
- {
- if (a->words[i] != 0)
- return +1;
- }
- for (i = shortlen; i < b->nwords; i++)
- {
- if (b->words[i] != 0)
- return -1;
- }
- /* Process words in common */
- i = shortlen;
- while (--i >= 0)
+
+ /* the set with the most words must be greater */
+ if (a->nwords != b->nwords)
+ return (a->nwords > b->nwords) ? +1 : -1;
+
+ for (i = a->nwords - 1; i >= 0; i--)
{
bitmapword aw = a->words[i];
bitmapword bw = b->words[i];
@@ -261,6 +233,7 @@ bms_intersect(const Bitmapset *a, const Bitmapset *b)
{
Bitmapset *result;
const Bitmapset *other;
+ int lastnonzero;
int resultlen;
int i;
@@ -280,14 +253,23 @@ bms_intersect(const Bitmapset *a, const Bitmapset *b)
}
/* And intersect the longer input with the result */
resultlen = result->nwords;
+ lastnonzero = -1;
for (i = 0; i < resultlen; i++)
+ {
result->words[i] &= other->words[i];
+
+ if (result->words[i] != 0)
+ lastnonzero = i;
+ }
/* If we computed an empty result, we must return NULL */
- if (bms_is_empty_internal(result))
+ if (lastnonzero == -1)
{
pfree(result);
return NULL;
}
+
+ /* get rid of trailing zero words */
+ result->nwords = lastnonzero + 1;
return result;
}
@@ -298,6 +280,7 @@ Bitmapset *
bms_difference(const Bitmapset *a, const Bitmapset *b)
{
Bitmapset *result;
+ int lastnonzero;
int shortlen;
int i;
@@ -319,8 +302,19 @@ bms_difference(const Bitmapset *a, const Bitmapset *b)
result = bms_copy(a);
/* And remove b's bits from result */
shortlen = Min(a->nwords, b->nwords);
+ lastnonzero = -1;
for (i = 0; i < shortlen; i++)
+ {
result->words[i] &= ~b->words[i];
+
+ if (result->words[i] != 0)
+ lastnonzero = i;
+ }
+
+ /* get rid of trailing zero words */
+ result->nwords = lastnonzero + 1;
+ Assert(result->nwords != 0);
+
/* Need not check for empty result, since we handled that case above */
return result;
}
@@ -331,32 +325,23 @@ bms_difference(const Bitmapset *a, const Bitmapset *b)
bool
bms_is_subset(const Bitmapset *a, const Bitmapset *b)
{
- int shortlen;
- int longlen;
int i;
-
/* Handle cases where either input is NULL */
if (a == NULL)
return true; /* empty set is a subset of anything */
if (b == NULL)
return false;
- /* Check common words */
- shortlen = Min(a->nwords, b->nwords);
- for (i = 0; i < shortlen; i++)
+
+ /* 'a' can't be a subset of 'b' if it contains more words */
+ if (a->nwords > b->nwords)
+ return false;
+
+ /* Check all 'a' members are set in 'b' */
+ for (i = 0; i < a->nwords; i++)
{
if ((a->words[i] & ~b->words[i]) != 0)
return false;
}
- /* Check extra words */
- if (a->nwords > b->nwords)
- {
- longlen = a->nwords;
- for (; i < longlen; i++)
- {
- if (a->words[i] != 0)
- return false;
- }
- }
return true;
}
@@ -370,7 +355,6 @@ bms_subset_compare(const Bitmapset *a, const Bitmapset *b)
{
BMS_Comparison result;
int shortlen;
- int longlen;
int i;
/* Handle cases where either input is NULL */
@@ -408,31 +392,17 @@ bms_subset_compare(const Bitmapset *a, const Bitmapset *b)
/* Check extra words */
if (a->nwords > b->nwords)
{
- longlen = a->nwords;
- for (; i < longlen; i++)
- {
- if (a->words[i] != 0)
- {
- /* a is not a subset of b */
- if (result == BMS_SUBSET1)
- return BMS_DIFFERENT;
- result = BMS_SUBSET2;
- }
- }
+ /* if a has more words then a is not a subset of b */
+ if (result == BMS_SUBSET1)
+ return BMS_DIFFERENT;
+ return BMS_SUBSET2;
}
else if (a->nwords < b->nwords)
{
- longlen = b->nwords;
- for (; i < longlen; i++)
- {
- if (b->words[i] != 0)
- {
- /* b is not a subset of a */
- if (result == BMS_SUBSET2)
- return BMS_DIFFERENT;
- result = BMS_SUBSET1;
- }
- }
+ /* if b has more words then b is not a subset of a */
+ if (result == BMS_SUBSET2)
+ return BMS_DIFFERENT;
+ return BMS_SUBSET1;
}
return result;
}
@@ -563,27 +533,21 @@ bms_overlap_list(const Bitmapset *a, const List *b)
bool
bms_nonempty_difference(const Bitmapset *a, const Bitmapset *b)
{
- int shortlen;
int i;
-
/* Handle cases where either input is NULL */
if (a == NULL)
return false;
if (b == NULL)
return true;
- /* Check words in common */
- shortlen = Min(a->nwords, b->nwords);
- for (i = 0; i < shortlen; i++)
+ /* if a has more words then it must contain additional members */
+ if (a->nwords > b->nwords)
+ return true;
+ /* Check all 'a' members are set in 'b' */
+ for (i = 0; i < a->nwords; i++)
{
if ((a->words[i] & ~b->words[i]) != 0)
return true;
}
- /* Check extra words in a */
- for (; i < a->nwords; i++)
- {
- if (a->words[i] != 0)
- return true;
- }
return false;
}
@@ -927,6 +891,7 @@ bms_add_range(Bitmapset *a, int lower, int upper)
Bitmapset *
bms_int_members(Bitmapset *a, const Bitmapset *b)
{
+ int lastnonzero;
int shortlen;
int i;
@@ -940,16 +905,24 @@ bms_int_members(Bitmapset *a, const Bitmapset *b)
}
/* Intersect b into a; we need never copy */
shortlen = Min(a->nwords, b->nwords);
+ lastnonzero = -1;
for (i = 0; i < shortlen; i++)
+ {
a->words[i] &= b->words[i];
- for (; i < a->nwords; i++)
- a->words[i] = 0;
+
+ if (a->words[i] != 0)
+ lastnonzero = i;
+ }
+
/* If we computed an empty result, we must return NULL */
- if (bms_is_empty_internal(a))
+ if (lastnonzero == -1)
{
pfree(a);
return NULL;
}
+
+ /* get rid of trailing zero words */
+ a->nwords = lastnonzero + 1;
return a;
}
@@ -959,6 +932,7 @@ bms_int_members(Bitmapset *a, const Bitmapset *b)
Bitmapset *
bms_del_members(Bitmapset *a, const Bitmapset *b)
{
+ int lastnonzero;
int shortlen;
int i;
@@ -969,14 +943,25 @@ bms_del_members(Bitmapset *a, const Bitmapset *b)
return a;
/* Remove b's bits from a; we need never copy */
shortlen = Min(a->nwords, b->nwords);
+ lastnonzero = -1;
for (i = 0; i < shortlen; i++)
+ {
a->words[i] &= ~b->words[i];
+
+ if (a->words[i] != 0)
+ lastnonzero = i;
+ }
+
/* If we computed an empty result, we must return NULL */
- if (bms_is_empty_internal(a))
+ if (lastnonzero == -1)
{
pfree(a);
return NULL;
}
+
+ /* get rid of trailing zero words */
+ a->nwords = lastnonzero + 1;
+
return a;
}
@@ -1140,28 +1125,14 @@ bms_prev_member(const Bitmapset *a, int prevbit)
/*
* bms_hash_value - compute a hash key for a Bitmapset
- *
- * Note: we must ensure that any two bitmapsets that are bms_equal() will
- * hash to the same value; in practice this means that trailing all-zero
- * words must not affect the result. Hence we strip those before applying
- * hash_any().
*/
uint32
bms_hash_value(const Bitmapset *a)
{
- int lastword;
-
if (a == NULL)
return 0; /* All empty sets hash to 0 */
- for (lastword = a->nwords; --lastword >= 0;)
- {
- if (a->words[lastword] != 0)
- break;
- }
- if (lastword < 0)
- return 0; /* All empty sets hash to 0 */
return DatumGetUInt32(hash_any((const unsigned char *) a->words,
- (lastword + 1) * sizeof(bitmapword)));
+ a->nwords * sizeof(bitmapword)));
}
/*
--
2.41.0.windows.1
v2-0002-Use-do-while-loops-instead-of-for-loops.patchapplication/octet-stream; name=v2-0002-Use-do-while-loops-instead-of-for-loops.patchDownload
From b1fdf930965460eedf8cf9c25ebb6087530fa5da Mon Sep 17 00:00:00 2001
From: David Rowley <dgrowley@gmail.com>
Date: Tue, 7 Mar 2023 12:43:26 +1300
Subject: [PATCH v2 2/4] Use do while loops instead of for loops
---
src/backend/nodes/bitmapset.c | 118 +++++++++++++++++++---------------
1 file changed, 67 insertions(+), 51 deletions(-)
diff --git a/src/backend/nodes/bitmapset.c b/src/backend/nodes/bitmapset.c
index 14fb100087..aec7392cff 100644
--- a/src/backend/nodes/bitmapset.c
+++ b/src/backend/nodes/bitmapset.c
@@ -8,7 +8,13 @@
* say at most a few hundred. By convention, we always represent a set with
* the minimum possible number of words, i.e, there are never any trailing
* zero words. Enforcing this requires that an empty set is represented as
- * NULL.
+ * NULL. Because an empty Bitmapset is represented as NULL, a non-NULL
+ * Bitmapset always has at least 1 Bitmapword. We can exploit this fact to
+ * speedup various loops over the Bitmapset's words array by using "do while"
+ * loops instead of "for" loops. This means the code does not waste time
+ * checking the loop condition before the first iteration. For Bitmapsets
+ * containing only a single word (likely the majority of them) this reduces
+ * the loop condition tests by half.
*
*
* Copyright (c) 2003-2023, PostgreSQL Global Development Group
@@ -109,11 +115,11 @@ bms_equal(const Bitmapset *a, const Bitmapset *b)
return false;
/* check each word matches */
- for (i = 0; i < a->nwords; i++)
- {
+ i = 0;
+ do {
if (a->words[i] != b->words[i])
return false;
- }
+ } while (++i < a->nwords);
return true;
}
@@ -140,14 +146,14 @@ bms_compare(const Bitmapset *a, const Bitmapset *b)
if (a->nwords != b->nwords)
return (a->nwords > b->nwords) ? +1 : -1;
- for (i = a->nwords - 1; i >= 0; i--)
- {
+ i = a->nwords - 1;
+ do {
bitmapword aw = a->words[i];
bitmapword bw = b->words[i];
if (aw != bw)
return (aw > bw) ? +1 : -1;
- }
+ } while (--i >= 0);
return 0;
}
@@ -220,8 +226,10 @@ bms_union(const Bitmapset *a, const Bitmapset *b)
}
/* And union the shorter input into the result */
otherlen = other->nwords;
- for (i = 0; i < otherlen; i++)
+ i = 0;
+ do {
result->words[i] |= other->words[i];
+ } while (++i < otherlen);
return result;
}
@@ -254,13 +262,13 @@ bms_intersect(const Bitmapset *a, const Bitmapset *b)
/* And intersect the longer input with the result */
resultlen = result->nwords;
lastnonzero = -1;
- for (i = 0; i < resultlen; i++)
- {
+ i = 0;
+ do {
result->words[i] &= other->words[i];
if (result->words[i] != 0)
lastnonzero = i;
- }
+ } while (++i < resultlen);
/* If we computed an empty result, we must return NULL */
if (lastnonzero == -1)
{
@@ -303,13 +311,13 @@ bms_difference(const Bitmapset *a, const Bitmapset *b)
/* And remove b's bits from result */
shortlen = Min(a->nwords, b->nwords);
lastnonzero = -1;
- for (i = 0; i < shortlen; i++)
- {
+ i = 0;
+ do {
result->words[i] &= ~b->words[i];
if (result->words[i] != 0)
lastnonzero = i;
- }
+ } while (++i < shortlen);
/* get rid of trailing zero words */
result->nwords = lastnonzero + 1;
@@ -337,11 +345,11 @@ bms_is_subset(const Bitmapset *a, const Bitmapset *b)
return false;
/* Check all 'a' members are set in 'b' */
- for (i = 0; i < a->nwords; i++)
- {
+ i = 0;
+ do {
if ((a->words[i] & ~b->words[i]) != 0)
return false;
- }
+ } while (++i < a->nwords);
return true;
}
@@ -369,8 +377,8 @@ bms_subset_compare(const Bitmapset *a, const Bitmapset *b)
/* Check common words */
result = BMS_EQUAL; /* status so far */
shortlen = Min(a->nwords, b->nwords);
- for (i = 0; i < shortlen; i++)
- {
+ i = 0;
+ do {
bitmapword aword = a->words[i];
bitmapword bword = b->words[i];
@@ -388,7 +396,7 @@ bms_subset_compare(const Bitmapset *a, const Bitmapset *b)
return BMS_DIFFERENT;
result = BMS_SUBSET1;
}
- }
+ } while (++i < shortlen);
/* Check extra words */
if (a->nwords > b->nwords)
{
@@ -488,11 +496,11 @@ bms_overlap(const Bitmapset *a, const Bitmapset *b)
return false;
/* Check words in common */
shortlen = Min(a->nwords, b->nwords);
- for (i = 0; i < shortlen; i++)
- {
+ i = 0;
+ do {
if ((a->words[i] & b->words[i]) != 0)
return true;
- }
+ } while (++i < shortlen);
return false;
}
@@ -543,11 +551,11 @@ bms_nonempty_difference(const Bitmapset *a, const Bitmapset *b)
if (a->nwords > b->nwords)
return true;
/* Check all 'a' members are set in 'b' */
- for (i = 0; i < a->nwords; i++)
- {
+ i = 0;
+ do {
if ((a->words[i] & ~b->words[i]) != 0)
return true;
- }
+ } while (++i < a->nwords);
return false;
}
@@ -566,8 +574,8 @@ bms_singleton_member(const Bitmapset *a)
if (a == NULL)
elog(ERROR, "bitmapset is empty");
nwords = a->nwords;
- for (wordnum = 0; wordnum < nwords; wordnum++)
- {
+ wordnum = 0;
+ do {
bitmapword w = a->words[wordnum];
if (w != 0)
@@ -577,7 +585,7 @@ bms_singleton_member(const Bitmapset *a)
result = wordnum * BITS_PER_BITMAPWORD;
result += bmw_rightmost_one_pos(w);
}
- }
+ } while (++wordnum < nwords);
if (result < 0)
elog(ERROR, "bitmapset is empty");
return result;
@@ -604,8 +612,8 @@ bms_get_singleton_member(const Bitmapset *a, int *member)
if (a == NULL)
return false;
nwords = a->nwords;
- for (wordnum = 0; wordnum < nwords; wordnum++)
- {
+ wordnum = 0;
+ do {
bitmapword w = a->words[wordnum];
if (w != 0)
@@ -615,7 +623,7 @@ bms_get_singleton_member(const Bitmapset *a, int *member)
result = wordnum * BITS_PER_BITMAPWORD;
result += bmw_rightmost_one_pos(w);
}
- }
+ } while (++wordnum < nwords);
if (result < 0)
return false;
*member = result;
@@ -635,14 +643,14 @@ bms_num_members(const Bitmapset *a)
if (a == NULL)
return 0;
nwords = a->nwords;
- for (wordnum = 0; wordnum < nwords; wordnum++)
- {
+ wordnum = 0;
+ do {
bitmapword w = a->words[wordnum];
/* No need to count the bits in a zero word */
if (w != 0)
result += bmw_popcount(w);
- }
+ } while (++wordnum < nwords);
return result;
}
@@ -661,8 +669,8 @@ bms_membership(const Bitmapset *a)
if (a == NULL)
return BMS_EMPTY_SET;
nwords = a->nwords;
- for (wordnum = 0; wordnum < nwords; wordnum++)
- {
+ wordnum = 0;
+ do {
bitmapword w = a->words[wordnum];
if (w != 0)
@@ -671,7 +679,7 @@ bms_membership(const Bitmapset *a)
return BMS_MULTIPLE;
result = BMS_SINGLETON;
}
- }
+ } while (++wordnum < nwords);
return result;
}
@@ -689,13 +697,13 @@ bms_is_empty_internal(const Bitmapset *a)
int wordnum;
nwords = a->nwords;
- for (wordnum = 0; wordnum < nwords; wordnum++)
- {
+ wordnum = 0;
+ do {
bitmapword w = a->words[wordnum];
if (w != 0)
return false;
- }
+ } while (++wordnum < nwords);
return true;
}
@@ -737,8 +745,10 @@ bms_add_member(Bitmapset *a, int x)
a = (Bitmapset *) repalloc(a, BITMAPSET_SIZE(wordnum + 1));
a->nwords = wordnum + 1;
/* zero out the enlarged portion */
- for (i = oldnwords; i < a->nwords; i++)
+ i = oldnwords;
+ do {
a->words[i] = 0;
+ } while (++i < a->nwords);
}
a->words[wordnum] |= ((bitmapword) 1 << bitnum);
@@ -804,8 +814,10 @@ bms_add_members(Bitmapset *a, const Bitmapset *b)
}
/* And union the shorter input into the result */
otherlen = other->nwords;
- for (i = 0; i < otherlen; i++)
+ i = 0;
+ do {
result->words[i] |= other->words[i];
+ } while (++i < otherlen);
if (result != a)
pfree(a);
return result;
@@ -851,8 +863,10 @@ bms_add_range(Bitmapset *a, int lower, int upper)
a = (Bitmapset *) repalloc(a, BITMAPSET_SIZE(uwordnum + 1));
a->nwords = uwordnum + 1;
/* zero out the enlarged portion */
- for (i = oldnwords; i < a->nwords; i++)
+ i = oldnwords;
+ do {
a->words[i] = 0;
+ } while (++i < a->nwords);
}
wordnum = lwordnum = WORDNUM(lower);
@@ -906,13 +920,13 @@ bms_int_members(Bitmapset *a, const Bitmapset *b)
/* Intersect b into a; we need never copy */
shortlen = Min(a->nwords, b->nwords);
lastnonzero = -1;
- for (i = 0; i < shortlen; i++)
- {
+ i = 0;
+ do {
a->words[i] &= b->words[i];
if (a->words[i] != 0)
lastnonzero = i;
- }
+ } while (++i < shortlen);
/* If we computed an empty result, we must return NULL */
if (lastnonzero == -1)
@@ -944,13 +958,13 @@ bms_del_members(Bitmapset *a, const Bitmapset *b)
/* Remove b's bits from a; we need never copy */
shortlen = Min(a->nwords, b->nwords);
lastnonzero = -1;
- for (i = 0; i < shortlen; i++)
- {
+ i = 0;
+ do {
a->words[i] &= ~b->words[i];
if (a->words[i] != 0)
lastnonzero = i;
- }
+ } while (++i < shortlen);
/* If we computed an empty result, we must return NULL */
if (lastnonzero == -1)
@@ -994,8 +1008,10 @@ bms_join(Bitmapset *a, Bitmapset *b)
}
/* And union the shorter input into the result */
otherlen = other->nwords;
- for (i = 0; i < otherlen; i++)
+ i = 0;
+ do {
result->words[i] |= other->words[i];
+ } while (++i < otherlen);
if (other != result) /* pure paranoia */
pfree(other);
return result;
--
2.41.0.windows.1
v2-0003-Fixed-a-bug-where-the-result-Bitmapset-was-incorr.patchapplication/octet-stream; name=v2-0003-Fixed-a-bug-where-the-result-Bitmapset-was-incorr.patchDownload
From 361af5f930f4bb49804a1378df3c3840f7f62a1c Mon Sep 17 00:00:00 2001
From: Yuya Watari <watari.yuya@gmail.com>
Date: Fri, 9 Jun 2023 18:35:25 +0900
Subject: [PATCH v2 3/4] Fixed a bug where the result Bitmapset was incorrectly
truncated
If the result Bitmapset is longer than the other, we must not get rid
of its trailing words because they have at least one non-zero word.
---
src/backend/nodes/bitmapset.c | 17 +++++++++++++----
1 file changed, 13 insertions(+), 4 deletions(-)
diff --git a/src/backend/nodes/bitmapset.c b/src/backend/nodes/bitmapset.c
index aec7392cff..1839292d4b 100644
--- a/src/backend/nodes/bitmapset.c
+++ b/src/backend/nodes/bitmapset.c
@@ -319,8 +319,14 @@ bms_difference(const Bitmapset *a, const Bitmapset *b)
lastnonzero = i;
} while (++i < shortlen);
- /* get rid of trailing zero words */
- result->nwords = lastnonzero + 1;
+ /*
+ * get rid of trailing zero words.
+ *
+ * We cannot do this if 'a' is longer than 'b' because 'a' can never be
+ * empty in such cases.
+ */
+ if (shortlen == a->nwords)
+ result->nwords = lastnonzero + 1;
Assert(result->nwords != 0);
/* Need not check for empty result, since we handled that case above */
@@ -966,8 +972,11 @@ bms_del_members(Bitmapset *a, const Bitmapset *b)
lastnonzero = i;
} while (++i < shortlen);
- /* If we computed an empty result, we must return NULL */
- if (lastnonzero == -1)
+ /*
+ * If we computed an empty result, we must return NULL.
+ * Note that 'a' can never be empty if it is longer than 'b'.
+ */
+ if (lastnonzero == -1 && shortlen == a->nwords)
{
pfree(a);
return NULL;
--
2.41.0.windows.1
v2-0004-Fix-a-bug-where-the-necessary-truncation-was-miss.patchapplication/octet-stream; name=v2-0004-Fix-a-bug-where-the-necessary-truncation-was-miss.patchDownload
From 7025d85048468134823cfeec1c84559bb2607634 Mon Sep 17 00:00:00 2001
From: Yuya Watari <watari.yuya@gmail.com>
Date: Mon, 12 Jun 2023 07:33:04 +0900
Subject: [PATCH v2 4/4] Fix a bug where the necessary truncation was missing
---
src/backend/nodes/bitmapset.c | 53 +++++++++++++++--------------------
1 file changed, 22 insertions(+), 31 deletions(-)
diff --git a/src/backend/nodes/bitmapset.c b/src/backend/nodes/bitmapset.c
index 1839292d4b..fd59826c00 100644
--- a/src/backend/nodes/bitmapset.c
+++ b/src/backend/nodes/bitmapset.c
@@ -72,8 +72,6 @@
#error "invalid BITS_PER_BITMAPWORD"
#endif
-static bool bms_is_empty_internal(const Bitmapset *a);
-
/*
* bms_copy - make a palloc'd copy of a bitmapset
@@ -689,30 +687,6 @@ bms_membership(const Bitmapset *a)
return result;
}
-/*
- * bms_is_empty_internal - is a set empty?
- *
- * This is now used only locally, to detect cases where a function has
- * computed an empty set that we must now get rid of. Hence, we can
- * assume the input isn't NULL.
- */
-static bool
-bms_is_empty_internal(const Bitmapset *a)
-{
- int nwords;
- int wordnum;
-
- nwords = a->nwords;
- wordnum = 0;
- do {
- bitmapword w = a->words[wordnum];
-
- if (w != 0)
- return false;
- } while (++wordnum < nwords);
- return true;
-}
-
/*
* These operations all "recycle" their non-const inputs, ie, either
@@ -781,12 +755,29 @@ bms_del_member(Bitmapset *a, int x)
wordnum = WORDNUM(x);
bitnum = BITNUM(x);
if (wordnum < a->nwords)
- a->words[wordnum] &= ~((bitmapword) 1 << bitnum);
- /* If we computed an empty result, we must return NULL */
- if (bms_is_empty_internal(a))
{
- pfree(a);
- return NULL;
+ a->words[wordnum] &= ~((bitmapword) 1 << bitnum);
+
+ if (a->words[wordnum] == 0)
+ {
+ int lastnonzero;
+
+ /* If this word became zero, we may have to truncate the result */
+ lastnonzero = a->nwords - 1;
+ do
+ {
+ if (a->words[lastnonzero] != 0)
+ break;
+ } while (--lastnonzero >= 0);
+ /* If we computed an empty result, we must return NULL */
+ if (lastnonzero == -1)
+ {
+ pfree(a);
+ return NULL;
+ }
+ /* get rid of trailing zero words */
+ a->nwords = lastnonzero + 1;
+ }
}
return a;
}
--
2.41.0.windows.1
figure.pngimage/png; name=figure.pngDownload
�PNG
IHDR b 8 J�� sRGB ��� gAMA ���a pHYs � �]�� ��IDATx^��xU�� �J�B���
v���w�c��{����W�.��]QEEQP����|����L&��n�M6���wf�d����w����1��� 2����m��A~+9w�u��y��~ 2C] �
F M��&�g�}l�]w��K��= �~-[����;�oULj��{������ �6lh�������k~O$s�����'��� ������ILEb��(� ��=��v�)���Hj2f� �]4�B� �4! �&b ��@ @�� H1 iB M� � � �4! �&b ��@ @�� H1 iB M� � � �4! �&b ��@ @�� H1 iB M� � � �4! �&b ��@ �l��6s�L�5k���;�-Zd�/������Km���[�������< H��0�O�_�e��y�o����o�>����1��_�~��ONN�� d�:�K���;����:�,�T�%K���!C��dvv��[:�$�[��������cG[k���M�6���������#�X�&Ml�������������E���k����5j��5|v�a�v�m�������j�>��5n����X:n{��e{���}��7���o������m�����t��w�{�>���}h������U�~}��bL�2��x�
���/l�����W��@VV�m�����eK�}����H����~K���~�I���r�J����s�1�@��SG�������A��Vr���.;��3�V�������� &X�z������w�����m���M�.]�5�S���?�pS;.��"k����������Y��
��Np���j�����O�����qE���v������W_m
4p'���:����������i��f�����_�/�n�y�U+��5�O)�3z�h�8q��&�C��;u�����w����@���j���6i���~k�S?�O�>��E[u�U�5@����;�����[1�����;���� �������(8����7��Z�l����������GN����+r��c
�����/�z���kj���~��k��e���w���n*����/w���~��"�]t�v�m��������9������5j��%Z�5k�w�)����?�?j
����[����O�� �^��<x���<�'�@:��������R�^���M��m��v�����7���c������E���2i�$M���_{M*zi����kE_�:u����=�_�L�t�����_���]^~�e��1n����={��[���u�����*y#F�����f���)���E}�����m���y.��
T�Z��$��P�4�%�K�o��fh4�F^h��FYhdM"���f���4b)L33j����O0�&:B�c��F��x��~+����W���`����^Zd�M24�V�&4B�����{Q\y��~��~O5k ����DY�b��������)��b�o����R����GT�����g����"��#�Z��d6�4�j��l��q~O|=z��k���cp�M~���79�M������{�����3�_��B������o��y�H��!��r������LyE|�0�)mVm�l�2��>j<H���n#3)0���;�m��fw�}��\�t�I������{m����[E�����j��w�K��>j��P���:,^x����.�q(�_~�_ T�����6�d�����+y�<�ae�-�������_���o�V�R�?�����(E��/����J1��SO�=E�����8��w��Q�F��x�5�l��6�����=��t�\s�5~�|��A����F#���hv��_~i��u+�����������Z� �Fe�1�o�����_�~~�l�}��a���-�j���v�����L*�w�q��FWm�:�K������n��cXT'��_t�k5�+}6��V^{�5w�^�9����p�!���������&?��cv�������<��\r��*�|���~������)N��U?K�d�;�0����:�6�~_}�U�e��W_��@U��qK�d��v��>��C�e��{���[nY� �u"S��\p�M�<�_��
�����!��}���2�:u���������k���B��
��_[���~vI3c��Q�D�{���~��nf��(�(��f���~{7�[����G}�V���~��"���������u����OU����o�#�8���O�������M���R�{�M7�[�d����D����V��/^������3f���/��~��7����
��1�R����:�s����w��k���W_�<���W���c�-
�wT��f�}��� �+��]�F�j��������{+�K/�T�����~�o���^{-����������k�"�����7n\���n��[U+|��F2��;�X�x+�o����j-<��c�E�������N���*��+�6�l�"���w���EMv�Ey�o��vM�R�����r����T�r����p�qV_}ud:}�l��VE���>��_��Y�f��o���c���j�Z ����%�,���7o��*��@�����x�P�idWE�������[1�;w�������d���v��mv��G��?���P�ht�[o������f[s�5�{��~Ol��f� �.�������j��O?�T�;Y4� �T�j���_��G3���Z�IYT;+��+�p)�S�1�,JI����=1�;�#;*G�����icO?����QV����o��@���T��c��5 �Le9IS�[n�������)�AJ�Ti:�RC�)����M��Q�:9�������W^y�o *����UF
B H�R.�����,�&U��0�������V�4`w�}��[1O<����=�o��S:x�?
�*�Tk���s�����B�5����+�rR�2�A�I�Z���(����z�N��U�0�����.����E�zt-��YZ}�0�j�4i�{�
�.����M���k�`�m��5?n�cB��:+�vu�cD�{��E���Z����k�F��������{��2xm��T�qu�!����ZQ�CY����%x��Y�7�/}.�����$��W�������I�������{�Z�&���e������2a��dQ:��o�����J�z���:�<��>�Cz��Cz�u-��i=������sT�3����Lu��>{�s�����������v[����'�TJ�^ @q�~��NLE�o��&������8�� ���71���w_�[���^���S�������E�t��}'��S�;����"����'Nt��2^�O�CmE=�3QA�T�u����O���<J�'x~j����.��b������� n�g������d��z]��K�?T�_�Y�q��+Ky�3�3������E�e���T� �2���h��
7����F�x�y��U����A�,�+���k��#�sF�~����9
����{��
O���g������>����?�k�c���)����a��~-F�����_�P#���)V#&��a?��c�cK4_dYk���(������c�=�V]u�"��E5j�w�����[�����{��e����b�-���������??o�5��k��i����z���y��y�1����{�����yy�F��;���\����n�M7����K��;;����}��E��a��]�]w��^�-Z�M���]��w�y��25/��r�q��^����j�*����r�/[n�e��YYY~oz�7����y������������_9z����+��.��Z������z
v�e�w7��~�-o�=��k��Y���k�.o��v������-S��/�m��6yo�q��U�
��s�� UY�;my���j^����{��h/��t��59r��G|����W�����{���/,�X�:u����k�g��9��~�A��k��.��U4o�����)Y~��}����g��EC���������G�{�N�<F�>}���P���|g��=����F��nX�_���R��O?��=�5����/y�}���_}�}�Y
P5��#5b���5b^�uM���S���=�����Be����jW�}�,]�t��|���N;�������{%�����_~����{���]m�5�\��m��d�M���oY�p�Y������+���/v������&�o��}�L�8�_S��o�)r�q���k�����������X�F���w�9����LM�f�{�CjQ;5�f���_�\_�Z�,YR�FLYj����e��Y��B�cm��in��+\z���.r�����iQ3f��;����������a�\��,�?�����[�qu�C�)�=�����z���r|�������Zk;���TzT�J}�D�F��%-�++�a��<���Zm������e�������=�]��+}6�������[:���W�b������z����[�N����|O?���E��i�9!}���E�y���>�Z�`A^�6m�<Fnn��6u��Gk��;�,:��"����F@X�\G�R�A �V���h�X'�����b;����
�_i�NH���������[���uT��S��L�'|��.���������O�4h� ��/�p�ID�C�����K�5E�Q����;��$�O��C�����J���.j����`_���t��@����_�����n���"��#F��8�?��������}��SN)vb ����O>���t
,Ff%-�����+�A�����Y�h���'�|��35j�F����(�NH��]]�8���R�\=��CE��c�4��������h����q2�E��=��-u|��^�������1��c������� |���Z���@�z���R�x$�LW����ci �����`�T�7Z��y��g�G����?/���`�s���w��J����`CI��Z�s�=W�qJZ}�Qw���o���z����[�v�����@Kx�E�f��������i����N�������GJ�tbt�Y�������E������S[.p�}���K���
P[�l��W����VZ)Xt\�r<���U�O�Z�m�K�Z���[VYe���|G����%�H��s��-������\��Q�+��=�V����n*60�������wU�~z�� �E�s���S�`v��
��GEb4�/$���O��@�P�5�����w\!�������=����t�R��P~C�-�h�������u&#�����?6R$N�[�h���:��#�sK�K)i���*�'F�i��
M�����/�����8�J��k�bS��[�
f{����JL���:��w��=��^E_���:Vd���@���z�"�����+�����7v�JM����n[��~�������7��{S�
�������BM�4�{L��x~��F���T�c�9����7]��O~��o�k��m[7�;J��U=��U�Z�m��F��
6��}oD�^&K��h��h����k���Z���k�yU:���m�u�����i����!���{�}W$�cn���v)�^
������u�����n;�7�� ������_���X�}�L��s�����w��z����b�-�}6 �M�#��)���[�����o�NV� �n�q�v����=%�o�R�l���������1��}��K��l�\Cm�C=����_�~�����?��|�I�Uq�RV������y�� ��#G�v_2��i���E�������[l�T��&���~e���&�q�T�j�������\� ������������Q��v���|P��$:7�9�����>�����S�TK�c��qSJ������Rm���{��)�~��,����������������C��������R_���~�j��}��7~�j(��z��g]tQ��z���;�����k�}���z�Xj�p�.�t���3,��CW^y�_�����Z��gu��Q~��wH���lQf� �*zFL4��FcE�2#&<K"X4;F3 ~����2a������#���������N;��3����j���������M�/i�p������g|��1���)�_��K����J��3b�"(X����M����^����En,%�)����k,������F�hJ�F)�o��Tf�hdR���
�M��G�B~'2��>M��5���k�q�t?G��{o��k)mT�`���K/��Q�������h��������������G=/������m5�+:zR�5�o��ynO����i7�+�c�F��vZ/�x�+z����Y��D�W<���kF�F2�o�E#(������1���x�u~'�?R|�1�� M��Hg=������@�8J��O�~J�VQ��~� �Z����o�Y4@U ���A���1���Z�IvF��&��iQ�f���.�����=S;\i)�ik�%����,����m[�����e=������1p�=��G,.<#Fi����e��*A[Mm���>���`Q;M��D��U�4�1��kz^Jk��\=�{5Z;��(e[�>Z4�G��E�������������i��u��^�#������Kj��o�Ei���jk~��w�����fZE_G-%�����c������g:F<��b���(k �h�:X�&����H���w�um���4[H�>��VJ}�
��y��W�>���_��hQ�����I�&��)�r�o��/^z�����Q4E�}�����g�_:7��*�'����D�3b��W:������~�����P�#z.G�O���
��L
�e�)M�1�c�4:������l�2Dg��/�b�n���E���oZi���������&z�X��D�
�����jLF�/_t z[-��\�h�-�R!HY1�RZ��h
u6�������VKI�Dt7�p��� �D'�%^PN�>�����������m�75���
�G�DE�q~l-A��D���G��T��mUs��D�5�+�����D����IG &��u�W�k�S��h.|[ b�E��J�`�~�����TR�<p�m��[:�PQ�ust�!�hnyu�*������H ���1�e~-�{O����w����T��4����eFO��R"�$zBMK"�@L��}��'�kM��]���`I���V�t�:��
����������iv���b�E5��u��������
�i@_"��i�y���_�O�&M�5��s
���Zt�Em�D�o�h����G�����������%Z[��W^��T���@����I��@��\�o����fI��
����^�x��0���?��I�o\��5�/���-����[���9�W-h��D1�&C��7}�4�~M���(�}���o�N)��N<�D7��4/����������\M��N�
�t�h*�xS�KRZ:��O?���f����o���s�gX~��o�7t�P��9Ju�i��T�|������ow�)��)���%�\bp��*N�|</���_+n�M7-���1��M��q7�x���OS���"�6 �3fc���[e�4�
Y����J-P� �����VL~�����K�U���_+�I�&���<�h�Ma�oU�����Z�I'���/�D�����.�VR�D����J��
0�o%��K�"�����'����z�-��[��A�U>�/����V�72��_����js��q~ �,��J�~S��S���H��T��n���n��V����G�m�J�`��v*��&J��h��x)�Q;s�UW�[�m��f�������~��������������^���c����[E=��s6k�,�{-K{�J��tQ��R��v�m~���N;�����O������cw�}���Q��x������7��������J����A���7���:m����=��x����Vq��LNN�_+���g����j�)]c�R���TQ�^��^�[��B}��RR���y��T�q(��*�����������^���������o[E���4�����e�}�u����HjN�����_]�k���A�S�@'��YH��6?����[�n]�{�����sQR��$jL(/j�^�NZ'C?P�� �Fv2 I�9�{��~-&z��$��%r������dN �B�y���FuL��!�W�G�^t�1����� '�`������=����n���N&��s�=����l�N��9�X(��;=z�pue
t�J��Q$����d����{��w��5������*G4�|yjd�$z�$����6m�4��8�N�w���J��+��X�)�����*��������*Y���v�K�m����+�vE��H����K�E���o����w1 �t
�k�H��L�����d��8��=���l��V�J��`��x��Y�� Ri�(i���a��VL�M_
�P��4��w�_�I�������x�����Z~+V�4�v�y��~-���&�?����j�F��Q��D��Gy���W�ga�?��_+����U�����{�j+(=i~�}���� ��Du=�'������U�yr�FbU)-`P��+�*R��� 5@Q}�d�u�]E�g
Fk�&��I$z<�nlID�9���9�������G
��@�� M���[m�U�E'���V�H�8���+��/+��*Z�N���D�RS#���x���K$:k(�b��56����H�F��4',���c���Q������OG��L��}�"#��i���k�4�3\�;J��'�E���4����m0j�`*3������
�L���;���Wv &�i���6�&:�J�m��yi�>�l����du�Q~�t���Z@���C.��\Vz��w�N�V$X#���I+ ���K����g�E#��oQ� Z�Zv�e���[�V����`�N�>��#v����kJm�'��Q.<��$���F('�_�~~�d�����dit�����h`I�N`��p��n���~�d
����M��vK� |����ZL���Q������5������&�l��J����6��A$�)���>��X?���_��;�Xl���U�t�m��O�
�|��_��4�/����_�
^Mf��$��}��o�c���j����@t0q&���fL�78�w1P��Z��
u,45��(�5�5,�N�e���F]�3xt�1|���Q�a���z2��>����H�Fz'K��x#T�'��i�E�t���tp5�FB�F�Y���1�L<���Dg�(��Y j4&�H����w�R���|��~-9:Q>�4e��G%F;'��M$���Dg�(�F�F��x�:�����QH�#���4QY�2�^y��V��v8���FG��Fz�S�)�X4�d�^u����� �8��j
�x�PJ���c�rBV36���d)0���dDG�'3�@��h!=�pP���G
�%+�G����'�d����hLFt�I2�3�q���x�P�@T�L��xm�x��g�)-�f����9aeImMsW������wCy������/��R$��>�������.:��b,,�1��2T���R��g���s�Yg����l?���;��-��k���G*�Y�{X3�/�` ����QCZ�H4rX��/��2M�������� �"���S�+������>�����6,��,��F: ��4/�9Gs�*EA��@*3�j�d�%�c@A��z��L���b.��"���(�d��R�#��b2���DGG�2�!}}��^Q�� &���=iP�4�e��2:jI���C���Yx�V��v����:���(=M����\
��?����1L9���] @�R�|��A���f�T&������Lc�) �������p*}���9����/����T�5��6Z�0�����j�d_��1������$z��-h�X�6h�E��pJX=�x5QS�sa�v�_K^x����9U�t�C��Y
�|.�}�)���?�9
�Y�3�E���1&,����4���l�p��D���
�U(�l(e������Wo�5e�Q����q/�@Ee# RA UJ_����B�j�$Z����� �+�r:g5��L��/�����h5r5ES_��R &<�4����F�~��M�nJ��.:Q�jq���a�q�*uv�;�$/��F��d2K��@y�LD��j�&:I�O�)JG}�������=�tl�y�;^�-������xR����Gx�����'�c1�Yk�����1�g�`'Z\�7����k��- @iT�K3Z��g���
���O>���N�������.��A�2�o��U
����j�)��
H�E8]k:h�f�.aUIg�F�_RmgEG{�te��Hyq�����h %U�je��h�Q�����e ��Gt�Y:1?���_���@L��V�'��Q:����d�K���������3�*!�z2��i�,���F��!$��
�(bP��E������:������b���(NV�|���1��*\���#��R�%��i���j�Y����sS��jY;���2QE���Rc1ER5���EgbU��m��7�k1:y�UI�p'H'*�D�:�������g-�bL#��z�-�� R8X���d�(�&� �������h� �����N ������?^T@Ap�hL6rY( ���~��;s�5��K/���o���'Z�:����E�u��4E���v���~��bS}��8U]Te�F�����X�t���2Z���Mt6���*�RV�i0R�����PEK��IY�+��u�.�
.����\&8p���l�P���A�+���t8��Cl���Kj4���U�FS�8� �7y���{�Ie�`)IE>�hGO'�S���No&��cA
�����3��i�?��C�}F�Y-�h0�,�D�A�I�pPD�sEw���K�X��5+Vd7�����5��<��R��uDei�����%L�L�i_4��:��Z:���b�� �x���f�j��/��l��l��L��dX&�;��������FzkG*��T�h@���o��~�-n{3�E����>�?Z�D�5eiW*#HUVT ;,����S��^����i�Y��#�E�T#2�����
�{��0=���mV��T�t��� ��v�b%�T�"���G�q4���!�d�~t���H ��Q��p�s�_t�:��6�5B�C3���*�BA#�6�h�2-�{�.w/\�]����PH*�p+�RWhVa������*�F��?_�����I)��
�I��sy�!��I�w�
��~X��g��k1J���\V_|������4�� �d��Sz�h���z~ ����.��Dg~����}����~�T�L���M��j�����E��.OX�����T�h{�UVq����7�Y����KRM�^��Y�����w�,��
ES����j/�]}��~���x P����;������#�����:��#�V��N��t��>q��]�~���@�O����:���:':a� �~|��oJ�j ��D��in�#?��s���}������
"��%�����)�He��T�P��J����o�����V|��w�_�Q��d�2:3�>���:(�F�0���R\�uh^E�0z����d<���t{�Jf�I9�
;����#�(������ �iL�{[5���+�}��
�o����BJ��}T����Tg���H�h����~��U�h��S����E�B=z��k�G�zU�5��+����*�I���:]���o��g�O��L�o�n��QTZ���B�������i����b�����h�D��n�"�{�����$R~g�bIv�����ZL��/��4�<������QJ"T�h�L��S�N��>k������:�Pa�NK�w�����Nw
�x4�5<rL��h`9��.��.��BWOJ���p�Z����TFgFSw�}�����P1FC:��� ��G]�7����s���k�eE�>��A��ZjN9��"��4Q� �) s��w��_N=���>�6fX�k����6�G}��%����k��Y�\�%��:j��F�Fg��*��K��T�H|��S���p��g���Gy��EK�:���{�K�����`�h6Lt�KI��u��
PO�0��cb�
6(����u�T����R�zTp)`�HJ������-���?���������w��k@� ��6;���Z���=����5���X�E;�%Q:T.�� S��T��+����j�3Z���
������ ��|�O h�V��Z���a�,JL+W�EuD�A��h���#�z���/�k��g%;�B����G���4�-��c
��������'���IM��t�-�~ (XE��Q����=�*(�z����b4` �������A����u�����pZP��L�M�T���F�i��i������e�Th���r�UoV��X{��������TfV)�D�F0���E��zn�����J,�f^uw��S�3�gr�y����R�����~�8
�
����A
�*�y�Z���N5��R����cIi��U#F4�8<SI�?���{�������`&6l�_�!U*� _�d��5���.������@j��
��U�+�N�F�0}���������_?�V2��Rg���F����Qk������u��FEG/VUgE4�+:{E
a�-�RQ��\�d����kw�u�y��~o�Fn]z��~+�h���R@H&x�T_��r���Nf���!u����t���;�Z,p�����0:1�N`EP*��ha�Ti�a�>��� 2[����M4�<:8��'���h���c��k%Ke0*��\q�~+F����m��W�A�
����B����QJ�dl��v~-&�o�l�;���������k��_�]��
R]y�����o�kb�J��L���d�"?��~�d�sNd����P�b�
���t�����pZ/�_~�e�{���|3�f�DQ'�I�(b�|�����:�Z�>� �x)uHM�~*h8`� ����?����*NS~u��/D�EG!i�B���a���������_+��S��h'&J#��ul.���V5���k��^{;���F�Eg�5��S�#<�#�������0u@��o?�U���_��(ur�8��"�5��2g�N������p��T��>�o����������J� �l��B�a�_�_KL',{����
�R�
e��Kx��N�~��~+>����P9��,X�f���1���Om�hj��j_E�=
b���R[::�1���t�`��l
����DY4#C�zt~&����nV��H��$:����/5;�B}��7~�d�$
\h���/����S��h P�w����C������R?2������L����n����Sm���%�n���|JU�������j��R ?:�&M���z���R�D~���A�P����_������:1���Z�U�K�Yi6��f1EG��h�>?�c����Y�=��M����� Sg�O�>~�|���v~��UG��W^q��u\)�����H���#������=/
������9*(��NE�a?�pR5�������Y3{������E�������o_��������W`C�W���Y������!}�uRI���9�/���J������uQJ���"��7����?��Z��H �M��JU�Y:��v�F��Ejh�N�i ��R��u���X]�\�����=�ejG�����\v�
7�[���h��X}�9�~���t����h �Yg��o���[�:,YJu�� �5�����j�������j;�
����0�A�������,���W�T�
>���� k���P��4J�v������W� �� ���k�9��lK��SO��)��
����{���`D�Z��QPB��������-8��s�Z��<��
L�(`u�������q/��}�� H� �~L�i]�P��`�|�I_��k:���5#�����3��<�[*�R(D��(@��r-�D�����F��������f�v�a�C��sg������EJ�p���������{���V��_��5kT�>���� :��4�*��v������L �����n��QA� ��f��c�:������o��o�������e����aCW03�_����O>���(�t�{�g:��#�YP�B����u�wK�I�
u�<�{��Py����~-F�=�M� �:W]uU��;��W�F�^48F#����o�N�t�j�]w�[�`�N4"���=Q�jP�I�(�� � -��pUo��`�p���>kj��-��L�;e�� �0e����/�V�P�RA�0�T�Xmc���VV�9^[T'��Y'�������$S=L�����Q}
>�������$�%��;
n&��[nq��0�r��N���3D_K
�:����V�4�4��#���Yg7�TG��j?��i���I���2���c[�
���������wf�E�!���7�`�(�(o*g�,� ���_~��*�4D�q�H�hm�\��~����� 6�O
)��j�Di�Htz�:��f
��(U�F���Q?��,� �F���F�%J������Q:�������R���c�����K3�4:H��Fl���:"����T�R��df�ifM4]C@�e�`u�>@��p������������D����?�r!��R�)^���H���h���['��W;,� d�8T�8�H_���o�~���
4p���(<�\��x'���o����
����O%�+*���:G��23���2�eE�5�-=�x��,�,�L�e�������
��SMJ�m��S����`zmv�q��7 Q0(�60��R����:�(W2��Qm�O���x�w�Gj���)PSY�;/�����E�I����*bP�48\�C'����+zr��]J;���m��C�� �>�@��������2������ ���z� � �9D'����W� �����?IT�!z�:�6�4��I��/�f���^p�n�~�}S�R�M>���b��$���t��m����H�u�6��������~��\�9~���F��F)���J�i��!�Fj`*����S�>bE#k�)_�f�E���r������n��RU5���}��'�#��(Iu4�H�|To)@� N4z(���F*8��Oi���QU U��f�h����9�t�����+���$���N�Fs�1�����~M���Dk�hfE�u���y�h����TiQ�&N���( ���Sm��E�o&�O�7]m�/�����������Zz�A� �&S;*��+�&\T�w>��m���w
?���=�x#z�T����F������4D��������_�[4 0��M�u*����b��K������E��D����q�����~��i������ �.���RPTmrn�����tR{P��>�j�K����R�k �^��L��D�������1��.��R��d�5W�/����:��X��QZ�i�[Q�G����
|+��f�m��gR�Pi�A
�hv��J�7�+�������:2#F�(�]=���c�&�ZY��4�2]�}��B}z����������)��(WF��T���N�*�~4�Z
����N��Dy�����i��~p��=1�F~���]=W�W?����7�A�1���������Q����:��<���4��yhVN�0���9�`����f��Dj��$����/����N2��� Z����Z�N��D��!�vj�����v<:F������V�}J6m�^_��{����������#���q���z>���R_��F����T
P��
^5*4R'j��).��n����P$3e9x���tl�wiEZuL��z�9Qc4�i,����j��-j���������Hyo�=����J�SzNjl�J�������uU����8����\�X#���
:�4�^����*}Wk�M���z�K;6���14�_�C��w�^K��az^���q�|R T�;F�u.�}C�n�g_���s����:1/B���if�R(T���e��E����S�+A�K��:}Jg�C������A��Vr4[.<2S��@�hv�N��;X�E��DS�V���T{E3`K�O���m�v�>c�\h`��5j�G�Zz����~�����0���?�}���\����l���g)�����o���~�t�x/���5(N�K�Z����8�k����F��S�S�$���c����(���U������d�t�>>���{������L����K'�^�n�i�S�Ar��������Q����z_��'��D�/���O����o�D���]z>j���w�NIiT�B�W���k����H�����-����u-zzN�����8�������K:L�<��?X���^�0}x��.5������ %
X'J��i�>��_�����o��;Z��tlk�wW��3D���^�cC:��'�c?��^�z
t��YZ��4z^����
�K�����3�`��k���\�\F������@Y�N_8]!� ��!�F�f@�sc(JD��d�w�Km��(�xP�Hru`R ���N8� @�4�"�zU�Jtr@|����A�����)�e85������&�!5�jI����R*9��I�R6��:r�m��Mu�5��"f����K�a @�m���f�j�*��y�K�Y �y��S�*������)
@�|� �!�ZR�%�b��c�J���d�z��~-&Q� ��
C��0<��C�^�F)�F&��� a�����Jo�� 1��={��2�Z�2�D��Rw�h���U�2�:��~��k���P-��J���%C��� (�p:������=l�}��k 1��Pe��I�
��������������\
��QG�� $�@�j�C�E�zjj�m��Vb.�W^y�X�tuzT�
�C�=*Xv�9��D�p�v �@�>}�ZL�~�\Q��(]l4+�{��� ���y������[fp�A RC�~ ��5�\cW^y��������x����];W�a���.��N������X��% �������w���eV]�@��-��V�x����F�-r��h}���>����u����@���K�~N���>j�w�����2e�;���M�W��K������kc��Q�@���� � ���V,Z|?}���?��uh ��f��i����[������ JF @m�A�z��[�y��G�����[ Pv�/v��&L������a��D1�&P�}���n��f�$��#���#G�Pa4Z,�& J���������=�[g�u��_$��dgg'�r�G������ ��@�jO������;��cl�u����u�]��{�q�:�~�i� *�����d4����w��5
�4=z�p��>��#���\1�
�kcT�a�]vq��G�mx�� ��~��.���E��l��w�/����Rd�2���� @F 5 ����d ��@ @�� H1 iB M� � � �4! �&b ��@ @�� H1 iB M� � � �4! �&b ��@ @�� H1 iB M� � � �4! �&b ��@ @���_�b�fw�q��u�Y~m����G��au����;��;�hM�6���o��e6l�0����,++��-*//�/^lg�}��S���s��������[NN�������zkm����_�<V�\������o_- P>jcl�
�[�������3��[�62*�/��b������������� &�~I��
�����l��J�o�7������g��5��7���_}m�F�ic��q}�UVY���b[}���� @��y��E����$�^z�
2����o�'F����W\�������>����J�����o�����)ut;w�l�=���D�����f�����egg��k��{�u��{ ��!S�u���Y��rK���/���6�`D)��I<���*����W_}��,Y���5j����w_{����A�~oq��~��g��/r�(s����}���� e
����v�av�
7� �{���p�n���i���+���������)S��Ku,z����������owSA�_���r��s�i�����n��.N`���������up����:Z����=��3�� j���?��
$Q�$0}�tw��kX�.]��m��i���G��g�}�T4�F������mk�f�(A"�7���{�a��sOw��Q�������m�o T1i��k��s�=�����j7�]�^z�%����\D�|�M{��w�z���S��Zk�e~��}��W���_[��*����.������j6b���_x�7Jm�UWu�]|��.]Y����nw�}�[�����=�^~�e�����?v�b��#�t� j��>��n��V�U2�S���u���s�����|���v�i����i ���K����_oo�����|��'��#���r�q�����?�x�f�O��������^��k ���^�� ��@ &�����0�������r+����r�����(u
D�YLi����D���:��c
F�M�<���.�]�� r3�|���2��Cq���NR�R,Z��o�f� �=���l{Qj���;����]v��Z�h�o��S'k����]��?�t�D��.���P�%He�����?���� �����C�Y�a
�h��(��?���� ��"�F
Rl��6n]������n�����~��]Fit�$z���qv�}wwO���p
��I�����o}��q��p�B� ��S�b���.����F��5#F��RM����\-!q�Q��V�Z��h��s���0��I��,�����9s��a ���4R���Gu
�O$�Z���[�������5�]w���%Gi���@Q�Q�����������I$5������[ P�)-�jEv����j��/��$�����K��o���[O�1��l�o��[���������������2�m��Q��xt]�i �= P^b*�Fl%�"�ZD����B���];W/F�M�W��w�}�_[�F���g�hDX@������������s��e�>