Marginal performance improvement: replace bms_first_member loops - Mailing list pgsql-hackers

Another thing that came out of the discussion at
http://www.postgresql.org/message-id/flat/CAOR=d=3j1U_q-zf8+jUx1hkx8ps+N8pm=EUTqyFdJ5ov=+fawg@mail.gmail.com
was that there was a significant amount of palloc/pfree traffic blamable
on the bms_first_member() loop in plpgsql's setup_param_list().  I've
been experimenting with a variant of bms_first_member() called
bms_next_member(), which doesn't modify the input bitmapset and therefore
removes the need to make a working copy when iterating over the members
of a set.

In isolation, bms_next_member() is fractionally slower than
bms_first_member() because it has to do a bit more shifting-and-masking,
but of course we more than win that back from eliminating a palloc/pfree
cycle.  It's also worth noting that in principle, a bms_first_member()
loop is O(N^2) for large sets because it scans from the start of the
set each time; but I doubt this is much of an issue in practice, because
the bitmapsets we work with just aren't very large.  (I did some
microbenchmarking and found that if one ignores the palloc overhead
question, a bms_next_member loop is a tad slower up to about four words
in the bitmapset, and faster beyond that because the rescans start to
make a difference.  But four words would be 128 bits and very very few
bitmapsets in PG would have more members than that.)

The attached proposed patch adds bms_next_member() and replaces
bms_first_member() calls where it seemed to make sense.  I've had a
hard time measuring much speed difference for this patch in isolation,
but in principle it should be less code and less cycles.  It also seems
safer and more natural to not use destructive looping techniques.

            regards, tom lane

diff --git a/contrib/postgres_fdw/postgres_fdw.c b/contrib/postgres_fdw/postgres_fdw.c
index 76bda73..7dcedd1 100644
*** a/contrib/postgres_fdw/postgres_fdw.c
--- b/contrib/postgres_fdw/postgres_fdw.c
*************** postgresPlanForeignModify(PlannerInfo *r
*** 1198,1212 ****
      }
      else if (operation == CMD_UPDATE)
      {
-         Bitmapset  *tmpset = bms_copy(rte->modifiedCols);
          AttrNumber    col;

!         while ((col = bms_first_member(tmpset)) >= 0)
          {
              col += FirstLowInvalidHeapAttributeNumber;
              if (col <= InvalidAttrNumber)        /* shouldn't happen */
                  elog(ERROR, "system-column update is not supported");
              targetAttrs = lappend_int(targetAttrs, col);
          }
      }

--- 1198,1213 ----
      }
      else if (operation == CMD_UPDATE)
      {
          AttrNumber    col;

!         col = -1;
!         while ((col = bms_next_member(rte->modifiedCols, col)) >= 0)
          {
              col += FirstLowInvalidHeapAttributeNumber;
              if (col <= InvalidAttrNumber)        /* shouldn't happen */
                  elog(ERROR, "system-column update is not supported");
              targetAttrs = lappend_int(targetAttrs, col);
+             col -= FirstLowInvalidHeapAttributeNumber;
          }
      }

diff --git a/contrib/sepgsql/dml.c b/contrib/sepgsql/dml.c
index bb82c0d..44c067d 100644
*** a/contrib/sepgsql/dml.c
--- b/contrib/sepgsql/dml.c
*************** static Bitmapset *
*** 94,100 ****
  fixup_inherited_columns(Oid parentId, Oid childId, Bitmapset *columns)
  {
      AttrNumber    attno;
-     Bitmapset  *tmpset;
      Bitmapset  *result = NULL;
      char       *attname;
      int            index;
--- 94,99 ----
*************** fixup_inherited_columns(Oid parentId, Oi
*** 105,112 ****
      if (parentId == childId)
          return columns;

!     tmpset = bms_copy(columns);
!     while ((index = bms_first_member(tmpset)) > 0)
      {
          attno = index + FirstLowInvalidHeapAttributeNumber;

--- 104,111 ----
      if (parentId == childId)
          return columns;

!     index = -1;
!     while ((index = bms_next_member(columns, index)) > 0)
      {
          attno = index + FirstLowInvalidHeapAttributeNumber;

*************** fixup_inherited_columns(Oid parentId, Oi
*** 128,139 ****
              elog(ERROR, "cache lookup failed for attribute %s of relation %u",
                   attname, childId);

!         index = attno - FirstLowInvalidHeapAttributeNumber;
!         result = bms_add_member(result, index);

          pfree(attname);
      }
-     bms_free(tmpset);

      return result;
  }
--- 127,137 ----
              elog(ERROR, "cache lookup failed for attribute %s of relation %u",
                   attname, childId);

!         result = bms_add_member(result,
!                                 attno - FirstLowInvalidHeapAttributeNumber);

          pfree(attname);
      }

      return result;
  }
diff --git a/src/backend/executor/execMain.c b/src/backend/executor/execMain.c
index c499486..436b0fa 100644
*** a/src/backend/executor/execMain.c
--- b/src/backend/executor/execMain.c
*************** ExecCheckRTEPerms(RangeTblEntry *rte)
*** 547,553 ****
      AclMode        remainingPerms;
      Oid            relOid;
      Oid            userid;
-     Bitmapset  *tmpset;
      int            col;

      /*
--- 547,552 ----
*************** ExecCheckRTEPerms(RangeTblEntry *rte)
*** 614,621 ****
                      return false;
              }

!             tmpset = bms_copy(rte->selectedCols);
!             while ((col = bms_first_member(tmpset)) >= 0)
              {
                  /* remove the column number offset */
                  col += FirstLowInvalidHeapAttributeNumber;
--- 613,620 ----
                      return false;
              }

