Add optimized functions for linear search within byte arrays

In similar vein to b6ef167564, add pg_lfind8() and pg_lfind8_le()
to search for bytes equal or less-than-or-equal to a given byte,
respectively. To abstract away platform details, add helper functions
and typedefs to simd.h.

John Naylor and Nathan Bossart, per suggestion from Andres Freund

Discussion: https://www.postgresql.org/message-id/CAFBsxsGzaaGLF%3DNuq61iRXTyspbO9rOjhSqFN%3DV6ozzmta5mXg%40mail.gmail.com

4 files changed, 125 insertions, 7 deletions

diff --git a/src/test/modules/test_lfind/expected/test_lfind.out b/src/test/modules/test_lfind/expected/test_lfind.out
index 222c8fd7fff..1d4b14e7032 100644
--- a/src/test/modules/test_lfind/expected/test_lfind.out
+++ b/src/test/modules/test_lfind/expected/test_lfind.out
@@ -4,9 +4,21 @@ CREATE EXTENSION test_lfind;
 -- the operations complete without crashing or hanging and that none of their
 -- internal sanity tests fail.
 --
-SELECT test_lfind();
- test_lfind 
-------------
+SELECT test_lfind8();
+ test_lfind8 
+-------------
+ 
+(1 row)
+
+SELECT test_lfind8_le();
+ test_lfind8_le 
+----------------
+ 
+(1 row)
+
+SELECT test_lfind32();
+ test_lfind32 
+--------------
  
 (1 row)
 
diff --git a/src/test/modules/test_lfind/sql/test_lfind.sql b/src/test/modules/test_lfind/sql/test_lfind.sql
index 899f1dd49bf..766c640831f 100644
--- a/src/test/modules/test_lfind/sql/test_lfind.sql
+++ b/src/test/modules/test_lfind/sql/test_lfind.sql
@@ -5,4 +5,6 @@ CREATE EXTENSION test_lfind;
 -- the operations complete without crashing or hanging and that none of their
 -- internal sanity tests fail.
 --
-SELECT test_lfind();
+SELECT test_lfind8();
+SELECT test_lfind8_le();
+SELECT test_lfind32();
diff --git a/src/test/modules/test_lfind/test_lfind--1.0.sql b/src/test/modules/test_lfind/test_lfind--1.0.sql
index d82ab0567ef..81801926ae8 100644
--- a/src/test/modules/test_lfind/test_lfind--1.0.sql
+++ b/src/test/modules/test_lfind/test_lfind--1.0.sql
@@ -3,6 +3,14 @@
 -- 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()
+CREATE FUNCTION test_lfind32()
+	RETURNS pg_catalog.void
+	AS 'MODULE_PATHNAME' LANGUAGE C;
+
+CREATE FUNCTION test_lfind8()
+	RETURNS pg_catalog.void
+	AS 'MODULE_PATHNAME' LANGUAGE C;
+
+CREATE FUNCTION test_lfind8_le()
 	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
index a000746fb83..82673d54c6e 100644
--- a/src/test/modules/test_lfind/test_lfind.c
+++ b/src/test/modules/test_lfind/test_lfind.c
@@ -16,12 +16,108 @@
 #include "fmgr.h"
 #include "port/pg_lfind.h"
 
+/*
+ * Convenience macros for testing both vector and scalar operations. The 2x
+ * factor is to make sure iteration works
+ */
+#define LEN_NO_TAIL(vectortype) (2 * sizeof(vectortype))
+#define LEN_WITH_TAIL(vectortype) (LEN_NO_TAIL(vectortype) + 3)
+
 PG_MODULE_MAGIC;
 
