agora inbox for pgsql-hackers@postgresql.org  

help / color / mirror / Atom feed

[PATCH v2 4/7] Row pattern recognition patch (executor).
9+ messages / 2 participants
[nested] [flat]

* [PATCH v2 4/7] Row pattern recognition patch (executor).
@ 2023-06-26 08:05  Tatsuo Ishii <ishii@postgresql.org>
  0 siblings, 0 replies; 9+ messages in thread

From: Tatsuo Ishii @ 2023-06-26 08:05 UTC (permalink / raw)

---
 src/backend/executor/nodeWindowAgg.c | 225 +++++++++++++++++++-
 src/backend/utils/adt/windowfuncs.c  | 302 ++++++++++++++++++++++++++-
 src/include/catalog/pg_proc.dat      |   9 +
 src/include/nodes/execnodes.h        |  13 ++
 src/include/windowapi.h              |   9 +
 5 files changed, 548 insertions(+), 10 deletions(-)

diff --git a/src/backend/executor/nodeWindowAgg.c b/src/backend/executor/nodeWindowAgg.c
index 310ac23e3a..bef2bc62b2 100644
--- a/src/backend/executor/nodeWindowAgg.c
+++ b/src/backend/executor/nodeWindowAgg.c
@@ -48,6 +48,7 @@
 #include "utils/acl.h"
 #include "utils/builtins.h"
 #include "utils/datum.h"
+#include "utils/fmgroids.h"
 #include "utils/expandeddatum.h"
 #include "utils/lsyscache.h"
 #include "utils/memutils.h"
@@ -159,6 +160,14 @@ typedef struct WindowStatePerAggData
 	bool		restart;		/* need to restart this agg in this cycle? */
 } WindowStatePerAggData;
 
+/*
+ * Map between Var attno in a target list and the parsed attno.
+ */
+typedef struct AttnoMap {
+	List		*attno;			/* att number in target list (list of AttNumber) */
+	List		*attnosyn;		/* parsed att number (list of AttNumber) */
+} AttnoMap;
+
 static void initialize_windowaggregate(WindowAggState *winstate,
 									   WindowStatePerFunc perfuncstate,
 									   WindowStatePerAgg peraggstate);
@@ -195,9 +204,9 @@ static Datum GetAggInitVal(Datum textInitVal, Oid transtype);
 
 static bool are_peers(WindowAggState *winstate, TupleTableSlot *slot1,
 					  TupleTableSlot *slot2);
-static bool window_gettupleslot(WindowObject winobj, int64 pos,
-								TupleTableSlot *slot);
 
+static void attno_map(Node *node, AttnoMap *map);
+static bool attno_map_walker(Node *node, void *context);
 
 /*
  * initialize_windowaggregate
@@ -2388,6 +2397,12 @@ ExecInitWindowAgg(WindowAgg *node, EState *estate, int eflags)
 	TupleDesc	scanDesc;
 	ListCell   *l;
 
+	TargetEntry	*te;
+	Expr		*expr;
+	Var			*var;
+	int			nargs;
+	AttnoMap	attnomap;
+
 	/* check for unsupported flags */
 	Assert(!(eflags & (EXEC_FLAG_BACKWARD | EXEC_FLAG_MARK)));
 
@@ -2483,6 +2498,16 @@ ExecInitWindowAgg(WindowAgg *node, EState *estate, int eflags)
 	winstate->temp_slot_2 = ExecInitExtraTupleSlot(estate, scanDesc,
 												   &TTSOpsMinimalTuple);
 
+	winstate->prev_slot = ExecInitExtraTupleSlot(estate, scanDesc,
+												 &TTSOpsMinimalTuple);
+
+	winstate->next_slot = ExecInitExtraTupleSlot(estate, scanDesc,
+												 &TTSOpsMinimalTuple);
+
+	winstate->null_slot = ExecInitExtraTupleSlot(estate, scanDesc,
+												 &TTSOpsMinimalTuple);
+	winstate->null_slot = ExecStoreAllNullTuple(winstate->null_slot);
+
 	/*
 	 * create frame head and tail slots only if needed (must create slots in
 	 * exactly the same cases that update_frameheadpos and update_frametailpos
@@ -2667,6 +2692,71 @@ ExecInitWindowAgg(WindowAgg *node, EState *estate, int eflags)
 	winstate->inRangeAsc = node->inRangeAsc;
 	winstate->inRangeNullsFirst = node->inRangeNullsFirst;
 
+	/* Set up SKIP TO type */
+	winstate->rpSkipTo = node->rpSkipTo;
+	/* Set up row pattern recognition PATTERN clause */
+	winstate->patternVariableList = node->patternVariable;
+	winstate->patternRegexpList = node->patternRegexp;
+
+	/* Set up row pattern recognition DEFINE clause */
+
+	/*
+	 * Collect mapping between varattno and varattnosyn in the targetlist.
+	 * XXX: For now we only check RPR's argument. Eventually we have to
+	 * recurse the targetlist to find out all mappings in Var nodes.
+	 */
+	attnomap.attno = NIL;
+	attnomap.attnosyn = NIL;
+
+	foreach (l, node->plan.targetlist)
+	{
+		te = lfirst(l);
+		if (IsA(te->expr, WindowFunc))
+		{
+			WindowFunc	*func = (WindowFunc *)te->expr;
+			if (func->winfnoid != F_RPR)
+				continue;
+
+			/* sanity check */
+			nargs = list_length(func->args);
+			if (list_length(func->args) != 1)
+				elog(ERROR, "RPR must have 1 argument but function %d has %d args", func->winfnoid, nargs);
+
+			expr = (Expr *) lfirst(list_head(func->args));
+			if (!IsA(expr, Var))
+				elog(ERROR, "RPR's arg is not Var");
+
+			var = (Var *)expr;
+			elog(DEBUG1, "resname: %s varattno: %d varattnosyn: %d",
+				 te->resname, var->varattno, var->varattnosyn);
+			attnomap.attno = lappend_int(attnomap.attno, var->varattno);
+			attnomap.attnosyn = lappend_int(attnomap.attnosyn, var->varattnosyn);
+		}
+	}
+
+	winstate->defineVariableList = NIL;
+	winstate->defineClauseList = NIL;
+	if (node->defineClause != NIL)
+	{
+		foreach(l, node->defineClause)
+		{
+			char		*name;
+			ExprState	*exps;
+
+			te = lfirst(l);
+			name = te->resname;
+			expr = te->expr;
+
+			elog(DEBUG1, "defineVariable name: %s", name);
+			winstate->defineVariableList = lappend(winstate->defineVariableList,
+												   makeString(pstrdup(name)));
+			/* tweak expr so that it referes to outer slot */
+			attno_map((Node *)expr, &attnomap);
+			exps = ExecInitExpr(expr, (PlanState *) winstate);
+			winstate->defineClauseList = lappend(winstate->defineClauseList, exps);
+		}
+	}
+
 	winstate->all_first = true;
 	winstate->partition_spooled = false;
 	winstate->more_partitions = false;
@@ -2674,6 +2764,76 @@ ExecInitWindowAgg(WindowAgg *node, EState *estate, int eflags)
 	return winstate;
 }
 
+/*
+ * Rewrite Var node's varattno to the varattno which is used in the target
+ * list using AttnoMap.  We also rewrite varno so that it sees outer tuple
+ * (PREV) or inner tuple (NEXT).
+ */
+static void
+attno_map(Node *node, AttnoMap *map)
+{
+	(void) expression_tree_walker(node, attno_map_walker, (void *) map);
+}
+
+static bool
+attno_map_walker(Node *node, void *context)
+{
+	FuncExpr	*func;
+	int			nargs;
+	Expr		*expr;
+	Var			*var;
+	AttnoMap	*attnomap;
+	ListCell	*lc1, *lc2;
+	
+	if (node == NULL)
+		return false;
+
+	attnomap = (AttnoMap *) context;
+
+	if (IsA(node, FuncExpr))
+	{
+		func = (FuncExpr *)node;
+
+		if (func->funcid == F_PREV || func->funcid == F_NEXT)
+		{
+			/* sanity check */
+			nargs = list_length(func->args);
+			if (list_length(func->args) != 1)
+				elog(ERROR, "PREV/NEXT must have 1 argument but function %d has %d args", func->funcid, nargs);
+
+			expr = (Expr *) lfirst(list_head(func->args));
+			if (!IsA(expr, Var))
+				elog(ERROR, "PREV/NEXT's arg is not Var");	/* XXX: is it possible that arg type is Const? */
+			var = (Var *)expr;
+
+			if (func->funcid == F_PREV)
+				var->varno = OUTER_VAR;
+			else
+				var->varno = INNER_VAR;
+		}
+		return expression_tree_walker(node, attno_map_walker, (void *) context);
+	}
+	else if (IsA(node, Var))
+	{
+		var = (Var *)node;	 
+
+		elog(DEBUG1, "original varno: %d varattno: %d", var->varno, var->varattno);
+
+		forboth(lc1, attnomap->attno, lc2, attnomap->attnosyn)
+		{
+			int	attno = lfirst_int(lc1);
+			int	attnosyn = lfirst_int(lc2);
+
+			if (var->varattno == attnosyn)
+			{
+				elog(DEBUG1, "loc: %d rewrite varattno from: %d to %d", var->location, attnosyn, attno);
+				var->varattno = attno;
+			}
+		}
+	}
+	return expression_tree_walker(node, attno_map_walker, (void *) context);
+}
+
 /* -----------------
  * ExecEndWindowAgg
  * -----------------
@@ -2691,6 +2851,8 @@ ExecEndWindowAgg(WindowAggState *node)
 	ExecClearTuple(node->agg_row_slot);
 	ExecClearTuple(node->temp_slot_1);
 	ExecClearTuple(node->temp_slot_2);
+	ExecClearTuple(node->prev_slot);
+	ExecClearTuple(node->next_slot);
 	if (node->framehead_slot)
 		ExecClearTuple(node->framehead_slot);
 	if (node->frametail_slot)
@@ -2740,6 +2902,8 @@ ExecReScanWindowAgg(WindowAggState *node)
 	ExecClearTuple(node->agg_row_slot);
 	ExecClearTuple(node->temp_slot_1);
 	ExecClearTuple(node->temp_slot_2);
+	ExecClearTuple(node->prev_slot);
+	ExecClearTuple(node->next_slot);
 	if (node->framehead_slot)
 		ExecClearTuple(node->framehead_slot);
 	if (node->frametail_slot)
@@ -3080,7 +3244,7 @@ are_peers(WindowAggState *winstate, TupleTableSlot *slot1,
  *
  * Returns true if successful, false if no such row
  */
