v2-0002-Improve-list-manipulation-in-several-places.patch

From 08fd0abbb9f4f44ea2a2bf06c9b1524c176ec6ca Mon Sep 17 00:00:00 2001
From: Richard Guo <guofenglinux@gmail.com>
Date: Sun, 23 Apr 2023 14:14:39 +0800
Subject: [PATCH v2 2/2] Improve list manipulation in several places

In several places where we manipulate List in such a way as
lappend(list_copy(list), datum), or lcons(datum, list_copy(list)), we can
improve their performance by reducing the movement of list elements.  This
patch introduces new functions to do that, which may also benefit future
callers.
---
 src/backend/commands/extension.c              |  2 +-
 src/backend/nodes/list.c                      | 86 +++++++++++++++++++
 src/backend/optimizer/path/joinpath.c         |  6 +-
 .../replication/logical/applyparallelworker.c |  2 +-
 src/backend/utils/adt/ruleutils.c             |  2 +-
 src/include/nodes/pg_list.h                   | 14 +++
 6 files changed, 105 insertions(+), 7 deletions(-)

diff --git a/src/backend/commands/extension.c b/src/backend/commands/extension.c
index 0eabe18335..1471725f24 100644
--- a/src/backend/commands/extension.c
+++ b/src/backend/commands/extension.c
@@ -1710,7 +1710,7 @@ get_required_extension(char *reqExtensionName,
 							reqExtensionName)));
 
 			/* Add current extension to list of parents to pass down. */
-			cascade_parents = lappend(list_copy(parents), extensionName);
+			cascade_parents = lappend_copy(parents, extensionName);
 
 			/*
 			 * Create the required extension.  We propagate the SCHEMA option
diff --git a/src/backend/nodes/list.c b/src/backend/nodes/list.c
index 750ee5a7e5..0714e34873 100644
--- a/src/backend/nodes/list.c
+++ b/src/backend/nodes/list.c
@@ -349,6 +349,36 @@ lappend(List *list, void *datum)
 	return list;
 }
 
+/*
+ * Form a new list by appending a new element to a shallow copy of the
+ * specified list.
+ *
+ * The input list is not modified.
+ *
+ * This is equivalent to, but more efficient than,
+ * lappend(list_copy(list), datum).
+ */
+List *
+lappend_copy(const List *list, void *datum)
+{
+	List	   *result;
+
+	Assert(IsPointerList(list));
+
+	if (list == NIL)
+		result = new_list(T_List, 1);
+	else
+	{
+		result = new_list(list->type, list->length + 1);
+		memcpy(result->elements, list->elements,
+			   list->length * sizeof(ListCell));
+	}
+
+	llast(result) = datum;
+	check_list_invariants(result);
+	return result;
+}
+
 /*
  * Append an integer to the specified list. See lappend()
  */
@@ -505,6 +535,36 @@ lcons(void *datum, List *list)
 	return list;
 }
 
+/*
+ * Form a new list by prepending a new element to a shallow copy of the
+ * specified list.
+ *
+ * The input list is not modified.
+ *
+ * This is equivalent to, but more efficient than,
+ * lcons(datum, list_copy(list)).
+ */
+List *
+lcons_copy(void *datum, const List *list)
+{
+	List	   *result;
+
+	Assert(IsPointerList(list));
+
+	if (list == NIL)
+		result = new_list(T_List, 1);
+	else
+	{
+		result = new_list(list->type, list->length + 1);
+		memcpy(result->elements + 1, list->elements,
+			   list->length * sizeof(ListCell));
+	}
+
+	linitial(result) = datum;
+	check_list_invariants(result);
+	return result;
+}
+
 /*
  * Prepend an integer to the list. See lcons()
  */
@@ -1654,6 +1714,32 @@ list_copy_deep(const List *oldlist)
 	return newlist;
 }
 
+/*
+ * Return a shallow copy of the specified list with nth element being moved to
+ * the head.
+ */
+List *
+list_copy_move_nth_to_head(const List *oldlist, int n)
+{
+	List	   *newlist;
+
+	if (oldlist == NIL)
+		return NIL;
+
+	Assert(n >= 0 && n < oldlist->length);
+
+	newlist = new_list(oldlist->type, oldlist->length);
+
+	newlist->elements[0] = oldlist->elements[n];
+	memcpy(newlist->elements + 1, oldlist->elements,
+		   n * sizeof(ListCell));
+	memcpy(newlist->elements + 1 + n, oldlist->elements + 1 + n,
+		   (newlist->length - 1 - n) * sizeof(ListCell));
+
+	check_list_invariants(newlist);
+	return newlist;
+}
+
 /*
  * Sort a list according to the specified comparator function.
  *
diff --git a/src/backend/optimizer/path/joinpath.c b/src/backend/optimizer/path/joinpath.c
index cd80e61fd7..98ede13c99 100644
--- a/src/backend/optimizer/path/joinpath.c
+++ b/src/backend/optimizer/path/joinpath.c
@@ -1317,7 +1317,6 @@ sort_inner_and_outer(PlannerInfo *root,
 
 	foreach(l, all_pathkeys)
 	{
-		PathKey    *front_pathkey = (PathKey *) lfirst(l);
 		List	   *cur_mergeclauses;
 		List	   *outerkeys;
 		List	   *innerkeys;
@@ -1325,9 +1324,8 @@ sort_inner_and_outer(PlannerInfo *root,
 
 		/* Make a pathkey list with this guy first */
 		if (l != list_head(all_pathkeys))