!             col = -1;
!             while ((col = bms_next_member(rte->selectedCols, col)) >= 0)
              {
                  /* remove the column number offset */
                  col += FirstLowInvalidHeapAttributeNumber;
*************** ExecCheckRTEPerms(RangeTblEntry *rte)
*** 632,639 ****
                                                ACL_SELECT) != ACLCHECK_OK)
                          return false;
                  }
              }
-             bms_free(tmpset);
          }

          /*
--- 631,638 ----
                                                ACL_SELECT) != ACLCHECK_OK)
                          return false;
                  }
+                 col -= FirstLowInvalidHeapAttributeNumber;
              }
          }

          /*
*************** ExecCheckRTEPerms(RangeTblEntry *rte)
*** 656,663 ****
                      return false;
              }

!             tmpset = bms_copy(rte->modifiedCols);
!             while ((col = bms_first_member(tmpset)) >= 0)
              {
                  /* remove the column number offset */
                  col += FirstLowInvalidHeapAttributeNumber;
--- 655,662 ----
                      return false;
              }

!             col = -1;
!             while ((col = bms_next_member(rte->modifiedCols, col)) >= 0)
              {
                  /* remove the column number offset */
                  col += FirstLowInvalidHeapAttributeNumber;
*************** ExecCheckRTEPerms(RangeTblEntry *rte)
*** 672,679 ****
                                                remainingPerms) != ACLCHECK_OK)
                          return false;
                  }
              }
-             bms_free(tmpset);
          }
      }
      return true;
--- 671,678 ----
                                                remainingPerms) != ACLCHECK_OK)
                          return false;
                  }
+                 col -= FirstLowInvalidHeapAttributeNumber;
              }
          }
      }
      return true;
diff --git a/src/backend/nodes/bitmapset.c b/src/backend/nodes/bitmapset.c
index c927b78..23eb1eb 100644
*** a/src/backend/nodes/bitmapset.c
--- b/src/backend/nodes/bitmapset.c
*************** bms_join(Bitmapset *a, Bitmapset *b)
*** 793,799 ****
      return result;
  }

! /*----------
   * bms_first_member - find and remove first member of a set
   *
   * Returns -1 if set is empty.  NB: set is destructively modified!
--- 793,799 ----
      return result;
  }

! /*
   * bms_first_member - find and remove first member of a set
   *
   * Returns -1 if set is empty.  NB: set is destructively modified!
*************** bms_join(Bitmapset *a, Bitmapset *b)
*** 801,811 ****
   * This is intended as support for iterating through the members of a set.
   * The typical pattern is
   *
!  *            tmpset = bms_copy(inputset);
!  *            while ((x = bms_first_member(tmpset)) >= 0)
   *                process member x;
!  *            bms_free(tmpset);
!  *----------
   */
  int
  bms_first_member(Bitmapset *a)
--- 801,811 ----
   * 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)