-static bool
+bool
 window_gettupleslot(WindowObject winobj, int64 pos, TupleTableSlot *slot)
 {
 	WindowAggState *winstate = winobj->winstate;
@@ -3420,14 +3584,53 @@ WinGetFuncArgInFrame(WindowObject winobj, int argno,
 	WindowAggState *winstate;
 	ExprContext *econtext;
 	TupleTableSlot *slot;
-	int64		abs_pos;
-	int64		mark_pos;
 
 	Assert(WindowObjectIsValid(winobj));
 	winstate = winobj->winstate;
 	econtext = winstate->ss.ps.ps_ExprContext;
 	slot = winstate->temp_slot_1;
 
+	if (WinGetSlotInFrame(winobj, slot,
+						  relpos, seektype, set_mark,
+						  isnull, isout) == 0)
+	{
+		econtext->ecxt_outertuple = slot;
+		return ExecEvalExpr((ExprState *) list_nth(winobj->argstates, argno),
+							econtext, isnull);
+	}
+
+	if (isout)
+		*isout = true;
+	*isnull = true;
+	return (Datum) 0;
+}
+
+/*
+ * WinGetSlotInFrame
+ * slot: TupleTableSlot to store the result
+ * relpos: signed rowcount offset from the seek position
+ * seektype: WINDOW_SEEK_HEAD or WINDOW_SEEK_TAIL
+ * set_mark: If the row is found/in frame and set_mark is true, the mark is
+ *		moved to the row as a side-effect.
+ * isnull: output argument, receives isnull status of result
+ * isout: output argument, set to indicate whether target row position
+ *		is out of frame (can pass NULL if caller doesn't care about this)
+ *
+ * Returns 0 if we successfullt got the slot. false if out of frame.
+ * (also isout is set)
+ */
+int
+WinGetSlotInFrame(WindowObject winobj, TupleTableSlot *slot,
+					 int relpos, int seektype, bool set_mark,
+					 bool *isnull, bool *isout)
+{
+	WindowAggState *winstate;
+	int64		abs_pos;
+	int64		mark_pos;
+
+	Assert(WindowObjectIsValid(winobj));
+	winstate = winobj->winstate;
+
 	switch (seektype)
 	{
 		case WINDOW_SEEK_CURRENT:
@@ -3583,15 +3786,13 @@ WinGetFuncArgInFrame(WindowObject winobj, int argno,
 		*isout = false;
 	if (set_mark)
 		WinSetMarkPosition(winobj, mark_pos);
-	econtext->ecxt_outertuple = slot;
-	return ExecEvalExpr((ExprState *) list_nth(winobj->argstates, argno),
-						econtext, isnull);
+	return 0;
 
 out_of_frame:
 	if (isout)
 		*isout = true;
 	*isnull = true;
-	return (Datum) 0;
+	return -1;
 }
 
 /*
@@ -3622,3 +3823,9 @@ WinGetFuncArgCurrent(WindowObject winobj, int argno, bool *isnull)
 	return ExecEvalExpr((ExprState *) list_nth(winobj->argstates, argno),
 						econtext, isnull);
 }
+
+WindowAggState *
+WinGetAggState(WindowObject winobj)
+{
+	return winobj->winstate;
+}
diff --git a/src/backend/utils/adt/windowfuncs.c b/src/backend/utils/adt/windowfuncs.c
index b87a624fb2..74ef11ce55 100644
--- a/src/backend/utils/adt/windowfuncs.c
+++ b/src/backend/utils/adt/windowfuncs.c
@@ -13,6 +13,9 @@
  */
 #include "postgres.h"
 
+#include "catalog/pg_collation_d.h"
+#include "executor/executor.h"
+#include "nodes/execnodes.h"
 #include "nodes/supportnodes.h"
 #include "utils/builtins.h"
 #include "windowapi.h"
@@ -36,10 +39,21 @@ typedef struct
 	int64		remainder;		/* (total rows) % (bucket num) */
 } ntile_context;
 
+/*
+ * rpr process information.
+ * Used for AFTER MATCH SKIP PAST LAST ROW
+ */
+typedef struct SkipContext
+{
+	int64		pos;	/* last row absolute position */
+} SkipContext;
+
 static bool rank_up(WindowObject winobj);
 static Datum leadlag_common(FunctionCallInfo fcinfo,
 							bool forward, bool withoffset, bool withdefault);
-
+static bool get_slots(WindowObject winobj, WindowAggState *winstate, int current_pos);
+static int evaluate_pattern(WindowObject winobj, WindowAggState *winstate,
+							int relpos, char *vname, char *quantifier, bool *result);
 
 /*
  * utility routine for *_rank functions.
@@ -713,3 +727,289 @@ window_nth_value(PG_FUNCTION_ARGS)
 
 	PG_RETURN_DATUM(result);
 }
+
+/*
+ * rpr
+ * allow to use "Row pattern recognition: WINDOW clause" (SQL:2016 R020) in
+ * the target list.
+ * Usage: SELECT rpr(colname) OVER (..)
+ * where colname is defined in PATTERN clause.
+ */
+Datum
+window_rpr(PG_FUNCTION_ARGS)
+{
+#define	MAX_PATTERNS	16	/* max variables in PATTERN clause */
+
+	WindowObject winobj = PG_WINDOW_OBJECT();
+	WindowAggState	*winstate = WinGetAggState(winobj);
+	Datum		result;
+	bool		expression_result;
+	bool		isnull;
+	int			relpos;
+	int64		curr_pos, markpos;
+	ListCell	*lc, *lc1;
+	SkipContext	*context = NULL;
+
+	curr_pos = WinGetCurrentPosition(winobj);
+	elog(DEBUG1, "rpr is called. row: " INT64_FORMAT, curr_pos);
+
+	if (winstate->rpSkipTo == ST_PAST_LAST_ROW)
+	{
+		context = (SkipContext *) WinGetPartitionLocalMemory(winobj, sizeof(SkipContext));
+		if (curr_pos < context->pos)
+		{
+			elog(DEBUG1, "skip this row: curr_pos: " INT64_FORMAT "context->pos: " INT64_FORMAT,
+				 curr_pos, context->pos);
+			PG_RETURN_NULL();
+		}
+	}
+
+	/*
+	 * Evaluate PATTERN until one of expressions is not true or out of frame.
+	 */
+	relpos = 0;
+
+	forboth(lc, winstate->patternVariableList, lc1, winstate->patternRegexpList)
+	{
+		char	*vname = strVal(lfirst(lc));
+		char	*quantifier = strVal(lfirst(lc1));
+
+		elog(DEBUG1, "relpos: %d pattern vname: %s quantifier: %s", relpos, vname, quantifier);
+
+		/* evaluate row pattern against current row */
+		relpos = evaluate_pattern(winobj, winstate, relpos, vname, quantifier, &expression_result);
+
+		/*
+		 * If the expression did not match, we are done.
+		 */
+		if (!expression_result)
+			break;
+
+		/* out of frame? */
+		if (relpos < 0)
+			break;
+
+		/* count up relative row position */
+		relpos++;
+	}
+
+	elog(DEBUG1, "relpos: %d", relpos);
+
+	/*
+	 * If current row satified the pattern, return argument expression.
+	 */
+	if (expression_result)
+	{
+		result = WinGetFuncArgInFrame(winobj, 0,
+									  0, WINDOW_SEEK_HEAD, false,
+									  &isnull, NULL);
+	}
+
+	/*
+	 * At this point we can set mark down to current pos -2.
+	 */
+	markpos = curr_pos -2;
+	elog(DEBUG1, "markpos: " INT64_FORMAT, markpos);
+	if (markpos >= 0)
+		WinSetMarkPosition(winobj, markpos);
+
+	if (expression_result)
+	{
+		if (winstate->rpSkipTo == ST_PAST_LAST_ROW)
+		{
+			context->pos += relpos;
+			elog(DEBUG1, "context->pos: " INT64_FORMAT, context->pos);
+		}
+		PG_RETURN_DATUM(result);
+	}
+
+	PG_RETURN_NULL();
+}
+
+/*
+ * Evaluate expression associated with PATTERN variable vname.
+ * relpos is relative row position in a frame (starting from 0).
+ * "quantifier" is the quatifier part of the PATTERN regular expression.
+ * Currently only '+' is allowed.
+ * result is out paramater representing the expression evaluation result
+ * is true of false.
+ * Return values are:
+ * >=0: the last match relative row position
+ * -1: current row is out of frame
+ */
+static
+int evaluate_pattern(WindowObject winobj, WindowAggState *winstate,
+					 int relpos, char *vname, char *quantifier, bool *result)
+{
+	ExprContext	*econtext = winstate->ss.ps.ps_ExprContext;
+	ListCell	*lc1, *lc2;
+	ExprState	*pat;
+	Datum		eval_result;
+	int			sts;
+	bool		out_of_frame = false;
+	bool		isnull;
+	StringInfo	encoded_str = makeStringInfo();
+	char		pattern_str[128];
+
+	forboth (lc1, winstate->defineVariableList, lc2, winstate->defineClauseList)
+	{
+		char	*name = strVal(lfirst(lc1));
+		bool	second_try_match = false;
+
+		if (strcmp(vname, name))
+			continue;
+
+		/* set expression to evaluate */
+		pat = lfirst(lc2);
+
+		for (;;)
+		{
+			if (!get_slots(winobj, winstate, relpos))
+			{
+				out_of_frame = true;
+				break;	/* current row is out of frame */
+			}
+
+			/* evaluate the expression */
+			eval_result = ExecEvalExpr(pat, econtext, &isnull);
+			if (isnull)
+			{
+				/* expression is NULL */
+				elog(DEBUG1, "expression for %s is NULL at row: %d", vname, relpos);
+				break;
+			}
+			else
+			{
+				if (!DatumGetBool(eval_result))
+				{
+					/* expression is false */
+					elog(DEBUG1, "expression for %s is false at row: %d", vname, relpos);
+					break;
+				}
+				else
+				{
+					/* expression is true */
+					elog(DEBUG1, "expression for %s is true at row: %d", vname, relpos);
+					appendStringInfoChar(encoded_str, vname[0]);
+
+					/* If quantifier is "+", we need to look for more matching row */
+					if (quantifier && !strcmp(quantifier, "+"))
+					{
+						/* remember that we want to try another row */
+						second_try_match = true;
+						relpos++;
+					}
+					else
+						break;
+				}
+			}
+		}
+		if (second_try_match)
+			relpos--;
+
+		if (out_of_frame)
+		{
+			*result = false;
+			return -1;
+		}
+
+		/* build regular expression */
+		snprintf(pattern_str, sizeof(pattern_str), "%c%s", vname[0], quantifier);
+
+		/*
+		 * Do regular expression matching against sequence of rows satisfying
+		 * the expression using regexp_instr().
+		 */
+		sts = DatumGetInt32(DirectFunctionCall2Coll(regexp_instr, DEFAULT_COLLATION_OID,
+													PointerGetDatum(cstring_to_text(encoded_str->data)),
+													PointerGetDatum(cstring_to_text(pattern_str))));
+		elog(DEBUG1, "regexp_instr returned: %d. str: %s regexp: %s",
+			 sts, encoded_str->data, pattern_str);
+		*result = (sts > 0)? true : false;
+	}
+	return relpos;
+}
+
+/*
+ * Get current, previous and next tuple.
+ * Returns true if still within frame.
+ */
+static bool
+get_slots(WindowObject winobj, WindowAggState *winstate, int current_pos)
+{
+	TupleTableSlot *slot;
+	bool	isnull, isout;
+	int		sts;
+	ExprContext *econtext;
+
+	econtext = winstate->ss.ps.ps_ExprContext;
+
+	/* for current row */
+	slot = winstate->temp_slot_1;
+	sts = WinGetSlotInFrame(winobj, slot,
+							current_pos, WINDOW_SEEK_HEAD, false,
+							&isnull, &isout);
+	if (sts < 0)
+	{
+		elog(DEBUG1, "current row is out of frame");
+		econtext->ecxt_scantuple = winstate->null_slot;
+		return false;
+	}
+	else
+		econtext->ecxt_scantuple = slot;
+
+	/* for PREV */
+	if (current_pos > 0)
+	{
+		slot = winstate->prev_slot;
+		sts = WinGetSlotInFrame(winobj, slot,
+								current_pos - 1, WINDOW_SEEK_HEAD, false,
+								&isnull, &isout);
+		if (sts < 0)
+		{
+			elog(DEBUG1, "previous row out of frame at: %d", current_pos);
+			econtext->ecxt_outertuple = winstate->null_slot;
+		}
+		econtext->ecxt_outertuple = slot;
+	}
+	else
+		econtext->ecxt_outertuple = winstate->null_slot;
+
+	/* for NEXT */
+	slot = winstate->next_slot;
+	sts = WinGetSlotInFrame(winobj, slot,
+							current_pos + 1, WINDOW_SEEK_HEAD, false,
+							&isnull, &isout);
+	if (sts < 0)
+	{
+		elog(DEBUG1, "next row out of frame at: %d", current_pos);
+		econtext->ecxt_innertuple = winstate->null_slot;
+	}
+	else
+		econtext->ecxt_innertuple = slot;
+
+	return true;
+}
+
+/*
+ * prev
+ * Dummy function to invoke RPR's navigation operator "PREV".
+ * This is *not* a window function.
+ */
+Datum
+window_prev(PG_FUNCTION_ARGS)
+{
+	PG_RETURN_DATUM(PG_GETARG_DATUM(0));
+}
+
+/*
+ * next
+ * Dummy function to invoke RPR's navigation operation "NEXT".
+ * This is *not* a window function.
+ */
+Datum
+window_next(PG_FUNCTION_ARGS)
+{
+	PG_RETURN_DATUM(PG_GETARG_DATUM(0));
+}
+
diff --git a/src/include/catalog/pg_proc.dat b/src/include/catalog/pg_proc.dat
index 6996073989..e3a9e0ffeb 100644
--- a/src/include/catalog/pg_proc.dat
+++ b/src/include/catalog/pg_proc.dat
@@ -10397,6 +10397,15 @@
 { oid => '3114', descr => 'fetch the Nth row value',
   proname => 'nth_value', prokind => 'w', prorettype => 'anyelement',
   proargtypes => 'anyelement int4', prosrc => 'window_nth_value' },
+{ oid => '6122', descr => 'row pattern recognition in window',
+  proname => 'rpr', prokind => 'w', prorettype => 'anyelement',
+  proargtypes => 'anyelement', prosrc => 'window_rpr' },
+{ oid => '6123', descr => 'previous value',
+  proname => 'prev', provolatile => 's', prorettype => 'anyelement',
+  proargtypes => 'anyelement', prosrc => 'window_prev' },
+{ oid => '6124', descr => 'next value',
+  proname => 'next', provolatile => 's', prorettype => 'anyelement',
+  proargtypes => 'anyelement', prosrc => 'window_next' },
 
 # functions for range types
 { oid => '3832', descr => 'I/O',
diff --git a/src/include/nodes/execnodes.h b/src/include/nodes/execnodes.h
index cb714f4a19..1643eaa6f1 100644
--- a/src/include/nodes/execnodes.h
+++ b/src/include/nodes/execnodes.h
@@ -2519,6 +2519,14 @@ typedef struct WindowAggState
 	int64		groupheadpos;	/* current row's peer group head position */
 	int64		grouptailpos;	/* " " " " tail position (group end+1) */
 
+	/* these fields are used in Row pattern recognition: */
+	RPSkipTo	rpSkipTo;		/* Row Pattern Skip To type */	
+	List	   *patternVariableList;	/* list of row pattern variables names (list of String) */
+	List	   *patternRegexpList;	/* list of row pattern regular expressions ('+' or ''. list of String) */
+	List	   *defineVariableList;	/* list of row pattern definition variables (list of String) */
+	List	   *defineClauseList;	/* expression for row pattern definition
+									 * search conditions ExprState list */
+
 	MemoryContext partcontext;	/* context for partition-lifespan data */
 	MemoryContext aggcontext;	/* shared context for aggregate working data */
 	MemoryContext curaggcontext;	/* current aggregate's working data */
@@ -2555,6 +2563,11 @@ typedef struct WindowAggState
 	TupleTableSlot *agg_row_slot;
 	TupleTableSlot *temp_slot_1;
 	TupleTableSlot *temp_slot_2;
+
+	/* temporary slots for RPR */
+	TupleTableSlot *prev_slot;	/* PREV row navigation operator */
+	TupleTableSlot *next_slot;	/* NEXT row navigation operator */
+	TupleTableSlot *null_slot;	/* all NULL slot */
 } WindowAggState;
 
 /* ----------------
diff --git a/src/include/windowapi.h b/src/include/windowapi.h
index b8c2c565d1..a0facf38fe 100644
--- a/src/include/windowapi.h
+++ b/src/include/windowapi.h
@@ -58,7 +58,16 @@ extern Datum WinGetFuncArgInFrame(WindowObject winobj, int argno,
 								  int relpos, int seektype, bool set_mark,
 								  bool *isnull, bool *isout);
 
+extern int WinGetSlotInFrame(WindowObject winobj, TupleTableSlot *slot,
+							 int relpos, int seektype, bool set_mark,
+							 bool *isnull, bool *isout);
+
 extern Datum WinGetFuncArgCurrent(WindowObject winobj, int argno,
 								  bool *isnull);
 
+extern WindowAggState *WinGetAggState(WindowObject winobj);
+
+extern bool window_gettupleslot(WindowObject winobj, int64 pos, TupleTableSlot *slot);
+
+
 #endif							/* WINDOWAPI_H */
-- 
2.25.1


----Next_Part(Mon_Jun_26_17_45_07_2023_724)--
Content-Type: Text/X-Patch; charset=us-ascii
Content-Transfer-Encoding: 7bit
Content-Disposition: inline;
 filename="v2-0005-Row-pattern-recognition-patch-docs.patch"



^ permalink  raw  reply  [nested|flat] 9+ messages in thread

* [PATCH v12 3/4] Remove uses of popcount builtins.
@ 2026-02-06 16:00  Nathan Bossart <nathan@postgresql.org>
  0 siblings, 0 replies; 9+ messages in thread

From: Nathan Bossart @ 2026-02-06 16:00 UTC (permalink / raw)

This commit replaces the implementations of pg_popcount{32,64} with
branchless ones in plain C.  While these new implementations do not
make use of more sophisticated population count instructions
available on some CPUs, testing indicates they perform well,
especially now that they are inlined.  A follow-up commit will
replace various loops over these functions with calls to
pg_popcount(), leaving us little reason to worry about
micro-optimizing them further.

Since this commit removes the only uses of the popcount builtins,
we can also remove the corresponding configuration checks.

Suggested-by: John Naylor <johncnaylorls@gmail.com>
Reviewed-by: John Naylor <johncnaylorls@gmail.com>
Discussion: https://postgr.es/m/CANWCAZY7R%2Biy%2Br9YM_sySNydHzNqUirx1xk0tB3ej5HO62GdgQ%40mail.gmail.com
---
 configure                      | 38 ----------------------------
 configure.ac                   |  1 -
 meson.build                    |  1 -
 src/include/pg_config.h.in     |  3 ---
 src/include/port/pg_bitutils.h | 46 +++++++++++-----------------------
 src/port/pg_popcount_aarch64.c |  5 ----
 6 files changed, 14 insertions(+), 80 deletions(-)

diff --git a/configure b/configure
index a10a2c85c6a..8fe368b7201 100755
--- a/configure
+++ b/configure
@@ -15878,44 +15878,6 @@ cat >>confdefs.h <<_ACEOF
 #define HAVE__BUILTIN_CTZ 1
 _ACEOF
 
-fi
-{ $as_echo "$as_me:${as_lineno-$LINENO}: checking for __builtin_popcount" >&5
-$as_echo_n "checking for __builtin_popcount... " >&6; }
-if ${pgac_cv__builtin_popcount+:} false; then :
-  $as_echo_n "(cached) " >&6
-else
-  cat confdefs.h - <<_ACEOF >conftest.$ac_ext
-/* end confdefs.h.  */
-
-int
-call__builtin_popcount(unsigned int x)
-{
-    return __builtin_popcount(x);
-}
-int
-main ()
-{
-
-  ;
-  return 0;
-}
-_ACEOF
-if ac_fn_c_try_link "$LINENO"; then :
-  pgac_cv__builtin_popcount=yes
-else
-  pgac_cv__builtin_popcount=no
-fi
-rm -f core conftest.err conftest.$ac_objext \
-    conftest$ac_exeext conftest.$ac_ext
-fi
-{ $as_echo "$as_me:${as_lineno-$LINENO}: result: $pgac_cv__builtin_popcount" >&5
-$as_echo "$pgac_cv__builtin_popcount" >&6; }
-if test x"${pgac_cv__builtin_popcount}" = xyes ; then
-
-cat >>confdefs.h <<_ACEOF
-#define HAVE__BUILTIN_POPCOUNT 1
-_ACEOF
-
 fi
 # __builtin_frame_address may draw a diagnostic for non-constant argument,
 # so it needs a different test function.
diff --git a/configure.ac b/configure.ac
index 814e64a967e..f569b1c3f35 100644
--- a/configure.ac
+++ b/configure.ac
@@ -1852,7 +1852,6 @@ PGAC_CHECK_BUILTIN_FUNC([__builtin_bswap64], [long int x])
 # We assume that we needn't test all widths of these explicitly:
 PGAC_CHECK_BUILTIN_FUNC([__builtin_clz], [unsigned int x])
 PGAC_CHECK_BUILTIN_FUNC([__builtin_ctz], [unsigned int x])
-PGAC_CHECK_BUILTIN_FUNC([__builtin_popcount], [unsigned int x])
 # __builtin_frame_address may draw a diagnostic for non-constant argument,
 # so it needs a different test function.
 PGAC_CHECK_BUILTIN_FUNC_PTR([__builtin_frame_address], [0])
diff --git a/meson.build b/meson.build
index 96b3869df86..c89293cd80f 100644
--- a/meson.build
+++ b/meson.build
@@ -2004,7 +2004,6 @@ builtins = [
   'ctz',
   'constant_p',
   'frame_address',
-  'popcount',
   'unreachable',
 ]
 
diff --git a/src/include/pg_config.h.in b/src/include/pg_config.h.in
index 339268dc8ef..2651b56ae4d 100644
--- a/src/include/pg_config.h.in
+++ b/src/include/pg_config.h.in
@@ -526,9 +526,6 @@
 /* Define to 1 if your compiler understands __builtin_$op_overflow. */
 #undef HAVE__BUILTIN_OP_OVERFLOW
 
-/* Define to 1 if your compiler understands __builtin_popcount. */
-#undef HAVE__BUILTIN_POPCOUNT
-
 /* Define to 1 if your compiler understands __builtin_types_compatible_p. */
 #undef HAVE__BUILTIN_TYPES_COMPATIBLE_P
 
diff --git a/src/include/port/pg_bitutils.h b/src/include/port/pg_bitutils.h
index 789663edd93..c9b1f5f17dc 100644
--- a/src/include/port/pg_bitutils.h
+++ b/src/include/port/pg_bitutils.h
@@ -297,51 +297,33 @@ extern uint64 pg_popcount_masked_optimized(const char *buf, int bytes, bits8 mas
 /*
  * pg_popcount32
  *		Return the number of 1 bits set in word
+ *
+ * Adapted from
+ * https://graphics.stanford.edu/~seander/bithacks.html#CountBitsSetParallel.
  */
 static inline int
 pg_popcount32(uint32 word)
 {
-#ifdef HAVE__BUILTIN_POPCOUNT
-	return __builtin_popcount(word);
-#else							/* !HAVE__BUILTIN_POPCOUNT */
-	int			result = 0;
-
-	while (word != 0)
-	{
-		result += pg_number_of_ones[word & 255];
-		word >>= 8;
-	}
-
-	return result;
-#endif							/* HAVE__BUILTIN_POPCOUNT */
+	word -= (word >> 1) & 0x55555555;
+	word = (word & 0x33333333) + ((word >> 2) & 0x33333333);
+	return (((word + (word >> 4)) & 0xf0f0f0f) * 0x1010101) >> 24;
 }
 
 /*
  * pg_popcount64
  *		Return the number of 1 bits set in word
+ *
+ * Adapted from
+ * https://graphics.stanford.edu/~seander/bithacks.html#CountBitsSetParallel.
  */
 static inline int
 pg_popcount64(uint64 word)
 {
-#ifdef HAVE__BUILTIN_POPCOUNT
-#if SIZEOF_LONG == 8
-	return __builtin_popcountl(word);
-#elif SIZEOF_LONG_LONG == 8
-	return __builtin_popcountll(word);
-#else
-#error "cannot find integer of the same size as uint64_t"
-#endif
-#else							/* !HAVE__BUILTIN_POPCOUNT */
-	int			result = 0;
-
-	while (word != 0)
-	{
-		result += pg_number_of_ones[word & 255];
-		word >>= 8;
-	}
-
-	return result;
-#endif							/* HAVE__BUILTIN_POPCOUNT */
+	word -= (word >> 1) & UINT64CONST(0x5555555555555555);
+	word = (word & UINT64CONST(0x3333333333333333)) +
+		((word >> 2) & UINT64CONST(0x3333333333333333));
+	word = (word + (word >> 4)) & UINT64CONST(0xf0f0f0f0f0f0f0f);
+	return (word * UINT64CONST(0x101010101010101)) >> 56;
 }
 
 /*
diff --git a/src/port/pg_popcount_aarch64.c b/src/port/pg_popcount_aarch64.c
index f474ef45510..b0f10ae07a4 100644
--- a/src/port/pg_popcount_aarch64.c
+++ b/src/port/pg_popcount_aarch64.c
@@ -298,11 +298,6 @@ pg_popcount_masked_optimized(const char *buf, int bytes, bits8 mask)
 static inline int
 pg_popcount64_neon(uint64 word)
 {
-	/*
-	 * For some compilers, __builtin_popcountl() already emits Neon
-	 * instructions.  The line below should compile to the same code on those
-	 * systems.
-	 */
 	return vaddv_u8(vcnt_u8(vld1_u8((const uint8 *) &word)));
 }
 
-- 
2.50.1 (Apple Git-155)


--AFLuD1w+kMRlv6Zk
Content-Type: text/plain; charset=us-ascii
Content-Disposition: attachment;
	filename=v12-0004-Make-use-of-pg_popcount-in-more-places.patch



^ permalink  raw  reply  [nested|flat] 9+ messages in thread

* [PATCH v11 4/4] Remove uses of popcount builtins.
@ 2026-02-06 16:00  Nathan Bossart <nathan@postgresql.org>
  0 siblings, 0 replies; 9+ messages in thread

From: Nathan Bossart @ 2026-02-06 16:00 UTC (permalink / raw)

---
 configure                      | 38 ----------------------------------
 configure.ac                   |  1 -
 meson.build                    |  1 -
 src/include/pg_config.h.in     |  3 ---
 src/include/port/pg_bitutils.h | 17 +--------------
 src/port/pg_popcount_aarch64.c |  5 -----
 6 files changed, 1 insertion(+), 64 deletions(-)

diff --git a/configure b/configure
index ba293931878..623aa397fae 100755
--- a/configure
+++ b/configure
@@ -15920,44 +15920,6 @@ cat >>confdefs.h <<_ACEOF
 #define HAVE__BUILTIN_CTZ 1
 _ACEOF
 
-fi
-{ $as_echo "$as_me:${as_lineno-$LINENO}: checking for __builtin_popcount" >&5
-$as_echo_n "checking for __builtin_popcount... " >&6; }
-if ${pgac_cv__builtin_popcount+:} false; then :
-  $as_echo_n "(cached) " >&6
-else
-  cat confdefs.h - <<_ACEOF >conftest.$ac_ext
-/* end confdefs.h.  */
-
-int
-call__builtin_popcount(unsigned int x)
-{
-    return __builtin_popcount(x);
-}
-int
-main ()
-{
-
-  ;
-  return 0;
-}
-_ACEOF
-if ac_fn_c_try_link "$LINENO"; then :
-  pgac_cv__builtin_popcount=yes
-else
-  pgac_cv__builtin_popcount=no
-fi
-rm -f core conftest.err conftest.$ac_objext \
-    conftest$ac_exeext conftest.$ac_ext
-fi
-{ $as_echo "$as_me:${as_lineno-$LINENO}: result: $pgac_cv__builtin_popcount" >&5
-$as_echo "$pgac_cv__builtin_popcount" >&6; }
-if test x"${pgac_cv__builtin_popcount}" = xyes ; then
-
-cat >>confdefs.h <<_ACEOF
-#define HAVE__BUILTIN_POPCOUNT 1
-_ACEOF
-
 fi
 # __builtin_frame_address may draw a diagnostic for non-constant argument,
 # so it needs a different test function.
diff --git a/configure.ac b/configure.ac
index 412fe358a2f..04c6a75bff7 100644
--- a/configure.ac
+++ b/configure.ac
@@ -1853,7 +1853,6 @@ PGAC_CHECK_BUILTIN_FUNC([__builtin_bswap64], [long int x])
 # We assume that we needn't test all widths of these explicitly:
 PGAC_CHECK_BUILTIN_FUNC([__builtin_clz], [unsigned int x])
 PGAC_CHECK_BUILTIN_FUNC([__builtin_ctz], [unsigned int x])
-PGAC_CHECK_BUILTIN_FUNC([__builtin_popcount], [unsigned int x])
 # __builtin_frame_address may draw a diagnostic for non-constant argument,
 # so it needs a different test function.
 PGAC_CHECK_BUILTIN_FUNC_PTR([__builtin_frame_address], [0])
diff --git a/meson.build b/meson.build
index 0722b16927e..c607d8ac69a 100644
--- a/meson.build
+++ b/meson.build
@@ -2004,7 +2004,6 @@ builtins = [
   'ctz',
   'constant_p',
   'frame_address',
-  'popcount',
   'unreachable',
 ]
 
diff --git a/src/include/pg_config.h.in b/src/include/pg_config.h.in
index c089f2252c3..301328b8cd3 100644
--- a/src/include/pg_config.h.in
+++ b/src/include/pg_config.h.in
@@ -530,9 +530,6 @@
 /* Define to 1 if your compiler understands __builtin_$op_overflow. */
 #undef HAVE__BUILTIN_OP_OVERFLOW
 
-/* Define to 1 if your compiler understands __builtin_popcount. */
-#undef HAVE__BUILTIN_POPCOUNT
-
 /* Define to 1 if your compiler understands __builtin_types_compatible_p. */
 #undef HAVE__BUILTIN_TYPES_COMPATIBLE_P
 
diff --git a/src/include/port/pg_bitutils.h b/src/include/port/pg_bitutils.h
index 3c58f6c6864..c9b1f5f17dc 100644
--- a/src/include/port/pg_bitutils.h
+++ b/src/include/port/pg_bitutils.h
@@ -313,32 +313,17 @@ pg_popcount32(uint32 word)
  * pg_popcount64
  *		Return the number of 1 bits set in word
  *
- * Plain C version adapted from
+ * Adapted from
  * https://graphics.stanford.edu/~seander/bithacks.html#CountBitsSetParallel.
  */
 static inline int
 pg_popcount64(uint64 word)
 {
-	/*
-	 * On x86, gcc generates a function call for this built-in unless the
-	 * popcnt instruction is available, so we use the plain C version in that
-	 * case to ensure inlining.
-	 */
-#if defined(HAVE__BUILTIN_POPCOUNT) && (defined(__POPCNT__) || !defined(__x86_64__))
-#if SIZEOF_LONG == 8
-	return __builtin_popcountl(word);
-#elif SIZEOF_LONG_LONG == 8
-	return __builtin_popcountll(word);
-#else
-#error "cannot find integer of the same size as uint64_t"
-#endif
-#else
 	word -= (word >> 1) & UINT64CONST(0x5555555555555555);
 	word = (word & UINT64CONST(0x3333333333333333)) +
 		((word >> 2) & UINT64CONST(0x3333333333333333));
 	word = (word + (word >> 4)) & UINT64CONST(0xf0f0f0f0f0f0f0f);
 	return (word * UINT64CONST(0x101010101010101)) >> 56;
-#endif
 }
 
 /*
diff --git a/src/port/pg_popcount_aarch64.c b/src/port/pg_popcount_aarch64.c
index f474ef45510..b0f10ae07a4 100644
--- a/src/port/pg_popcount_aarch64.c
+++ b/src/port/pg_popcount_aarch64.c
@@ -298,11 +298,6 @@ pg_popcount_masked_optimized(const char *buf, int bytes, bits8 mask)
 static inline int
 pg_popcount64_neon(uint64 word)
 {
-	/*
-	 * For some compilers, __builtin_popcountl() already emits Neon
-	 * instructions.  The line below should compile to the same code on those
-	 * systems.
-	 */
 	return vaddv_u8(vcnt_u8(vld1_u8((const uint8 *) &word)));
 }
 
-- 
2.50.1 (Apple Git-155)


--mih0IfQp6StcW7xc--





^ permalink  raw  reply  [nested|flat] 9+ messages in thread

* [PATCH v13 3/5] Remove uses of popcount builtins.
@ 2026-02-06 16:00  Nathan Bossart <nathan@postgresql.org>
  0 siblings, 0 replies; 9+ messages in thread

From: Nathan Bossart @ 2026-02-06 16:00 UTC (permalink / raw)

This commit replaces the implementations of pg_popcount{32,64} with
branchless ones in plain C.  While these new implementations do not
make use of more sophisticated population count instructions
available on some CPUs, testing indicates they perform well,
especially now that they are inlined.  A follow-up commit will
replace various loops over these functions with calls to
pg_popcount(), leaving us little reason to worry about
micro-optimizing them further.

Since this commit removes the only uses of the popcount builtins,
we can also remove the corresponding configuration checks.

Suggested-by: John Naylor <johncnaylorls@gmail.com>
Reviewed-by: John Naylor <johncnaylorls@gmail.com>
Discussion: https://postgr.es/m/CANWCAZY7R%2Biy%2Br9YM_sySNydHzNqUirx1xk0tB3ej5HO62GdgQ%40mail.gmail.com
---
 configure                      | 38 ----------------------------
 configure.ac                   |  1 -
 meson.build                    |  1 -
 src/include/pg_config.h.in     |  3 ---
 src/include/port/pg_bitutils.h | 46 +++++++++++-----------------------
 src/port/pg_popcount_aarch64.c |  5 ----
 6 files changed, 14 insertions(+), 80 deletions(-)

diff --git a/configure b/configure
index a10a2c85c6a..8fe368b7201 100755
--- a/configure
+++ b/configure
@@ -15878,44 +15878,6 @@ cat >>confdefs.h <<_ACEOF
 #define HAVE__BUILTIN_CTZ 1
 _ACEOF
 
-fi
-{ $as_echo "$as_me:${as_lineno-$LINENO}: checking for __builtin_popcount" >&5
-$as_echo_n "checking for __builtin_popcount... " >&6; }
-if ${pgac_cv__builtin_popcount+:} false; then :
-  $as_echo_n "(cached) " >&6
-else
-  cat confdefs.h - <<_ACEOF >conftest.$ac_ext
-/* end confdefs.h.  */
-
-int
-call__builtin_popcount(unsigned int x)
-{
-    return __builtin_popcount(x);
-}
-int
-main ()
-{
-
-  ;
-  return 0;
-}
-_ACEOF
-if ac_fn_c_try_link "$LINENO"; then :
-  pgac_cv__builtin_popcount=yes
-else
-  pgac_cv__builtin_popcount=no
-fi
-rm -f core conftest.err conftest.$ac_objext \
-    conftest$ac_exeext conftest.$ac_ext
-fi
-{ $as_echo "$as_me:${as_lineno-$LINENO}: result: $pgac_cv__builtin_popcount" >&5
-$as_echo "$pgac_cv__builtin_popcount" >&6; }
-if test x"${pgac_cv__builtin_popcount}" = xyes ; then
-
-cat >>confdefs.h <<_ACEOF
-#define HAVE__BUILTIN_POPCOUNT 1
-_ACEOF
-
 fi
 # __builtin_frame_address may draw a diagnostic for non-constant argument,
 # so it needs a different test function.
diff --git a/configure.ac b/configure.ac
index 814e64a967e..f569b1c3f35 100644
--- a/configure.ac
+++ b/configure.ac
@@ -1852,7 +1852,6 @@ PGAC_CHECK_BUILTIN_FUNC([__builtin_bswap64], [long int x])
 # We assume that we needn't test all widths of these explicitly:
 PGAC_CHECK_BUILTIN_FUNC([__builtin_clz], [unsigned int x])
 PGAC_CHECK_BUILTIN_FUNC([__builtin_ctz], [unsigned int x])
-PGAC_CHECK_BUILTIN_FUNC([__builtin_popcount], [unsigned int x])
 # __builtin_frame_address may draw a diagnostic for non-constant argument,
 # so it needs a different test function.
 PGAC_CHECK_BUILTIN_FUNC_PTR([__builtin_frame_address], [0])
diff --git a/meson.build b/meson.build
index 96b3869df86..c89293cd80f 100644
--- a/meson.build
+++ b/meson.build
@@ -2004,7 +2004,6 @@ builtins = [
   'ctz',
   'constant_p',
   'frame_address',
-  'popcount',
   'unreachable',
 ]
 
diff --git a/src/include/pg_config.h.in b/src/include/pg_config.h.in
index 339268dc8ef..2651b56ae4d 100644
--- a/src/include/pg_config.h.in
+++ b/src/include/pg_config.h.in
@@ -526,9 +526,6 @@
 /* Define to 1 if your compiler understands __builtin_$op_overflow. */
 #undef HAVE__BUILTIN_OP_OVERFLOW
 
-/* Define to 1 if your compiler understands __builtin_popcount. */
-#undef HAVE__BUILTIN_POPCOUNT
-
 /* Define to 1 if your compiler understands __builtin_types_compatible_p. */
 #undef HAVE__BUILTIN_TYPES_COMPATIBLE_P
 
diff --git a/src/include/port/pg_bitutils.h b/src/include/port/pg_bitutils.h
index 789663edd93..c9b1f5f17dc 100644
--- a/src/include/port/pg_bitutils.h
+++ b/src/include/port/pg_bitutils.h
@@ -297,51 +297,33 @@ extern uint64 pg_popcount_masked_optimized(const char *buf, int bytes, bits8 mas
 /*
  * pg_popcount32
  *		Return the number of 1 bits set in word
+ *
+ * Adapted from
+ * https://graphics.stanford.edu/~seander/bithacks.html#CountBitsSetParallel.
  */
 static inline int
 pg_popcount32(uint32 word)
 {
-#ifdef HAVE__BUILTIN_POPCOUNT
-	return __builtin_popcount(word);
-#else							/* !HAVE__BUILTIN_POPCOUNT */
-	int			result = 0;
-
-	while (word != 0)
-	{
-		result += pg_number_of_ones[word & 255];
-		word >>= 8;
-	}
-
-	return result;
-#endif							/* HAVE__BUILTIN_POPCOUNT */
+	word -= (word >> 1) & 0x55555555;
+	word = (word & 0x33333333) + ((word >> 2) & 0x33333333);
+	return (((word + (word >> 4)) & 0xf0f0f0f) * 0x1010101) >> 24;
 }
 
 /*
  * pg_popcount64
  *		Return the number of 1 bits set in word
+ *
+ * Adapted from
+ * https://graphics.stanford.edu/~seander/bithacks.html#CountBitsSetParallel.
  */
 static inline int
 pg_popcount64(uint64 word)
 {
-#ifdef HAVE__BUILTIN_POPCOUNT
-#if SIZEOF_LONG == 8
-	return __builtin_popcountl(word);
-#elif SIZEOF_LONG_LONG == 8
-	return __builtin_popcountll(word);
-#else
-#error "cannot find integer of the same size as uint64_t"
-#endif
-#else							/* !HAVE__BUILTIN_POPCOUNT */
-	int			result = 0;
-
-	while (word != 0)
-	{
-		result += pg_number_of_ones[word & 255];
-		word >>= 8;
-	}
-
-	return result;
-#endif							/* HAVE__BUILTIN_POPCOUNT */
+	word -= (word >> 1) & UINT64CONST(0x5555555555555555);
+	word = (word & UINT64CONST(0x3333333333333333)) +
+		((word >> 2) & UINT64CONST(0x3333333333333333));
+	word = (word + (word >> 4)) & UINT64CONST(0xf0f0f0f0f0f0f0f);
+	return (word * UINT64CONST(0x101010101010101)) >> 56;
 }
 
 /*
diff --git a/src/port/pg_popcount_aarch64.c b/src/port/pg_popcount_aarch64.c
index f474ef45510..b0f10ae07a4 100644
--- a/src/port/pg_popcount_aarch64.c
+++ b/src/port/pg_popcount_aarch64.c
@@ -298,11 +298,6 @@ pg_popcount_masked_optimized(const char *buf, int bytes, bits8 mask)
 static inline int
 pg_popcount64_neon(uint64 word)
 {
-	/*
-	 * For some compilers, __builtin_popcountl() already emits Neon
-	 * instructions.  The line below should compile to the same code on those
-	 * systems.
-	 */
 	return vaddv_u8(vcnt_u8(vld1_u8((const uint8 *) &word)));
 }
 
-- 
2.50.1 (Apple Git-155)


--5NNwvjHYUnRaoEDo
Content-Type: text/plain; charset=us-ascii
Content-Disposition: attachment;
	filename=v13-0004-Convert-some-popcount-functions-to-macros.patch



^ permalink  raw  reply  [nested|flat] 9+ messages in thread

* [PATCH v14 1/2] Remove uses of popcount builtins.
@ 2026-02-06 16:00  Nathan Bossart <nathan@postgresql.org>
  0 siblings, 0 replies; 9+ messages in thread

From: Nathan Bossart @ 2026-02-06 16:00 UTC (permalink / raw)

This commit replaces the implementations of pg_popcount{32,64} with
branchless ones in plain C.  While these new implementations do not
make use of more sophisticated population count instructions
available on some CPUs, testing indicates they perform well,
especially now that they are inlined.  A follow-up commit will
replace various loops over these functions with calls to
pg_popcount(), leaving us little reason to worry about
micro-optimizing them further.

Since this commit removes the only uses of the popcount builtins,
we can also remove the corresponding configuration checks.

Suggested-by: John Naylor <johncnaylorls@gmail.com>
Reviewed-by: John Naylor <johncnaylorls@gmail.com>
Discussion: https://postgr.es/m/CANWCAZY7R%2Biy%2Br9YM_sySNydHzNqUirx1xk0tB3ej5HO62GdgQ%40mail.gmail.com
---
 configure                      | 38 ----------------------------
 configure.ac                   |  1 -
 meson.build                    |  1 -
 src/include/pg_config.h.in     |  3 ---
 src/include/port/pg_bitutils.h | 46 +++++++++++-----------------------
 src/port/pg_popcount_aarch64.c |  5 ----
 6 files changed, 14 insertions(+), 80 deletions(-)

diff --git a/configure b/configure
index a10a2c85c6a..8fe368b7201 100755
--- a/configure
+++ b/configure
@@ -15878,44 +15878,6 @@ cat >>confdefs.h <<_ACEOF
 #define HAVE__BUILTIN_CTZ 1
 _ACEOF
 
-fi
-{ $as_echo "$as_me:${as_lineno-$LINENO}: checking for __builtin_popcount" >&5
-$as_echo_n "checking for __builtin_popcount... " >&6; }
-if ${pgac_cv__builtin_popcount+:} false; then :
-  $as_echo_n "(cached) " >&6
-else
-  cat confdefs.h - <<_ACEOF >conftest.$ac_ext
-/* end confdefs.h.  */
-
-int
-call__builtin_popcount(unsigned int x)
-{
-    return __builtin_popcount(x);
-}
-int
-main ()
-{
-
-  ;
-  return 0;
-}
-_ACEOF
-if ac_fn_c_try_link "$LINENO"; then :
-  pgac_cv__builtin_popcount=yes
-else
-  pgac_cv__builtin_popcount=no
-fi
-rm -f core conftest.err conftest.$ac_objext \
-    conftest$ac_exeext conftest.$ac_ext
-fi
-{ $as_echo "$as_me:${as_lineno-$LINENO}: result: $pgac_cv__builtin_popcount" >&5
-$as_echo "$pgac_cv__builtin_popcount" >&6; }
-if test x"${pgac_cv__builtin_popcount}" = xyes ; then
-
-cat >>confdefs.h <<_ACEOF
-#define HAVE__BUILTIN_POPCOUNT 1
-_ACEOF
-
 fi
 # __builtin_frame_address may draw a diagnostic for non-constant argument,
 # so it needs a different test function.
diff --git a/configure.ac b/configure.ac
index 814e64a967e..f569b1c3f35 100644
--- a/configure.ac
+++ b/configure.ac
@@ -1852,7 +1852,6 @@ PGAC_CHECK_BUILTIN_FUNC([__builtin_bswap64], [long int x])
 # We assume that we needn't test all widths of these explicitly:
 PGAC_CHECK_BUILTIN_FUNC([__builtin_clz], [unsigned int x])
 PGAC_CHECK_BUILTIN_FUNC([__builtin_ctz], [unsigned int x])
-PGAC_CHECK_BUILTIN_FUNC([__builtin_popcount], [unsigned int x])
 # __builtin_frame_address may draw a diagnostic for non-constant argument,
 # so it needs a different test function.
 PGAC_CHECK_BUILTIN_FUNC_PTR([__builtin_frame_address], [0])
diff --git a/meson.build b/meson.build
index 96b3869df86..c89293cd80f 100644
--- a/meson.build
+++ b/meson.build
@@ -2004,7 +2004,6 @@ builtins = [
   'ctz',
   'constant_p',
   'frame_address',
-  'popcount',
   'unreachable',
 ]
 
diff --git a/src/include/pg_config.h.in b/src/include/pg_config.h.in
index 339268dc8ef..2651b56ae4d 100644
--- a/src/include/pg_config.h.in
+++ b/src/include/pg_config.h.in
@@ -526,9 +526,6 @@
 /* Define to 1 if your compiler understands __builtin_$op_overflow. */
 #undef HAVE__BUILTIN_OP_OVERFLOW
 
-/* Define to 1 if your compiler understands __builtin_popcount. */
-#undef HAVE__BUILTIN_POPCOUNT
-
 /* Define to 1 if your compiler understands __builtin_types_compatible_p. */
 #undef HAVE__BUILTIN_TYPES_COMPATIBLE_P
 
diff --git a/src/include/port/pg_bitutils.h b/src/include/port/pg_bitutils.h
index 789663edd93..c9b1f5f17dc 100644
--- a/src/include/port/pg_bitutils.h
+++ b/src/include/port/pg_bitutils.h
@@ -297,51 +297,33 @@ extern uint64 pg_popcount_masked_optimized(const char *buf, int bytes, bits8 mas
 /*
  * pg_popcount32
  *		Return the number of 1 bits set in word
+ *
+ * Adapted from
+ * https://graphics.stanford.edu/~seander/bithacks.html#CountBitsSetParallel.
  */
 static inline int
 pg_popcount32(uint32 word)
 {
-#ifdef HAVE__BUILTIN_POPCOUNT
-	return __builtin_popcount(word);
-#else							/* !HAVE__BUILTIN_POPCOUNT */
-	int			result = 0;
-
-	while (word != 0)
-	{
-		result += pg_number_of_ones[word & 255];
-		word >>= 8;
-	}
-
-	return result;
-#endif							/* HAVE__BUILTIN_POPCOUNT */
+	word -= (word >> 1) & 0x55555555;
+	word = (word & 0x33333333) + ((word >> 2) & 0x33333333);
+	return (((word + (word >> 4)) & 0xf0f0f0f) * 0x1010101) >> 24;
 }
 
 /*
  * pg_popcount64
  *		Return the number of 1 bits set in word
+ *
+ * Adapted from
+ * https://graphics.stanford.edu/~seander/bithacks.html#CountBitsSetParallel.
  */
 static inline int
 pg_popcount64(uint64 word)
 {
-#ifdef HAVE__BUILTIN_POPCOUNT
-#if SIZEOF_LONG == 8
-	return __builtin_popcountl(word);
-#elif SIZEOF_LONG_LONG == 8
-	return __builtin_popcountll(word);
-#else
-#error "cannot find integer of the same size as uint64_t"
-#endif
-#else							/* !HAVE__BUILTIN_POPCOUNT */
-	int			result = 0;
-
-	while (word != 0)
-	{
-		result += pg_number_of_ones[word & 255];
-		word >>= 8;
-	}
-
-	return result;
-#endif							/* HAVE__BUILTIN_POPCOUNT */
+	word -= (word >> 1) & UINT64CONST(0x5555555555555555);
+	word = (word & UINT64CONST(0x3333333333333333)) +
+		((word >> 2) & UINT64CONST(0x3333333333333333));
+	word = (word + (word >> 4)) & UINT64CONST(0xf0f0f0f0f0f0f0f);
+	return (word * UINT64CONST(0x101010101010101)) >> 56;
 }
 
 /*
diff --git a/src/port/pg_popcount_aarch64.c b/src/port/pg_popcount_aarch64.c
index f474ef45510..b0f10ae07a4 100644
--- a/src/port/pg_popcount_aarch64.c
+++ b/src/port/pg_popcount_aarch64.c
@@ -298,11 +298,6 @@ pg_popcount_masked_optimized(const char *buf, int bytes, bits8 mask)
 static inline int
 pg_popcount64_neon(uint64 word)
 {
-	/*
-	 * For some compilers, __builtin_popcountl() already emits Neon
-	 * instructions.  The line below should compile to the same code on those
-	 * systems.
-	 */
 	return vaddv_u8(vcnt_u8(vld1_u8((const uint8 *) &word)));
 }
 
-- 
2.50.1 (Apple Git-155)


--rjsRYmGG7r/fFdxn
Content-Type: text/plain; charset=us-ascii
Content-Disposition: attachment;
	filename=v14-0002-Make-use-of-pg_popcount-in-more-places.patch



^ permalink  raw  reply  [nested|flat] 9+ messages in thread

* [PATCH v14 1/2] Remove uses of popcount builtins.
@ 2026-02-06 16:00  Nathan Bossart <nathan@postgresql.org>
  0 siblings, 0 replies; 9+ messages in thread

From: Nathan Bossart @ 2026-02-06 16:00 UTC (permalink / raw)

This commit replaces the implementations of pg_popcount{32,64} with
branchless ones in plain C.  While these new implementations do not
make use of more sophisticated population count instructions
available on some CPUs, testing indicates they perform well,
especially now that they are inlined.  A follow-up commit will
replace various loops over these functions with calls to
pg_popcount(), leaving us little reason to worry about
micro-optimizing them further.

Since this commit removes the only uses of the popcount builtins,
we can also remove the corresponding configuration checks.

Suggested-by: John Naylor <johncnaylorls@gmail.com>
Reviewed-by: John Naylor <johncnaylorls@gmail.com>
Discussion: https://postgr.es/m/CANWCAZY7R%2Biy%2Br9YM_sySNydHzNqUirx1xk0tB3ej5HO62GdgQ%40mail.gmail.com
---
 configure                      | 38 ----------------------------
 configure.ac                   |  1 -
 meson.build                    |  1 -
 src/include/pg_config.h.in     |  3 ---
 src/include/port/pg_bitutils.h | 46 +++++++++++-----------------------
 src/port/pg_popcount_aarch64.c |  5 ----
 6 files changed, 14 insertions(+), 80 deletions(-)

diff --git a/configure b/configure
index a10a2c85c6a..8fe368b7201 100755
--- a/configure
+++ b/configure
@@ -15878,44 +15878,6 @@ cat >>confdefs.h <<_ACEOF
 #define HAVE__BUILTIN_CTZ 1
 _ACEOF
 
-fi
-{ $as_echo "$as_me:${as_lineno-$LINENO}: checking for __builtin_popcount" >&5
-$as_echo_n "checking for __builtin_popcount... " >&6; }
-if ${pgac_cv__builtin_popcount+:} false; then :
-  $as_echo_n "(cached) " >&6
-else
-  cat confdefs.h - <<_ACEOF >conftest.$ac_ext
-/* end confdefs.h.  */
-
-int
-call__builtin_popcount(unsigned int x)
-{
-    return __builtin_popcount(x);
-}
-int
-main ()
-{
-
-  ;
-  return 0;
-}
-_ACEOF
-if ac_fn_c_try_link "$LINENO"; then :
-  pgac_cv__builtin_popcount=yes
-else
-  pgac_cv__builtin_popcount=no
-fi
-rm -f core conftest.err conftest.$ac_objext \
-    conftest$ac_exeext conftest.$ac_ext
-fi
-{ $as_echo "$as_me:${as_lineno-$LINENO}: result: $pgac_cv__builtin_popcount" >&5
-$as_echo "$pgac_cv__builtin_popcount" >&6; }
-if test x"${pgac_cv__builtin_popcount}" = xyes ; then
-
-cat >>confdefs.h <<_ACEOF
-#define HAVE__BUILTIN_POPCOUNT 1
-_ACEOF
-
 fi
 # __builtin_frame_address may draw a diagnostic for non-constant argument,
 # so it needs a different test function.
diff --git a/configure.ac b/configure.ac
index 814e64a967e..f569b1c3f35 100644
--- a/configure.ac
+++ b/configure.ac
@@ -1852,7 +1852,6 @@ PGAC_CHECK_BUILTIN_FUNC([__builtin_bswap64], [long int x])
 # We assume that we needn't test all widths of these explicitly:
 PGAC_CHECK_BUILTIN_FUNC([__builtin_clz], [unsigned int x])
 PGAC_CHECK_BUILTIN_FUNC([__builtin_ctz], [unsigned int x])
-PGAC_CHECK_BUILTIN_FUNC([__builtin_popcount], [unsigned int x])
 # __builtin_frame_address may draw a diagnostic for non-constant argument,
 # so it needs a different test function.
 PGAC_CHECK_BUILTIN_FUNC_PTR([__builtin_frame_address], [0])
diff --git a/meson.build b/meson.build
index 96b3869df86..c89293cd80f 100644
--- a/meson.build
+++ b/meson.build
@@ -2004,7 +2004,6 @@ builtins = [
   'ctz',
   'constant_p',
   'frame_address',
-  'popcount',
   'unreachable',
 ]
 
diff --git a/src/include/pg_config.h.in b/src/include/pg_config.h.in
index 339268dc8ef..2651b56ae4d 100644
--- a/src/include/pg_config.h.in
+++ b/src/include/pg_config.h.in
@@ -526,9 +526,6 @@
 /* Define to 1 if your compiler understands __builtin_$op_overflow. */
 #undef HAVE__BUILTIN_OP_OVERFLOW
 
-/* Define to 1 if your compiler understands __builtin_popcount. */
-#undef HAVE__BUILTIN_POPCOUNT
-
 /* Define to 1 if your compiler understands __builtin_types_compatible_p. */
 #undef HAVE__BUILTIN_TYPES_COMPATIBLE_P
 
diff --git a/src/include/port/pg_bitutils.h b/src/include/port/pg_bitutils.h
index 789663edd93..c9b1f5f17dc 100644
--- a/src/include/port/pg_bitutils.h
+++ b/src/include/port/pg_bitutils.h
@@ -297,51 +297,33 @@ extern uint64 pg_popcount_masked_optimized(const char *buf, int bytes, bits8 mas
 /*
  * pg_popcount32
  *		Return the number of 1 bits set in word
+ *
+ * Adapted from
+ * https://graphics.stanford.edu/~seander/bithacks.html#CountBitsSetParallel.
  */
 static inline int
 pg_popcount32(uint32 word)
 {
-#ifdef HAVE__BUILTIN_POPCOUNT
-	return __builtin_popcount(word);
-#else							/* !HAVE__BUILTIN_POPCOUNT */
-	int			result = 0;
-
-	while (word != 0)
-	{
-		result += pg_number_of_ones[word & 255];
-		word >>= 8;
-	}
-
-	return result;
-#endif							/* HAVE__BUILTIN_POPCOUNT */
+	word -= (word >> 1) & 0x55555555;
+	word = (word & 0x33333333) + ((word >> 2) & 0x33333333);
+	return (((word + (word >> 4)) & 0xf0f0f0f) * 0x1010101) >> 24;
 }
 
 /*
  * pg_popcount64
  *		Return the number of 1 bits set in word
+ *
+ * Adapted from
+ * https://graphics.stanford.edu/~seander/bithacks.html#CountBitsSetParallel.
  */
 static inline int
 pg_popcount64(uint64 word)
 {
-#ifdef HAVE__BUILTIN_POPCOUNT
-#if SIZEOF_LONG == 8
-	return __builtin_popcountl(word);
-#elif SIZEOF_LONG_LONG == 8
-	return __builtin_popcountll(word);
-#else
-#error "cannot find integer of the same size as uint64_t"
-#endif
-#else							/* !HAVE__BUILTIN_POPCOUNT */
-	int			result = 0;
-
-	while (word != 0)
-	{
-		result += pg_number_of_ones[word & 255];
-		word >>= 8;
-	}
-
-	return result;
-#endif							/* HAVE__BUILTIN_POPCOUNT */
+	word -= (word >> 1) & UINT64CONST(0x5555555555555555);
+	word = (word & UINT64CONST(0x3333333333333333)) +
+		((word >> 2) & UINT64CONST(0x3333333333333333));
+	word = (word + (word >> 4)) & UINT64CONST(0xf0f0f0f0f0f0f0f);
+	return (word * UINT64CONST(0x101010101010101)) >> 56;
 }
 
 /*
diff --git a/src/port/pg_popcount_aarch64.c b/src/port/pg_popcount_aarch64.c
index f474ef45510..b0f10ae07a4 100644
--- a/src/port/pg_popcount_aarch64.c
+++ b/src/port/pg_popcount_aarch64.c
@@ -298,11 +298,6 @@ pg_popcount_masked_optimized(const char *buf, int bytes, bits8 mask)
 static inline int
 pg_popcount64_neon(uint64 word)
 {
-	/*
-	 * For some compilers, __builtin_popcountl() already emits Neon
-	 * instructions.  The line below should compile to the same code on those
-	 * systems.
-	 */
 	return vaddv_u8(vcnt_u8(vld1_u8((const uint8 *) &word)));
 }
 
-- 
2.50.1 (Apple Git-155)


--rjsRYmGG7r/fFdxn
Content-Type: text/plain; charset=us-ascii
Content-Disposition: attachment;
	filename=v14-0002-Make-use-of-pg_popcount-in-more-places.patch



^ permalink  raw  reply  [nested|flat] 9+ messages in thread

* [PATCH v15 1/2] Remove uses of popcount builtins.
@ 2026-02-20 20:33  Nathan Bossart <nathan@postgresql.org>
  0 siblings, 0 replies; 9+ messages in thread

From: Nathan Bossart @ 2026-02-20 20:33 UTC (permalink / raw)

This commit replaces the implementations of pg_popcount{32,64} with
branchless ones in plain C.  Newer versions of popular compilers
will automatically replace these with more sophisticated population
count instructions if possible, leaving us little reason to
continue using the builtins.  This also allows us to remove the
remaining architecture-specific implementations of pg_popcount64(),
which were only used by the corresponding architecture-specific
implementations of pg_popcount() and pg_popcount_masked().  Since
this commit removes the only uses of the popcount builtins, we can
remove the corresponding configuration checks, too.

Suggested-by: John Naylor <johncnaylorls@gmail.com>
Reviewed-by: John Naylor <johncnaylorls@gmail.com>
Discussion: https://postgr.es/m/CANWCAZY7R%2Biy%2Br9YM_sySNydHzNqUirx1xk0tB3ej5HO62GdgQ%40mail.gmail.com
---
 config/c-compiler.m4           |  26 +++++++
 configure                      | 119 +++++++++++++--------------------
 configure.ac                   |  23 +++----
 meson.build                    |  43 +++++++-----
 src/include/pg_config.h.in     |   7 +-
 src/include/port/pg_bitutils.h |  56 +++++++---------
 src/port/pg_bitutils.c         |   4 +-
 src/port/pg_popcount_aarch64.c |  19 +-----
 src/port/pg_popcount_x86.c     |  27 ++------
 9 files changed, 143 insertions(+), 181 deletions(-)

diff --git a/config/c-compiler.m4 b/config/c-compiler.m4
index 1509dbfa2ab..93fd6b3b617 100644
--- a/config/c-compiler.m4
+++ b/config/c-compiler.m4
@@ -743,6 +743,32 @@ fi
 undefine([Ac_cachevar])dnl
 ])# PGAC_XSAVE_INTRINSICS
 
