pg.ddx.io  pgsql-hackers@postgresql.org mailing list archive  

help / color / mirror / Atom feed
From: Nathan Bossart <nathandbossart@gmail.com>
To: Sehrope Sarkuni <sehrope@jackdb.com>
Cc: Pg Hackers <pgsql-hackers@postgresql.org>
Subject: Re: Speed up lpad() and rpad() for one-byte padding strings
Date: Wed, 23 Sep 2026 12:09:08 -0500
Message-ID: <arQHtMApsI6MX-XH@nathan> (raw)
In-Reply-To: <arPlICNzFXv6zTbS@nathan>
References: <CAH7T-apj+pFg9bRkXVGfGejS2Uu4WzdMd7KoLKTW11mdsrt1Ew@mail.gmail.com>
	<arPlICNzFXv6zTbS@nathan>

On Wed, Sep 23, 2026 at 09:41:36AM -0500, Nathan Bossart wrote:
> On Wed, Sep 23, 2026 at 10:10:09AM -0400, Sehrope Sarkuni wrote:
>> lpad() and rpad() pad one character at a time, calling
>> pg_mblen_range() and memcpy() once per padding char.  When the padding
>> string is a single byte, e.g., lpad(x, n, '0') or rpad(x, n, ' '),
>> the padding is that byte repeated, so the attached patch fills it with
>> one memset().
> 
> I wonder if we could expand these gains by using SIMD whenever the vector
> length is divisible by the padding string length.  My hunch is that's where
> a lot of the memset() gains come from.

Actually, I think we can expand this to any padding string length by
copying the padding string once, and then copying from the beginning of the
padding to the end repeatedly so that we write double the padding each
time.  This is a bit like what commit c60e520 added for pglz_decompress().
I've attached some proof-of-concept grade patches.  This doesn't quite
match the performance of your 1-byte fast-path, but it's pretty close and
applies to many more cases.

-- 
nathan
From db26e9d41843c6837f3c4ce77c4667bac5c00644 Mon Sep 17 00:00:00 2001
From: Nathan Bossart <nathan@postgresql.org>
Date: Wed, 23 Sep 2026 11:47:02 -0500
Subject: [PATCH v2 1/2] Factor the padding loop out of lpad() and rpad().

lpad() and rpad() each carry an identical copy of the loop that
writes the padding characters.  This commit moves it into a helper
function that both call.  No functional change.

This is preparatory work for a follow-up commit that will teach the
helper to write long padding with a few large memcpy() calls instead
of one per character.
---
 src/backend/utils/adt/oracle_compat.c | 60 ++++++++++++---------------
 1 file changed, 27 insertions(+), 33 deletions(-)

diff --git a/src/backend/utils/adt/oracle_compat.c b/src/backend/utils/adt/oracle_compat.c
index 7422a454397..2adc3874bc2 100644
--- a/src/backend/utils/adt/oracle_compat.c
+++ b/src/backend/utils/adt/oracle_compat.c
@@ -143,6 +143,31 @@ casefold(PG_FUNCTION_ARGS)
 }
 
 
+/*
+ * Append m characters of the padding string s2 (s2len bytes) to dst,
+ * cycling through s2 as needed, and return a pointer past the last byte
+ * written.
+ */
+static char *
+append_padding(char *dst, const char *s2, int s2len, int m)
+{
+	const char *ptr2 = s2;
+	const char *ptr2end = s2 + s2len;
+
+	while (m--)
+	{
+		int			mlen = pg_mblen_range(ptr2, ptr2end);
+
+		memcpy(dst, ptr2, mlen);
+		dst += mlen;
+		ptr2 += mlen;
+		if (ptr2 == ptr2end)	/* wrap around at end of s2 */
+			ptr2 = s2;
+	}
+
+	return dst;
+}
+
 /********************************************************************
  *
  * lpad
@@ -167,10 +192,7 @@ lpad(PG_FUNCTION_ARGS)
 	text	   *string2 = PG_GETARG_TEXT_PP(2);
 	text	   *ret;
 	char	   *ptr1,
-			   *ptr2,
-			   *ptr2start,
 			   *ptr_ret;
-	const char *ptr2end;
 	int			m,
 				s1len,
 				s2len;
@@ -209,20 +231,7 @@ lpad(PG_FUNCTION_ARGS)
 
 	m = len - s1len;
 
-	ptr2 = ptr2start = VARDATA_ANY(string2);
-	ptr2end = ptr2 + s2len;
-	ptr_ret = VARDATA(ret);
-
-	while (m--)
-	{
-		int			mlen = pg_mblen_range(ptr2, ptr2end);
-
-		memcpy(ptr_ret, ptr2, mlen);
-		ptr_ret += mlen;
-		ptr2 += mlen;
-		if (ptr2 == ptr2end)	/* wrap around at end of s2 */
-			ptr2 = ptr2start;
-	}
+	ptr_ret = append_padding(VARDATA(ret), VARDATA_ANY(string2), s2len, m);
 
 	ptr1 = VARDATA_ANY(string1);
 