-			outerkeys = lcons(front_pathkey,
-							  list_delete_nth_cell(list_copy(all_pathkeys),
-												   foreach_current_index(l)));
+			outerkeys = list_copy_move_nth_to_head(all_pathkeys,
+												   foreach_current_index(l));
 		else
 			outerkeys = all_pathkeys;	/* no work at first one... */
 
diff --git a/src/backend/replication/logical/applyparallelworker.c b/src/backend/replication/logical/applyparallelworker.c
index 4518683779..45935070d4 100644
--- a/src/backend/replication/logical/applyparallelworker.c
+++ b/src/backend/replication/logical/applyparallelworker.c
@@ -1473,7 +1473,7 @@ pa_stream_abort(LogicalRepStreamAbortData *abort_data)
 		 */
 		for (i = list_length(subxactlist) - 1; i >= 0; i--)
 		{
-			TransactionId xid_tmp = lfirst_xid(list_nth_cell(subxactlist, i));
+			TransactionId xid_tmp = list_nth_xid(subxactlist, i);
 
 			if (xid_tmp == subxid)
 			{
diff --git a/src/backend/utils/adt/ruleutils.c b/src/backend/utils/adt/ruleutils.c
index 461735e84f..c1231db8c8 100644
--- a/src/backend/utils/adt/ruleutils.c
+++ b/src/backend/utils/adt/ruleutils.c
@@ -5417,7 +5417,7 @@ get_query_def(Query *query, StringInfo buf, List *parentnamespace,
 	AcquireRewriteLocks(query, false, false);
 
 	context.buf = buf;
-	context.namespaces = lcons(&dpns, list_copy(parentnamespace));
+	context.namespaces = lcons_copy(&dpns, parentnamespace);
 	context.windowClause = NIL;
 	context.windowTList = NIL;
 	context.varprefix = (parentnamespace != NIL ||
diff --git a/src/include/nodes/pg_list.h b/src/include/nodes/pg_list.h
index 529a382d28..b8bcdec2ce 100644
--- a/src/include/nodes/pg_list.h
+++ b/src/include/nodes/pg_list.h
@@ -324,6 +324,17 @@ list_nth_oid(const List *list, int n)
 	return lfirst_oid(list_nth_cell(list, n));
 }
 
+/*
+ * Return the Xid value contained in the n'th element of the specified
+ * list.
+ */
+static inline TransactionId
+list_nth_xid(const List *list, int n)
+{
+	Assert(IsA(list, XidList));
+	return lfirst_xid(list_nth_cell(list, n));
+}
+
 #define list_nth_node(type,list,n)	castNode(type, list_nth(list, n))
 
 /*
@@ -558,6 +569,7 @@ extern List *list_make5_impl(NodeTag t, ListCell datum1, ListCell datum2,
 							 ListCell datum5);
 
 extern pg_nodiscard List *lappend(List *list, void *datum);
+extern pg_nodiscard List *lappend_copy(const List *list, void *datum);
 extern pg_nodiscard List *lappend_int(List *list, int datum);
 extern pg_nodiscard List *lappend_oid(List *list, Oid datum);
 extern pg_nodiscard List *lappend_xid(List *list, TransactionId datum);
@@ -567,6 +579,7 @@ extern pg_nodiscard List *list_insert_nth_int(List *list, int pos, int datum);
 extern pg_nodiscard List *list_insert_nth_oid(List *list, int pos, Oid datum);
 
 extern pg_nodiscard List *lcons(void *datum, List *list);
+extern pg_nodiscard List *lcons_copy(void *datum, const List *list);
 extern pg_nodiscard List *lcons_int(int datum, List *list);
 extern pg_nodiscard List *lcons_oid(Oid datum, List *list);
 
@@ -625,6 +638,7 @@ extern pg_nodiscard List *list_copy(const List *oldlist);
 extern pg_nodiscard List *list_copy_head(const List *oldlist, int len);
 extern pg_nodiscard List *list_copy_tail(const List *oldlist, int nskip);
 extern pg_nodiscard List *list_copy_deep(const List *oldlist);
+extern pg_nodiscard List *list_copy_move_nth_to_head(const List *oldlist, int n);
 
 typedef int (*list_sort_comparator) (const ListCell *a, const ListCell *b);
 extern void list_sort(List *list, list_sort_comparator cmp);
-- 
2.31.0