*************** bms_first_member(Bitmapset *a)
*** 841,846 ****
--- 841,899 ----
  }

  /*
+  * bms_next_member - find next member of a set
+  *
+  * Returns smallest member greater than "prevbit", or -1 if there is none.
+  *
+  * This is intended as support for iterating through the members of a set.
+  * The typical pattern is
+  *
+  *            x = -1;
+  *            while ((x = bms_next_member(inputset, x)) >= 0)
+  *                process member x;
+  */
+ int
+ bms_next_member(const Bitmapset *a, int prevbit)
+ {
+     int            nwords;
+     int            wordnum;
+     bitmapword    mask;
+
+     if (a == NULL)
+         return -1;
+     nwords = a->nwords;
+     prevbit++;
+     mask = (~(bitmapword) 0) << BITNUM(prevbit);
+     for (wordnum = WORDNUM(prevbit); wordnum < nwords; wordnum++)
+     {
+         bitmapword    w = a->words[wordnum];
+
+         /* ignore bits before prevbit */
+         w &= mask;
+
+         if (w != 0)
+         {
+             int            result;
+
+             w = RIGHTMOST_ONE(w);
+
+             result = wordnum * BITS_PER_BITMAPWORD;
+             while ((w & 255) == 0)
+             {
+                 w >>= 8;
+                 result += 8;
+             }
+             result += rightmost_one_pos[w & 255];
+             return result;
+         }
+
+         /* in subsequent words, consider all bits */
+         mask = (~(bitmapword) 0);
+     }
+     return -1;
+ }
+
+ /*
   * bms_hash_value - compute a hash key for a Bitmapset
   *
   * Note: we must ensure that any two bitmapsets that are bms_equal() will
diff --git a/src/backend/nodes/outfuncs.c b/src/backend/nodes/outfuncs.c
index ca9bd4f..edbd09f 100644
*** a/src/backend/nodes/outfuncs.c
--- b/src/backend/nodes/outfuncs.c
*************** _outList(StringInfo str, const List *nod
*** 184,198 ****
  static void
  _outBitmapset(StringInfo str, const Bitmapset *bms)
  {
-     Bitmapset  *tmpset;
      int            x;

      appendStringInfoChar(str, '(');
      appendStringInfoChar(str, 'b');
!     tmpset = bms_copy(bms);
!     while ((x = bms_first_member(tmpset)) >= 0)
          appendStringInfo(str, " %d", x);
-     bms_free(tmpset);
      appendStringInfoChar(str, ')');
  }

--- 184,196 ----
  static void
  _outBitmapset(StringInfo str, const Bitmapset *bms)
  {
      int            x;

      appendStringInfoChar(str, '(');
      appendStringInfoChar(str, 'b');
!     x = -1;
!     while ((x = bms_next_member(bms, x)) >= 0)
          appendStringInfo(str, " %d", x);
      appendStringInfoChar(str, ')');
  }

diff --git a/src/backend/optimizer/path/allpaths.c b/src/backend/optimizer/path/allpaths.c
index 25f3067..449fdc3 100644
*** a/src/backend/optimizer/path/allpaths.c
--- b/src/backend/optimizer/path/allpaths.c
*************** remove_unused_subquery_outputs(Query *su
*** 2272,2290 ****
  static void
  print_relids(Relids relids)
  {
-     Relids        tmprelids;
      int            x;
      bool        first = true;

!     tmprelids = bms_copy(relids);
!     while ((x = bms_first_member(tmprelids)) >= 0)
      {
          if (!first)
              printf(" ");
          printf("%d", x);
          first = false;
      }
-     bms_free(tmprelids);
  }

  static void
--- 2272,2288 ----
  static void
  print_relids(Relids relids)
  {
      int            x;
      bool        first = true;

!     x = -1;
!     while ((x = bms_next_member(relids, x)) >= 0)
      {
          if (!first)
              printf(" ");
          printf("%d", x);
          first = false;
      }
  }

  static void
diff --git a/src/backend/optimizer/path/indxpath.c b/src/backend/optimizer/path/indxpath.c
index 1ee3b93..7aab644 100644
*** a/src/backend/optimizer/path/indxpath.c
--- b/src/backend/optimizer/path/indxpath.c
*************** get_loop_count(PlannerInfo *root, Relids
*** 1875,1883 ****
      {
          int            relid;

!         /* Need a working copy since bms_first_member is destructive */
!         outer_relids = bms_copy(outer_relids);
!         while ((relid = bms_first_member(outer_relids)) >= 0)
          {
              RelOptInfo *outer_rel;

--- 1875,1882 ----
      {
          int            relid;

!         relid = -1;
!         while ((relid = bms_next_member(outer_relids, relid)) >= 0)
          {
              RelOptInfo *outer_rel;

*************** get_loop_count(PlannerInfo *root, Relids
*** 1900,1906 ****
              if (result == 1.0 || result > outer_rel->rows)
                  result = outer_rel->rows;
          }
-         bms_free(outer_relids);
      }
      return result;
  }
--- 1899,1904 ----
diff --git a/src/backend/optimizer/util/joininfo.c b/src/backend/optimizer/util/joininfo.c
index 0418946..40af38d 100644
*** a/src/backend/optimizer/util/joininfo.c
--- b/src/backend/optimizer/util/joininfo.c
*************** add_join_clause_to_rels(PlannerInfo *roo
*** 96,112 ****
                          RestrictInfo *restrictinfo,
                          Relids join_relids)
  {
-     Relids        tmprelids;
      int            cur_relid;

!     tmprelids = bms_copy(join_relids);
!     while ((cur_relid = bms_first_member(tmprelids)) >= 0)
      {
          RelOptInfo *rel = find_base_rel(root, cur_relid);

          rel->joininfo = lappend(rel->joininfo, restrictinfo);
      }
-     bms_free(tmprelids);
  }

  /*
--- 96,110 ----
                          RestrictInfo *restrictinfo,
                          Relids join_relids)
  {
      int            cur_relid;

!     cur_relid = -1;
!     while ((cur_relid = bms_next_member(join_relids, cur_relid)) >= 0)
      {
          RelOptInfo *rel = find_base_rel(root, cur_relid);

          rel->joininfo = lappend(rel->joininfo, restrictinfo);
      }
  }

  /*
*************** remove_join_clause_from_rels(PlannerInfo
*** 125,135 ****
                               RestrictInfo *restrictinfo,
                               Relids join_relids)
  {
-     Relids        tmprelids;
      int            cur_relid;

!     tmprelids = bms_copy(join_relids);
!     while ((cur_relid = bms_first_member(tmprelids)) >= 0)
      {
          RelOptInfo *rel = find_base_rel(root, cur_relid);

--- 123,132 ----
                               RestrictInfo *restrictinfo,
                               Relids join_relids)
  {
      int            cur_relid;

!     cur_relid = -1;
!     while ((cur_relid = bms_next_member(join_relids, cur_relid)) >= 0)
      {
          RelOptInfo *rel = find_base_rel(root, cur_relid);

*************** remove_join_clause_from_rels(PlannerInfo
*** 140,144 ****
          Assert(list_member_ptr(rel->joininfo, restrictinfo));
          rel->joininfo = list_delete_ptr(rel->joininfo, restrictinfo);
      }
-     bms_free(tmprelids);
  }
--- 137,140 ----
diff --git a/src/backend/optimizer/util/var.c b/src/backend/optimizer/util/var.c
index d4f46b8..a64a8d7 100644
*** a/src/backend/optimizer/util/var.c
--- b/src/backend/optimizer/util/var.c
*************** static Relids
*** 773,783 ****
  alias_relid_set(PlannerInfo *root, Relids relids)
  {
      Relids        result = NULL;
-     Relids        tmprelids;
      int            rtindex;

!     tmprelids = bms_copy(relids);
!     while ((rtindex = bms_first_member(tmprelids)) >= 0)
      {
          RangeTblEntry *rte = rt_fetch(rtindex, root->parse->rtable);

--- 773,782 ----
  alias_relid_set(PlannerInfo *root, Relids relids)
  {
      Relids        result = NULL;
      int            rtindex;

!     rtindex = -1;
!     while ((rtindex = bms_next_member(relids, rtindex)) >= 0)
      {
          RangeTblEntry *rte = rt_fetch(rtindex, root->parse->rtable);

*************** alias_relid_set(PlannerInfo *root, Relid
*** 786,791 ****
          else
              result = bms_add_member(result, rtindex);
      }
-     bms_free(tmprelids);
      return result;
  }
--- 785,789 ----
diff --git a/src/backend/rewrite/rewriteHandler.c b/src/backend/rewrite/rewriteHandler.c
index ad983c7..c7afea1 100644
*** a/src/backend/rewrite/rewriteHandler.c
--- b/src/backend/rewrite/rewriteHandler.c
*************** static Bitmapset *
*** 2456,2466 ****
  adjust_view_column_set(Bitmapset *cols, List *targetlist)
  {
      Bitmapset  *result = NULL;
-     Bitmapset  *tmpcols;
      AttrNumber    col;

!     tmpcols = bms_copy(cols);
!     while ((col = bms_first_member(tmpcols)) >= 0)
      {
          /* bit numbers are offset by FirstLowInvalidHeapAttributeNumber */
          AttrNumber    attno = col + FirstLowInvalidHeapAttributeNumber;
--- 2456,2465 ----
  adjust_view_column_set(Bitmapset *cols, List *targetlist)
  {
      Bitmapset  *result = NULL;
      AttrNumber    col;

!     col = -1;
!     while ((col = bms_next_member(cols, col)) >= 0)
      {
          /* bit numbers are offset by FirstLowInvalidHeapAttributeNumber */
          AttrNumber    attno = col + FirstLowInvalidHeapAttributeNumber;
*************** adjust_view_column_set(Bitmapset *cols,
*** 2510,2516 ****
                       attno);
          }
      }
-     bms_free(tmpcols);

      return result;
  }