@@ -265,10 +274,7 @@ rpad(PG_FUNCTION_ARGS)
 	text	   *string2 = PG_GETARG_TEXT_PP(2);
 	text	   *ret;
 	char	   *ptr1,
-			   *ptr2,
-			   *ptr2start,
 			   *ptr_ret;
-	const char *ptr2end;
 	int			m,
 				s1len,
 				s2len;
@@ -320,19 +326,7 @@ rpad(PG_FUNCTION_ARGS)
 		ptr1 += mlen;
 	}
 
-	ptr2 = ptr2start = VARDATA_ANY(string2);
-	ptr2end = ptr2 + s2len;
-
-	while (m--)
-	{
-		int			mlen = pg_mblen_range(ptr2, ptr2end);
-
-		memcpy(ptr_ret, ptr2, mlen);
-		ptr_ret += mlen;
-		ptr2 += mlen;
-		if (ptr2 == ptr2end)	/* wrap around at end of s2 */
-			ptr2 = ptr2start;
-	}
+	ptr_ret = append_padding(ptr_ret, VARDATA_ANY(string2), s2len, m);
 
 	SET_VARSIZE(ret, ptr_ret - (char *) ret);
 
-- 
2.55.0
From 8bdb4237a3b08b192ddfa7d69128bff3e0b92d47 Mon Sep 17 00:00:00 2001
From: Nathan Bossart <nathan@postgresql.org>
Date: Wed, 23 Sep 2026 11:47:23 -0500
Subject: [PATCH v2 2/2] Optimize padding in lpad() and rpad().

lpad() and rpad() write the padding one character at a time, calling
pg_mblen_range() and memcpy() for each one, which gets slow once the
padding runs to many kilobytes.  Since the padding is just the pad
string repeated, this commit copies the pad string once, as before,
and then produces the rest by copying what has already been written
onto the end of itself, doubling the length each time.  That takes a
handful of memcpy() calls for a pad string of any length, and it is
dramatically faster for long padding.

Note that the pad string is still only checked for a truncated
multibyte character as far as it is actually used, so a bad tail is
accepted when no padding is needed, as before.

Co-authored-by: Sehrope Sarkuni <sehrope@jackdb.com>
Discussion: https://postgr.es/m/CAH7T-apj%2BpFg9bRkXVGfGejS2Uu4WzdMd7KoLKTW11mdsrt1Ew%40mail.gmail.com
---
 src/backend/utils/adt/oracle_compat.c  | 45 ++++++++++++++++++++++++--
 src/test/regress/expected/encoding.out | 19 +++++++++++
 src/test/regress/sql/encoding.sql      |  7 ++++
 3 files changed, 68 insertions(+), 3 deletions(-)

diff --git a/src/backend/utils/adt/oracle_compat.c b/src/backend/utils/adt/oracle_compat.c
index 2adc3874bc2..d54fe948355 100644
--- a/src/backend/utils/adt/oracle_compat.c
+++ b/src/backend/utils/adt/oracle_compat.c
@@ -147,22 +147,61 @@ casefold(PG_FUNCTION_ARGS)
  * Append m characters of the padding string s2 (s2len bytes) to dst,
  * cycling through s2 as needed, and return a pointer past the last byte
  * written.
