agora inbox for pgsql-hackers@postgresql.org
help / color / mirror / Atom feedSpeed up lpad() and rpad() for one-byte padding strings
7+ messages / 3 participants
[nested] [flat]
* Speed up lpad() and rpad() for one-byte padding strings
@ 2026-09-23 14:10 Sehrope Sarkuni <sehrope@jackdb.com>
0 siblings, 2 replies; 7+ messages in thread
From: Sehrope Sarkuni @ 2026-09-23 14:10 UTC (permalink / raw)
To: pgsql-hackers
Hi hackers,
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().
pg_mblen_range() is still called once on the byte, so a lone lead byte
of a multibyte character is rejected as before. The fast path is
skipped when no padding is needed, so such a byte is still accepted in
that case. Multibyte and multi-character padding strings still use
the loop.
One oddity of the current implementation I noticed is that the pad
string is only validated when it is being copied. So an invalid pad
string is accepted when no padding is needed. This patch preserves
that behavior but it seemed weird enough (to me) to mention here.
The existing strings.sql tests already run the one-byte path through
the default space padding. The patch adds tests to encoding.sql,
for padding with a multibyte character and for the lone-lead-byte
cases.
Timings on an AMD Ryzen 7 5700G, release build (-O3, no asserts),
pgbench -c 1 with one statement per transaction, alternating
before/after rounds, median latency in ms of 5 rounds (3 at 100M):
SELECT octet_length(rpad('x', N, ' '))
or
SELECT octet_length(lpad('x', N, '0'))
N rpad before after lpad before after
1 0.056 0.056 0.057 0.056
10 0.056 0.056 0.057 0.056
100 0.056 0.056 0.057 0.057
1000 0.062 0.056 0.062 0.056
10000 0.106 0.058 0.106 0.057
100000 0.543 0.061 0.548 0.061
1000000 4.799 0.102 4.805 0.102
10000000 53.415 5.350 53.773 5.194
100000000 567.672 96.637 567.826 96.564
controls (generic loop):
octet_length(rpad('x', 1000000, 'é')) 5.342 5.676
octet_length(lpad('x', 1000000, 'ab')) 4.841 5.078
The generic-loop controls are consistently about 5-6% slower. I
tried a few arrangements of the if-block, but they produced the same
code layout. The generic loop now straddles a 64-byte boundary where
it fit within one before. I wasn't able to eliminate that difference
by rearranging the fast path.
Large pads with a single byte seem far more common than large pads
with a multi-byte or multi-character string.
Passes check-world with asserts enabled.
Regards,
-- Sehrope Sarkuni
Founder & CEO | JackDB, Inc. | https://www.jackdb.com/
Attachments:
[text/x-patch] 0001-Use-memset-for-one-byte-padding-in-lpad-and-rpad.patch (4.9K, ../../CAH7T-apj+pFg9bRkXVGfGejS2Uu4WzdMd7KoLKTW11mdsrt1Ew@mail.gmail.com/2-0001-Use-memset-for-one-byte-padding-in-lpad-and-rpad.patch)
download | inline diff:
From 4506127f660e28aba45ce5d69169eaaea1f1c4bb Mon Sep 17 00:00:00 2001
From: Sehrope Sarkuni <sehrope@jackdb.com>
Date: Tue, 22 Sep 2026 13:36:03 +0000
Subject: [PATCH] Use memset() for one-byte padding in lpad() and rpad()
A one-byte padding string is that byte repeated, so fill the padding
with memset() instead of the per-character loop, which called
pg_mblen_range() and memcpy() once per output byte.
pg_mblen_range() is still called once on the byte, so a lone lead byte
of a multibyte character is rejected as before. The fast path is
skipped when there is nothing to pad, so such a byte is still accepted
in that case.
---
src/backend/utils/adt/oracle_compat.c | 53 +++++++++++++++++++-------
src/test/regress/expected/encoding.out | 19 +++++++++
src/test/regress/sql/encoding.sql | 7 ++++
3 files changed, 65 insertions(+), 14 deletions(-)
diff --git a/src/backend/utils/adt/oracle_compat.c b/src/backend/utils/adt/oracle_compat.c
index 7422a454397..5e9459a364d 100644
--- a/src/backend/utils/adt/oracle_compat.c
+++ b/src/backend/utils/adt/oracle_compat.c
@@ -213,15 +213,30 @@ lpad(PG_FUNCTION_ARGS)
ptr2end = ptr2 + s2len;
ptr_ret = VARDATA(ret);
- while (m--)
+ if (s2len == 1 && m > 0)
{
- int mlen = pg_mblen_range(ptr2, ptr2end);
+ /*
+ * A one-byte padding string is a single character repeated m times,
+ * so fill it in with one memset() rather than one memcpy() per
+ * character. pg_mblen_range() is still called once so that a lone
+ * lead byte of a multibyte character is rejected as before.
+ */
+ (void) pg_mblen_range(ptr2, ptr2end);
+ memset(ptr_ret, *ptr2, m);
+ ptr_ret += m;
+ }
+ else
+ {
+ 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;
+ memcpy(ptr_ret, ptr2, mlen);
+ ptr_ret += mlen;
+ ptr2 += mlen;
+ if (ptr2 == ptr2end) /* wrap around at end of s2 */
+ ptr2 = ptr2start;
+ }
}
ptr1 = VARDATA_ANY(string1);
@@ -323,15 +338,25 @@ rpad(PG_FUNCTION_ARGS)
ptr2 = ptr2start = VARDATA_ANY(string2);
ptr2end = ptr2 + s2len;
- while (m--)
+ if (s2len == 1 && m > 0)
+ {
+ /* Same one-byte padding fast path as in lpad() */
+ (void) pg_mblen_range(ptr2, ptr2end);
+ memset(ptr_ret, *ptr2, m);
+ ptr_ret += m;
+ }
+ else
{
- int mlen = pg_mblen_range(ptr2, ptr2end);
+ 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;
+ memcpy(ptr_ret, ptr2, mlen);
+ ptr_ret += mlen;
+ ptr2 += mlen;
+ if (ptr2 == ptr2end) /* wrap around at end of s2 */
+ ptr2 = ptr2start;
+ }
}
SET_VARSIZE(ret, ptr_ret - (char *) ret);
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.17.1
^ permalink raw reply [nested|flat] 7+ messages in thread
* Re: Speed up lpad() and rpad() for one-byte padding strings
@ 2026-09-23 14:41 Nathan Bossart <nathandbossart@gmail.com>
parent: Sehrope Sarkuni <sehrope@jackdb.com>
1 sibling, 2 replies; 7+ messages in thread
From: Nathan Bossart @ 2026-09-23 14:41 UTC (permalink / raw)
To: Sehrope Sarkuni <sehrope@jackdb.com>; +Cc: pgsql-hackers
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.
--
nathan
^ permalink raw reply [nested|flat] 7+ messages in thread
* Re: Speed up lpad() and rpad() for one-byte padding strings
@ 2026-09-23 17:09 Nathan Bossart <nathandbossart@gmail.com>
parent: Nathan Bossart <nathandbossart@gmail.com>
1 sibling, 1 reply; 7+ messages in thread
From: Nathan Bossart @ 2026-09-23 17:09 UTC (permalink / raw)
To: Sehrope Sarkuni <sehrope@jackdb.com>; +Cc: pgsql-hackers
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
Attachments:
[text/plain] v2-0001-Factor-the-padding-loop-out-of-lpad-and-rpad.patch (0B, ../../arQHtMApsI6MX-XH@nathan/2-v2-0001-Factor-the-padding-loop-out-of-lpad-and-rpad.patch)
download
^ permalink raw reply [nested|flat] 7+ messages in thread
* Re: Speed up lpad() and rpad() for one-byte padding strings
@ 2026-09-23 17:16 Sehrope Sarkuni <sehrope@jackdb.com>
parent: Nathan Bossart <nathandbossart@gmail.com>
1 sibling, 0 replies; 7+ messages in thread
From: Sehrope Sarkuni @ 2026-09-23 17:16 UTC (permalink / raw)
To: Nathan Bossart <nathandbossart@gmail.com>; +Cc: pgsql-hackers
On Wed, Sep 23, 2026 at 10:41 AM Nathan Bossart
<nathandbossart@gmail.com> 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.
I think the repeated pg_mblen_range() calls for every iteration are a
big factor too. I tried a different route that covers every pad
string (not just divisible) without explicit SIMD.
The attached v2 walks the pad string once to count its characters,
copies the whole repetitions as byte sequences, and runs the
per-character loop only for the partial final repetition. The whole
repetitions are written by copying one and then doubling the copied
region, so it takes log2(repetitions) memcpy() calls and memcpy()
does the vectorizing.
Validation is unchanged from master. The counting pass stops at the
number of characters needed, so a pad string ending in a lone lead
byte still errors only if the padding reaches that byte. The two
identical loops in lpad() and rpad() become a static pad_fill().
This replaces the memset() patch. On the one-byte case memset() was
5-7% faster than doubling (0.100 vs 0.107 ms at 1M), which does not
seem worth a separate fast path, and the multi-character controls that
were 5% slower with v1 now get the same speedup as everything else.
Same setup as before, median ms of 5 rounds:
SELECT octet_length(rpad('x', N, PAD))
PAD N before after
' ' 1000000 4.852 0.108
'ab' 1000000 4.822 0.111
'abc' 999999 4.824 0.107 (exact multiple)
'abc' 1000000 4.793 0.108 (partial tail)
'abcd' 1000000 4.809 0.110
16 chars 1000000 5.012 0.107
100 chars 1000000 4.917 0.110
'é' 1000000 5.394 0.155
'aéb' 999999 5.012 0.126 (exact multiple)
'aéb' 1000000 4.994 0.122 (partial tail)
' ' 10000000 53.705 5.466
'ab' 10000000 53.376 5.413
'abc' 1000 0.063 0.057
'abc' 10 0.056 0.056
This is more of a change than just adding the memset() fastpath, but I
think the end result of the code is easier to follow too with both
lpad() and rpad() sharing the helper.
Regards,
-- Sehrope Sarkuni
Founder & CEO | JackDB, Inc. | https://www.jackdb.com/
Attachments:
[text/x-patch] v2-0001-Copy-whole-repetitions-of-the-pad-string-at-once-.patch (9.0K, ../../CAH7T-ao_8pUW0gKs0aX0He-zff-fxPe7sd1PZOCX91=Xi6T=qg@mail.gmail.com/2-v2-0001-Copy-whole-repetitions-of-the-pad-string-at-once-.patch)
download | inline diff:
From 512b8c05da4d7db8108a3ea9234f09307d35ed15 Mon Sep 17 00:00:00 2001
From: Sehrope Sarkuni <sehrope@jackdb.com>
Date: Wed, 23 Sep 2026 15:29:23 +0000
Subject: [PATCH v2] Copy whole repetitions of the pad string at once in lpad()
and rpad()
The padding loop called pg_mblen_range() and memcpy() once per
character. Walk the pad string once to count its characters, copy the
whole repetitions as byte sequences by doubling the copied region, and
use the per-character loop only for the partial final repetition.
The pad string is validated as far as before, which is all of it when
a full repetition is copied and otherwise only the characters copied.
---
src/backend/utils/adt/oracle_compat.c | 101 +++++++++++++++++--------
src/test/regress/expected/encoding.out | 37 +++++++++
src/test/regress/expected/strings.out | 26 +++++++
src/test/regress/sql/encoding.sql | 10 +++
src/test/regress/sql/strings.sql | 7 ++
5 files changed, 150 insertions(+), 31 deletions(-)
diff --git a/src/backend/utils/adt/oracle_compat.c b/src/backend/utils/adt/oracle_compat.c
index 7422a454397..c2c58f28e38 100644
--- a/src/backend/utils/adt/oracle_compat.c
+++ b/src/backend/utils/adt/oracle_compat.c
@@ -143,6 +143,74 @@ casefold(PG_FUNCTION_ARGS)
}
+/*
+ * Write m characters of padding at dst, taken cyclically from the pad
+ * string of padlen bytes, and return the number of bytes written.
+ *
+ * The pad string is validated with pg_mblen_range() only as far as it is
+ * used, so an incomplete multibyte character at its end is an error only
+ * if the padding reaches it.
+ */
+static int
+pad_fill(char *dst, const char *pad, int padlen, int m)
+{
+ const char *padend = pad + padlen;
+ const char *p = pad;
+ int nchars = 0;
+ int nrep;
+ int total;
+ int copied;
+
+ if (m <= 0)
+ return 0;
+
+ /* count the characters of one repetition, stopping at m */
+ while (p < padend && nchars < m)
+ {
+ p += pg_mblen_range(p, padend);
+ nchars++;
+ }
+
+ /* fewer than one repetition is needed, so copy the first m characters */
+ if (p < padend)
+ {
+ memcpy(dst, pad, p - pad);
+ return p - pad;
+ }
+
+ /*
+ * Whole repetitions are byte copies of the pad string. Copy one, then
+ * double the copied region until all of them are written, so the number
+ * of memcpy() calls is logarithmic in the number of repetitions. total
+ * cannot overflow, since the caller sized the output for m characters.
+ */
+ nrep = m / nchars;
+ total = nrep * padlen;
+ memcpy(dst, pad, padlen);
+ copied = padlen;
+ while (copied < total)
+ {
+ int n = Min(copied, total - copied);
+
+ memcpy(dst + copied, dst, n);
+ copied += n;
+ }
+
+ /* partial final repetition, one character at a time */
+ m -= nrep * nchars;
+ p = pad;
+ while (m-- > 0)
+ {
+ int mlen = pg_mblen_range(p, padend);
+
+ memcpy(dst + copied, p, mlen);
+ copied += mlen;
+ p += mlen;
+ }
+
+ return copied;
+}
+
/********************************************************************
*
* lpad
@@ -167,10 +235,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 +274,9 @@ 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 += pad_fill(ptr_ret, VARDATA_ANY(string2), s2len, m);
ptr1 = VARDATA_ANY(string1);
@@ -265,10 +319,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 +371,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 += pad_fill(ptr_ret, VARDATA_ANY(string2), s2len, m);
SET_VARSIZE(ret, ptr_ret - (char *) ret);
diff --git a/src/test/regress/expected/encoding.out b/src/test/regress/expected/encoding.out
index 0bb72a1df6f..9fc871215b0 100644
--- a/src/test/regress/expected/encoding.out
+++ b/src/test/regress/expected/encoding.out
@@ -60,6 +60,43 @@ SELECT reverse(good) FROM regress_encoding;
éfac
(1 row)
+-- multibyte pad strings: whole repetitions, a partial final repetition, and
+-- fewer than one repetition
+SELECT lpad(good, 7, 'é'), rpad(good, 7, 'é') FROM regress_encoding;
+ lpad | rpad
+---------+---------
+ ééécafé | caféééé
+(1 row)
+
+SELECT lpad(good, 12, 'éab'), rpad(good, 12, 'éab') FROM regress_encoding;
+ lpad | rpad
+--------------+--------------
+ éabéabéacafé | cafééabéabéa
+(1 row)
+
+SELECT lpad(good, 5, 'éab'), rpad(good, 5, 'éab') FROM regress_encoding;
+ lpad | rpad
+-------+-------
+ écafé | caféé
+(1 row)
+
+-- a lone lead byte in the pad string is an error if the padding reaches it
+SELECT lpad(good, 7, test_bytea_to_text('\xc3')) FROM regress_encoding;
+ERROR: invalid byte sequence for encoding "UTF8": 0xc3
+SELECT rpad(good, 7, 'ab' || test_bytea_to_text('\xc3')) FROM regress_encoding;
+ERROR: invalid byte sequence for encoding "UTF8": 0xc3
+SELECT lpad(good, 5, 'ab' || test_bytea_to_text('\xc3')), rpad(good, 6, 'ab' || test_bytea_to_text('\xc3')) FROM regress_encoding;
+ lpad | rpad
+-------+--------
+ acafé | caféab
+(1 row)
+
+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/expected/strings.out b/src/test/regress/expected/strings.out
index fa29abfd829..6e064e3807f 100644
--- a/src/test/regress/expected/strings.out
+++ b/src/test/regress/expected/strings.out
@@ -3441,6 +3441,32 @@ SELECT rpad('hi', 5, '');
hi
(1 row)
+-- whole repetitions of the pad string, a partial final repetition, and
+-- fewer than one repetition
+SELECT lpad('hi', 8, 'abc'), rpad('hi', 8, 'abc');
+ lpad | rpad
+----------+----------
+ abcabchi | hiabcabc
+(1 row)
+
+SELECT lpad('hi', 9, 'abc'), rpad('hi', 9, 'abc');
+ lpad | rpad
+-----------+-----------
+ abcabcahi | hiabcabca
+(1 row)
+
+SELECT lpad('hi', 12, 'ab'), rpad('hi', 12, 'ab');
+ lpad | rpad
+--------------+--------------
+ abababababhi | hiababababab
+(1 row)
+
+SELECT lpad('hi', 3, 'abc'), rpad('hi', 3, 'abc');
+ lpad | rpad
+------+------
+ ahi | hia
+(1 row)
+
SELECT ltrim('zzzytrim', 'xyz');
ltrim
-------
diff --git a/src/test/regress/sql/encoding.sql b/src/test/regress/sql/encoding.sql
index 26caa93a5d5..3ea6e54e52d 100644
--- a/src/test/regress/sql/encoding.sql
+++ b/src/test/regress/sql/encoding.sql
@@ -37,6 +37,16 @@ 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;
+-- multibyte pad strings: whole repetitions, a partial final repetition, and
+-- fewer than one repetition
+SELECT lpad(good, 7, 'é'), rpad(good, 7, 'é') FROM regress_encoding;
+SELECT lpad(good, 12, 'éab'), rpad(good, 12, 'éab') FROM regress_encoding;
+SELECT lpad(good, 5, 'éab'), rpad(good, 5, 'éab') FROM regress_encoding;
+-- a lone lead byte in the pad string is an error if the padding reaches it
+SELECT lpad(good, 7, test_bytea_to_text('\xc3')) FROM regress_encoding;
+SELECT rpad(good, 7, 'ab' || test_bytea_to_text('\xc3')) FROM regress_encoding;
+SELECT lpad(good, 5, 'ab' || test_bytea_to_text('\xc3')), rpad(good, 6, 'ab' || test_bytea_to_text('\xc3')) FROM regress_encoding;
+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;
diff --git a/src/test/regress/sql/strings.sql b/src/test/regress/sql/strings.sql
index 7d9c7275a02..04651a0a46f 100644
--- a/src/test/regress/sql/strings.sql
+++ b/src/test/regress/sql/strings.sql
@@ -1165,6 +1165,13 @@ SELECT rpad('hi', -5, 'xy');
SELECT rpad('hello', 2);
SELECT rpad('hi', 5, '');
+-- whole repetitions of the pad string, a partial final repetition, and
+-- fewer than one repetition
+SELECT lpad('hi', 8, 'abc'), rpad('hi', 8, 'abc');
+SELECT lpad('hi', 9, 'abc'), rpad('hi', 9, 'abc');
+SELECT lpad('hi', 12, 'ab'), rpad('hi', 12, 'ab');
+SELECT lpad('hi', 3, 'abc'), rpad('hi', 3, 'abc');
+
SELECT ltrim('zzzytrim', 'xyz');
SELECT translate('', '14', 'ax');
--
2.43.0
^ permalink raw reply [nested|flat] 7+ messages in thread
* Re: Speed up lpad() and rpad() for one-byte padding strings
@ 2026-09-23 17:19 Sehrope Sarkuni <sehrope@jackdb.com>
parent: Nathan Bossart <nathandbossart@gmail.com>
0 siblings, 1 reply; 7+ messages in thread
From: Sehrope Sarkuni @ 2026-09-23 17:19 UTC (permalink / raw)
To: Nathan Bossart <nathandbossart@gmail.com>; +Cc: pgsql-hackers
On Wed, Sep 23, 2026 at 1:09 PM Nathan Bossart <nathandbossart@gmail.com> wrote:
>
> 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.
Ah! just saw this after I hit send.
I think my version does the rest of what you're describing!
Exact conclusion reached from testing it too.
Regards,
-- Sehrope Sarkuni
Founder & CEO | JackDB, Inc. | https://www.jackdb.com/
^ permalink raw reply [nested|flat] 7+ messages in thread
* Re: Speed up lpad() and rpad() for one-byte padding strings
@ 2026-09-23 22:51 Sehrope Sarkuni <sehrope@jackdb.com>
parent: Sehrope Sarkuni <sehrope@jackdb.com>
0 siblings, 0 replies; 7+ messages in thread
From: Sehrope Sarkuni @ 2026-09-23 22:51 UTC (permalink / raw)
To: Nathan Bossart <nathandbossart@gmail.com>; +Cc: pgsql-hackers
On Wed, Sep 23, 2026 at 1:19 PM Sehrope Sarkuni <sehrope@jackdb.com> wrote:
>
> On Wed, Sep 23, 2026 at 1:09 PM Nathan Bossart <nathandbossart@gmail.com> wrote:
> >
> > 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.
>
> Ah! just saw this after I hit send.
I like your split with the refactor into the separate function first
better. It makes the second piece purely the perf improvement. And
the copy-as-you-count for the first piece is nifty.
Attached is v4 (retroactively referring to my v2, as v3). I stepped
through and renamed it a bit. The rest of it is your v2 with some
updated tests.
Passes tests, CI, and the numbers match my v3.
Regards,
-- Sehrope Sarkuni
Founder & CEO | JackDB, Inc. | https://www.jackdb.com/
Attachments:
[text/x-patch] v4-0001-Factor-the-padding-loop-out-of-lpad-and-rpad.patch (2.9K, ../../CAH7T-ap_DTWMi+5y5AoQfnHPWgw8LTfqXibH-88EFfiT-TnuTA@mail.gmail.com/2-v4-0001-Factor-the-padding-loop-out-of-lpad-and-rpad.patch)
download | inline diff:
From d8a3b9507845c28c2e458cd57637524e1eacfc95 Mon Sep 17 00:00:00 2001
From: Nathan Bossart <nathan@postgresql.org>
Date: Wed, 23 Sep 2026 11:47:02 -0500
Subject: [PATCH v4 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..e5238e44813 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 pad (padlen bytes) to dst,
+ * cycling through pad as needed, and return a pointer past the last byte
+ * written.
+ */
+static char *
+append_padding(char *dst, const char *pad, int padlen, int m)
+{
+ const char *p = pad;
+ const char *pend = pad + padlen;
+
+ while (m--)
+ {
+ int mlen = pg_mblen_range(p, pend);
+
+ memcpy(dst, p, mlen);
+ dst += mlen;
+ p += mlen;
+ if (p == pend) /* wrap around at end of pad */
+ p = pad;
+ }
+
+ 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.17.1
[text/x-patch] v4-0002-Optimize-padding-in-lpad-and-rpad.patch (7.9K, ../../CAH7T-ap_DTWMi+5y5AoQfnHPWgw8LTfqXibH-88EFfiT-TnuTA@mail.gmail.com/3-v4-0002-Optimize-padding-in-lpad-and-rpad.patch)
download | inline diff:
From a5007ff32afe3bd608a88d0f64a79bdb327e8448 Mon Sep 17 00:00:00 2001
From: Sehrope Sarkuni <sehrope@jackdb.com>
Date: Wed, 23 Sep 2026 21:41:57 +0000
Subject: [PATCH v4 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.
---
src/backend/utils/adt/oracle_compat.c | 47 ++++++++++++++++++++++++--
src/test/regress/expected/encoding.out | 37 ++++++++++++++++++++
src/test/regress/expected/strings.out | 26 ++++++++++++++
src/test/regress/sql/encoding.sql | 10 ++++++
src/test/regress/sql/strings.sql | 7 ++++
5 files changed, 124 insertions(+), 3 deletions(-)
diff --git a/src/backend/utils/adt/oracle_compat.c b/src/backend/utils/adt/oracle_compat.c
index e5238e44813..f457e01a2ae 100644
--- a/src/backend/utils/adt/oracle_compat.c
+++ b/src/backend/utils/adt/oracle_compat.c
@@ -147,22 +147,63 @@ casefold(PG_FUNCTION_ARGS)
* Append m characters of the padding string pad (padlen bytes) to dst,
* cycling through pad as needed, and return a pointer past the last byte
* written.
+ *
+ * The pad string is validated with pg_mblen_range() only as far as it is
+ * used, so an incomplete multibyte character at its end is an error only
+ * if the padding reaches it.
*/
static char *
append_padding(char *dst, const char *pad, int padlen, int m)
{
const char *p = pad;
const char *pend = pad + padlen;
+ char *start = dst;
+ int nchars = 0;
+ int nbytes;
+ int written;
- while (m--)
+ /* copy pad once, one character at a time, or until m runs out */
+ while (m > 0 && p < pend)
{
int mlen = pg_mblen_range(p, pend);
memcpy(dst, p, mlen);
dst += mlen;
p += mlen;
- if (p == pend) /* wrap around at end of pad */
- p = pad;
+ m--;
+ nchars++;
+ }
+
+ if (m == 0)
+ return dst;
+
+ /*
+ * The rest of the padding is pad repeated, so work out how many bytes
+ * that is: whole copies of pad, plus the first m % nchars characters of
+ * one more.
+ */
+ nbytes = (m / nchars) * padlen;
+ p = pad;
+ for (m %= nchars; m > 0; m--)
+ p += pg_mblen_unbounded(p);
+ nbytes += p - pad;
+
+ /*
+ * Produce those bytes by copying what has already been written onto the
+ * end, doubling the length each time, so the work is done by a few large
+ * memcpy() calls rather than one per character. The last chunk, if
+ * shorter, is a prefix of the padding written so far and therefore of
+ * pad, which is the partial final repetition.
+ */
+ 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..9fc871215b0 100644
--- a/src/test/regress/expected/encoding.out
+++ b/src/test/regress/expected/encoding.out
@@ -60,6 +60,43 @@ SELECT reverse(good) FROM regress_encoding;
éfac
(1 row)
+-- multibyte pad strings: whole repetitions, a partial final repetition, and
+-- fewer than one repetition
+SELECT lpad(good, 7, 'é'), rpad(good, 7, 'é') FROM regress_encoding;
+ lpad | rpad
+---------+---------
+ ééécafé | caféééé
+(1 row)
+
+SELECT lpad(good, 12, 'éab'), rpad(good, 12, 'éab') FROM regress_encoding;
+ lpad | rpad
+--------------+--------------
+ éabéabéacafé | cafééabéabéa
+(1 row)
+
+SELECT lpad(good, 5, 'éab'), rpad(good, 5, 'éab') FROM regress_encoding;
+ lpad | rpad
+-------+-------
+ écafé | caféé
+(1 row)
+
+-- a lone lead byte in the pad string is an error if the padding reaches it
+SELECT lpad(good, 7, test_bytea_to_text('\xc3')) FROM regress_encoding;
+ERROR: invalid byte sequence for encoding "UTF8": 0xc3
+SELECT rpad(good, 7, 'ab' || test_bytea_to_text('\xc3')) FROM regress_encoding;
+ERROR: invalid byte sequence for encoding "UTF8": 0xc3
+SELECT lpad(good, 5, 'ab' || test_bytea_to_text('\xc3')), rpad(good, 6, 'ab' || test_bytea_to_text('\xc3')) FROM regress_encoding;
+ lpad | rpad
+-------+--------
+ acafé | caféab
+(1 row)
+
+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/expected/strings.out b/src/test/regress/expected/strings.out
index fa29abfd829..6e064e3807f 100644
--- a/src/test/regress/expected/strings.out
+++ b/src/test/regress/expected/strings.out
@@ -3441,6 +3441,32 @@ SELECT rpad('hi', 5, '');
hi
(1 row)
+-- whole repetitions of the pad string, a partial final repetition, and
+-- fewer than one repetition
+SELECT lpad('hi', 8, 'abc'), rpad('hi', 8, 'abc');
+ lpad | rpad
+----------+----------
+ abcabchi | hiabcabc
+(1 row)
+
+SELECT lpad('hi', 9, 'abc'), rpad('hi', 9, 'abc');
+ lpad | rpad
+-----------+-----------
+ abcabcahi | hiabcabca
+(1 row)
+
+SELECT lpad('hi', 12, 'ab'), rpad('hi', 12, 'ab');
+ lpad | rpad
+--------------+--------------
+ abababababhi | hiababababab
+(1 row)
+
+SELECT lpad('hi', 3, 'abc'), rpad('hi', 3, 'abc');
+ lpad | rpad
+------+------
+ ahi | hia
+(1 row)
+
SELECT ltrim('zzzytrim', 'xyz');
ltrim
-------
diff --git a/src/test/regress/sql/encoding.sql b/src/test/regress/sql/encoding.sql
index 26caa93a5d5..3ea6e54e52d 100644
--- a/src/test/regress/sql/encoding.sql
+++ b/src/test/regress/sql/encoding.sql
@@ -37,6 +37,16 @@ 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;
+-- multibyte pad strings: whole repetitions, a partial final repetition, and
+-- fewer than one repetition
+SELECT lpad(good, 7, 'é'), rpad(good, 7, 'é') FROM regress_encoding;
+SELECT lpad(good, 12, 'éab'), rpad(good, 12, 'éab') FROM regress_encoding;
+SELECT lpad(good, 5, 'éab'), rpad(good, 5, 'éab') FROM regress_encoding;
+-- a lone lead byte in the pad string is an error if the padding reaches it
+SELECT lpad(good, 7, test_bytea_to_text('\xc3')) FROM regress_encoding;
+SELECT rpad(good, 7, 'ab' || test_bytea_to_text('\xc3')) FROM regress_encoding;
+SELECT lpad(good, 5, 'ab' || test_bytea_to_text('\xc3')), rpad(good, 6, 'ab' || test_bytea_to_text('\xc3')) FROM regress_encoding;
+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;
diff --git a/src/test/regress/sql/strings.sql b/src/test/regress/sql/strings.sql
index 7d9c7275a02..04651a0a46f 100644
--- a/src/test/regress/sql/strings.sql
+++ b/src/test/regress/sql/strings.sql
@@ -1165,6 +1165,13 @@ SELECT rpad('hi', -5, 'xy');
SELECT rpad('hello', 2);
SELECT rpad('hi', 5, '');
+-- whole repetitions of the pad string, a partial final repetition, and
+-- fewer than one repetition
+SELECT lpad('hi', 8, 'abc'), rpad('hi', 8, 'abc');
+SELECT lpad('hi', 9, 'abc'), rpad('hi', 9, 'abc');
+SELECT lpad('hi', 12, 'ab'), rpad('hi', 12, 'ab');
+SELECT lpad('hi', 3, 'abc'), rpad('hi', 3, 'abc');
+
SELECT ltrim('zzzytrim', 'xyz');
SELECT translate('', '14', 'ax');
--
2.17.1
^ permalink raw reply [nested|flat] 7+ messages in thread
* Re: Speed up lpad() and rpad() for one-byte padding strings
@ 2026-09-24 05:21 John Naylor <johncnaylorls@gmail.com>
parent: Sehrope Sarkuni <sehrope@jackdb.com>
1 sibling, 0 replies; 7+ messages in thread
From: John Naylor @ 2026-09-24 05:21 UTC (permalink / raw)
To: Sehrope Sarkuni <sehrope@jackdb.com>; +Cc: pgsql-hackers
On Wed, Sep 23, 2026 at 9:10 PM Sehrope Sarkuni <sehrope@jackdb.com> wrote:
> Timings on an AMD Ryzen 7 5700G, release build (-O3, no asserts),
> pgbench -c 1 with one statement per transaction, alternating
> before/after rounds, median latency in ms of 5 rounds (3 at 100M):
>
> SELECT octet_length(rpad('x', N, ' '))
> or
> SELECT octet_length(lpad('x', N, '0'))
>
> N rpad before after lpad before after
> 1 0.056 0.056 0.057 0.056
> 10 0.056 0.056 0.057 0.056
> 100 0.056 0.056 0.057 0.057
100 is already far beyond the usual N values I've seen in real life,
and there is no measured difference here, so I don't see what problem
this is solving.
--
John Naylor
Amazon Web Services
^ permalink raw reply [nested|flat] 7+ messages in thread
end of thread, other threads:[~2026-09-24 05:21 UTC | newest]
Thread overview: 7+ messages (download: mbox mbox.gz follow: Atom feed)
-- links below jump to the message on this page --
2026-09-23 14:10 Speed up lpad() and rpad() for one-byte padding strings Sehrope Sarkuni <sehrope@jackdb.com>
2026-09-23 14:41 ` Nathan Bossart <nathandbossart@gmail.com>
2026-09-23 17:09 ` Nathan Bossart <nathandbossart@gmail.com>
2026-09-23 17:19 ` Sehrope Sarkuni <sehrope@jackdb.com>
2026-09-23 22:51 ` Sehrope Sarkuni <sehrope@jackdb.com>
2026-09-23 17:16 ` Sehrope Sarkuni <sehrope@jackdb.com>
2026-09-24 05:21 ` John Naylor <johncnaylorls@gmail.com>
This inbox is served by agora; see mirroring instructions
for how to clone and mirror all data and code used for this inbox