Re: [PATCH] Speed up repeat() for larger counts

Hi Hackers,

On 28.07.26 04:15, Jeevan Chalke wrote:
> On Mon, Jul 27, 2026 at 7:11 PM David Rowley <dgrowleyml(at)gmail(dot)com <mailto:dgrowleyml(at)gmail(dot)com>> wrote:
> On Mon, 27 Jul 2026 at 22:18, Heikki Linnakangas <hlinnaka(at)iki(dot)fi <mailto:hlinnaka(at)iki(dot)fi>> wrote:
> > Beyond certain size, I'd guess it might even become slower, if the
> > string no longer fits in the L0 CPU cache for example. Also, if the
> > fast-path used a constant size, like 64 bytes, maybe the compiler could
> > optimize the memcpy() into a single SIMD instruction or something.
>
> I read this earlier and wondered the same thing. The thing that might
> save it would be the hardware prefetcher seeing the linear memory
> access and loading the cachelines back again before there's a stall.
> However, that assumes memory can keep up with a modern memcpy(), and I
> believe that a good AVX512 memcpy could well outpace even DDR5 RAM
> speed. Capping the chunks at something L1-sized might solve that. It
> might be worth the author looking at what I did with
> ESCAPE_JSON_FLUSH_AFTER in json.c. Benchmarks for that in [1]. I
> expect it'll be diminishing returns with memcpy sizes beyond a handful
> of kilobytes.
>
> It does feel like a rather incomplete performance patch as it doesn't
> come with any results to demonstrate that it actually has a positive
> impact on performance. It would be good to see a script posted here
> that tests various input lengths and repeat counts that people could
> easily run to see if they get the same improvement on their hardware.
>
>
> +1. While the simple example shows good performance, I agree with David that having actual performance numbers and a script would be helpful here.

I ran a few experiments on two of my systems (a modern ARM CPU with
large caches and an older Intel CPU with small caches) using the patch
and the attached benchmark script (repeat_bench.sql).

* System 1: Debian 13.5 VM on an Apple M5 Max,
32MB of L2 cache / 24 MB of L3 cache,
36 GB RAM, gcc 14.2.0 -O2

* System 2: Debian 13.5 on an Intel Pentium Silver J5005,
4 MB L2 cache, no L3 cache,
16 GB RAM, gcc 14.2.0 -O2

Using the SQL benchmark script, I get these results:

System 1: Without the patch (master at 72e6184)
=====

jan2=# SELECT * FROM repeat_bench_sql();
output_mb | source_len | repeat_count | best_ms | ns_per_byte
-----------+------------+--------------+----------+-------------
0.0 | 0 | 10000000 | 15.8710 |
16.0 | 1 | 16777216 | 24.7230 | 1.4736
16.0 | 10 | 1677721 | 2.0880 | 0.1245
16.0 | 100 | 167772 | 0.5810 | 0.0346
16.0 | 1024 | 16384 | 0.5130 | 0.0306
16.0 | 4096 | 4096 | 0.5040 | 0.0300
16.0 | 16384 | 1024 | 0.4880 | 0.0291
16.0 | 65536 | 256 | 0.4010 | 0.0239
16.0 | 262144 | 64 | 0.5000 | 0.0298
16.0 | 1048576 | 16 | 0.5020 | 0.0299
64.0 | 1 | 67108864 | 111.7530 | 1.6652
64.0 | 10 | 6710886 | 14.8360 | 0.2211
64.0 | 100 | 671088 | 8.9660 | 0.1336
64.0 | 1024 | 65536 | 8.7150 | 0.1299
64.0 | 4096 | 16384 | 8.8710 | 0.1322
64.0 | 16384 | 4096 | 8.8390 | 0.1317
64.0 | 65536 | 1024 | 8.5130 | 0.1269
64.0 | 262144 | 256 | 8.7930 | 0.1310
64.0 | 1048576 | 64 | 9.0270 | 0.1345
256.0 | 1 | 268435456 | 421.7930 | 1.5713
256.0 | 10 | 26843545 | 56.2210 | 0.2094
256.0 | 100 | 2684354 | 32.6070 | 0.1215
256.0 | 1024 | 262144 | 31.8170 | 0.1185
256.0 | 4096 | 65536 | 31.8400 | 0.1186
256.0 | 16384 | 16384 | 32.1850 | 0.1199
256.0 | 65536 | 4096 | 31.7850 | 0.1184
256.0 | 262144 | 1024 | 32.8390 | 0.1223
256.0 | 1048576 | 256 | 32.9460 | 0.1227