+ *
+ * Note that s2 is only checked for a truncated multibyte character as far as
+ * we actually use it, so a bad tail is accepted when the padding stops short
+ * of it, as it always has been.
  */
 static char *
 append_padding(char *dst, const char *s2, int s2len, int m)
 {
 	const char *ptr2 = s2;
 	const char *ptr2end = s2 + s2len;
+	char	   *start = dst;
+	int			nchars = 0;
+	int			nbytes;
+	int			written;
 
-	while (m--)
+	/* Copy s2 once, one character at a time, or until m runs out. */
+	while (m > 0 && ptr2 < ptr2end)
 	{
 		int			mlen = pg_mblen_range(ptr2, ptr2end);
 
 		memcpy(dst, ptr2, mlen);
 		dst += mlen;
 		ptr2 += mlen;
-		if (ptr2 == ptr2end)	/* wrap around at end of s2 */
-			ptr2 = s2;
+		m--;
+		nchars++;
+	}
+
+	if (m == 0)
+		return dst;
+
+	/*
+	 * The rest of the padding is s2 repeated, so work out how many bytes that
+	 * is: whole copies of s2, plus the first m % nchars characters of one
+	 * more.
+	 */
+	nbytes = (m / nchars) * s2len;
+	ptr2 = s2;
+	for (m %= nchars; m > 0; m--)
+		ptr2 += pg_mblen_unbounded(ptr2);
+	nbytes += ptr2 - s2;
+
+	/*
+	 * Now produce those bytes by copying what we've already written, doubling
+	 * the length each time, so that the work is done by a few large memcpy()
+	 * calls rather than one per character.
+	 */
+	written = dst - start;
+	while (nbytes > 0)
+	{
+		int			chunk = Min(written, nbytes);
+
+		memcpy(dst, start, chunk);
+		dst += chunk;
+		nbytes -= chunk;
+		written += chunk;
 	}
 
 	return dst;
diff --git a/src/test/regress/expected/encoding.out b/src/test/regress/expected/encoding.out
index 0bb72a1df6f..8098599e302 100644
--- a/src/test/regress/expected/encoding.out
+++ b/src/test/regress/expected/encoding.out
@@ -60,6 +60,25 @@ SELECT reverse(good) FROM regress_encoding;
  éfac
 (1 row)
 
+-- padding with a multibyte character
+SELECT lpad(good, 7, 'é'), rpad(good, 7, 'é') FROM regress_encoding;
+  lpad   |  rpad   
+---------+---------
+ ééécafé | caféééé
+(1 row)
+
+-- padding with a lone lead byte of a multibyte character = error
+SELECT lpad(good, 7, test_bytea_to_text('\xc3')) FROM regress_encoding;
+ERROR:  invalid byte sequence for encoding "UTF8": 0xc3
+SELECT rpad(good, 7, test_bytea_to_text('\xc3')) FROM regress_encoding;
+ERROR:  invalid byte sequence for encoding "UTF8": 0xc3
+-- no error when no padding is needed
+SELECT lpad(good, 4, test_bytea_to_text('\xc3')), rpad(good, 4, test_bytea_to_text('\xc3')) FROM regress_encoding;
+ lpad | rpad 
+------+------
+ café | café
+(1 row)
+
 -- invalid short mb character = error
 SELECT length(truncated) FROM regress_encoding;
 ERROR:  invalid byte sequence for encoding "UTF8": 0xc3
diff --git a/src/test/regress/sql/encoding.sql b/src/test/regress/sql/encoding.sql
index 26caa93a5d5..7121704f790 100644
--- a/src/test/regress/sql/encoding.sql
+++ b/src/test/regress/sql/encoding.sql
@@ -37,6 +37,13 @@ SELECT substring(good, 3, 1) FROM regress_encoding;
 SELECT substring(good, 4, 1) FROM regress_encoding;
 SELECT regexp_replace(good, '^caf(.)$', '\1') FROM regress_encoding;
 SELECT reverse(good) FROM regress_encoding;
+-- padding with a multibyte character
+SELECT lpad(good, 7, 'é'), rpad(good, 7, 'é') FROM regress_encoding;
+-- padding with a lone lead byte of a multibyte character = error
+SELECT lpad(good, 7, test_bytea_to_text('\xc3')) FROM regress_encoding;
+SELECT rpad(good, 7, test_bytea_to_text('\xc3')) FROM regress_encoding;
+-- no error when no padding is needed
+SELECT lpad(good, 4, test_bytea_to_text('\xc3')), rpad(good, 4, test_bytea_to_text('\xc3')) FROM regress_encoding;
 
 -- invalid short mb character = error
 SELECT length(truncated) FROM regress_encoding;
-- 
2.55.0

Attachments:

  [text/plain] v2-0001-Factor-the-padding-loop-out-of-lpad-and-rpad.patch (2.9K, ../arQHtMApsI6MX-XH@nathan/2-v2-0001-Factor-the-padding-loop-out-of-lpad-and-rpad.patch)
  download | inline diff:
From db26e9d41843c6837f3c4ce77c4667bac5c00644 Mon Sep 17 00:00:00 2001
From: Nathan Bossart <nathan@postgresql.org>
Date: Wed, 23 Sep 2026 11:47:02 -0500
Subject: [PATCH v2 1/2] Factor the padding loop out of lpad() and rpad().

lpad() and rpad() each carry an identical copy of the loop that
writes the padding characters.  This commit moves it into a helper
function that both call.  No functional change.

This is preparatory work for a follow-up commit that will teach the
helper to write long padding with a few large memcpy() calls instead
of one per character.
---
 src/backend/utils/adt/oracle_compat.c | 60 ++++++++++++---------------
 1 file changed, 27 insertions(+), 33 deletions(-)

diff --git a/src/backend/utils/adt/oracle_compat.c b/src/backend/utils/adt/oracle_compat.c
index 7422a454397..2adc3874bc2 100644
--- a/src/backend/utils/adt/oracle_compat.c
+++ b/src/backend/utils/adt/oracle_compat.c
@@ -143,6 +143,31 @@ casefold(PG_FUNCTION_ARGS)
 }
 
 
