Speed up lpad() and rpad() for one-byte padding strings
Hackorum builds and tests every patch posted to the lists, not only commitfest submissions. This is Hackorum's own CI rather than the PostgreSQL project's, and it is still under testing - please report anything that looks wrong.
You can run a PostgreSQL built from this patch straight from Docker, with no checkout and no build:
docker run --rm -p 5432:5432 ghcr.io/hackorum-dev/postgres-patch:t253908psql -h localhost -U postgresBuilt from patchset v10 (message #10), October 22, 2026 at 09:58 AM.
Every patchset is also pushed to a branch of our PostgreSQL fork, so you can check out the same tree CI built. Without a PostgreSQL checkout:
git clone --branch t253908_10 https://github.com/hackorum-dev/postgres.gitIn a checkout you already have, add the fork once:
git remote add hackorum https://github.com/hackorum-dev/postgres.gitthen, for this patchset and every later one:
git fetch hackorum t253908_10 && git checkout t253908_10Patchset v10 (message #10) is on t253908_10
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/
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
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
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/
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/
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:
t253908_6v4-0001-Factor-the-padding-loop-out-of-lpad-and-rpad.patchtext/x-patch; charset=US-ASCII; name=v4-0001-Factor-the-padding-loop-out-of-lpad-and-rpad.patchDownload+27-34
v4-0002-Optimize-padding-in-lpad-and-rpad.patchtext/x-patch; charset=UTF-8; name=v4-0002-Optimize-padding-in-lpad-and-rpad.patchDownload+124-4
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
On Thu, Sep 24, 2026 at 1:21 AM John Naylor <johncnaylorls@gmail.com> wrote:
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.057100 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.
That's probably true for the usual formatting uses.
But large N does show up for test data. We already have this in
src/test/regress/sql/join_hash.sql:
--- Make a relation with several enormous tuples.
create table wide as select generate_series(1, 3) as id, rpad('',
320000, 'x') as t;There are similar uses in benchmarks and reproducers in the wild too.
So I don't think large N is particularly artificial. We also have lots
of places in the tree doing essentially the same thing with
'foo' || repeat('bar', large_N) to generate test data.
Regards,
-- Sehrope Sarkuni
Founder & CEO | JackDB, Inc. | https://www.jackdb.com/
On 23/09/2026 20:19, Sehrope Sarkuni 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 think my version does the rest of what you're describing!
Exact conclusion reached from testing it too.
See also similar thread on REPEAT():
/messages/by-id/tencent_C5BBECF985A270FBC49463EDAF722CD5E005@qq.com.
Whatever we do here, let's use the same implementation for REPEAT(),
LPAD(), and RPAD().
- Heikki
On Thu, Sep 24, 2026 at 7:20 AM Heikki Linnakangas <hlinnaka@iki.fi> wrote:
See also similar thread on REPEAT():
/messages/by-id/tencent_C5BBECF985A270FBC49463EDAF722CD5E005@qq.com.
Thanks for linking to that. A lot overlap in ideas and results too.
Whatever we do here, let's use the same implementation for REPEAT(),
LPAD(), and RPAD().
Attached v5 moves the doubling copy into its own helper so repeat()
can use it too.
0001 is the refactor for rpad/lpad to use append_padding().
0002 adds repeat_bytes(dst, src, srclen, count) and rebuilds
append_padding() on it.
0003 replaces repeat()'s per-copy loop with a call to repeat_bytes().
repeat_bytes() copies the string once, doubles the copied region
until it is at least 16 kB, and then copies that region repeatedly
with a CHECK_FOR_INTERRUPTS() per copy. Pure doubling in v4 was 6-8%
slower than master's loop for repeat() with a source of 100 bytes or
more and a 100 MB result, because the loop's source stays in L1 while
the doubling reads back what it just wrote.
The fixed block keeps the source in cache and puts those cases back
at parity, while still needing only a few calls for short strings.
It also keeps large results cancellable. With and without the
interrupts check was not measurable.
Timings on an AMD Ryzen 7 5700G, release build (-O3, no asserts),
pgbench -c 1, alternating before/after rounds, median ms of 5 rounds.
Pad is 'abcdefghij' repeated and cut to len. N is the result size in
bytes. Each cell is master / patched.
# repeat(pad, N / len)
len \ N 10k 100k 1M 10M 100M
1 0.088 / 0.056 0.422 / 0.102 3.88 / 0.83 39.5 / 9.1 393 / 97
10 0.061 / 0.056 0.128 / 0.102 1.10 / 0.83 11.5 / 8.9 121 / 97
100 0.058 / 0.058 0.105 / 0.102 0.85 / 0.83 9.2 / 8.9 96 / 96
1000 0.058 / 0.059 0.106 / 0.105 0.84 / 0.83 9.2 / 9.0 95 / 95
10000 0.078 / 0.083 0.123 / 0.124 0.85 / 0.86 8.9 / 9.2 97 / 95
# rpad('x', N, pad)
len \ N 10k 100k 1M 10M 100M
1 0.106 / 0.057 0.548 / 0.061 4.80 / 0.11 53.7 / 5.7 560 / 97
10 0.105 / 0.057 0.543 / 0.061 4.83 / 0.12 52.5 / 5.6 564 / 97
100 0.107 / 0.058 0.560 / 0.062 4.89 / 0.12 53.6 / 5.5 564 / 96
1000 0.109 / 0.064 0.563 / 0.069 4.89 / 0.13 53.5 / 5.8 560 / 96
10000 0.129 / 0.107 0.576 / 0.129 5.02 / 0.18 53.2 / 5.7 566 / 97
Tests are the lpad/rpad set from v3 plus some additional ones to go
past the 16K doubling limit.
On this machine, block sizes from 16 kB up to 4 MB performed the same
within noise, while 16 MB was consistently slower for large results,
much like v4's pure doubling. So I don't see a reason to go bigger
than 16 kB.
The doubling approach for repeat() was proposed by Chenhui Mo in [1].
Jeevan Chalke, Heikki Linnakangas, David Rowley, and Jan Nidzwetzki
also discussed and benchmarked capped/fixed-size variants there, and
that work shaped the fixed-size block used here.
This series overlaps with the repeat() work linked above, so the two are not
independent. The v2 series there, currently marked Ready for Committer,
contains the empty-result and single-byte memset() changes but leaves
the doubling change out.
Regards,
-- Sehrope Sarkuni
Founder & CEO | JackDB, Inc. | https://www.jackdb.com/
Attachments:
t253908_10v5-0001-Factor-the-padding-loop-out-of-lpad-and-rpad.patchapplication/x-patch; name=v5-0001-Factor-the-padding-loop-out-of-lpad-and-rpad.patchDownload+27-34
v5-0003-Use-repeat_bytes-in-repeat.patchapplication/x-patch; name=v5-0003-Use-repeat_bytes-in-repeat.patchDownload+25-12
v5-0002-Copy-whole-repetitions-of-the-pad-string-at-once-.patchapplication/x-patch; name=v5-0002-Copy-whole-repetitions-of-the-pad-string-at-once-.patchDownload+174-9
Hi,
Sehrope Sarkuni <sehrope@jackdb.com> wrote:
On this machine, block sizes from 16 kB up to 4 MB performed the same
within noise, while 16 MB was consistently slower for large results,
much like v4's pure doubling. So I don't see a reason to go bigger
than 16 kB.
I ran v5 on a different x86 machine: an AMD Ryzen AI 9 HX 370 (Zen 5),
glibc 2.43, where x86_non_temporal_threshold is 6 MiB. Release builds
of master 2c10c2ce4d7, with your method: pgbench -c 1, rounds
alternating between builds, median of 5. This CPU mixes Zen 5 and
Zen 5c cores, so the server was pinned to one Zen 5 core. I also
included Chenhui's v2 from the repeat() thread (Ready for Committer),
since 0003 replaces the same loop.
1. Block size
The repeat() thread found the best block to be the first one at or
above glibc's non-temporal threshold, on three Intel machines. To
test that here, I built v5 with REPEAT_BYTES_BLOCK = 8 MB, above the
6 MiB threshold, and ran that build a second time with non-temporal
stores disabled through GLIBC_TUNABLES.
At 100 MB the three stay within the round-to-round spread (about 10%)
for repeat() and rpad() with 1-, 10- and 100-byte sources. For
example, repeat() with a 10-byte source took 46.8 ms with 16 kB,
50.4 ms with 8 MB, and 46.7 ms with 8 MB and no non-temporal stores.
So the effect seen on the Intel machines does not show up on this
Zen 5, and 16 kB costs nothing here.
2. repeat() against the Ready for Committer patch
- 1-byte source, 100 MB: master 173.1 ms, v5 47.2 ms, RfC 47.7 ms
- 1-byte source, 16 MB: master 27.3 ms, v5 7.0 ms, RfC 6.7 ms
- 10-byte source, 100 MB: master 58.6 ms, v5 46.8 ms, RfC 55.3 ms
- 100-byte source, 100 MB: master 46.8 ms, v5 44.9 ms
So on this machine dropping the memset() path costs nothing for a
one-byte source, and v5 also speeds up the 10-byte case, which the RfC
patch does not touch. Jan's M5 Max numbers upthread had chunked
memset() well behind a single one. I have no ARM machine to check
whether that carries over to repeat_bytes().
3. rpad(), 100 MB
- 1-byte pad: master 330.6 ms, v5 45.5 ms
- 10-byte pad: master 342.5 ms, v5 44.6 ms
- 100-byte pad: master 325.9 ms, v5 43.2 ms
4. Results are unchanged
I compared lpad(), rpad() and repeat() output between master and v5
in UTF8, EUC_JP and SQL_ASCII databases: 6075 calls, with lengths
around the 16 kB and 8 MB boundaries, multibyte and mixed pads with
partial tails, and sizes near the 1 GB limit. Lengths, md5 of every
result and error messages are identical, including the same 16
"requested length too large" errors. Invalid pad strings are not in
it, since the encoding.sql tests cover those.
5. Cancellation
On master, lpad() and rpad() have no CHECK_FOR_INTERRUPTS() in the
padding loop. With statement_timeout = 20ms,
rpad('x', 268000000, 'ab') runs for about 900 ms, the whole call,
before the cancel takes effect. With v5 it is cancelled after about
24 ms, as repeat() already is on master (21 ms), because the padding
now goes through repeat_bytes().
Scripts, raw timings and outputs are in the attachment.
Regards,
Manu
Attachments:
nocfbot-pad-v5-review.txttext/plainDownload
Hi,
Manu wrote:
I have no ARM machine to check whether that carries over to
repeat_bytes().
I ran v5 on an Apple M2 Max. It does not carry over. repeat() with a
one byte source matches the memset() patch, and rpad() to 100M goes
from 304 ms to 5.5 ms.
For the short cases I counted instructions instead of time, by reading
proc_pid_rusage() for the backend around each statement. Two master
servers agree to within one instruction per call.
Two things are slower than master.
lpad(s, 7, '0') takes 772 instructions per call against 694 on master.
Padding costs more up to three characters and breaks even at four.
repeat() with a 1000 byte source and a 10M result runs fewer
instructions, 4.06M against 4.33M, but is 24% slower. So that one is
memory cost. Changing the block size does not help here.
Thanks,
Shihao