PostgreSQL Uses SIMD to Scan Strings Faster

Every string-scanning loop in every database has the same shape: look at one byte, decide something about it, advance. It is the shape we all write because it is obviously correct and obviously portable. It is also, on a modern CPU, about as slow as code can be.

The reason is not that the work is hard. Comparing a byte to '\n' is about as cheap as an operation gets. The reason is that the loop is latency-bound and branch-bound: the processor must fetch the next byte, compare it, and decide whether to keep going, and it cannot start fetching the byte after that until the branch resolves. A well-predicted branch hides some of that, but a mispredicted one costs fifteen or twenty cycles, and the loop-carried dependency — the pointer advancing by one — means each iteration waits for the previous one to resolve.

A SIMD compare changes the arithmetic. Instead of “is this byte a newline?” asked sixteen times, you ask “which of these sixteen bytes is a newline?” once. One instruction, sixteen bytes, one branch instead of sixteen.

PostgreSQL has been doing this quietly for years, and version 20devel (commit e75fcc9867f) has quite a lot of it. This is a tour of the abstraction it built, the places it is used, and the places it is deliberately not used.

The abstraction: `port/simd.h`

PostgreSQL does not use compiler intrinsics directly at the call sites. Instead, there is exactly one header that knows about SSE2 and NEON, and everybody else calls through it.

c
// src/include/port/simd.h
#if defined(USE_SSE2)
/*
 * We use emmintrin.h rather than the comprehensive header immintrin.h in
 * order to exclude extensions beyond SSE2. This is because MSVC, at least,
 * will allow the use of intrinsics that haven't been enabled at compile
 * time.
 */
#include <emmintrin.h>
typedef __m128i Vector8;
typedef __m128i Vector32;

#elif defined(USE_NEON)
#include <arm_neon.h>
typedef uint8x16_t Vector8;
typedef uint32x4_t Vector32;

#else
/*
 * If no SIMD instructions are available, we can in some cases emulate vector
 * operations using bitwise operations on unsigned integers.  Note that many
 * of the functions in this file presently do not have non-SIMD
 * implementations.  In particular, none of the functions involving Vector32
 * are implemented without SIMD since it's likely not worthwhile to represent
 * two 32-bit integers using a uint64.
 */
#define USE_NO_SIMD
typedef uint64 Vector8;
#endif

The whole design fits in one typedef. Vector8 is a vector of 8-bit elements — sixteen of them on x86-64 with SSE2, sixteen of them on AArch64 with NEON, and eight of them in the portable fallback, because there the vector is a uint64. Vector32 is the 32-bit analogue: four elements on x86, four on ARM, and no implementation at all in the fallback case.

Where do the two macros come from? src/include/c.h:

c
// src/include/c.h
/*
 * SSE2 instructions are part of the spec for the 64-bit x86 ISA. We assume
 * that compilers targeting this architecture understand SSE2 intrinsics.
 */
#if defined(__x86_64__)
#define USE_SSE2

#else							/* ! x86_64 */

/*
 * In "universal" macOS builds, it's possible for AVX-related symbols to
 * get defined if the build host is x86_64, but we mustn't try to build
 * that code when cross-compiling to aarch64.
 */
#undef USE_AVX2_WITH_RUNTIME_CHECK
#undef USE_AVX512_CRC32C_WITH_RUNTIME_CHECK
#undef USE_AVX512_POPCNT_WITH_RUNTIME_CHECK

/*
 * We use the Neon instructions if the compiler provides access to them (as
 * indicated by __ARM_NEON) and we are on aarch64.  While Neon support is
 * technically optional for aarch64, it appears that all available 64-bit
 * hardware does have it.  Neon exists in some 32-bit hardware too, but we
 * could not realistically use it there without a run-time check, which seems
 * not worth the trouble for now.
 */
#if defined(__aarch64__) && defined(__ARM_NEON)
#define USE_NEON
#endif
#endif							/* x86_64 */

SSE2 is part of the 64-bit x86 ISA baseline, so it is unconditional there. NEON is technically optional on AArch64 but effectively universal, and it cannot be runtime-detected cheaply enough to be worth it.

Why write an abstraction at all?

The obvious objection is: why not just call _mm_cmpeq_epi8() where you need it? Three reasons, all visible in the code.

First, portability. Every consumer would otherwise need #ifdef scaffolding for x86, ARM, and everything else. With one header, the #ifdef lives in exactly one place, and consumers are written once.

Second, and more subtle: the fallback has to exist and be correct. A build for a platform with no SIMD at all must still produce correct results. If SIMD is sprinkled through the call sites, every call site needs a scalar version too, and the two versions will drift apart. Here the fallback is expressed in terms of the same small set of primitives — vector8_broadcast, vector8_or, vector8_has_le — and the higher-level algorithms in encode.c, json.c and copyfromparse.c are guarded so that they simply do not run at all when USE_NO_SIMD is defined.

Third, the abstraction lets PostgreSQL pick the right width. A Vector8 is 16 bytes on a machine with SIMD and 8 bytes without, and every consumer is written in terms of sizeof(Vector8), so the same source produces a 16-byte-at-a-time loop or an 8-byte-at-a-time loop with no source changes. You can see this in the loop bounds all over the tree: tail_idx = nelem & ~(sizeof(Vector8) - 1).

There is also a deliberate decision about which intrinsics header to include. From the top of the file:

We use emmintrin.h rather than the comprehensive header immintrin.h in order to exclude extensions beyond SSE2. This is because MSVC, at least, will allow the use of intrinsics that haven’t been enabled at compile time.

That is a subtle and important point: if you include <immintrin.h>, the compiler will happily let you write _mm256_loadu_si256() in a binary compiled for a pre-AVX2 machine, and it will emit an illegal instruction. Keeping the door closed at the header level means the mistake cannot be made.

The primitive set

The primitives are deliberately small. Here is the load:

c
// src/include/port/simd.h
/*
 * Load a chunk of memory into the given vector.
 */
static inline void
vector8_load(Vector8 *v, const uint8 *s)
{
#if defined(USE_SSE2)
	*v = _mm_loadu_si128((const __m128i *) s);
#elif defined(USE_NEON)
	*v = vld1q_u8(s);
#else
	memcpy(v, s, sizeof(Vector8));
#endif
}

Note _mm_loadu_si128 — the unaligned load. PostgreSQL scans bytes in StringInfo buffers and page buffers, and those are not aligned to 16 bytes in any interesting way, so an aligned load would fault.

The broadcast is the workhorse: it manufactures a vector with the same byte in every lane, so that a comparison against it is a comparison against a scalar.

c
// src/include/port/simd.h
/*
 * Create a vector with all elements set to the same value.
 */
static inline Vector8
vector8_broadcast(const uint8 c)
{
#if defined(USE_SSE2)
	return _mm_set1_epi8(c);
#elif defined(USE_NEON)
	return vdupq_n_u8(c);
#else
	return ~UINT64CONST(0) / 0xFF * c;
#endif
}

The fallback version is cute and worth understanding: ~UINT64CONST(0) / 0xFF is 0x0101010101010101, and multiplying it by c replicates c into all eight bytes of the word. That is the classic SWAR broadcast trick.

The comparison primitive returns a vector, not a boolean, and that is important:

c
// src/include/port/simd.h
/*
 * Return a vector with all bits set in each lane where the corresponding
 * lanes in the inputs are equal.
 */
#ifndef USE_NO_SIMD
static inline Vector8
vector8_eq(const Vector8 v1, const Vector8 v2)
{
#ifdef USE_SSE2
	return _mm_cmpeq_epi8(v1, v2);
#elif defined(USE_NEON)
	return vceqq_u8(v1, v2);
#endif
}
#endif							/* ! USE_NO_SIMD */

vector8_eq produces a vector whose lanes are all-ones where the two inputs matched and all-zeros where they did not. That shape is what makes everything else possible: you can or several such vectors together to ask “does any of these four characters appear anywhere in these sixteen bytes?”, and you can and the high bit out of one vector to mask another.

The high-bit machinery is the crux of the whole design:

c
// src/include/port/simd.h
/*
 * Return true if the high bit of any element is set
 */
static inline bool
vector8_is_highbit_set(const Vector8 v)
{
#ifdef USE_SSE2
	return _mm_movemask_epi8(v) != 0;
#elif defined(USE_NEON)
	return vmaxvq_u8(v) > 0x7F;
#else
	return v & vector8_broadcast(0x80);
#endif
}

and

c
// src/include/port/simd.h
/*
 * Return a bitmask formed from the high-bit of each element.
 */
#ifndef USE_NO_SIMD
static inline uint32
vector8_highbit_mask(const Vector8 v)
{
#ifdef USE_SSE2
	return (uint32) _mm_movemask_epi8(v);
#elif defined(USE_NEON)
	/*
	 * Note: It would be faster to use vget_lane_u64 and vshrn_n_u16, but that
	 * returns a uint64, making it inconvenient to combine mask values from
	 * multiple vectors.
	 */
	static const uint8 mask[16] = {
		1 << 0, 1 << 1, 1 << 2, 1 << 3,
		1 << 4, 1 << 5, 1 << 6, 1 << 7,
		1 << 0, 1 << 1, 1 << 2, 1 << 3,
		1 << 4, 1 << 5, 1 << 6, 1 << 7,
	};

	uint8x16_t	masked = vandq_u8(vld1q_u8(mask), (uint8x16_t) vshrq_n_s8((int8x16_t) v, 7));
	uint8x16_t	maskedhi = vextq_u8(masked, masked, 8);

	return (uint32) vaddvq_u16((uint16x8_t) vzip1q_u8(masked, maskedhi));
#endif
}
#endif							/* ! USE_NO_SIMD */

vector8_is_highbit_set asks “is there any interesting byte in this vector?” by asking “does any lane have its top bit set?”. On x86 that is literally one instruction — pmovmskb — which produces a 16-bit mask of the top bits and then compares it to zero.

vector8_highbit_mask asks the more detailed question “which lanes have their top bit set?”, and returns the answer as a 16-bit bitmap, with bit i corresponding to byte i. That bitmap is what lets the COPY parser say “the special character I am looking for is at offset 7 in this chunk” without a second pass.

On ARM there is no pmovmskb, so the NEON implementation has to build the mask by hand, and the comment explains why it is done that way:

Note: It would be faster to use vget_lane_u64 and vshrn_n_u16, but that returns a uint64, making it inconvenient to combine mask values from multiple vectors.

The remaining primitives are ordinary vector operations — logical or, add, shift, and the interleave that the hex encoder depends on:

c
// src/include/port/simd.h
/*
 * Interleave elements of low halves (e.g., for SSE2, bits 0-63) of given
 * vectors.  Bytes 0, 2, 4, etc. use v1, and bytes 1, 3, 5, etc. use v2.
 */
#ifndef USE_NO_SIMD
static inline Vector8
vector8_interleave_low(const Vector8 v1, const Vector8 v2)
{
#ifdef USE_SSE2
	return _mm_unpacklo_epi8(v1, v2);
#elif defined(USE_NEON)
	return vzip1q_u8(v1, v2);
#endif
}
#endif							/* ! USE_NO_SIMD */

/*
 * Interleave elements of high halves (e.g., for SSE2, bits 64-127) of given
 * vectors.  Bytes 0, 2, 4, etc. use v1, and bytes 1, 3, 5, etc. use v2.
 */
#ifndef USE_NO_SIMD
static inline Vector8
vector8_interleave_high(const Vector8 v1, const Vector8 v2)
{
#ifdef USE_SSE2
	return _mm_unpackhi_epi8(v1, v2);
#elif defined(USE_NEON)
	return vzip2q_u8(v1, v2);
#endif
}

c
// src/include/port/simd.h
/*
 * Unsigned shift left of each 32-bit element in the vector by "i" bits.
 */
#ifndef USE_NO_SIMD
static inline Vector8
vector8_shift_left(const Vector8 v1, int i)
{
#ifdef USE_SSE2
	return _mm_slli_epi32(v1, i);
#elif defined(USE_NEON)
	return (Vector8) vshlq_u32((Vector32) v1, vdupq_n_s32(i));
#endif
}
#endif							/* ! USE_NO_SIMD */

/*
 * Unsigned shift right of each 32-bit element in the vector by "i" bits.
 */
#ifndef USE_NO_SIMD
static inline Vector8
vector8_shift_right(const Vector8 v1, int i)
{
#ifdef USE_SSE2
	return _mm_srli_epi32(v1, i);
#elif defined(USE_NEON)
	/* negative shift count means right shift */
	return (Vector8) vshlq_u32((Vector32) v1, vdupq_n_s32(-i));
#endif
}
#endif							/* ! USE_NO_SIMD */

The fallback is not a stub

Here is the part that makes the abstraction honest. When SIMD is not available, Vector8 is a uint64, and the primitives that can be expressed as integer arithmetic are:

c
// src/include/port/simd.h
/*
 * Return true if any elements in the vector are less than or equal to the
 * given scalar.
 */
static inline bool
vector8_has_le(const Vector8 v, const uint8 c)
{
	bool		result = false;
#ifdef USE_SSE2
	Vector8		umin;
	Vector8		cmpe;
#endif

	/* pre-compute the result for assert checking */
#ifdef USE_ASSERT_CHECKING
	bool		assert_result = false;

	for (Size i = 0; i < sizeof(Vector8); i++)
	{
		if (((const uint8 *) &v)[i] <= c)
		{
			assert_result = true;
			break;
		}
	}
#endif							/* USE_ASSERT_CHECKING */

#if defined(USE_NO_SIMD)

	/*
	 * To find bytes <= c, we can use bitwise operations to find bytes < c+1,
	 * but it only works if c+1 <= 128 and if the highest bit in v is not set.
	 * Adapted from
	 * https://graphics.stanford.edu/~seander/bithacks.html#HasLessInWord
	 */
	if ((int64) v >= 0 && c < 0x80)
		result = (v - vector8_broadcast(c + 1)) & ~v & vector8_broadcast(0x80);
	else
	{
		/* one byte at a time */
		for (Size i = 0; i < sizeof(Vector8); i++)
		{
			if (((const uint8 *) &v)[i] <= c)
			{
				result = true;
				break;
			}
		}
	}
#elif defined(USE_SSE2)
	umin = vector8_min(v, vector8_broadcast(c));
	cmpe = vector8_eq(umin, v);
	result = vector8_is_highbit_set(cmpe);
#elif defined(USE_NEON)
	result = vminvq_u8(v) <= c;
#endif

	Assert(assert_result == result);
	return result;
}

The USE_NO_SIMD branch of vector8_has_le is a textbook SWAR trick — find bytes less than a threshold without a loop, using the observation that subtracting from a word can only borrow within a byte if that byte’s high bit was clear. The comment even cites the source:

Adapted from https://graphics.stanford.edu/~seander/bithacks.html#HasLessInWord

and it carefully guards the precondition:

c
	if ((int64) v >= 0 && c < 0x80)
		result = (v - vector8_broadcast(c + 1)) & ~v & vector8_broadcast(0x80);
	else
	{
		/* one byte at a time */

If any byte in the word has its high bit set, the borrow can propagate across byte boundaries and the trick is invalid, so it falls back to a byte-at-a-time loop. That is correct, just slower — and this is the “slow path” that only ever executes on machines without SIMD.

Note also the USE_ASSERT_CHECKING blocks. Every one of these functions computes the answer a second time, the naive way, and asserts that the two agree:

c
// src/include/port/simd.h
/*
 * Return true if any elements in the vector are equal to the given scalar.
 */
static inline bool
vector8_has(const Vector8 v, const uint8 c)
{
	bool		result;

	/* pre-compute the result for assert checking */
#ifdef USE_ASSERT_CHECKING
	bool		assert_result = false;

	for (Size i = 0; i < sizeof(Vector8); i++)
	{
		if (((const uint8 *) &v)[i] == c)
		{
			assert_result = true;
			break;
		}
	}
#endif							/* USE_ASSERT_CHECKING */

#if defined(USE_NO_SIMD)
	/* any bytes in v equal to c will evaluate to zero via XOR */
	result = vector8_has_zero(v ^ vector8_broadcast(c));
#else
	result = vector8_is_highbit_set(vector8_eq(v, vector8_broadcast(c)));
#endif

	Assert(assert_result == result);
	return result;
}

That is a very cheap way to keep an entire class of bit-twiddling bug from ever shipping: in a debug build, every SIMD answer is cross-checked against the obvious implementation.

Consumer one: `COPY FROM` text and CSV

The biggest SIMD win in PostgreSQL is in the COPY parser, because COPY is the one place where PostgreSQL spends real time moving bytes it does not care about. A 100 GB CSV file is 100 GB of bytes, and the parser needs exactly three things from most of them: nothing.

CopyReadLineText() is the scalar loop. CopyReadLineTextSIMDHelper() is the vector version. Here is the whole helper:

c
// src/backend/commands/copyfromparse.c
#ifndef USE_NO_SIMD
/*
 * Helper function for CopyReadLineText() that uses SIMD instructions to scan
 * the input buffer for special characters.  This can be much faster.
 *
 * Note that we disable SIMD for the remainder of the COPY FROM command upon
 * encountering a special character (except for end-of-line characters) or a
 * short line.  This is perhaps too conservative, but it should help avoid
 * regressions.  It could probably be made more lenient in the future via
 * fine-tuned heuristics.
 */
static bool
CopyReadLineTextSIMDHelper(CopyFromState cstate, bool is_csv,
						   bool *hit_eof_p, int *input_buf_ptr_p)
{
	char	   *copy_input_buf;
	int			input_buf_ptr;
	int			copy_buf_len;
	bool		unique_esc_char;	/* for csv, do quote/esc chars differ? */
	bool		first = true;
	bool		result = false;
	const Vector8 nl_vec = vector8_broadcast('\n');
	const Vector8 cr_vec = vector8_broadcast('\r');
	Vector8		bs_or_quote_vec;	/* '\' for text, quote for csv */
	Vector8		esc_vec;		/* only for csv */

	if (is_csv)
	{
		char		quote = cstate->opts.quote[0];
		char		esc = cstate->opts.escape[0];

		bs_or_quote_vec = vector8_broadcast(quote);
		esc_vec = vector8_broadcast(esc);
		unique_esc_char = (quote != esc);
	}
	else
	{
		bs_or_quote_vec = vector8_broadcast('\\');
		unique_esc_char = false;
	}

	/*
	 * For a little extra speed within the loop, we copy some state members
	 * into local variables. Note that we need to use a separate local
	 * variable for input_buf_ptr so that the REFILL_LINEBUF macro works.  We
	 * copy its value into the input_buf_ptr_p argument before returning.
	 */
	copy_input_buf = cstate->input_buf;
	input_buf_ptr = cstate->input_buf_index;
	copy_buf_len = cstate->input_buf_len;

	/*
	 * See the corresponding loop in CopyReadLineText() for more information
	 * about the purpose of this loop.  This one does the same thing using
	 * SIMD instructions, although we are quick to bail out to the scalar path
	 * if we encounter a special character.
	 */
	for (;;)
	{
		Vector8		chunk;
		Vector8		match;

		/* Load more data if needed. */
		if (copy_buf_len - input_buf_ptr < sizeof(Vector8))
		{
			REFILL_LINEBUF;

			CopyLoadInputBuf(cstate, true);
			/* update our local variables */
			*hit_eof_p = cstate->input_reached_eof;
			input_buf_ptr = cstate->input_buf_index;
			copy_buf_len = cstate->input_buf_len;

			/*
			 * If we are completely out of data, break out of the loop,
			 * reporting EOF.
			 */
			if (INPUT_BUF_BYTES(cstate) <= 0)
			{
				result = true;
				break;
			}
		}

		/*
		 * If we still don't have enough data for the SIMD path, fall back to
		 * the scalar code.  Note that this doesn't necessarily mean we
		 * encountered a short line, so we leave cstate->simd_enabled set to
		 * true.
		 */
		if (copy_buf_len - input_buf_ptr < sizeof(Vector8))
			break;

		/*
		 * If we made it here, we have at least enough data to fit in a
		 * Vector8, so we can use SIMD instructions to scan for special
		 * characters.
		 */
		vector8_load(&chunk, (const uint8 *) &copy_input_buf[input_buf_ptr]);

		/*
		 * Check for \n, \r, \\ (for text), quotes (for csv), and escapes (for
		 * csv, if different from quotes).
		 */
		match = vector8_eq(chunk, nl_vec);
		match = vector8_or(match, vector8_eq(chunk, cr_vec));
		match = vector8_or(match, vector8_eq(chunk, bs_or_quote_vec));
		if (unique_esc_char)
			match = vector8_or(match, vector8_eq(chunk, esc_vec));

		/*
		 * If we found a special character, advance to it and hand off to the
		 * scalar path.  Except for end-of-line characters, we also disable
		 * SIMD processing for the remainder of the COPY FROM command.
		 */
		if (vector8_is_highbit_set(match))
		{
			uint32		mask;
			char		c;

			mask = vector8_highbit_mask(match);
			input_buf_ptr += pg_rightmost_one_pos32(mask);

			/*
			 * Don't disable SIMD if we found \n or \r, else we'd stop using
			 * SIMD instructions after the first line.  As an exception, we do
			 * disable it if this is the first vector we processed, as that
			 * means the line is too short for SIMD.
			 */
			c = copy_input_buf[input_buf_ptr];
			if (first || (c != '\n' && c != '\r'))
				cstate->simd_enabled = false;

			break;
		}

		/* That chunk was clear of special characters, so we can skip it. */
		input_buf_ptr += sizeof(Vector8);
		first = false;
	}

	*input_buf_ptr_p = input_buf_ptr;
	return result;
}
#endif							/* ! USE_NO_SIMD */

The core loop is short and is the entire idea of this article in nine lines:

c
		vector8_load(&chunk, (const uint8 *) &copy_input_buf[input_buf_ptr]);

		/*
		 * Check for \n, \r, \\ (for text), quotes (for csv), and escapes (for
		 * csv, if different from quotes).
		 */
		match = vector8_eq(chunk, nl_vec);
		match = vector8_or(match, vector8_eq(chunk, cr_vec));
		match = vector8_or(match, vector8_eq(chunk, bs_or_quote_vec));
		if (unique_esc_char)
			match = vector8_or(match, vector8_eq(chunk, esc_vec));

		/*
		 * If we found a special character, advance to it and hand off to the
		 * scalar path.  Except for end-of-line characters, we also disable
		 * SIMD processing for the remainder of the COPY FROM command.
		 */
		if (vector8_is_highbit_set(match))
		{
			uint32		mask;
			char		c;

			mask = vector8_highbit_mask(match);
			input_buf_ptr += pg_rightmost_one_pos32(mask);

Four compares, three ORs, one test. If the chunk is clean — no newline, no carriage return, no backslash, no quote, no escape — we advance the pointer by sixteen bytes and go around again. If it is not clean, we extract the bitmap of where the special bytes were and jump straight to the first one.

pg_rightmost_one_pos32() is the low bit scan:

c
// src/include/port/pg_bitutils.h
/*
 * pg_rightmost_one_pos32
 *		Returns the position of the least significant set bit in "word",
 *		measured from the least significant bit.  word must not be 0.
 */
static inline int
pg_rightmost_one_pos32(uint32 word)
{
#ifdef HAVE__BUILTIN_CTZ
	Assert(word != 0);

	return __builtin_ctz(word);
#elif defined(_MSC_VER)

The name is a historical misnomer — it returns the position of the least significant set bit, i.e. the first matching byte in memory order. Which is exactly what you want: the first special character is the one that ends the fast scan.

The conservatism, and why it exists

The interesting design decision is not the vector loop. It is what happens afterwards. Here is the header comment:

Note that we disable SIMD for the remainder of the COPY FROM command upon encountering a special character (except for end-of-line characters) or a short line. This is perhaps too conservative, but it should help avoid regressions. It could probably be made more lenient in the future via fine-tuned heuristics.

And the code:

c
			/*
			 * Don't disable SIMD if we found \n or \r, else we'd stop using
			 * SIMD instructions after the first line.  As an exception, we do
			 * disable it if this is the first vector we processed, as that
			 * means the line is too short for SIMD.
			 */
			c = copy_input_buf[input_buf_ptr];
			if (first || (c != '\n' && c != '\r'))
				cstate->simd_enabled = false;

			break;

So the policy is:

What was found	Effect
A newline or carriage return	SIMD stays enabled for the rest of the COPY
A backslash, quote, or escape	SIMD is disabled for the rest of the COPY
A special character in the first 16-byte chunk of the line	SIMD is disabled for the rest of the COPY

The reasoning is a bet about workload shape. A CSV file of long lines with no embedded quotes is the best case for SIMD, and it stays SIMD for the whole file. A file where every line has a quoted field containing a comma — that is, most real CSVs — hits a quote on the first line and permanently drops to the scalar path. The alternative would be to handle quoted regions in the vector path too, but the CSV quoting state machine (interleaved quotes and escapes, quotes that may or may not be escaped) is genuinely hard to vectorize, and the payoff depends on the data.

The first case is subtler: if the first chunk of a line contains a special character, the line is short enough that the vector path cannot possibly pay for itself — you spent a vector load and a compare to find a character in the first sixteen bytes. So the SIMD path disables itself.

The switch is a single boolean on the COPY state:

c
// src/include/commands/copyfrom_internal.h
	int		   *defmap;			/* array of default att numbers related to
								 * missing att */
	ExprState **defexprs;		/* array of default att expressions for all
								 * att */
	bool	   *defaults;		/* if DEFAULT marker was found for
								 * corresponding att */
	bool		simd_enabled;	/* use SIMD to scan for special chars? */

set to true when the COPY starts:

c
// src/backend/commands/copyfrom.c
	cstate->cur_relname = RelationGetRelationName(cstate->rel);
	cstate->cur_lineno = 0;
	cstate->cur_attname = NULL;
	cstate->cur_attval = NULL;
	cstate->relname_only = false;
	cstate->simd_enabled = true;

and consulted at the top of every line, so that the vector helper runs before the scalar loop and the scalar loop resumes at the exact byte the vector helper stopped at.

Note that the SIMD helper only ever handles the clean prefix of a line. When it finds a special character it stops and returns, and the scalar loop takes over from that exact byte. The two paths interleave per line, not per command.

Consumer two: hex encoding

hex_encode() is used by bytea output (src/backend/utils/adt/bytea.c) and by the backup manifest writer (src/backend/backup/backup_manifest.c). The scalar version is a lookup table:

c
// src/backend/utils/adt/encode.c
/*
 * The hex expansion of each possible byte value (two chars per value).
 */
static const char hextbl[512] =
"000102030405060708090a0b0c0d0e0f"
"101112131415161718191a1b1c1d1e1f"
"202122232425262728292a2b2c2d2e2f"
"303132333435363738393a3b3c3d3e3f"
"404142434445464748494a4b4c4d4e4f"
"505152535455565758595a5b5c5d5e5f"
"606162636465666768696a6b6c6d6e6f"
"707172737475767778797a7b7c7d7e7f"
"808182838485868788898a8b8c8d8e8f"
"909192939495969798999a9b9c9d9e9f"
"a0a1a2a3a4a5a6a7a8a9aaabacadaeaf"
"b0b1b2b3b4b5b6b7b8b9babbbcbdbebf"
"c0c1c2c3c4c5c6c7c8c9cacbcccdcecf"
"d0d1d2d3d4d5d6d7d8d9dadbdcdddedf"
"e0e1e2e3e4e5e6e7e8e9eaebecedeeef"
"f0f1f2f3f4f5f6f7f8f9fafbfcfdfeff";

static const int8 hexlookup[128] = {
	-1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1,
	-1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1,
	-1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1,
	0, 1, 2, 3, 4, 5, 6, 7, 8, 9, -1, -1, -1, -1, -1, -1,
	-1, 10, 11, 12, 13, 14, 15, -1, -1, -1, -1, -1, -1, -1, -1, -1,
	-1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1,
	-1, 10, 11, 12, 13, 14, 15, -1, -1, -1, -1, -1, -1, -1, -1, -1,
	-1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1,
};

static inline uint64
hex_encode_scalar(const char *src, size_t len, char *dst)
{
	const char *end = src + len;

	while (src < end)
	{
		unsigned char usrc = *((const unsigned char *) src);

		memcpy(dst, &hextbl[2 * usrc], 2);
		src++;
		dst += 2;
	}
	return (uint64) len * 2;
}

hextbl is 512 bytes — two characters for every possible byte value — and the scalar loop does a memcpy of two bytes per input byte. That is a perfectly reasonable implementation, but it does one memory load and one branch per byte.

The SIMD version computes the hex digits arithmetically instead, with no table at all:

c
// src/backend/utils/adt/encode.c
uint64
hex_encode(const char *src, size_t len, char *dst)
{
#ifdef USE_NO_SIMD
	return hex_encode_scalar(src, len, dst);
#else
	const uint64 tail_idx = len & ~(sizeof(Vector8) - 1);
	uint64		i;

	/*
	 * This splits the high and low nibbles of each byte into separate
	 * vectors, adds the vectors to a mask that converts the nibbles to their
	 * equivalent ASCII bytes, and interleaves those bytes back together to
	 * form the final hex-encoded string.
	 */
	for (i = 0; i < tail_idx; i += sizeof(Vector8))
	{
		Vector8		srcv;
		Vector8		lo;
		Vector8		hi;
		Vector8		mask;

		vector8_load(&srcv, (const uint8 *) &src[i]);

		lo = vector8_and(srcv, vector8_broadcast(0x0f));
		mask = vector8_gt(lo, vector8_broadcast(0x9));
		mask = vector8_and(mask, vector8_broadcast('a' - '0' - 10));
		mask = vector8_add(mask, vector8_broadcast('0'));
		lo = vector8_add(lo, mask);

		hi = vector8_and(srcv, vector8_broadcast(0xf0));
		hi = vector8_shift_right(hi, 4);
		mask = vector8_gt(hi, vector8_broadcast(0x9));
		mask = vector8_and(mask, vector8_broadcast('a' - '0' - 10));
		mask = vector8_add(mask, vector8_broadcast('0'));
		hi = vector8_add(hi, mask);

		vector8_store((uint8 *) &dst[i * 2],
					  vector8_interleave_low(hi, lo));
		vector8_store((uint8 *) &dst[i * 2 + sizeof(Vector8)],
					  vector8_interleave_high(hi, lo));
	}

	(void) hex_encode_scalar(src + i, len - i, dst + i * 2);

	return (uint64) len * 2;
#endif
}

Read the nibble arithmetic carefully, because it is the whole trick:

c
		lo = vector8_and(srcv, vector8_broadcast(0x0f));
		mask = vector8_gt(lo, vector8_broadcast(0x9));
		mask = vector8_and(mask, vector8_broadcast('a' - '0' - 10));
		mask = vector8_add(mask, vector8_broadcast('0'));
		lo = vector8_add(lo, mask);

'a' - '0' - 10 is 39. The mask is therefore all-ones for nibbles greater than 9 and all-zeros otherwise. Adding 39 to a nibble of 10..15 gives 49..54, plus the '0' (48) added next gives 97..102 — that is, 'a' through 'f'. For nibbles 0..9 the mask is zero and the nibble is simply offset by '0'. The high nibble is the same computation with a shift:

c
		hi = vector8_and(srcv, vector8_broadcast(0xf0));
		hi = vector8_shift_right(hi, 4);

and then the two nibble vectors are interleaved back into “high, low, high, low” order and stored:

c
		vector8_store((uint8 *) &dst[i * 2],
					  vector8_interleave_low(hi, lo));
		vector8_store((uint8 *) &dst[i * 2 + sizeof(Vector8)],
					  vector8_interleave_high(hi, lo));

Sixteen input bytes become thirty-two output bytes: the first sixteen output bytes are the low halves of the interleaves (input bytes 0-7), the next sixteen are the high halves (input bytes 8-15). The tail of the buffer — fewer than sixteen bytes — falls back to the table-driven scalar loop.

Hex decoding is the harder direction and equally clever. The scalar version uses a lookup table with a special case for whitespace:

c
// src/backend/utils/adt/encode.c
static inline bool
get_hex(const char *cp, char *out)
{
	unsigned char c = (unsigned char) *cp;
	int			res = -1;

	if (c < 127)
		res = hexlookup[c];

	*out = (char) res;

	return (res >= 0);
}

uint64
hex_decode(const char *src, size_t len, char *dst)
{
	return hex_decode_safe(src, len, dst, NULL);
}

static inline uint64
hex_decode_safe_scalar(const char *src, size_t len, char *dst, Node *escontext)
{
	const char *s,
			   *srcend;
	char		v1,
				v2,
			   *p;

	srcend = src + len;
	s = src;
	p = dst;
	while (s < srcend)
	{
		if (*s == ' ' || *s == '\n' || *s == '\t' || *s == '\r')
		{
			s++;
			continue;
		}
		if (!get_hex(s, &v1))
			ereturn(escontext, 0,
					(errcode(ERRCODE_INVALID_PARAMETER_VALUE),
					 errmsg("invalid hexadecimal digit: \"%.*s\"",
							pg_mblen_range(s, srcend), s)));
		s++;
		if (s >= srcend)
			ereturn(escontext, 0,
					(errcode(ERRCODE_INVALID_PARAMETER_VALUE),
					 errmsg("invalid hexadecimal data: odd number of digits")));
		if (!get_hex(s, &v2))
			ereturn(escontext, 0,
					(errcode(ERRCODE_INVALID_PARAMETER_VALUE),
					 errmsg("invalid hexadecimal digit: \"%.*s\"",
							pg_mblen_range(s, srcend), s)));
		s++;
		*p++ = (v1 << 4) | v2;
	}

	return p - dst;
}

The SIMD version computes nibble values by subtracting a per-character constant, and uses saturating subtraction so that invalid characters underflow to a recognizable value instead of wrapping:

c
// src/backend/utils/adt/encode.c
/*
 * This helper converts each byte to its binary-equivalent nibble by
 * subtraction and combines them to form the return bytes (separated by zero
 * bytes).  Returns false if any input bytes are outside the expected ranges of
 * ASCII values.  Otherwise, returns true.
 */
#ifndef USE_NO_SIMD
static inline bool
hex_decode_simd_helper(const Vector8 src, Vector8 *dst)
{
	Vector8		sub;
	Vector8		mask_hi = vector8_interleave_low(vector8_broadcast(0), vector8_broadcast(0x0f));
	Vector8		mask_lo = vector8_interleave_low(vector8_broadcast(0x0f), vector8_broadcast(0));
	Vector8		tmp;
	bool		ret;

	tmp = vector8_gt(vector8_broadcast('9' + 1), src);
	sub = vector8_and(tmp, vector8_broadcast('0'));

	tmp = vector8_gt(src, vector8_broadcast('A' - 1));
	tmp = vector8_and(tmp, vector8_broadcast('A' - 10));
	sub = vector8_add(sub, tmp);

	tmp = vector8_gt(src, vector8_broadcast('a' - 1));
	tmp = vector8_and(tmp, vector8_broadcast('a' - 'A'));
	sub = vector8_add(sub, tmp);

	*dst = vector8_issub(src, sub);
	ret = !vector8_has_ge(*dst, 0x10);

	tmp = vector8_and(*dst, mask_hi);
	tmp = vector8_shift_right(tmp, 8);
	*dst = vector8_and(*dst, mask_lo);
	*dst = vector8_shift_left(*dst, 4);
	*dst = vector8_or(*dst, tmp);
	return ret;
}
#endif							/* ! USE_NO_SIMD */

c
// src/backend/utils/adt/encode.c
uint64
hex_decode_safe(const char *src, size_t len, char *dst, Node *escontext)
{
#ifdef USE_NO_SIMD
	return hex_decode_safe_scalar(src, len, dst, escontext);
#else
	const uint64 tail_idx = len & ~(sizeof(Vector8) * 2 - 1);
	uint64		i;
	bool		success = true;

	/*
	 * We must process 2 vectors at a time since the output will be half the
	 * length of the input.
	 */
	for (i = 0; i < tail_idx; i += sizeof(Vector8) * 2)
	{
		Vector8		srcv;
		Vector8		dstv1;
		Vector8		dstv2;

		vector8_load(&srcv, (const uint8 *) &src[i]);
		success &= hex_decode_simd_helper(srcv, &dstv1);

		vector8_load(&srcv, (const uint8 *) &src[i + sizeof(Vector8)]);
		success &= hex_decode_simd_helper(srcv, &dstv2);

		vector8_store((uint8 *) &dst[i / 2], vector8_pack_16(dstv1, dstv2));
	}

	/*
	 * If something didn't look right in the vector path, try again in the
	 * scalar path so that we can handle it correctly.
	 */
	if (!success)
		i = 0;

	return i / 2 + hex_decode_safe_scalar(src + i, len - i, dst + i / 2, escontext);
#endif
}

Three things are worth noting here.

The validation is free. vector8_issub saturates at −128, so a character that is not a hex digit produces a value that is not in 0..15. The check !vector8_has_ge(*dst, 0x10) therefore validates all sixteen characters at once, as a side effect of the conversion.

Whitespace is not handled in the vector path. The scalar path skips ' ', '\n', '\t' and '\r'. The SIMD path has no idea what those are, so they fail the range check — and the fallback re-does the whole buffer from the beginning with the scalar code:

c
	if (!success)
		i = 0;

	return i / 2 + hex_decode_safe_scalar(src + i, len - i, dst + i / 2, escontext);

So a hex string containing whitespace is simply not accelerated. That is the right trade: whitespace in hex data is rare, and the correctness fallback is trivial to reason about.

The output is half the input length, so the loop consumes two vectors at a time and packs them with vector8_pack_16, which narrows sixteen 16-bit lanes down to sixteen bytes.

Consumer three: JSON escaping

escape_json_with_len() has to escape control characters, " and \\ in a string of arbitrary length. The naive implementation tests every byte against three conditions. The vector version searches sixteen bytes at a time for “anything needing special handling”:

c
// src/backend/utils/adt/json.c
/*
 * escape_json_with_len
 *		Produce a JSON string literal, properly escaping the possibly not
 *		NUL-terminated characters in 'str'.  'len' defines the number of bytes
 *		from 'str' to process.
 */
void
escape_json_with_len(StringInfo buf, const char *str, int len)
{
	int			vlen;

	Assert(len >= 0);

	/*
	 * Since we know the minimum length we'll need to append, let's just
	 * enlarge the buffer now rather than incrementally making more space when
	 * we run out.  Add two extra bytes for the enclosing quotes.
	 */
	enlargeStringInfo(buf, len + 2);

	/*
	 * Figure out how many bytes to process using SIMD.  Round 'len' down to
	 * the previous multiple of sizeof(Vector8), assuming that's a power-of-2.
	 */
	vlen = len & (int) (~(sizeof(Vector8) - 1));

	appendStringInfoCharMacro(buf, '"');

	for (int i = 0, copypos = 0;;)
	{
		/*
		 * To speed this up, try searching sizeof(Vector8) bytes at once for
		 * special characters that we need to escape.  When we find one, we
		 * fall out of the Vector8 loop and copy the portion we've vector
		 * searched and then we process sizeof(Vector8) bytes one byte at a
		 * time.  Once done, come back and try doing vector searching again.
		 * We'll also process any remaining bytes at the tail end of the
		 * string byte-by-byte.  This optimization assumes that most chunks of
		 * sizeof(Vector8) bytes won't contain any special characters.
		 */
		for (; i < vlen; i += sizeof(Vector8))
		{
			Vector8		chunk;

			vector8_load(&chunk, (const uint8 *) &str[i]);

			/*
			 * Break on anything less than ' ' or if we find a '"' or '\\'.
			 * Those need special handling.  That's done in the per-byte loop.
			 */
			if (vector8_has_le(chunk, (unsigned char) 0x1F) ||
				vector8_has(chunk, (unsigned char) '"') ||
				vector8_has(chunk, (unsigned char) '\\'))
				break;

#ifdef ESCAPE_JSON_FLUSH_AFTER

			/*
			 * Flush what's been checked so far out to the destination buffer
			 * every so often to avoid having to re-read cachelines when
			 * escaping large strings.
			 */
			if (i - copypos >= ESCAPE_JSON_FLUSH_AFTER)
			{
				appendBinaryStringInfo(buf, &str[copypos], i - copypos);
				copypos = i;
			}
#endif
		}

		/*
		 * Write to the destination up to the point that we've vector searched
		 * so far.  Do this only when switching into per-byte mode rather than
		 * once every sizeof(Vector8) bytes.
		 */
		if (copypos < i)
		{
			appendBinaryStringInfo(buf, &str[copypos], i - copypos);
			copypos = i;
		}

		/*
		 * Per-byte loop for Vector8s containing special chars and for
		 * processing the tail of the string.
		 */
		for (size_t b = 0; b < sizeof(Vector8); b++)
		{
			/* check if we've finished */
			if (i == len)
				goto done;

			Assert(i < len);

			escape_json_char(buf, str[i++]);
		}

		copypos = i;
		/* We're not done yet.  Try the vector search again. */
	}

done:
	appendStringInfoCharMacro(buf, '"');
}

The search itself is two lines:

c
			if (vector8_has_le(chunk, (unsigned char) 0x1F) ||
				vector8_has(chunk, (unsigned char) '"') ||
				vector8_has(chunk, (unsigned char) '\\'))
				break;

vector8_has_le(chunk, (unsigned char) 0x1F) catches every control character with one comparison, because “less than or equal to 0x1F” is exactly the set of characters JSON requires to be escaped.

The structure is: scan a vector; if it is clean, keep going; if it is dirty, copy out everything scanned so far and process sixteen bytes one at a time (some of which need escaping, some of which do not), then resume vector scanning.

The cache-residency window

There is a subtlety in this loop that has nothing to do with SIMD and everything to do with memory. It is this constant:

c
// src/backend/utils/adt/json.c
/*
 * Define the number of bytes that escape_json_with_len will look ahead in the
 * input string before flushing the input string to the destination buffer.
 * Looking ahead too far could result in cachelines being evicted that will
 * need to be reloaded in order to perform the appendBinaryStringInfo call.
 * Smaller values will result in a larger number of calls to
 * appendBinaryStringInfo and introduce additional function call overhead.
 * Values larger than the size of L1d cache will likely result in worse
 * performance.
 */
#define ESCAPE_JSON_FLUSH_AFTER 512

The comment is a complete performance essay in ten lines:

Define the number of bytes that escape_json_with_len will look ahead in the input string before flushing the input string to the destination buffer. Looking ahead too far could result in cachelines being evicted that will need to be reloaded in order to perform the appendBinaryStringInfo call. Smaller values will result in a larger number of calls to appendBinaryStringInfo and introduce additional function call overhead. Values larger than the size of L1d cache will likely result in worse performance.

The mechanism is in the loop:

c
			if (i - copypos >= ESCAPE_JSON_FLUSH_AFTER)
			{
				appendBinaryStringInfo(buf, &str[copypos], i - copypos);
				copypos = i;
			}

Without this, the entire input string would be scanned before any of it was written to the output buffer, and the output buffer’s memcpy would then have to re-read the whole input from memory — evicting it from L1 along the way. With the window set to 512 bytes, the scanner never gets more than 512 bytes ahead of the writer, so the bytes being copied are still in L1. 512 is small enough to stay resident and large enough that the per-flush function call overhead is negligible.

This is a nice illustration of a general point: SIMD changes the inner loop cost, but the outer memory behaviour can dominate. Vectorizing a loop and then letting it run ahead of the memory system can easily be a net loss.

Consumer four: ASCII validation

is_valid_ascii() answers “are all of these bytes plain ASCII?” — that is, no zero bytes and no bytes with the high bit set. It is used by the UTF-8 verifier to skip the expensive state machine when the input is obviously ASCII:

c
// src/common/wchar.c
	const unsigned char *start = s;
	const int	orig_len = len;
	uint32		state = BGN;

/*
 * With a stride of two vector widths, gcc will unroll the loop. Even if
 * the compiler can unroll a longer loop, it's not worth it because we
 * must fall back to the byte-wise algorithm if we find any non-ASCII.
 */
#define STRIDE_LENGTH (2 * sizeof(Vector8))

	if (len >= STRIDE_LENGTH)
	{
		while (len >= STRIDE_LENGTH)
		{
			/*
			 * If the chunk is all ASCII, we can skip the full UTF-8 check,
			 * but we must first check for a non-END state, which means the
			 * previous chunk ended in the middle of a multibyte sequence.
			 */
			if (state != END || !is_valid_ascii(s, STRIDE_LENGTH))
				utf8_advance(s, &state, STRIDE_LENGTH);

			s += STRIDE_LENGTH;
			len -= STRIDE_LENGTH;
		}

The implementation:

c
// src/include/utils/ascii.h
/*
 * Verify a chunk of bytes for valid ASCII.
 *
 * Returns false if the input contains any zero bytes or bytes with the
 * high-bit set. Input len must be a multiple of the chunk size (8 or 16).
 */
static inline bool
is_valid_ascii(const unsigned char *s, int len)
{
	const unsigned char *const s_end = s + len;
	Vector8		chunk;
	Vector8		highbit_cum = vector8_broadcast(0);
#ifdef USE_NO_SIMD
	Vector8		zero_cum = vector8_broadcast(0x80);
#endif

	Assert(len % sizeof(chunk) == 0);

	while (s < s_end)
	{
		vector8_load(&chunk, s);

		/* Capture any zero bytes in this chunk. */
#ifdef USE_NO_SIMD

		/*
		 * First, add 0x7f to each byte. This sets the high bit in each byte,
		 * unless it was a zero. If any resulting high bits are zero, the
		 * corresponding high bits in the zero accumulator will be cleared.
		 *
		 * If none of the bytes in the chunk had the high bit set, the max
		 * value each byte can have after the addition is 0x7f + 0x7f = 0xfe,
		 * and we don't need to worry about carrying over to the next byte. If
		 * any input bytes did have the high bit set, it doesn't matter
		 * because we check for those separately.
		 */
		zero_cum &= (chunk + vector8_broadcast(0x7F));
#else

		/*
		 * Set all bits in each lane of the highbit accumulator where input
		 * bytes are zero.
		 */
		highbit_cum = vector8_or(highbit_cum,
								 vector8_eq(chunk, vector8_broadcast(0)));
#endif

		/* Capture all set bits in this chunk. */
		highbit_cum = vector8_or(highbit_cum, chunk);

		s += sizeof(chunk);
	}

	/* Check if any high bits in the high bit accumulator got set. */
	if (vector8_is_highbit_set(highbit_cum))
		return false;

#ifdef USE_NO_SIMD
	/* Check if any high bits in the zero accumulator got cleared. */
	if (zero_cum != vector8_broadcast(0x80))
		return false;
#endif

	return true;
}

This one is interesting because the fallback is the cleverer code and the SIMD path is the simple one — the reverse of the usual arrangement.

In the SIMD path, finding a zero byte is a single vector8_eq against zero, which produces all-ones lanes that get OR-ed into the accumulator:

c
		highbit_cum = vector8_or(highbit_cum,
								 vector8_eq(chunk, vector8_broadcast(0)));

and finding a high-bit byte is just OR-ing the chunk itself in. At the end, one vector8_is_highbit_set() answers “did anything interesting happen anywhere in the whole buffer?”.

In the fallback path there is no vector8_eq to use, so it does the classic SWAR trick of adding 0x7f to every byte:

c
		zero_cum &= (chunk + vector8_broadcast(0x7F));

Adding 0x7f to a byte sets its high bit, unless the byte was zero — in which case 0x7f + 0x00 = 0x7f, high bit clear. So AND-ing the chunk into an accumulator initialized to 0x80 in every lane clears the bit for any byte that was zero. The comment explains the carry-safety argument:

If none of the bytes in the chunk had the high bit set, the max value each byte can have after the addition is 0x7f + 0x7f = 0xfe, and we don’t need to worry about carrying over to the next byte.

Note the API constraint: len must be a multiple of the chunk size, and there is an Assert enforcing it. Callers round up accordingly — the UTF-8 verifier uses a stride of two vector widths precisely so the compiler will unroll the loop.

Consumer five: linear search

pg_lfind32() answers “is this 32-bit value present in this array?” — in PostgreSQL, that is almost always “is this transaction ID in this snapshot’s list of in-progress XIDs?”. It is a hot path in snapmgr.c, procarray.c and predicate.c. The scalar version is a plain loop.

The SIMD version has a specific and rather subtle structure:

c
// src/include/port/pg_lfind.h
#ifndef USE_NO_SIMD
/*
 * pg_lfind32_simd_helper
 *
 * Searches one 4-register-block of integers.  The caller is responsible for
 * ensuring that there are at least 4-registers-worth of integers remaining.
 */
static inline bool
pg_lfind32_simd_helper(const Vector32 keys, const uint32 *base)
{
	const uint32 nelem_per_vector = sizeof(Vector32) / sizeof(uint32);
	Vector32	vals1,
				vals2,
				vals3,
				vals4,
				result1,
				result2,
				result3,
				result4,
				tmp1,
				tmp2,
				result;

	/* load the next block into 4 registers */
	vector32_load(&vals1, base);
	vector32_load(&vals2, &base[nelem_per_vector]);
	vector32_load(&vals3, &base[nelem_per_vector * 2]);
	vector32_load(&vals4, &base[nelem_per_vector * 3]);

	/* compare each value to the key */
	result1 = vector32_eq(keys, vals1);
	result2 = vector32_eq(keys, vals2);
	result3 = vector32_eq(keys, vals3);
	result4 = vector32_eq(keys, vals4);

	/* combine the results into a single variable */
	tmp1 = vector32_or(result1, result2);
	tmp2 = vector32_or(result3, result4);
	result = vector32_or(tmp1, tmp2);

	/* return whether there was a match */
	return vector32_is_highbit_set(result);
}
#endif							/* ! USE_NO_SIMD */

/*
 * pg_lfind32
 *
 * Return true if there is an element in 'base' that equals 'key', otherwise
 * return false.
 */
static inline bool
pg_lfind32(uint32 key, const uint32 *base, uint32 nelem)
{
#ifndef USE_NO_SIMD
	uint32		i = 0;

	/*
	 * For better instruction-level parallelism, each loop iteration operates
	 * on a block of four registers.
	 */
	const Vector32 keys = vector32_broadcast(key);	/* load copies of key */
	const uint32 nelem_per_vector = sizeof(Vector32) / sizeof(uint32);
	const uint32 nelem_per_iteration = 4 * nelem_per_vector;

	/* round down to multiple of elements per iteration */
	const uint32 tail_idx = nelem & ~(nelem_per_iteration - 1);

#if defined(USE_ASSERT_CHECKING)
	bool		assert_result = pg_lfind32_one_by_one_helper(key, base, nelem);
#endif

	/*
	 * If there aren't enough elements for the SIMD code, use the standard
	 * one-by-one linear search code.
	 */
	if (nelem < nelem_per_iteration)
		return pg_lfind32_one_by_one_helper(key, base, nelem);

	/*
	 * Process as many elements as possible with a block of 4 registers.
	 */
	do
	{
		if (pg_lfind32_simd_helper(keys, &base[i]))
		{
			Assert(assert_result == true);
			return true;
		}

		i += nelem_per_iteration;

	} while (i < tail_idx);

	/*
	 * Process the last 'nelem_per_iteration' elements in the array with a
	 * 4-register block.  This will cause us to check a subset of the elements
	 * more than once, but that won't affect correctness, and testing has
	 * demonstrated that this helps more cases than it harms.
	 */
	Assert(assert_result == pg_lfind32_simd_helper(keys, &base[nelem - nelem_per_iteration]));
	return pg_lfind32_simd_helper(keys, &base[nelem - nelem_per_iteration]);
#else
	/* Process the elements one at a time. */
	return pg_lfind32_one_by_one_helper(key, base, nelem);
#endif
}

Two ideas are packed into it.

The four-register block. The helper loads four vectors and compares all four to the key before combining the results:

c
	/* load the next block into 4 registers */
	vector32_load(&vals1, base);
	vector32_load(&vals2, &base[nelem_per_vector]);
	vector32_load(&vals3, &base[nelem_per_vector * 2]);
	vector32_load(&vals4, &base[nelem_per_vector * 3]);

	/* compare each value to the key */
	result1 = vector32_eq(keys, vals1);
	result2 = vector32_eq(keys, vals2);
	result3 = vector32_eq(keys, vals3);
	result4 = vector32_eq(keys, vals4);

	/* combine the results into a single variable */
	tmp1 = vector32_or(result1, result2);
	tmp2 = vector32_or(result3, result4);
	result = vector32_or(tmp1, tmp2);

Why four? Because of instruction-level parallelism. A single compare-then-branch loop has a loop-carried dependency: the next compare cannot issue until the branch on the previous one resolves. If you issue four independent compares and four independent loads before testing any of them, the processor has four independent chains to interleave and the latency of one is hidden by the throughput of the others. The comment says so directly:

c
	/*
	 * For better instruction-level parallelism, each loop iteration operates
	 * on a block of four registers.
	 */

On x86-64, Vector32 holds four uint32s, so one iteration covers sixteen elements.

The overlapping tail. After the main loop, the code does something that looks like a bug and is not:

c
	/*
	 * Process the last 'nelem_per_iteration' elements in the array with a
	 * 4-register block.  This will cause us to check a subset of the elements
	 * more than once, but that won't affect correctness, and testing has
	 * demonstrated that this helps more cases than it harms.
	 */
	Assert(assert_result == pg_lfind32_simd_helper(keys, &base[nelem - nelem_per_iteration]));
	return pg_lfind32_simd_helper(keys, &base[nelem - nelem_per_iteration]);

The array length is not necessarily a multiple of sixteen. Rather than write a scalar loop for the remainder — which reintroduces the latency-bound behaviour the whole exercise was meant to eliminate — it re-runs the vector search starting at nelem - 16, overlapping the already-searched region. The answer is the same (a search is a search; looking at some elements twice changes nothing), and the code stays branch-free. “Testing has demonstrated that this helps more cases than it harms” is the sound engineering voice of someone who measured it.

The assert-build cross-check is worth noting too: in a debug build, the function computes the answer with the plain one-by-one loop and asserts that the vector path agrees.

Consumer six: radix tree lookups

The radix tree used by the regular-expression and pattern-matching machinery has nodes with up to 32 children, keyed by a one-byte “chunk” of the search key. Finding the right child in a 32-way node is a linear scan over the chunk bytes — and it is now a SIMD scan:

c
// src/include/lib/radixtree.h
/*
 * Return the address of the child corresponding to "chunk",
 * or NULL if there is no such element.
 */
static inline RT_PTR_ALLOC *
RT_NODE_16_SEARCH_EQ(RT_NODE_16 * node, uint8 chunk)
{
	int			count = node->base.count;
#ifndef USE_NO_SIMD
	Vector8		spread_chunk;
	Vector8		haystack1;
	Vector8		haystack2;
	Vector8		cmp1;
	Vector8		cmp2;
	uint32		bitfield;
	RT_PTR_ALLOC *slot_simd = NULL;
#endif

#if defined(USE_NO_SIMD) || defined(USE_ASSERT_CHECKING)
	RT_PTR_ALLOC *slot = NULL;

	for (int i = 0; i < count; i++)
	{
		if (node->chunks[i] == chunk)
		{
			slot = &node->children[i];
			break;
		}
	}
#endif

#ifndef USE_NO_SIMD
	/* replicate the search key */
	spread_chunk = vector8_broadcast(chunk);

	/* compare to all 32 keys stored in the node */
	vector8_load(&haystack1, &node->chunks[0]);
	vector8_load(&haystack2, &node->chunks[sizeof(Vector8)]);
	cmp1 = vector8_eq(spread_chunk, haystack1);
	cmp2 = vector8_eq(spread_chunk, haystack2);

	/* convert comparison to a bitfield */
	bitfield = vector8_highbit_mask(cmp1) | (vector8_highbit_mask(cmp2) << sizeof(Vector8));

	/* mask off invalid entries */
	bitfield &= ((UINT64CONST(1) << count) - 1);

	/* convert bitfield to index by counting trailing zeros */
	if (bitfield)
		slot_simd = &node->children[pg_rightmost_one_pos32(bitfield)];

	Assert(slot_simd == slot);
	return slot_simd;
#else
	return slot;
#endif
}

This is the most elegant use of the primitives in the tree, because it uses the mask rather than just the boolean. The comparison produces a bitmap of which of the 32 chunk bytes match, and then the index of the match is recovered with a trailing-zeros count:

c
	/* convert comparison to a bitfield */
	bitfield = vector8_highbit_mask(cmp1) | (vector8_highbit_mask(cmp2) << sizeof(Vector8));

	/* mask off invalid entries */
	bitfield &= ((UINT64CONST(1) << count) - 1);

	/* convert bitfield to index by counting trailing zeros */
	if (bitfield)
		slot_simd = &node->children[pg_rightmost_one_pos32(bitfield)];

Three steps: compare, mask, count trailing zeros. The count masking handles the case where the node has fewer than 32 children — the unused lanes of the compare must not produce a false hit.

The scalar version is still there, guarded by USE_ASSERT_CHECKING, and the two results are asserted equal:

c
	Assert(slot_simd == slot);
	return slot_simd;

So the vector path is checked against the obvious implementation on every assert-enabled build. That is a very high bar, and it is exactly the kind of bar you want for code that indexes into an array using a bit count.

Why it matters

Let me put the byte-at-a-time loop next to the vector loop and count instructions.

For “find the next newline in a buffer”, the scalar loop per byte is roughly: load byte, compare, branch, increment, branch. That is two branches per byte, and a 64-byte cache line takes 64 iterations. The vector loop per sixteen bytes is: load 16 bytes, compare, OR, compare, OR, compare, OR, test, branch, add. That is one branch per sixteen bytes.

Work	Scalar	SIMD (SSE2)	Ratio
Bytes examined per branch	1	16	16×
Branches per 64-byte cache line	64	4	16×
Loads per 64-byte cache line	64	4	16×
Compare instructions per 64-byte cache line	64	12 (3 characters × 4 vectors)	~5×

The branch count is the headline. Branch mispredictions are the single biggest cost in a scanning loop, and they are what limits a character-classification loop far more than the comparisons themselves. A CSV file with a quoted field on every line will mispredict on every line in the scalar path — which is precisely why the COPY parser disables the vector path entirely for such files rather than trying to make the vector path handle quotes.

There is a second, subtler benefit: the vector path removes the loop-carried dependency. The scalar loop’s pointer increment depends on the branch resolution; the vector loop’s pointer increment is a fixed += 16 that the processor can speculate past. In practice this is where most of the win comes from on wide OoO cores.

And there is a third: the amount of work per useful result. In the scalar COPY loop, each byte is examined for three different characters, plus the CSV state machine. In the vector loop, the state machine is only consulted for bytes that the vector scan flags as interesting — and the vector scan is a straight line of independent instructions.

Caveats

The fallback must be exactly as correct

The USE_NO_SIMD path is not a “best effort”. It is a second implementation of the same algorithm, and the two must agree bit for bit. PostgreSQL manages this with two mechanisms:

Assertion cross-checks inside simd.h itself, which recompute the naive answer for every primitive.
Assertion cross-checks at the call sites, in pg_lfind32(), RT_NODE_16_SEARCH_EQ() and the COPY helper.

That is why vector8_has() looks the way it does — the assert_result loop at the top is not dead weight, it is the specification.

Note that the fallback is not always available. vector8_and(), vector8_eq(), vector8_add(), vector8_gt(), vector8_min() and the interleave functions are all inside #ifndef USE_NO_SIMD blocks, with the reason given at the top of the file:

Note that many of the functions in this file presently do not have non-SIMD implementations. In particular, none of the functions involving Vector32 are implemented without SIMD since it’s likely not worthwhile to represent two 32-bit integers using a uint64.

So the higher-level algorithms that need those primitives are simply not compiled on a non-SIMD platform. hex_encode() has a full scalar implementation; pg_lfind32() falls back to a one-by-one loop; RT_NODE_16_SEARCH_EQ() falls back to a linear scan.

Portability is a moving target

port/simd.h supports SSE2 and NEON. That is not the whole story of PostgreSQL’s SIMD usage — the page checksum code has a separate, runtime-dispatched AVX2 path — but it is the whole story of this header. The header is deliberately conservative: SSE2 only, no AVX, because SSE2 is guaranteed on x86-64 while AVX is not, and because a runtime check costs more than it saves for a per-call overhead this small.

The COPY heuristic is deliberately pessimistic

The COPY path gives up SIMD permanently after the first non-EOL special character. If you are profiling a CSV load and you see the vector path never engaging, this is why. It is a bet that the common case is “long lines, no special characters”, and that is a bet worth revisiting with better heuristics — the comment in the source says so explicitly.

The overhead is not zero

For short inputs, the vector path loses. Loading a vector, comparing, and combining is several instructions; a 5-byte string is better handled by a scalar loop. The COPY code knows this and bails out on the first chunk. Other callers round the length down to a multiple of the vector width and handle the tail scalar-ly. This is why every one of these functions has a tail_idx computation and a scalar remainder loop.

Look at it yourself

The clearest way to see this is to check what the compiler generates. Build with -O2 on x86-64 and look for pcmpeqb and pmovmskb in hex_encode or escape_json_with_len:

sh
objdump -d src/backend/utils/adt/encode.o | grep -A 40 '<hex_encode>' | less

You should see the load, the four compares, the ORs, and the pmovmskb that extracts the match bitmap.

For the COPY path, the simd_enabled flag is per-CopyFromState, so you can watch it flip by reading copyfromparse.c:1473 and seeing who gets there.

What it all means in practice

SIMD in PostgreSQL is not a special optimization; it is a layer. The interesting engineering is not “use pcmpeqb” — it is designing a small set of primitives that (a) has a correct scalar fallback, (b) works on SSE2 and NEON with one implementation each, and (c) is powerful enough that the algorithms above it are architecture-independent. Once that layer exists, hex encoding, JSON escaping, ASCII validation, linear search and radix-tree lookup all become “the same loop with different constants”.

The wins are concentrated where the data is boring. Every one of these optimizations assumes most bytes are uninteresting. That is true of CSV without quotes, of hex without whitespace, of JSON without control characters, of ASCII text, of arrays without duplicates, of radix-tree nodes with one matching key. When the data is not boring, the vector path still works — it just hands off to the scalar path sooner.

The most instructive consumer is the radix tree, because it uses the full mask rather than just the boolean, and turns “16 comparisons” into “one compare, one mask, one trailing-zero count”. That is the shape of good SIMD code: do the comparison in parallel, then extract the exact position, then do the interesting thing once.

The most instructive design decision is the conservative COPY heuristic. A SIMD optimization that helps 90% of workloads and hurts 10% is a regression waiting to happen, and the cheapest way to avoid it is to detect the bad case and turn the optimization off for the rest of the command. It is not elegant, but it is honest, and the source says so.

The abstraction: port/simd.h