System 1: With the patch applied
=====

jan2=# SELECT * FROM repeat_bench_sql();
output_mb | source_len | repeat_count | best_ms | ns_per_byte
-----------+------------+--------------+---------+-------------
0.0 | 0 | 10000000 | 0.0000 |
16.0 | 1 | 16777216 | 0.9460 | 0.0564
16.0 | 10 | 1677721 | 0.9350 | 0.0557
16.0 | 100 | 167772 | 0.7410 | 0.0442
16.0 | 1024 | 16384 | 0.6820 | 0.0407
16.0 | 4096 | 4096 | 0.5850 | 0.0349
16.0 | 16384 | 1024 | 0.5250 | 0.0313
16.0 | 65536 | 256 | 0.5060 | 0.0302
16.0 | 262144 | 64 | 0.5060 | 0.0302
16.0 | 1048576 | 16 | 0.5070 | 0.0302
64.0 | 1 | 67108864 | 8.0250 | 0.1196
64.0 | 10 | 6710886 | 7.6990 | 0.1147
64.0 | 100 | 671088 | 7.6640 | 0.1142
64.0 | 1024 | 65536 | 8.1790 | 0.1219
64.0 | 4096 | 16384 | 8.1190 | 0.1210
64.0 | 16384 | 4096 | 8.0930 | 0.1206
64.0 | 65536 | 1024 | 7.8130 | 0.1164
64.0 | 262144 | 256 | 7.7870 | 0.1160
64.0 | 1048576 | 64 | 7.7850 | 0.1160
256.0 | 1 | 268435456 | 30.5510 | 0.1138
256.0 | 10 | 26843545 | 29.3930 | 0.1095
256.0 | 100 | 2684354 | 29.3650 | 0.1094
256.0 | 1024 | 262144 | 30.8200 | 0.1148
256.0 | 4096 | 65536 | 29.7990 | 0.1110
256.0 | 16384 | 16384 | 29.8490 | 0.1112
256.0 | 65536 | 4096 | 29.7460 | 0.1108
256.0 | 262144 | 1024 | 29.6070 | 0.1103
256.0 | 1048576 | 256 | 29.8270 | 0.1111

System 2: Without the patch (master at 72e6184)
=====

jan2=# SELECT * FROM repeat_bench_sql();
output_mb | source_len | repeat_count | best_ms | ns_per_byte
-----------+------------+--------------+-----------+-------------
0.0 | 0 | 10000000 | 68.5470 |
16.0 | 1 | 16777216 | 118.7810 | 7.0799
16.0 | 10 | 1677721 | 16.1220 | 0.9609
16.0 | 100 | 167772 | 5.5260 | 0.3294
16.0 | 1024 | 16384 | 5.6850 | 0.3389
16.0 | 4096 | 4096 | 5.9350 | 0.3538
16.0 | 16384 | 1024 | 5.8580 | 0.3492
16.0 | 65536 | 256 | 5.6150 | 0.3347
16.0 | 262144 | 64 | 5.6130 | 0.3346
16.0 | 1048576 | 16 | 5.4430 | 0.3244
64.0 | 1 | 67108864 | 673.6170 | 10.0377
64.0 | 10 | 6710886 | 222.5620 | 3.3164
64.0 | 100 | 671088 | 179.0040 | 2.6674
64.0 | 1024 | 65536 | 178.2080 | 2.6555
64.0 | 4096 | 16384 | 182.1820 | 2.7147
64.0 | 16384 | 4096 | 180.0070 | 2.6823
64.0 | 65536 | 1024 | 179.4350 | 2.6738
64.0 | 262144 | 256 | 179.1260 | 2.6692
64.0 | 1048576 | 64 | 183.2310 | 2.7304
256.0 | 1 | 268435456 | 2669.7590 | 9.9456
256.0 | 10 | 26843545 | 872.4090 | 3.2500
256.0 | 100 | 2684354 | 699.4290 | 2.6056
256.0 | 1024 | 262144 | 690.5680 | 2.5726
256.0 | 4096 | 65536 | 705.9170 | 2.6297
256.0 | 16384 | 16384 | 700.8910 | 2.6110
256.0 | 65536 | 4096 | 702.4840 | 2.6170
256.0 | 262144 | 1024 | 695.1320 | 2.5896
256.0 | 1048576 | 256 | 722.5480 | 2.6917

