Introduce optimized routine for linear searches of arrays

Use SSE2 intrinsics to speed up the search, where available.  Otherwise,
use a simple 'for' loop.  The motivation to add this now is to speed up
XidInMVCCSnapshot(), which is the reason only unsigned 32-bit integer
arrays are optimized. Other types are left for future work, as is the
extension of this technique to non-x86 platforms.

Nathan Bossart

Reviewed by: Andres Freund, Bharath Rupireddy, Masahiko Sawada
Discussion: https://postgr.es/m/20220713170950.GA3116318%40nathanxps13

8 files changed, 112 insertions, 0 deletions

diff --git a/src/test/modules/Makefile b/src/test/modules/Makefile
index 9090226daa0..6c31c8707c2 100644
--- a/src/test/modules/Makefile
+++ b/src/test/modules/Makefile
@@ -19,6 +19,7 @@ SUBDIRS = \
 		  test_extensions \
 		  test_ginpostinglist \
 		  test_integerset \
+		  test_lfind \
 		  test_misc \
 		  test_oat_hooks \
 		  test_parser \
diff --git a/src/test/modules/test_lfind/.gitignore b/src/test/modules/test_lfind/.gitignore
new file mode 100644
index 00000000000..5dcb3ff9723
--- /dev/null
+++ b/src/test/modules/test_lfind/.gitignore
@@ -0,0 +1,4 @@
+# Generated subdirectories
+/log/
+/results/
+/tmp_check/
diff --git a/src/test/modules/test_lfind/Makefile b/src/test/modules/test_lfind/Makefile
new file mode 100644
index 00000000000..00ba56ff740
--- /dev/null
+++ b/src/test/modules/test_lfind/Makefile
@@ -0,0 +1,23 @@
+# src/test/modules/test_lfind/Makefile
+
+MODULE_big = test_lfind
+OBJS = \
+	$(WIN32RES) \
+	test_lfind.o
+PGFILEDESC = "test_lfind - test code for optimized linear search functions"
+
+EXTENSION = test_lfind
+DATA = test_lfind--1.0.sql
+
+REGRESS = test_lfind
+
+ifdef USE_PGXS
+PG_CONFIG = pg_config
+PGXS := $(shell $(PG_CONFIG) --pgxs)
+include $(PGXS)
+else
+subdir = src/test/modules/test_lfind
+top_builddir = ../../../..
+include $(top_builddir)/src/Makefile.global
+include $(top_srcdir)/contrib/contrib-global.mk
+endif
diff --git a/src/test/modules/test_lfind/expected/test_lfind.out b/src/test/modules/test_lfind/expected/test_lfind.out
new file mode 100644
index 00000000000..222c8fd7fff
--- /dev/null
+++ b/src/test/modules/test_lfind/expected/test_lfind.out
@@ -0,0 +1,12 @@
+CREATE EXTENSION test_lfind;
+--
+-- These tests don't produce any interesting output.  We're checking that
+-- the operations complete without crashing or hanging and that none of their
+-- internal sanity tests fail.
+--
+SELECT test_lfind();
+ test_lfind 
+------------
+ 
+(1 row)
+
diff --git a/src/test/modules/test_lfind/sql/test_lfind.sql b/src/test/modules/test_lfind/sql/test_lfind.sql
new file mode 100644
index 00000000000..899f1dd49bf
--- /dev/null
+++ b/src/test/modules/test_lfind/sql/test_lfind.sql
@@ -0,0 +1,8 @@
+CREATE EXTENSION test_lfind;
+
+--
+-- These tests don't produce any interesting output.  We're checking that
+-- the operations complete without crashing or hanging and that none of their
+-- internal sanity tests fail.
+--
+SELECT test_lfind();
diff --git a/src/test/modules/test_lfind/test_lfind--1.0.sql b/src/test/modules/test_lfind/test_lfind--1.0.sql
new file mode 100644
index 00000000000..d82ab0567ef
--- /dev/null
+++ b/src/test/modules/test_lfind/test_lfind--1.0.sql
@@ -0,0 +1,8 @@
+/* src/test/modules/test_lfind/test_lfind--1.0.sql */
+
+-- complain if script is sourced in psql, rather than via CREATE EXTENSION
+\echo Use "CREATE EXTENSION test_lfind" to load this file. \quit
+
+CREATE FUNCTION test_lfind()
+	RETURNS pg_catalog.void
+	AS 'MODULE_PATHNAME' LANGUAGE C;
diff --git a/src/test/modules/test_lfind/test_lfind.c b/src/test/modules/test_lfind/test_lfind.c
new file mode 100644
index 00000000000..a000746fb83
--- /dev/null
+++ b/src/test/modules/test_lfind/test_lfind.c
@@ -0,0 +1,52 @@
+/*--------------------------------------------------------------------------
+ *
+ * test_lfind.c
+ *		Test correctness of optimized linear search functions.
+ *
+ * Copyright (c) 2022, PostgreSQL Global Development Group
+ *
+ * IDENTIFICATION
+ *		src/test/modules/test_lfind/test_lfind.c
+ *
+ * -------------------------------------------------------------------------
+ */
+
+#include "postgres.h"
+
+#include "fmgr.h"
+#include "port/pg_lfind.h"
+
+PG_MODULE_MAGIC;
+
+PG_FUNCTION_INFO_V1(test_lfind);
+
+Datum
+test_lfind(PG_FUNCTION_ARGS)
+{
+#define TEST_ARRAY_SIZE 135
+	uint32		test_array[TEST_ARRAY_SIZE] = {0};
+
+	test_array[8] = 1;
+	test_array[64] = 2;
+	test_array[TEST_ARRAY_SIZE - 1] = 3;
+
+	if (pg_lfind32(1, test_array, 4))
+		elog(ERROR, "pg_lfind32() found nonexistent element");
+	if (!pg_lfind32(1, test_array, TEST_ARRAY_SIZE))
+		elog(ERROR, "pg_lfind32() did not find existing element");
+
+	if (pg_lfind32(2, test_array, 32))
+		elog(ERROR, "pg_lfind32() found nonexistent element");
+	if (!pg_lfind32(2, test_array, TEST_ARRAY_SIZE))
+		elog(ERROR, "pg_lfind32() did not find existing element");
+
+	if (pg_lfind32(3, test_array, 96))
+		elog(ERROR, "pg_lfind32() found nonexistent element");
+	if (!pg_lfind32(3, test_array, TEST_ARRAY_SIZE))
+		elog(ERROR, "pg_lfind32() did not find existing element");
+
+	if (pg_lfind32(4, test_array, TEST_ARRAY_SIZE))
+		elog(ERROR, "pg_lfind32() found nonexistent element");
+
+	PG_RETURN_VOID();
+}
diff --git a/src/test/modules/test_lfind/test_lfind.control b/src/test/modules/test_lfind/test_lfind.control
new file mode 100644
index 00000000000..d8b57dfca2d
--- /dev/null
+++ b/src/test/modules/test_lfind/test_lfind.control
@@ -0,0 +1,4 @@
+comment = 'Test code for optimized linear search functions'
+default_version = '1.0'
+module_pathname = '$libdir/test_lfind'
+relocatable = true