+/*
+ * Append m characters of the padding string s2 (s2len bytes) to dst,
+ * cycling through s2 as needed, and return a pointer past the last byte
+ * written.
+ */
+static char *
+append_padding(char *dst, const char *s2, int s2len, int m)
+{
+	const char *ptr2 = s2;
+	const char *ptr2end = s2 + s2len;
+
+	while (m--)
+	{
+		int			mlen = pg_mblen_range(ptr2, ptr2end);
+
+		memcpy(dst, ptr2, mlen);
+		dst += mlen;
+		ptr2 += mlen;
+		if (ptr2 == ptr2end)	/* wrap around at end of s2 */
+			ptr2 = s2;
+	}
+
+	return dst;
+}
+
 /********************************************************************
  *
  * lpad
@@ -167,10 +192,7 @@ lpad(PG_FUNCTION_ARGS)
 	text	   *string2 = PG_GETARG_TEXT_PP(2);
 	text	   *ret;
 	char	   *ptr1,
-			   *ptr2,
-			   *ptr2start,
 			   *ptr_ret;
-	const char *ptr2end;
 	int			m,
 				s1len,
 				s2len;
@@ -209,20 +231,7 @@ lpad(PG_FUNCTION_ARGS)
 
 	m = len - s1len;
 
-	ptr2 = ptr2start = VARDATA_ANY(string2);
-	ptr2end = ptr2 + s2len;
-	ptr_ret = VARDATA(ret);
-
-	while (m--)
-	{
-		int			mlen = pg_mblen_range(ptr2, ptr2end);
-
-		memcpy(ptr_ret, ptr2, mlen);
-		ptr_ret += mlen;
-		ptr2 += mlen;
-		if (ptr2 == ptr2end)	/* wrap around at end of s2 */
-			ptr2 = ptr2start;
-	}
+	ptr_ret = append_padding(VARDATA(ret), VARDATA_ANY(string2), s2len, m);
 
 	ptr1 = VARDATA_ANY(string1);
 
@@ -265,10 +274,7 @@ rpad(PG_FUNCTION_ARGS)
 	text	   *string2 = PG_GETARG_TEXT_PP(2);
 	text	   *ret;
 	char	   *ptr1,
-			   *ptr2,
-			   *ptr2start,
 			   *ptr_ret;
-	const char *ptr2end;
 	int			m,
 				s1len,
 				s2len;
@@ -320,19 +326,7 @@ rpad(PG_FUNCTION_ARGS)
 		ptr1 += mlen;
 	}
 