System 2: With the patch applied
=====

jan2=# SELECT * FROM repeat_bench_sql();
output_mb | source_len | repeat_count | best_ms | ns_per_byte
-----------+------------+--------------+----------+-------------
0.0 | 0 | 10000000 | 0.0000 |
16.0 | 1 | 16777216 | 5.8740 | 0.3501
16.0 | 10 | 1677721 | 5.7070 | 0.3402
16.0 | 100 | 167772 | 5.5940 | 0.3334
16.0 | 1024 | 16384 | 5.9030 | 0.3518
16.0 | 4096 | 4096 | 5.9310 | 0.3535
16.0 | 16384 | 1024 | 5.9300 | 0.3535
16.0 | 65536 | 256 | 5.8300 | 0.3475
16.0 | 262144 | 64 | 5.6770 | 0.3384
16.0 | 1048576 | 16 | 5.9440 | 0.3543
64.0 | 1 | 67108864 | 189.5320 | 2.8242
64.0 | 10 | 6710886 | 186.9150 | 2.7853
64.0 | 100 | 671088 | 187.3550 | 2.7918
64.0 | 1024 | 65536 | 186.8650 | 2.7845
64.0 | 4096 | 16384 | 187.5210 | 2.7943
64.0 | 16384 | 4096 | 188.7260 | 2.8122
64.0 | 65536 | 1024 | 187.4840 | 2.7937
64.0 | 262144 | 256 | 186.8230 | 2.7839
64.0 | 1048576 | 64 | 188.0490 | 2.8021
256.0 | 1 | 268435456 | 730.2740 | 2.7205
256.0 | 10 | 26843545 | 731.0500 | 2.7234
256.0 | 100 | 2684354 | 732.5100 | 2.7288
256.0 | 1024 | 262144 | 732.6140 | 2.7292
256.0 | 4096 | 65536 | 732.1680 | 2.7275
256.0 | 16384 | 16384 | 732.9070 | 2.7303
256.0 | 65536 | 4096 | 740.0030 | 2.7567
256.0 | 262144 | 1024 | 739.3400 | 2.7543
256.0 | 1048576 | 256 | 739.1520 | 2.7536

Comments
=====

Using the new shortcut for a source_len of 0 is highly beneficial. On
both CPUs the patch is much faster for very short sources and slower
from source_len ~ 100 upwards. On the M5 this is only visible with 16 MB
of output, where the patch is up to 33% slower (source_len 1024: 0.5130
ms -> 0.6820 ms). On the J5005 the same crossover is visible at every
output size, with a ~5% regression for source_len >= 100.

Further Tests
=====

To understand the problem better, I wrote an extension function (see
repeatbench--1.0.sql, repeatbench.c, repeatbench.control, Makefile) that
tries out a few strategies and numbers:

* master - the repeat() algorithm of the current master branch.
* doubling - the algorithm proposed in the patch.
* nobranch - the algorithm proposed in the patch but without the
special 'count < 8' branch.
* cap512 - doubling roughly capped at 512 bytes.
* cap4k - doubling roughly capped at 4 KB.
* cap64k - doubling roughly capped at 64 KB.
* nocap - doubling roughly capped at PG_INT32_MAX, so never in practice
(same as nobranch but with the capping machinery).
* memset - performing a memset when source = 1B (as suggested
by Heikki).

The extension checks every strategy against the built-in repeat() before
reporting any timing.

System 1
=====