+# PGAC_X86_POPCNT_INTRINSICS
+# ----------------------
+# Check if the compiler supports the x86 POPCNT instructions, using the
+# _popcnt64 intrinsic function.
+#
+# If the instrinsic is supported, sets pgac_x86_popcnt_intrinsics
+AC_DEFUN([PGAC_X86_POPCNT_INTRINSICS],
+[define([Ac_cachevar], [AS_TR_SH([pgac_cv_x86_popcnt_intrinsics])])dnl
+AC_CACHE_CHECK([for _popcnt64], [Ac_cachevar],
+[AC_LINK_IFELSE([AC_LANG_PROGRAM([#include <immintrin.h>
+    #if defined(__has_attribute) && __has_attribute (target)
+    __attribute__((target("popcnt")))
+    #endif
+    static int x86_popcnt_test(void)
+    {
+      return _popcnt64(0);
+    }],
+  [return x86_popcnt_test();])],
+  [Ac_cachevar=yes],
+  [Ac_cachevar=no])])
+if test x"$Ac_cachevar" = x"yes"; then
+  pgac_x86_popcnt_intrinsics=yes
+fi
+undefine([Ac_cachevar])dnl
+])# PGAC_X86_POPCNT_INTRINSICS
+
 # PGAC_AVX512_POPCNT_INTRINSICS
 # -----------------------------
 # Check if the compiler supports the AVX-512 popcount instructions using the