-	ptr2 = ptr2start = VARDATA_ANY(string2);
-	ptr2end = ptr2 + s2len;
-
-	while (m--)
-	{
-		int			mlen = pg_mblen_range(ptr2, ptr2end);
-
-		memcpy(ptr_ret, ptr2, mlen);
-		ptr_ret += mlen;
-		ptr2 += mlen;
-		if (ptr2 == ptr2end)	/* wrap around at end of s2 */
-			ptr2 = ptr2start;
-	}
+	ptr_ret = append_padding(ptr_ret, VARDATA_ANY(string2), s2len, m);
 
 	SET_VARSIZE(ret, ptr_ret - (char *) ret);
 
-- 
2.55.0

  [text/plain] v2-0002-Optimize-padding-in-lpad-and-rpad.patch (5.3K, ../arQHtMApsI6MX-XH@nathan/3-v2-0002-Optimize-padding-in-lpad-and-rpad.patch)
  download | inline diff:
From 8bdb4237a3b08b192ddfa7d69128bff3e0b92d47 Mon Sep 17 00:00:00 2001
From: Nathan Bossart <nathan@postgresql.org>
Date: Wed, 23 Sep 2026 11:47:23 -0500
Subject: [PATCH v2 2/2] Optimize padding in lpad() and rpad().

lpad() and rpad() write the padding one character at a time, calling
pg_mblen_range() and memcpy() for each one, which gets slow once the
padding runs to many kilobytes.  Since the padding is just the pad
string repeated, this commit copies the pad string once, as before,
and then produces the rest by copying what has already been written
onto the end of itself, doubling the length each time.  That takes a
handful of memcpy() calls for a pad string of any length, and it is
dramatically faster for long padding.

Note that the pad string is still only checked for a truncated
multibyte character as far as it is actually used, so a bad tail is
accepted when no padding is needed, as before.

Co-authored-by: Sehrope Sarkuni <sehrope@jackdb.com>
Discussion: https://postgr.es/m/CAH7T-apj%2BpFg9bRkXVGfGejS2Uu4WzdMd7KoLKTW11mdsrt1Ew%40mail.gmail.com
---
 src/backend/utils/adt/oracle_compat.c  | 45 ++++++++++++++++++++++++--
 src/test/regress/expected/encoding.out | 19 +++++++++++
 src/test/regress/sql/encoding.sql      |  7 ++++
 3 files changed, 68 insertions(+), 3 deletions(-)

diff --git a/src/backend/utils/adt/oracle_compat.c b/src/backend/utils/adt/oracle_compat.c
index 2adc3874bc2..d54fe948355 100644
--- a/src/backend/utils/adt/oracle_compat.c
+++ b/src/backend/utils/adt/oracle_compat.c
@@ -147,22 +147,61 @@ casefold(PG_FUNCTION_ARGS)
  * Append m characters of the padding string s2 (s2len bytes) to dst,
  * cycling through s2 as needed, and return a pointer past the last byte
  * written.