jan2=# SELECT * from repeat_bench();
source | repeats | output | master | doubling | nobranch | cap512 | cap4k | cap64k | nocap | memset | fastest
--------+-----------+----------+----------+----------+----------+--------+--------+---------+---------+---------+----------
32 B | 2 | 64 B | 5 ns | 0.98x | 0.99x | 0.88x | 0.88x | 0.88x | 0.88x | - | master
32 B | 4 | 128 B | 6 ns | 0.90x | 1.38x | 1.20x | 1.20x | 1.20x | 1.20x | - | nobranch
32 B | 6 | 192 B | 8 ns | 0.92x | 1.33x | 1.26x | 1.26x | 1.26x | 1.26x | - | nobranch
32 B | 7 | 224 B | 10 ns | 0.93x | 1.42x | 1.35x | 1.35x | 1.35x | 1.35x | - | nobranch
32 B | 8 | 256 B | 10 ns | 1.50x | 1.57x | 1.50x | 1.50x | 1.50x | 1.50x | - | nobranch
32 B | 9 | 288 B | 10 ns | 1.38x | 1.43x | 1.43x | 1.43x | 1.43x | 1.44x | - | nocap
32 B | 12 | 384 B | 13 ns | 1.50x | 1.56x | 1.22x | 1.25x | 1.26x | 1.28x | - | nobranch
32 B | 16 | 512 B | 16 ns | 1.26x | 1.24x | 1.22x | 1.23x | 1.22x | 1.23x | - | doubling
32 B | 64 | 2 KB | 61 ns | 2.24x | 2.26x | 2.22x | 2.24x | 2.24x | 2.25x | - | nobranch
32 B | 4096 | 128 KB | 3.4 us | 2.51x | 2.84x | 2.35x | 2.38x | 2.44x | 2.49x | - | nobranch
1 B | 16777216 | 16 MB | 20.0 ms | 79.58x | 79.84x | 89.11x | 90.73x | 127.12x | 79.97x | 161.94x | memset
10 B | 1677721 | 16 MB | 1.5 ms | 5.84x | 5.86x | 6.62x | 5.96x | 9.88x | 5.86x | - | cap64k
100 B | 167772 | 16 MB | 308.8 us | 1.23x | 1.24x | 1.39x | 0.72x | 2.17x | 1.24x | - | cap64k
1 KB | 16384 | 16 MB | 258.8 us | 1.03x | 1.04x | 1.01x | 1.19x | 1.64x | 1.04x | - | cap64k
64 KB | 256 | 16 MB | 211.3 us | 0.85x | 0.85x | 1.00x | 1.01x | 1.01x | 0.85x | - | cap4k
1 MB | 16 | 16 MB | 248.6 us | 0.99x | 0.99x | 1.00x | 1.00x | 1.01x | 0.99x | - | cap64k
1 B | 268435456 | 256 MB | 330.6 ms | 73.72x | 75.28x | 77.36x | 71.86x | 75.49x | 78.03x | 166.40x | memset
10 B | 26843545 | 256 MB | 23.5 ms | 5.59x | 5.57x | 5.58x | 5.19x | 6.30x | 5.57x | - | cap64k
100 B | 2684354 | 256 MB | 5.2 ms | 1.24x | 1.24x | 1.25x | 0.74x | 1.57x | 1.24x | - | cap64k
1 KB | 262144 | 256 MB | 4.3 ms | 1.04x | 1.04x | 1.00x | 0.98x | 1.06x | 1.04x | - | cap64k
64 KB | 4096 | 256 MB | 4.6 ms | 1.09x | 1.08x | 0.99x | 1.00x | 1.00x | 1.08x | - | doubling
1 MB | 256 | 256 MB | 4.1 ms | 0.96x | 0.96x | 1.00x | 1.02x | 1.02x | 0.96x | - | cap64k
1 B | 1000 | 1000 B | 1.3 us | 71.09x | 77.07x | 71.40x | 71.72x | 72.04x | 72.86x | 168.72x | memset
1 B | 1000000 | 976.6 KB | 1.3 ms | 99.40x | 99.71x | 99.40x | 98.46x | 137.32x | 104.02x | 174.90x | memset

System 2
=====