--- 2509,2514 ----
diff --git a/src/backend/rewrite/rewriteManip.c b/src/backend/rewrite/rewriteManip.c
index fb20314..c9e4b68 100644
*** a/src/backend/rewrite/rewriteManip.c
--- b/src/backend/rewrite/rewriteManip.c
*************** static Relids
*** 454,466 ****
  offset_relid_set(Relids relids, int offset)
  {
      Relids        result = NULL;
-     Relids        tmprelids;
      int            rtindex;

!     tmprelids = bms_copy(relids);
!     while ((rtindex = bms_first_member(tmprelids)) >= 0)
          result = bms_add_member(result, rtindex + offset);
-     bms_free(tmprelids);
      return result;
  }

--- 454,464 ----
  offset_relid_set(Relids relids, int offset)
  {
      Relids        result = NULL;
      int            rtindex;

!     rtindex = -1;
!     while ((rtindex = bms_next_member(relids, rtindex)) >= 0)
          result = bms_add_member(result, rtindex + offset);
      return result;
  }

diff --git a/src/include/nodes/bitmapset.h b/src/include/nodes/bitmapset.h
index f770608..a78ff48 100644
*** a/src/include/nodes/bitmapset.h
--- b/src/include/nodes/bitmapset.h
*************** extern Bitmapset *bms_join(Bitmapset *a,
*** 89,94 ****
--- 89,95 ----

  /* 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);

  /* support for hashtables using Bitmapsets as keys: */
  extern uint32 bms_hash_value(const Bitmapset *a);
diff --git a/src/pl/plpgsql/src/pl_exec.c b/src/pl/plpgsql/src/pl_exec.c
index 11cb47b..d1feef7 100644
*** a/src/pl/plpgsql/src/pl_exec.c
--- b/src/pl/plpgsql/src/pl_exec.c
*************** setup_param_list(PLpgSQL_execstate *esta
*** 5263,5269 ****
       */
      if (!bms_is_empty(expr->paramnos))
      {
-         Bitmapset  *tmpset;
          int            dno;

          paramLI = (ParamListInfo)
--- 5263,5268 ----
*************** setup_param_list(PLpgSQL_execstate *esta
*** 5276,5283 ****
          paramLI->numParams = estate->ndatums;

          /* Instantiate values for "safe" parameters of the expression */
!         tmpset = bms_copy(expr->paramnos);
!         while ((dno = bms_first_member(tmpset)) >= 0)
          {
              PLpgSQL_datum *datum = estate->datums[dno];

--- 5275,5282 ----
          paramLI->numParams = estate->ndatums;

          /* Instantiate values for "safe" parameters of the expression */
!         dno = -1;
!         while ((dno = bms_next_member(expr->paramnos, dno)) >= 0)
          {
              PLpgSQL_datum *datum = estate->datums[dno];

*************** setup_param_list(PLpgSQL_execstate *esta
*** 5292,5298 ****
                  prm->ptype = var->datatype->typoid;
              }
          }
-         bms_free(tmpset);

          /*
           * Set up link to active expr where the hook functions can find it.
--- 5291,5296 ----
*************** format_expr_params(PLpgSQL_execstate *es
*** 6528,6542 ****
      int            paramno;
      int            dno;
      StringInfoData paramstr;
-     Bitmapset  *tmpset;

      if (!expr->paramnos)
          return NULL;

      initStringInfo(¶mstr);
-     tmpset = bms_copy(expr->paramnos);
      paramno = 0;
!     while ((dno = bms_first_member(tmpset)) >= 0)
      {
          Datum        paramdatum;
          Oid            paramtypeid;
--- 6526,6539 ----
      int            paramno;
      int            dno;
      StringInfoData paramstr;

      if (!expr->paramnos)
          return NULL;

      initStringInfo(¶mstr);
      paramno = 0;
!     dno = -1;
!     while ((dno = bms_next_member(expr->paramnos, dno)) >= 0)
      {
          Datum        paramdatum;
          Oid            paramtypeid;
*************** format_expr_params(PLpgSQL_execstate *es
*** 6572,6578 ****

          paramno++;
      }
-     bms_free(tmpset);

      return paramstr.data;
  }
--- 6569,6574 ----