+ *
+ * Note that s2 is only checked for a truncated multibyte character as far as
+ * we actually use it, so a bad tail is accepted when the padding stops short
+ * of it, as it always has been.
  */
 static char *
 append_padding(char *dst, const char *s2, int s2len, int m)
 {
 	const char *ptr2 = s2;
 	const char *ptr2end = s2 + s2len;
+	char	   *start = dst;
+	int			nchars = 0;
+	int			nbytes;
+	int			written;
 
-	while (m--)
+	/* Copy s2 once, one character at a time, or until m runs out. */
+	while (m > 0 && ptr2 < ptr2end)
 	{
 		int			mlen = pg_mblen_range(ptr2, ptr2end);
 
 		memcpy(dst, ptr2, mlen);
 		dst += mlen;
 		ptr2 += mlen;
-		if (ptr2 == ptr2end)	/* wrap around at end of s2 */
-			ptr2 = s2;
+		m--;
+		nchars++;
+	}
+
+	if (m == 0)
+		return dst;
+
+	/*
+	 * The rest of the padding is s2 repeated, so work out how many bytes that
+	 * is: whole copies of s2, plus the first m % nchars characters of one
+	 * more.
+	 */
+	nbytes = (m / nchars) * s2len;
+	ptr2 = s2;
+	for (m %= nchars; m > 0; m--)
+		ptr2 += pg_mblen_unbounded(ptr2);
+	nbytes += ptr2 - s2;
+
+	/*
+	 * Now produce those bytes by copying what we've already written, doubling
+	 * the length each time, so that the work is done by a few large memcpy()
+	 * calls rather than one per character.
+	 */
+	written = dst - start;
+	while (nbytes > 0)
+	{
+		int			chunk = Min(written, nbytes);
+
+		memcpy(dst, start, chunk);
+		dst += chunk;
+		nbytes -= chunk;
+		written += chunk;
 	}
 
 	return dst;
diff --git a/src/test/regress/expected/encoding.out b/src/test/regress/expected/encoding.out
index 0bb72a1df6f..8098599e302 100644
--- a/src/test/regress/expected/encoding.out
+++ b/src/test/regress/expected/encoding.out
@@ -60,6 +60,25 @@ SELECT reverse(good) FROM regress_encoding;
  éfac
 (1 row)
 
+-- padding with a multibyte character
+SELECT lpad(good, 7, 'é'), rpad(good, 7, 'é') FROM regress_encoding;
+  lpad   |  rpad   
+---------+---------
+ ééécafé | caféééé
+(1 row)
+
+-- padding with a lone lead byte of a multibyte character = error
+SELECT lpad(good, 7, test_bytea_to_text('\xc3')) FROM regress_encoding;
+ERROR:  invalid byte sequence for encoding "UTF8": 0xc3
+SELECT rpad(good, 7, test_bytea_to_text('\xc3')) FROM regress_encoding;
+ERROR:  invalid byte sequence for encoding "UTF8": 0xc3
+-- no error when no padding is needed
+SELECT lpad(good, 4, test_bytea_to_text('\xc3')), rpad(good, 4, test_bytea_to_text('\xc3')) FROM regress_encoding;
+ lpad | rpad 
+------+------
+ café | café
+(1 row)
+
 -- invalid short mb character = error
 SELECT length(truncated) FROM regress_encoding;
 ERROR:  invalid byte sequence for encoding "UTF8": 0xc3
diff --git a/src/test/regress/sql/encoding.sql b/src/test/regress/sql/encoding.sql
index 26caa93a5d5..7121704f790 100644
--- a/src/test/regress/sql/encoding.sql
+++ b/src/test/regress/sql/encoding.sql
@@ -37,6 +37,13 @@ SELECT substring(good, 3, 1) FROM regress_encoding;
 SELECT substring(good, 4, 1) FROM regress_encoding;
 SELECT regexp_replace(good, '^caf(.)$', '\1') FROM regress_encoding;
 SELECT reverse(good) FROM regress_encoding;
+-- padding with a multibyte character
+SELECT lpad(good, 7, 'é'), rpad(good, 7, 'é') FROM regress_encoding;
+-- padding with a lone lead byte of a multibyte character = error
+SELECT lpad(good, 7, test_bytea_to_text('\xc3')) FROM regress_encoding;
+SELECT rpad(good, 7, test_bytea_to_text('\xc3')) FROM regress_encoding;
+-- no error when no padding is needed
+SELECT lpad(good, 4, test_bytea_to_text('\xc3')), rpad(good, 4, test_bytea_to_text('\xc3')) FROM regress_encoding;
 
 -- invalid short mb character = error
 SELECT length(truncated) FROM regress_encoding;
-- 
2.55.0

view thread (12+ messages)  latest in thread

Message-ID: <arQHtMApsI6MX-XH@nathan>
Permalink:  ../arQHtMApsI6MX-XH@nathan/
Also on:    postgresql.org/message-id/arQHtMApsI6MX-XH@nathan

 ·  · 

reply
Reply instructions:

You may reply publicly to this message via plain-text email
using any one of the following methods:

* Reply to all the recipients using the --to and --cc options:
  reply via email

  To: pgsql-hackers@postgresql.org
  Cc: nathandbossart@gmail.com, sehrope@jackdb.com
  Subject: Re: Speed up lpad() and rpad() for one-byte padding strings
  In-Reply-To: <arQHtMApsI6MX-XH@nathan>

* Save the following mbox file, import it into your mail client,
  and reply-to-all from there: mbox

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