jan2=# SELECT * from repeat_bench();
source | repeats | output | master | doubling | nobranch | cap512 | cap4k | cap64k | nocap | memset | fastest
--------+-----------+----------+-----------+----------+----------+---------+---------+--------+--------+---------+----------
32 B | 2 | 64 B | 17 ns | 0.85x | 1.09x | 0.85x | 0.85x | 0.85x | 0.85x | - | nobranch
32 B | 4 | 128 B | 26 ns | 1.09x | 1.40x | 1.20x | 1.20x | 1.20x | 1.13x | - | nobranch
32 B | 6 | 192 B | 31 ns | 0.94x | 1.21x | 1.07x | 1.07x | 1.07x | 1.07x | - | nobranch
32 B | 7 | 224 B | 36 ns | 0.94x | 1.41x | 1.25x | 1.25x | 1.25x | 1.25x | - | nobranch
32 B | 8 | 256 B | 40 ns | 1.57x | 1.59x | 1.41x | 1.41x | 1.41x | 1.41x | - | nobranch
32 B | 9 | 288 B | 45 ns | 1.47x | 1.48x | 1.34x | 1.34x | 1.34x | 1.34x | - | nobranch
32 B | 12 | 384 B | 59 ns | 1.81x | 1.83x | 1.67x | 1.67x | 1.67x | 1.67x | - | nobranch
32 B | 16 | 512 B | 84 ns | 2.26x | 2.28x | 2.10x | 2.10x | 2.10x | 2.10x | - | nobranch
32 B | 64 | 2 KB | 316 ns | 3.71x | 3.81x | 3.36x | 3.59x | 3.59x | 3.59x | - | nobranch
32 B | 4096 | 128 KB | 19.1 us | 2.05x | 2.06x | 2.78x | 2.79x | 2.05x | 2.06x | - | cap4k
1 B | 16777216 | 16 MB | 114.8 ms | 43.10x | 44.06x | 51.79x | 49.64x | 47.36x | 42.30x | 56.57x | memset
10 B | 1677721 | 16 MB | 12.8 ms | 4.68x | 4.85x | 5.89x | 5.58x | 5.29x | 4.71x | - | cap512
100 B | 167772 | 16 MB | 2.2 ms | 0.80x | 0.84x | 1.04x | 0.94x | 0.90x | 0.80x | - | cap512
1 KB | 16384 | 16 MB | 2.3 ms | 0.83x | 0.87x | 1.00x | 0.99x | 0.95x | 0.83x | - | cap512
64 KB | 256 | 16 MB | 2.4 ms | 0.85x | 0.89x | 1.00x | 0.97x | 0.97x | 0.85x | - | cap512
1 MB | 16 | 16 MB | 2.2 ms | 0.82x | 0.81x | 0.96x | 1.03x | 1.03x | 0.82x | - | cap4k
1 B | 268435456 | 256 MB | 1846.6 ms | 39.75x | 39.73x | 48.84x | 48.89x | 46.66x | 39.76x | 64.38x | memset
10 B | 26843545 | 256 MB | 207.6 ms | 4.30x | 4.31x | 5.08x | 5.12x | 4.89x | 4.28x | - | cap4k
100 B | 2684354 | 256 MB | 41.3 ms | 0.86x | 0.86x | 1.00x | 1.02x | 0.98x | 0.86x | - | cap4k
1 KB | 262144 | 256 MB | 37.4 ms | 0.81x | 0.81x | 1.00x | 0.99x | 0.94x | 0.81x | - | cap512
64 KB | 4096 | 256 MB | 42.0 ms | 0.87x | 0.87x | 1.00x | 1.00x | 1.00x | 0.87x | - | master
1 MB | 256 | 256 MB | 32.5 ms | 0.70x | 0.70x | 1.00x | 1.01x | 1.01x | 0.70x | - | cap4k
1 B | 1000 | 1000 B | 6.8 us | 75.86x | 76.51x | 74.68x | 73.84x | 73.86x | 73.86x | 264.24x | memset
1 B | 1000000 | 976.6 KB | 6.8 ms | 90.97x | 91.42x | 110.20x | 123.82x | 91.22x | 91.57x | 134.49x | memset

Discussion
=====

* An early return for source_len = 0 is a clear win.
* Using memset for source_len = 1 also seems to be the best strategy.
* The 'count < 8' branch slows down the operation on my hardware.
* The pure doubling strategy can cause regressions, probably because it
reads back from the destination buffer rather than from the source.
Once the output no longer fits in cache, that adds a full pass of
memory reads that master's loop does not do.
* Capping the doubling helps for larger sources, but costs ~10-15% at
very small counts because of the extra loop structure it needs. The
'nocap' column isolates this: it pays for the structure without ever
engaging the cap, and is still slower than 'nobranch'.
* The best capping value differs between my two systems: the M5 prefers
cap64k, the J5005 prefers a smaller cap.

So, I'd suggest keeping the slen=0 shortcut, adding a memset for slen=1,
dropping the 'count < 8' branch, and using capped doubling with the cap
value still to be settled.

I am curious what numbers other people get from these tests.

Best regards
Jan

--
Jan Nidzwetzki
PlanetScale Postgres Core Team