-PG_FUNCTION_INFO_V1(test_lfind);
+/* workhorse for test_lfind8 */
+static void
+test_lfind8_internal(uint8 key)
+{
+	uint8		charbuf[LEN_WITH_TAIL(Vector8)];
+	const int	len_no_tail = LEN_NO_TAIL(Vector8);
+	const int	len_with_tail = LEN_WITH_TAIL(Vector8);
+
+	memset(charbuf, 0xFF, len_with_tail);
+	/* search tail to test one-byte-at-a-time path */
+	charbuf[len_with_tail - 1] = key;
+	if (key > 0x00 && pg_lfind8(key - 1, charbuf, len_with_tail))
+		elog(ERROR, "pg_lfind8() found nonexistent element '0x%x'", key - 1);
+	if (key < 0xFF && !pg_lfind8(key, charbuf, len_with_tail))
+		elog(ERROR, "pg_lfind8() did not find existing element '0x%x'", key);
+	if (key < 0xFE && pg_lfind8(key + 1, charbuf, len_with_tail))
+		elog(ERROR, "pg_lfind8() found nonexistent element '0x%x'", key + 1);
+
+	memset(charbuf, 0xFF, len_with_tail);
+	/* search with vector operations */
+	charbuf[len_no_tail - 1] = key;
+	if (key > 0x00 && pg_lfind8(key - 1, charbuf, len_no_tail))
+		elog(ERROR, "pg_lfind8() found nonexistent element '0x%x'", key - 1);
+	if (key < 0xFF && !pg_lfind8(key, charbuf, len_no_tail))
+		elog(ERROR, "pg_lfind8() did not find existing element '0x%x'", key);
+	if (key < 0xFE && pg_lfind8(key + 1, charbuf, len_no_tail))
+		elog(ERROR, "pg_lfind8() found nonexistent element '0x%x'", key + 1);
+}
+
+PG_FUNCTION_INFO_V1(test_lfind8);
+Datum
+test_lfind8(PG_FUNCTION_ARGS)
+{
+	test_lfind8_internal(0);
+	test_lfind8_internal(1);
+	test_lfind8_internal(0x7F);
+	test_lfind8_internal(0x80);
+	test_lfind8_internal(0x81);
+	test_lfind8_internal(0xFD);
+	test_lfind8_internal(0xFE);
+	test_lfind8_internal(0xFF);
+
+	PG_RETURN_VOID();
+}
+
+/* workhorse for test_lfind8_le */
+static void
+test_lfind8_le_internal(uint8 key)
+{
+	uint8		charbuf[LEN_WITH_TAIL(Vector8)];
+	const int	len_no_tail = LEN_NO_TAIL(Vector8);
+	const int	len_with_tail = LEN_WITH_TAIL(Vector8);
+
+	memset(charbuf, 0xFF, len_with_tail);
+	/* search tail to test one-byte-at-a-time path */
+	charbuf[len_with_tail - 1] = key;
+	if (key > 0x00 && pg_lfind8_le(key - 1, charbuf, len_with_tail))
+		elog(ERROR, "pg_lfind8_le() found nonexistent element <= '0x%x'", key - 1);
+	if (key < 0xFF && !pg_lfind8_le(key, charbuf, len_with_tail))
+		elog(ERROR, "pg_lfind8_le() did not find existing element <= '0x%x'", key);
+	if (key < 0xFE && !pg_lfind8_le(key + 1, charbuf, len_with_tail))
+		elog(ERROR, "pg_lfind8_le() did not find existing element <= '0x%x'", key + 1);
+
+	memset(charbuf, 0xFF, len_with_tail);
+	/* search with vector operations */
+	charbuf[len_no_tail - 1] = key;
+	if (key > 0x00 && pg_lfind8_le(key - 1, charbuf, len_no_tail))
+		elog(ERROR, "pg_lfind8_le() found nonexistent element <= '0x%x'", key - 1);
+	if (key < 0xFF && !pg_lfind8_le(key, charbuf, len_no_tail))
+		elog(ERROR, "pg_lfind8_le() did not find existing element <= '0x%x'", key);
+	if (key < 0xFE && !pg_lfind8_le(key + 1, charbuf, len_no_tail))
+		elog(ERROR, "pg_lfind8_le() did not find existing element <= '0x%x'", key + 1);
+}
+
+PG_FUNCTION_INFO_V1(test_lfind8_le);
+Datum
+test_lfind8_le(PG_FUNCTION_ARGS)
+{
+	test_lfind8_le_internal(0);
+	test_lfind8_le_internal(1);
+	test_lfind8_le_internal(0x7F);
+	test_lfind8_le_internal(0x80);
+	test_lfind8_le_internal(0x81);
+	test_lfind8_le_internal(0xFD);
+	test_lfind8_le_internal(0xFE);
+	test_lfind8_le_internal(0xFF);
+
+	PG_RETURN_VOID();
+}
 
+PG_FUNCTION_INFO_V1(test_lfind32);
 Datum
-test_lfind(PG_FUNCTION_ARGS)
+test_lfind32(PG_FUNCTION_ARGS)
 {
 #define TEST_ARRAY_SIZE 135
 	uint32		test_array[TEST_ARRAY_SIZE] = {0};