diff --git a/configure b/configure
index e1a08129974..a37b8d9676c 100755
--- a/configure
+++ b/configure
@@ -15256,40 +15256,6 @@ fi
 
 
 case $host_cpu in
-  x86_64)
-    # On x86_64, check if we can compile a popcntq instruction
-    { $as_echo "$as_me:${as_lineno-$LINENO}: checking whether assembler supports x86_64 popcntq" >&5
-$as_echo_n "checking whether assembler supports x86_64 popcntq... " >&6; }
-if ${pgac_cv_have_x86_64_popcntq+:} false; then :
-  $as_echo_n "(cached) " >&6
-else
-  cat confdefs.h - <<_ACEOF >conftest.$ac_ext
-/* end confdefs.h.  */
-
-int
-main ()
-{
-long long x = 1; long long r;
-	 __asm__ __volatile__ (" popcntq %1,%0\n" : "=q"(r) : "rm"(x));
-  ;
-  return 0;
-}
-_ACEOF
-if ac_fn_c_try_compile "$LINENO"; then :
-  pgac_cv_have_x86_64_popcntq=yes
-else
-  pgac_cv_have_x86_64_popcntq=no
-fi
-rm -f core conftest.err conftest.$ac_objext conftest.$ac_ext
-fi
-{ $as_echo "$as_me:${as_lineno-$LINENO}: result: $pgac_cv_have_x86_64_popcntq" >&5
-$as_echo "$pgac_cv_have_x86_64_popcntq" >&6; }
-    if test x"$pgac_cv_have_x86_64_popcntq" = xyes ; then
-
-$as_echo "#define HAVE_X86_64_POPCNTQ 1" >>confdefs.h
-
-    fi
-  ;;
   ppc*|powerpc*)
     # On PPC, check if compiler accepts "i"(x) when __builtin_constant_p(x).
     { $as_echo "$as_me:${as_lineno-$LINENO}: checking whether __builtin_constant_p(x) implies \"i\"(x) acceptance" >&5
@@ -15836,44 +15802,6 @@ cat >>confdefs.h <<_ACEOF
 #define HAVE__BUILTIN_CTZ 1
 _ACEOF
 
-fi
-{ $as_echo "$as_me:${as_lineno-$LINENO}: checking for __builtin_popcount" >&5
-$as_echo_n "checking for __builtin_popcount... " >&6; }
-if ${pgac_cv__builtin_popcount+:} false; then :
-  $as_echo_n "(cached) " >&6
-else
-  cat confdefs.h - <<_ACEOF >conftest.$ac_ext
-/* end confdefs.h.  */
-
-int
-call__builtin_popcount(unsigned int x)
-{
-    return __builtin_popcount(x);
-}
-int
-main ()
-{
-
-  ;
-  return 0;
-}
-_ACEOF
-if ac_fn_c_try_link "$LINENO"; then :
-  pgac_cv__builtin_popcount=yes
-else
-  pgac_cv__builtin_popcount=no
-fi
-rm -f core conftest.err conftest.$ac_objext \
-    conftest$ac_exeext conftest.$ac_ext
-fi
-{ $as_echo "$as_me:${as_lineno-$LINENO}: result: $pgac_cv__builtin_popcount" >&5
-$as_echo "$pgac_cv__builtin_popcount" >&6; }
-if test x"${pgac_cv__builtin_popcount}" = xyes ; then
-
-cat >>confdefs.h <<_ACEOF
-#define HAVE__BUILTIN_POPCOUNT 1
-_ACEOF
-
 fi
 # __builtin_frame_address may draw a diagnostic for non-constant argument,
 # so it needs a different test function.
@@ -17721,6 +17649,53 @@ $as_echo "#define HAVE_XSAVE_INTRINSICS 1" >>confdefs.h
 
 fi
 
+# Check for x86 POPCNT intrinsics
+#
+if test x"$host_cpu" = x"x86_64"; then
+  { $as_echo "$as_me:${as_lineno-$LINENO}: checking for _popcnt64" >&5
+$as_echo_n "checking for _popcnt64... " >&6; }
+if ${pgac_cv_x86_popcnt_intrinsics+:} false; then :
+  $as_echo_n "(cached) " >&6
+else
+  cat confdefs.h - <<_ACEOF >conftest.$ac_ext
+/* end confdefs.h.  */
+#include <immintrin.h>
+    #if defined(__has_attribute) && __has_attribute (target)
+    __attribute__((target("popcnt")))
+    #endif
+    static int x86_popcnt_test(void)
+    {
+      return _popcnt64(0);
+    }
+int
+main ()
+{
+return x86_popcnt_test();
+  ;
+  return 0;
+}
+_ACEOF
+if ac_fn_c_try_link "$LINENO"; then :
+  pgac_cv_x86_popcnt_intrinsics=yes
+else
+  pgac_cv_x86_popcnt_intrinsics=no
+fi
+rm -f core conftest.err conftest.$ac_objext \
+    conftest$ac_exeext conftest.$ac_ext
+fi
+{ $as_echo "$as_me:${as_lineno-$LINENO}: result: $pgac_cv_x86_popcnt_intrinsics" >&5
+$as_echo "$pgac_cv_x86_popcnt_intrinsics" >&6; }
+if test x"$pgac_cv_x86_popcnt_intrinsics" = x"yes"; then
+  pgac_x86_popcnt_intrinsics=yes
+fi
+
+  if test x"$pgac_x86_popcnt_intrinsics" = x"yes"; then
+
+$as_echo "#define HAVE_X86_POPCNT_INTRINSICS 1" >>confdefs.h
+
+  fi
+fi
+
 # Check for AVX-512 popcount intrinsics
 #
 if test x"$host_cpu" = x"x86_64"; then
diff --git a/configure.ac b/configure.ac
index cc85c233c03..1594ee802b8 100644
--- a/configure.ac
+++ b/configure.ac
@@ -1746,19 +1746,6 @@ AC_CHECK_TYPES([struct option], [], [],
 #endif])
 
 case $host_cpu in
-  x86_64)
-    # On x86_64, check if we can compile a popcntq instruction
-    AC_CACHE_CHECK([whether assembler supports x86_64 popcntq],
-                   [pgac_cv_have_x86_64_popcntq],
-    [AC_COMPILE_IFELSE([AC_LANG_PROGRAM([],
-	[long long x = 1; long long r;
-	 __asm__ __volatile__ (" popcntq %1,%0\n" : "=q"(r) : "rm"(x));])],
-	[pgac_cv_have_x86_64_popcntq=yes],
-	[pgac_cv_have_x86_64_popcntq=no])])
-    if test x"$pgac_cv_have_x86_64_popcntq" = xyes ; then
-	AC_DEFINE(HAVE_X86_64_POPCNTQ, 1, [Define to 1 if the assembler supports X86_64's POPCNTQ instruction.])
-    fi
-  ;;
   ppc*|powerpc*)
     # On PPC, check if compiler accepts "i"(x) when __builtin_constant_p(x).
     AC_CACHE_CHECK([whether __builtin_constant_p(x) implies "i"(x) acceptance],
@@ -1851,7 +1838,6 @@ PGAC_CHECK_BUILTIN_FUNC([__builtin_bswap64], [long int x])
 # We assume that we needn't test all widths of these explicitly:
 PGAC_CHECK_BUILTIN_FUNC([__builtin_clz], [unsigned int x])
 PGAC_CHECK_BUILTIN_FUNC([__builtin_ctz], [unsigned int x])
-PGAC_CHECK_BUILTIN_FUNC([__builtin_popcount], [unsigned int x])
 # __builtin_frame_address may draw a diagnostic for non-constant argument,
 # so it needs a different test function.
 PGAC_CHECK_BUILTIN_FUNC_PTR([__builtin_frame_address], [0])
@@ -2128,6 +2114,15 @@ if test x"$pgac_xsave_intrinsics" = x"yes"; then
   AC_DEFINE(HAVE_XSAVE_INTRINSICS, 1, [Define to 1 if you have XSAVE intrinsics.])
 fi
 
+# Check for x86 POPCNT intrinsics
+#
+if test x"$host_cpu" = x"x86_64"; then
+  PGAC_X86_POPCNT_INTRINSICS()
+  if test x"$pgac_x86_popcnt_intrinsics" = x"yes"; then
+    AC_DEFINE(HAVE_X86_POPCNT_INTRINSICS, 1, [Define to 1 if you have x86 POPCNT intrinsics.])
+  fi
+fi
+
 # Check for AVX-512 popcount intrinsics
 #
 if test x"$host_cpu" = x"x86_64"; then
diff --git a/meson.build b/meson.build
index 055e96315d0..b44cfd3993a 100644
--- a/meson.build
+++ b/meson.build
@@ -2006,7 +2006,6 @@ builtins = [
   'ctz',
   'constant_p',
   'frame_address',
-  'popcount',
   'unreachable',
 ]
 
@@ -2377,6 +2376,31 @@ int main(void)
 endif
 
 
+###############################################################
+# Check for the availability of x86 POPCNT intrinsics.
+###############################################################
+
+if host_cpu == 'x86_64'
+
+  prog = '''
+#include <immintrin.h>
+
+#if defined(__has_attribute) && __has_attribute (target)
+__attribute__((target("popcnt")))
+#endif
+int main(void)
+{
+    return _popcnt64(0);
+}
+'''
+
+  if cc.links(prog, name: 'x86 POPCNT intrinsics', args: test_c_args)
+    cdata.set('HAVE_X86_POPCNT_INTRINSICS', 1)
+  endif
+
+endif
+
+
 ###############################################################
 # Check for the availability of AVX-512 popcount intrinsics.
 ###############################################################
@@ -2641,22 +2665,7 @@ endif
 # Other CPU specific stuff
 ###############################################################
 
-if host_cpu == 'x86_64'
-
-  if cc.get_id() == 'msvc'
-    cdata.set('HAVE_X86_64_POPCNTQ', 1)
-  elif cc.compiles('''
-      void main(void)
-      {
-          long long x = 1; long long r;
-          __asm__ __volatile__ (" popcntq %1,%0\n" : "=q"(r) : "rm"(x));
-      }''',
-      name: '@0@: popcntq instruction'.format(host_cpu),
-      args: test_c_args)
-    cdata.set('HAVE_X86_64_POPCNTQ', 1)
-  endif
-
-elif host_cpu == 'ppc' or host_cpu == 'ppc64'
+if host_cpu == 'ppc' or host_cpu == 'ppc64'
   # Check if compiler accepts "i"(x) when __builtin_constant_p(x).
   if cdata.has('HAVE__BUILTIN_CONSTANT_P')
     if cc.compiles('''
diff --git a/src/include/pg_config.h.in b/src/include/pg_config.h.in
index 3824a5571bb..2f6d291d9b2 100644
--- a/src/include/pg_config.h.in
+++ b/src/include/pg_config.h.in
@@ -493,8 +493,8 @@
 /* Define to 1 if you have the `X509_get_signature_info' function. */
 #undef HAVE_X509_GET_SIGNATURE_INFO
 
-/* Define to 1 if the assembler supports X86_64's POPCNTQ instruction. */
-#undef HAVE_X86_64_POPCNTQ
+/* Define to 1 if you have x86 POPCNT intrinsics. */
+#undef HAVE_X86_POPCNT_INTRINSICS
 
 /* Define to 1 if you have the <xlocale.h> header file. */
 #undef HAVE_XLOCALE_H
@@ -526,9 +526,6 @@
 /* Define to 1 if your compiler understands __builtin_$op_overflow. */
 #undef HAVE__BUILTIN_OP_OVERFLOW
 
-/* Define to 1 if your compiler understands __builtin_popcount. */
-#undef HAVE__BUILTIN_POPCOUNT
-
 /* Define to 1 if your compiler understands __builtin_types_compatible_p. */
 #undef HAVE__BUILTIN_TYPES_COMPATIBLE_P
 
diff --git a/src/include/port/pg_bitutils.h b/src/include/port/pg_bitutils.h
index 789663edd93..53df0594823 100644
--- a/src/include/port/pg_bitutils.h
+++ b/src/include/port/pg_bitutils.h
@@ -279,7 +279,7 @@ pg_ceil_log2_64(uint64 num)
 extern uint64 pg_popcount_portable(const char *buf, int bytes);
 extern uint64 pg_popcount_masked_portable(const char *buf, int bytes, bits8 mask);
 
-#if defined(HAVE_X86_64_POPCNTQ) || defined(USE_SVE_POPCNT_WITH_RUNTIME_CHECK)
+#if defined(HAVE_X86_POPCNT_INTRINSICS) || defined(USE_SVE_POPCNT_WITH_RUNTIME_CHECK)
 /*
  * Attempt to use specialized CPU instructions, but perform a runtime check
  * first.
@@ -297,51 +297,41 @@ extern uint64 pg_popcount_masked_optimized(const char *buf, int bytes, bits8 mas
 /*
  * pg_popcount32
  *		Return the number of 1 bits set in word
+ *
+ * Adapted from
+ * https://graphics.stanford.edu/~seander/bithacks.html#CountBitsSetParallel.
+ *
+ * Note that newer versions of popular compilers will automatically replace
+ * this with a special popcount instruction if possible, so there isn't much
+ * reason to use builtin functions or intrinsics.
  */
 static inline int
 pg_popcount32(uint32 word)
 {
-#ifdef HAVE__BUILTIN_POPCOUNT
-	return __builtin_popcount(word);
-#else							/* !HAVE__BUILTIN_POPCOUNT */
-	int			result = 0;
-
-	while (word != 0)
-	{
-		result += pg_number_of_ones[word & 255];
-		word >>= 8;
-	}
-
-	return result;
-#endif							/* HAVE__BUILTIN_POPCOUNT */
+	word -= (word >> 1) & 0x55555555;
+	word = (word & 0x33333333) + ((word >> 2) & 0x33333333);
+	return (((word + (word >> 4)) & 0xf0f0f0f) * 0x1010101) >> 24;
 }
 
 /*
  * pg_popcount64
  *		Return the number of 1 bits set in word
+ *
+ * Adapted from
+ * https://graphics.stanford.edu/~seander/bithacks.html#CountBitsSetParallel.
+ *
+ * Note that newer versions of popular compilers will automatically replace
+ * this with a special popcount instruction if possible, so there isn't much
+ * reason to use builtin functions or intrinsics.
  */
 static inline int
 pg_popcount64(uint64 word)
 {
-#ifdef HAVE__BUILTIN_POPCOUNT
-#if SIZEOF_LONG == 8
-	return __builtin_popcountl(word);
-#elif SIZEOF_LONG_LONG == 8
-	return __builtin_popcountll(word);
-#else
-#error "cannot find integer of the same size as uint64_t"
-#endif
-#else							/* !HAVE__BUILTIN_POPCOUNT */
-	int			result = 0;
-
-	while (word != 0)
-	{
-		result += pg_number_of_ones[word & 255];
-		word >>= 8;
-	}
-
-	return result;
-#endif							/* HAVE__BUILTIN_POPCOUNT */
+	word -= (word >> 1) & UINT64CONST(0x5555555555555555);
+	word = (word & UINT64CONST(0x3333333333333333)) +
+		((word >> 2) & UINT64CONST(0x3333333333333333));
+	word = (word + (word >> 4)) & UINT64CONST(0xf0f0f0f0f0f0f0f);
+	return (word * UINT64CONST(0x101010101010101)) >> 56;
 }
 
 /*
diff --git a/src/port/pg_bitutils.c b/src/port/pg_bitutils.c
index 49b130f1306..71327810119 100644
--- a/src/port/pg_bitutils.c
+++ b/src/port/pg_bitutils.c
@@ -162,7 +162,7 @@ pg_popcount_masked_portable(const char *buf, int bytes, bits8 mask)
 	return popcnt;
 }
 
-#if !defined(HAVE_X86_64_POPCNTQ) && !defined(USE_NEON)
+#if !defined(HAVE_X86_POPCNT_INTRINSICS) && !defined(USE_NEON)
 
 /*
  * When special CPU instructions are not available, there's no point in using
@@ -191,4 +191,4 @@ pg_popcount_masked_optimized(const char *buf, int bytes, bits8 mask)
 	return pg_popcount_masked_portable(buf, bytes, mask);
 }
 
-#endif							/* ! HAVE_X86_64_POPCNTQ && ! USE_NEON */
+#endif							/* ! HAVE_X86_POPCNT_INTRINSICS && ! USE_NEON */
diff --git a/src/port/pg_popcount_aarch64.c b/src/port/pg_popcount_aarch64.c
index f474ef45510..74f71593721 100644
--- a/src/port/pg_popcount_aarch64.c
+++ b/src/port/pg_popcount_aarch64.c
@@ -291,21 +291,6 @@ pg_popcount_masked_optimized(const char *buf, int bytes, bits8 mask)
 
 #endif							/* ! USE_SVE_POPCNT_WITH_RUNTIME_CHECK */
 
-/*
- * pg_popcount64_neon
- *		Return number of 1 bits in word
- */
-static inline int
-pg_popcount64_neon(uint64 word)
-{
-	/*
-	 * For some compilers, __builtin_popcountl() already emits Neon
-	 * instructions.  The line below should compile to the same code on those
-	 * systems.
-	 */
-	return vaddv_u8(vcnt_u8(vld1_u8((const uint8 *) &word)));
-}
-
 /*
  * pg_popcount_neon
  *		Returns number of 1 bits in buf
@@ -373,7 +358,7 @@ pg_popcount_neon(const char *buf, int bytes)
 	 */
 	for (; bytes >= sizeof(uint64); bytes -= sizeof(uint64))
 	{
-		popcnt += pg_popcount64_neon(*((const uint64 *) buf));
+		popcnt += pg_popcount64(*((const uint64 *) buf));
 		buf += sizeof(uint64);
 	}
 
@@ -455,7 +440,7 @@ pg_popcount_masked_neon(const char *buf, int bytes, bits8 mask)
 	 */
 	for (; bytes >= sizeof(uint64); bytes -= sizeof(uint64))
 	{
-		popcnt += pg_popcount64_neon(*((const uint64 *) buf) & mask64);
+		popcnt += pg_popcount64(*((const uint64 *) buf) & mask64);
 		buf += sizeof(uint64);
 	}
 
diff --git a/src/port/pg_popcount_x86.c b/src/port/pg_popcount_x86.c
index 6bce089432f..45ade1ee37b 100644
--- a/src/port/pg_popcount_x86.c
+++ b/src/port/pg_popcount_x86.c
@@ -12,7 +12,7 @@
  */
 #include "c.h"
 
-#ifdef HAVE_X86_64_POPCNTQ
+#ifdef HAVE_X86_POPCNT_INTRINSICS
 
 #if defined(HAVE__GET_CPUID) || defined(HAVE__GET_CPUID_COUNT)
 #include <cpuid.h>
@@ -314,28 +314,12 @@ pg_popcount_masked_avx512(const char *buf, int bytes, bits8 mask)
 
 #endif							/* USE_AVX512_POPCNT_WITH_RUNTIME_CHECK */
 
-/*
- * pg_popcount64_sse42
- *		Return the number of 1 bits set in word
- */
-static inline int
-pg_popcount64_sse42(uint64 word)
-{
-#ifdef _MSC_VER
-	return __popcnt64(word);
-#else
-	uint64		res;
-
-__asm__ __volatile__(" popcntq %1,%0\n":"=q"(res):"rm"(word):"cc");
-	return (int) res;
-#endif
-}
-
 /*
  * pg_popcount_sse42
  *		Returns the number of 1-bits in buf
  */
 pg_attribute_no_sanitize_alignment()
+pg_attribute_target("popcnt")
 static uint64
 pg_popcount_sse42(const char *buf, int bytes)
 {
@@ -344,7 +328,7 @@ pg_popcount_sse42(const char *buf, int bytes)
 
 	while (bytes >= 8)
 	{
-		popcnt += pg_popcount64_sse42(*words++);
+		popcnt += pg_popcount64(*words++);
 		bytes -= 8;
 	}
 
@@ -362,6 +346,7 @@ pg_popcount_sse42(const char *buf, int bytes)
  *		Returns the number of 1-bits in buf after applying the mask to each byte
  */
 pg_attribute_no_sanitize_alignment()
+pg_attribute_target("popcnt")
 static uint64
 pg_popcount_masked_sse42(const char *buf, int bytes, bits8 mask)
 {
@@ -371,7 +356,7 @@ pg_popcount_masked_sse42(const char *buf, int bytes, bits8 mask)
 
 	while (bytes >= 8)
 	{
-		popcnt += pg_popcount64_sse42(*words++ & maskv);
+		popcnt += pg_popcount64(*words++ & maskv);
 		bytes -= 8;
 	}
 
@@ -384,4 +369,4 @@ pg_popcount_masked_sse42(const char *buf, int bytes, bits8 mask)
 	return popcnt;
 }
 
-#endif							/* HAVE_X86_64_POPCNTQ */
+#endif							/* HAVE_X86_POPCNT_INTRINSICS */
-- 
2.50.1 (Apple Git-155)


--PPBl4GgF05zqfOFU
Content-Type: text/plain; charset=us-ascii
Content-Disposition: attachment;
	filename=v15-0002-Make-use-of-pg_popcount-in-more-places.patch



^ permalink  raw  reply  [nested|flat] 9+ messages in thread

* [PATCH v16 1/2] Remove uses of popcount builtins.
@ 2026-02-21 21:12  Nathan Bossart <nathan@postgresql.org>
  0 siblings, 0 replies; 9+ messages in thread

From: Nathan Bossart @ 2026-02-21 21:12 UTC (permalink / raw)

This commit replaces the implementations of pg_popcount{32,64} with
branchless ones in plain C.  While these new implementations do not
make use of more sophisticated population count instructions
available on some CPUs, testing indicates they perform well,
especially now that they are inlined.  Newer versions of popular
compilers will automatically replace these with special
instructions if possible, anyway.  A follow-up commit will replace
various loops over these functions with calls to pg_popcount(),
leaving us little reason to worry about micro-optimizing them
further.

Since this commit removes the only uses of the popcount builtins,
we can also remove the corresponding configuration checks.

Suggested-by: John Naylor <johncnaylorls@gmail.com>
Reviewed-by: John Naylor <johncnaylorls@gmail.com>
Discussion: https://postgr.es/m/CANWCAZY7R%2Biy%2Br9YM_sySNydHzNqUirx1xk0tB3ej5HO62GdgQ%40mail.gmail.com
---
 configure                      | 38 ------------------------
 configure.ac                   |  1 -
 meson.build                    |  1 -
 src/include/pg_config.h.in     |  3 --
 src/include/port/pg_bitutils.h | 54 ++++++++++++++--------------------
 src/port/pg_popcount_aarch64.c |  5 ----
 6 files changed, 22 insertions(+), 80 deletions(-)

diff --git a/configure b/configure
index e1a08129974..cb143a48141 100755
--- a/configure
+++ b/configure
@@ -15836,44 +15836,6 @@ cat >>confdefs.h <<_ACEOF
 #define HAVE__BUILTIN_CTZ 1
 _ACEOF
 
-fi
-{ $as_echo "$as_me:${as_lineno-$LINENO}: checking for __builtin_popcount" >&5
-$as_echo_n "checking for __builtin_popcount... " >&6; }
-if ${pgac_cv__builtin_popcount+:} false; then :
-  $as_echo_n "(cached) " >&6
-else
-  cat confdefs.h - <<_ACEOF >conftest.$ac_ext
-/* end confdefs.h.  */
-
-int
-call__builtin_popcount(unsigned int x)
-{
-    return __builtin_popcount(x);
-}
-int
-main ()
-{
-
-  ;
-  return 0;
-}
-_ACEOF
-if ac_fn_c_try_link "$LINENO"; then :
-  pgac_cv__builtin_popcount=yes
-else
-  pgac_cv__builtin_popcount=no
-fi
-rm -f core conftest.err conftest.$ac_objext \
-    conftest$ac_exeext conftest.$ac_ext
-fi
-{ $as_echo "$as_me:${as_lineno-$LINENO}: result: $pgac_cv__builtin_popcount" >&5
-$as_echo "$pgac_cv__builtin_popcount" >&6; }
-if test x"${pgac_cv__builtin_popcount}" = xyes ; then
-
-cat >>confdefs.h <<_ACEOF
-#define HAVE__BUILTIN_POPCOUNT 1
-_ACEOF
-
 fi
 # __builtin_frame_address may draw a diagnostic for non-constant argument,
 # so it needs a different test function.
diff --git a/configure.ac b/configure.ac
index cc85c233c03..3951787313a 100644
--- a/configure.ac
+++ b/configure.ac
@@ -1851,7 +1851,6 @@ PGAC_CHECK_BUILTIN_FUNC([__builtin_bswap64], [long int x])
 # We assume that we needn't test all widths of these explicitly:
 PGAC_CHECK_BUILTIN_FUNC([__builtin_clz], [unsigned int x])
 PGAC_CHECK_BUILTIN_FUNC([__builtin_ctz], [unsigned int x])
-PGAC_CHECK_BUILTIN_FUNC([__builtin_popcount], [unsigned int x])
 # __builtin_frame_address may draw a diagnostic for non-constant argument,
 # so it needs a different test function.
 PGAC_CHECK_BUILTIN_FUNC_PTR([__builtin_frame_address], [0])
diff --git a/meson.build b/meson.build
index 055e96315d0..e0972f3a3d9 100644
--- a/meson.build
+++ b/meson.build
@@ -2006,7 +2006,6 @@ builtins = [
   'ctz',
   'constant_p',
   'frame_address',
-  'popcount',
   'unreachable',
 ]
 
diff --git a/src/include/pg_config.h.in b/src/include/pg_config.h.in
index 3824a5571bb..af08c5a7eb8 100644
--- a/src/include/pg_config.h.in
+++ b/src/include/pg_config.h.in
@@ -526,9 +526,6 @@
 /* Define to 1 if your compiler understands __builtin_$op_overflow. */
 #undef HAVE__BUILTIN_OP_OVERFLOW
 
-/* Define to 1 if your compiler understands __builtin_popcount. */
-#undef HAVE__BUILTIN_POPCOUNT
-
 /* Define to 1 if your compiler understands __builtin_types_compatible_p. */
 #undef HAVE__BUILTIN_TYPES_COMPATIBLE_P
 
diff --git a/src/include/port/pg_bitutils.h b/src/include/port/pg_bitutils.h
index 789663edd93..0bca559caaa 100644
--- a/src/include/port/pg_bitutils.h
+++ b/src/include/port/pg_bitutils.h
@@ -297,51 +297,41 @@ extern uint64 pg_popcount_masked_optimized(const char *buf, int bytes, bits8 mas
 /*
  * pg_popcount32
  *		Return the number of 1 bits set in word
+ *
+ * Adapted from
+ * https://graphics.stanford.edu/~seander/bithacks.html#CountBitsSetParallel.
+ *
+ * Note that newer versions of popular compilers will automatically replace
+ * this with a special popcount instruction if possible, so we don't bother
+ * using builtin functions or intrinsics.
  */
 static inline int
 pg_popcount32(uint32 word)
 {
-#ifdef HAVE__BUILTIN_POPCOUNT
-	return __builtin_popcount(word);
-#else							/* !HAVE__BUILTIN_POPCOUNT */
-	int			result = 0;
-
-	while (word != 0)
-	{
-		result += pg_number_of_ones[word & 255];
-		word >>= 8;
-	}
-
-	return result;
-#endif							/* HAVE__BUILTIN_POPCOUNT */
+	word -= (word >> 1) & 0x55555555;
+	word = (word & 0x33333333) + ((word >> 2) & 0x33333333);
+	return (((word + (word >> 4)) & 0xf0f0f0f) * 0x1010101) >> 24;
 }
 
 /*
  * pg_popcount64
  *		Return the number of 1 bits set in word
+ *
+ * Adapted from
+ * https://graphics.stanford.edu/~seander/bithacks.html#CountBitsSetParallel.
+ *
+ * Note that newer versions of popular compilers will automatically replace
+ * this with a special popcount instruction if possible, so we don't bother
+ * using builtin functions or intrinsics.
  */
 static inline int
 pg_popcount64(uint64 word)
 {
-#ifdef HAVE__BUILTIN_POPCOUNT
-#if SIZEOF_LONG == 8
-	return __builtin_popcountl(word);
-#elif SIZEOF_LONG_LONG == 8
-	return __builtin_popcountll(word);
-#else
-#error "cannot find integer of the same size as uint64_t"
-#endif
-#else							/* !HAVE__BUILTIN_POPCOUNT */
-	int			result = 0;
-
-	while (word != 0)
-	{
-		result += pg_number_of_ones[word & 255];
-		word >>= 8;
-	}
-
-	return result;
-#endif							/* HAVE__BUILTIN_POPCOUNT */
+	word -= (word >> 1) & UINT64CONST(0x5555555555555555);
+	word = (word & UINT64CONST(0x3333333333333333)) +
+		((word >> 2) & UINT64CONST(0x3333333333333333));
+	word = (word + (word >> 4)) & UINT64CONST(0xf0f0f0f0f0f0f0f);
+	return (word * UINT64CONST(0x101010101010101)) >> 56;
 }
 
 /*
diff --git a/src/port/pg_popcount_aarch64.c b/src/port/pg_popcount_aarch64.c
index f474ef45510..b0f10ae07a4 100644
--- a/src/port/pg_popcount_aarch64.c
+++ b/src/port/pg_popcount_aarch64.c
@@ -298,11 +298,6 @@ pg_popcount_masked_optimized(const char *buf, int bytes, bits8 mask)
 static inline int
 pg_popcount64_neon(uint64 word)
 {
-	/*
-	 * For some compilers, __builtin_popcountl() already emits Neon
-	 * instructions.  The line below should compile to the same code on those
-	 * systems.
-	 */
 	return vaddv_u8(vcnt_u8(vld1_u8((const uint8 *) &word)));
 }
 
-- 
2.50.1 (Apple Git-155)


--/1paUjurV8mGDyTY
Content-Type: text/plain; charset=us-ascii
Content-Disposition: attachment;
	filename=v16-0002-Make-use-of-pg_popcount-in-more-places.patch



^ permalink  raw  reply  [nested|flat] 9+ messages in thread

* [PATCH v16 1/2] Remove uses of popcount builtins.
@ 2026-02-21 21:12  Nathan Bossart <nathan@postgresql.org>
  0 siblings, 0 replies; 9+ messages in thread

From: Nathan Bossart @ 2026-02-21 21:12 UTC (permalink / raw)

This commit replaces the implementations of pg_popcount{32,64} with
branchless ones in plain C.  While these new implementations do not
make use of more sophisticated population count instructions
available on some CPUs, testing indicates they perform well,
especially now that they are inlined.  Newer versions of popular
compilers will automatically replace these with special
instructions if possible, anyway.  A follow-up commit will replace
various loops over these functions with calls to pg_popcount(),
leaving us little reason to worry about micro-optimizing them
further.

Since this commit removes the only uses of the popcount builtins,
we can also remove the corresponding configuration checks.

Suggested-by: John Naylor <johncnaylorls@gmail.com>
Reviewed-by: John Naylor <johncnaylorls@gmail.com>
Discussion: https://postgr.es/m/CANWCAZY7R%2Biy%2Br9YM_sySNydHzNqUirx1xk0tB3ej5HO62GdgQ%40mail.gmail.com
---
 configure                      | 38 ------------------------
 configure.ac                   |  1 -
 meson.build                    |  1 -
 src/include/pg_config.h.in     |  3 --
 src/include/port/pg_bitutils.h | 54 ++++++++++++++--------------------
 src/port/pg_popcount_aarch64.c |  5 ----
 6 files changed, 22 insertions(+), 80 deletions(-)

diff --git a/configure b/configure
index e1a08129974..cb143a48141 100755
--- a/configure
+++ b/configure
@@ -15836,44 +15836,6 @@ cat >>confdefs.h <<_ACEOF
 #define HAVE__BUILTIN_CTZ 1
 _ACEOF
 
-fi
-{ $as_echo "$as_me:${as_lineno-$LINENO}: checking for __builtin_popcount" >&5
-$as_echo_n "checking for __builtin_popcount... " >&6; }
-if ${pgac_cv__builtin_popcount+:} false; then :
-  $as_echo_n "(cached) " >&6
-else
-  cat confdefs.h - <<_ACEOF >conftest.$ac_ext
-/* end confdefs.h.  */
-
-int
-call__builtin_popcount(unsigned int x)
-{
-    return __builtin_popcount(x);
-}
-int
-main ()
-{
-
-  ;
-  return 0;
-}
-_ACEOF
-if ac_fn_c_try_link "$LINENO"; then :
-  pgac_cv__builtin_popcount=yes
-else
-  pgac_cv__builtin_popcount=no
-fi
-rm -f core conftest.err conftest.$ac_objext \
-    conftest$ac_exeext conftest.$ac_ext
-fi
-{ $as_echo "$as_me:${as_lineno-$LINENO}: result: $pgac_cv__builtin_popcount" >&5
-$as_echo "$pgac_cv__builtin_popcount" >&6; }
-if test x"${pgac_cv__builtin_popcount}" = xyes ; then
-
-cat >>confdefs.h <<_ACEOF
-#define HAVE__BUILTIN_POPCOUNT 1
-_ACEOF
-
 fi
 # __builtin_frame_address may draw a diagnostic for non-constant argument,
 # so it needs a different test function.
diff --git a/configure.ac b/configure.ac
index cc85c233c03..3951787313a 100644
--- a/configure.ac
+++ b/configure.ac
@@ -1851,7 +1851,6 @@ PGAC_CHECK_BUILTIN_FUNC([__builtin_bswap64], [long int x])
 # We assume that we needn't test all widths of these explicitly:
 PGAC_CHECK_BUILTIN_FUNC([__builtin_clz], [unsigned int x])
 PGAC_CHECK_BUILTIN_FUNC([__builtin_ctz], [unsigned int x])
-PGAC_CHECK_BUILTIN_FUNC([__builtin_popcount], [unsigned int x])
 # __builtin_frame_address may draw a diagnostic for non-constant argument,
 # so it needs a different test function.
 PGAC_CHECK_BUILTIN_FUNC_PTR([__builtin_frame_address], [0])
diff --git a/meson.build b/meson.build
index 055e96315d0..e0972f3a3d9 100644
--- a/meson.build
+++ b/meson.build
@@ -2006,7 +2006,6 @@ builtins = [
   'ctz',
   'constant_p',
   'frame_address',
-  'popcount',
   'unreachable',
 ]
 
diff --git a/src/include/pg_config.h.in b/src/include/pg_config.h.in
index 3824a5571bb..af08c5a7eb8 100644
--- a/src/include/pg_config.h.in
+++ b/src/include/pg_config.h.in
@@ -526,9 +526,6 @@
 /* Define to 1 if your compiler understands __builtin_$op_overflow. */
 #undef HAVE__BUILTIN_OP_OVERFLOW
 
-/* Define to 1 if your compiler understands __builtin_popcount. */
-#undef HAVE__BUILTIN_POPCOUNT
-
 /* Define to 1 if your compiler understands __builtin_types_compatible_p. */
 #undef HAVE__BUILTIN_TYPES_COMPATIBLE_P
 
diff --git a/src/include/port/pg_bitutils.h b/src/include/port/pg_bitutils.h
index 789663edd93..0bca559caaa 100644
--- a/src/include/port/pg_bitutils.h
+++ b/src/include/port/pg_bitutils.h
@@ -297,51 +297,41 @@ extern uint64 pg_popcount_masked_optimized(const char *buf, int bytes, bits8 mas
 /*
  * pg_popcount32
  *		Return the number of 1 bits set in word
+ *
+ * Adapted from
+ * https://graphics.stanford.edu/~seander/bithacks.html#CountBitsSetParallel.
+ *
+ * Note that newer versions of popular compilers will automatically replace
+ * this with a special popcount instruction if possible, so we don't bother
+ * using builtin functions or intrinsics.
  */
 static inline int
 pg_popcount32(uint32 word)
 {
-#ifdef HAVE__BUILTIN_POPCOUNT
-	return __builtin_popcount(word);
-#else							/* !HAVE__BUILTIN_POPCOUNT */
-	int			result = 0;
-
-	while (word != 0)
-	{
-		result += pg_number_of_ones[word & 255];
-		word >>= 8;
-	}
-
-	return result;
-#endif							/* HAVE__BUILTIN_POPCOUNT */
+	word -= (word >> 1) & 0x55555555;
+	word = (word & 0x33333333) + ((word >> 2) & 0x33333333);
+	return (((word + (word >> 4)) & 0xf0f0f0f) * 0x1010101) >> 24;
 }
 
 /*
  * pg_popcount64
  *		Return the number of 1 bits set in word
+ *
+ * Adapted from
+ * https://graphics.stanford.edu/~seander/bithacks.html#CountBitsSetParallel.
+ *
+ * Note that newer versions of popular compilers will automatically replace
+ * this with a special popcount instruction if possible, so we don't bother
+ * using builtin functions or intrinsics.
  */
 static inline int
 pg_popcount64(uint64 word)
 {
-#ifdef HAVE__BUILTIN_POPCOUNT
-#if SIZEOF_LONG == 8
-	return __builtin_popcountl(word);
-#elif SIZEOF_LONG_LONG == 8
-	return __builtin_popcountll(word);
-#else
-#error "cannot find integer of the same size as uint64_t"
-#endif
-#else							/* !HAVE__BUILTIN_POPCOUNT */
-	int			result = 0;
-
-	while (word != 0)
-	{
-		result += pg_number_of_ones[word & 255];
-		word >>= 8;
-	}
-
-	return result;
-#endif							/* HAVE__BUILTIN_POPCOUNT */
+	word -= (word >> 1) & UINT64CONST(0x5555555555555555);
+	word = (word & UINT64CONST(0x3333333333333333)) +
+		((word >> 2) & UINT64CONST(0x3333333333333333));
+	word = (word + (word >> 4)) & UINT64CONST(0xf0f0f0f0f0f0f0f);
+	return (word * UINT64CONST(0x101010101010101)) >> 56;
 }
 
 /*
diff --git a/src/port/pg_popcount_aarch64.c b/src/port/pg_popcount_aarch64.c
index f474ef45510..b0f10ae07a4 100644
--- a/src/port/pg_popcount_aarch64.c
+++ b/src/port/pg_popcount_aarch64.c
@@ -298,11 +298,6 @@ pg_popcount_masked_optimized(const char *buf, int bytes, bits8 mask)
 static inline int
 pg_popcount64_neon(uint64 word)
 {
-	/*
-	 * For some compilers, __builtin_popcountl() already emits Neon
-	 * instructions.  The line below should compile to the same code on those
-	 * systems.
-	 */
 	return vaddv_u8(vcnt_u8(vld1_u8((const uint8 *) &word)));
 }
 
-- 
2.50.1 (Apple Git-155)


--/1paUjurV8mGDyTY
Content-Type: text/plain; charset=us-ascii
Content-Disposition: attachment;
	filename=v16-0002-Make-use-of-pg_popcount-in-more-places.patch



^ permalink  raw  reply  [nested|flat] 9+ messages in thread

end of thread, other threads:[~2026-02-21 21:12 UTC | newest]

Thread overview: 9+ messages (download: mbox mbox.gz follow: Atom feed)
-- links below jump to the message on this page --
2023-06-26 08:05 [PATCH v2 4/7] Row pattern recognition patch (executor). Tatsuo Ishii <ishii@postgresql.org>
2026-02-06 16:00 [PATCH v12 3/4] Remove uses of popcount builtins. Nathan Bossart <nathan@postgresql.org>
2026-02-06 16:00 [PATCH v14 1/2] Remove uses of popcount builtins. Nathan Bossart <nathan@postgresql.org>
2026-02-06 16:00 [PATCH v11 4/4] Remove uses of popcount builtins. Nathan Bossart <nathan@postgresql.org>
2026-02-06 16:00 [PATCH v13 3/5] Remove uses of popcount builtins. Nathan Bossart <nathan@postgresql.org>
2026-02-06 16:00 [PATCH v14 1/2] Remove uses of popcount builtins. Nathan Bossart <nathan@postgresql.org>
2026-02-20 20:33 [PATCH v15 1/2] Remove uses of popcount builtins. Nathan Bossart <nathan@postgresql.org>
2026-02-21 21:12 [PATCH v16 1/2] Remove uses of popcount builtins. Nathan Bossart <nathan@postgresql.org>
2026-02-21 21:12 [PATCH v16 1/2] Remove uses of popcount builtins. Nathan Bossart <nathan@postgresql.org>

This inbox is served by agora; see mirroring instructions
for how to clone and mirror all data and code used for this inbox