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

Hello Chenhui,

On 26.08.26 17:54, ChenhuiMo wrote:
[...]> I also extended your benchmark to test a wider range of block-size caps, from 512 bytes up to 16 MB.
>
> While testing this, I noticed that benchmark ordering can have a noticeable effect on
> some of the results. To reduce this effect, I changed the benchmark to rotate the strategy
> order between iterations. Each strategy is measured 25 times. The table reports the best
> timing, and when the strategy selected by the median differs from the best one, it is shown in parentheses.
[...]>
> If you have time, could you also run the wider cap sweep on your M5 Max and J5005 systems?
> It would be very useful to see whether the preferred block size changes with the output size there as well.

Thanks for the numbers and the updated benchmark. I looked into the
benchmark and saw that strat_double() has the "if (slen == 1)" -> memset
fast path. However, capped() is missing this, making the results for
slen == 1 hard to compare.

However, to get a comparable result with your data, I reran your
benchmark version on my machines without any modification. I also
took the results of the third run to do the same as you did.
Here are the numbers:

# 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
jan=# select * from repeat_bench();
source | repeats | output | master | doubling | nocap | cap512 | cap1k | cap2k | cap4k | cap8k | cap16k | cap32k | cap64k | cap128k | cap256k | cap512k | cap1m | cap2m | cap4m | cap8m | cap16m | fastest
--------+-----------+----------+----------+----------+--------+--------+---------+---------+---------+--------+--------+---------+---------+---------+---------+---------+---------+---------+---------+---------+---------+----------------------------
32 B | 2 | 64 B | 3 ns | 0.95x | 0.86x | 0.86x | 0.86x | 0.86x | 0.86x | 0.86x | 0.86x | 0.86x | 0.86x | 0.86x | 0.86x | 0.86x | 0.86x | 0.86x | 0.86x | 0.86x | 0.86x | master
32 B | 4 | 128 B | 5 ns | 1.31x | 1.13x | 1.06x | 1.05x | 1.09x | 1.11x | 1.05x | 1.06x | 1.13x | 1.13x | 1.13x | 1.12x | 1.11x | 1.08x | 1.13x | 1.13x | 1.13x | 1.13x | doubling
32 B | 6 | 192 B | 7 ns | 1.56x | 1.42x | 1.42x | 1.42x | 1.42x | 1.42x | 1.42x | 1.42x | 1.42x | 1.42x | 1.42x | 1.42x | 1.42x | 1.42x | 1.42x | 1.42x | 1.42x | 1.42x | doubling
32 B | 7 | 224 B | 7 ns | 1.65x | 1.50x | 1.50x | 1.50x | 1.50x | 1.50x | 1.50x | 1.50x | 1.49x | 1.50x | 1.50x | 1.50x | 1.50x | 1.50x | 1.50x | 1.50x | 1.50x | 1.50x | doubling
32 B | 8 | 256 B | 7 ns | 1.47x | 1.63x | 1.64x | 1.64x | 1.64x | 1.65x | 1.64x | 1.64x | 1.64x | 1.64x | 1.65x | 1.64x | 1.65x | 1.65x | 1.64x | 1.65x | 1.65x | 1.65x | cap1m (median: cap512k)
32 B | 9 | 288 B | 8 ns | 1.58x | 1.53x | 1.54x | 1.55x | 1.53x | 1.56x | 1.55x | 1.55x | 1.55x | 1.56x | 1.55x | 1.55x | 1.55x | 1.55x | 1.56x | 1.55x | 1.55x | 1.55x | doubling
32 B | 12 | 384 B | 9 ns | 1.25x | 1.42x | 1.50x | 1.45x | 1.50x | 1.50x | 1.47x | 1.50x | 1.50x | 1.50x | 1.50x | 1.50x | 1.50x | 1.50x | 1.50x | 1.47x | 1.50x | 1.50x | cap32k (median: cap512k)
32 B | 16 | 512 B | 12 ns | 1.43x | 1.23x | 1.24x | 1.24x | 1.29x | 1.23x | 1.29x | 1.37x | 1.29x | 1.30x | 1.32x | 1.32x | 1.56x | 1.29x | 1.32x | 1.31x | 1.28x | 1.27x | cap512k (median: cap8m)
32 B | 64 | 2 KB | 49 ns | 2.28x | 2.14x | 2.13x | 2.14x | 2.25x | 2.26x | 2.26x | 2.25x | 2.26x | 2.26x | 2.26x | 2.26x | 2.27x | 2.26x | 2.26x | 2.25x | 2.26x | 2.27x | doubling
32 B | 4096 | 128 KB | 2.7 us | 2.55x | 2.93x | 2.26x | 2.43x | 2.52x | 2.48x | 2.69x | 2.57x | 2.58x | 2.61x | 2.61x | 2.58x | 2.57x | 2.57x | 2.58x | 2.55x | 2.57x | 2.57x | nocap (median: cap8k)
1 B | 16777216 | 16 MB | 20.3 ms | 162.97x | 81.08x | 88.45x | 92.71x | 93.29x | 85.72x | 55.57x | 81.64x | 101.95x | 131.04x | 128.11x | 82.96x | 83.51x | 82.80x | 81.45x | 80.97x | 80.68x | 81.09x | doubling
10 B | 1677721 | 16 MB | 1.5 ms | 5.85x | 5.86x | 6.60x | 6.72x | 5.52x | 5.05x | 4.74x | 6.25x | 8.29x | 9.84x | 5.90x | 5.99x | 6.04x | 5.90x | 5.86x | 5.84x | 5.85x | 5.86x | cap64k
100 B | 167772 | 16 MB | 324.1 us | 1.30x | 1.30x | 1.46x | 1.51x | 1.42x | 0.76x | 1.21x | 1.61x | 2.01x | 2.26x | 1.32x | 1.33x | 1.33x | 1.30x | 1.30x | 1.30x | 1.30x | 1.30x | cap64k
1 KB | 16384 | 16 MB | 266.7 us | 1.06x | 1.07x | 1.04x | 1.04x | 1.21x | 0.57x | 0.75x | 1.06x | 1.34x | 1.72x | 1.68x | 1.09x | 1.10x | 1.09x | 1.07x | 1.07x | 1.07x | 1.07x | cap64k
64 KB | 256 | 16 MB | 211.6 us | 0.85x | 0.85x | 1.00x | 1.01x | 1.01x | 1.00x | 1.01x | 1.00x | 1.00x | 1.01x | 1.34x | 0.86x | 0.87x | 0.86x | 0.85x | 0.85x | 0.85x | 0.85x | cap128k
1 MB | 16 | 16 MB | 249.0 us | 0.99x | 0.99x | 1.00x | 1.01x | 1.01x | 1.01x | 1.01x | 1.01x | 1.01x | 1.01x | 1.01x | 1.01x | 1.01x | 1.01x | 0.99x | 0.99x | 0.99x | 0.99x | cap2k (median: cap64k)
1 B | 268435456 | 256 MB | 314.8 ms | 127.27x | 70.07x | 69.82x | 70.78x | 72.29x | 68.54x | 49.93x | 38.73x | 49.94x | 72.26x | 97.35x | 73.74x | 79.98x | 78.85x | 77.65x | 77.60x | 77.37x | 70.09x | doubling (median: cap128k)
10 B | 26843545 | 256 MB | 23.6 ms | 5.38x | 5.42x | 5.54x | 5.53x | 5.34x | 4.96x | 3.91x | 2.90x | 4.22x | 6.26x | 5.74x | 5.84x | 5.90x | 5.88x | 5.84x | 5.84x | 5.76x | 5.42x | cap64k
100 B | 2684354 | 256 MB | 5.3 ms | 1.22x | 1.23x | 1.24x | 1.25x | 1.18x | 0.73x | 0.84x | 0.72x | 1.04x | 1.55x | 1.25x | 1.32x | 1.35x | 1.31x | 1.31x | 1.30x | 1.18x | 1.20x | cap64k
1 KB | 262144 | 256 MB | 4.8 ms | 1.11x | 1.11x | 1.08x | 1.06x | 1.11x | 1.06x | 0.76x | 0.60x | 0.76x | 1.10x | 1.40x | 1.12x | 1.18x | 1.19x | 1.17x | 1.18x | 1.18x | 1.07x | cap128k
64 KB | 4096 | 256 MB | 4.7 ms | 1.08x | 1.09x | 1.00x | 1.02x | 1.01x | 1.02x | 1.03x | 1.00x | 1.03x | 1.02x | 1.39x | 1.10x | 1.16x | 1.17x | 1.15x | 1.16x | 1.15x | 1.11x | cap128k
1 MB | 256 | 256 MB | 4.2 ms | 0.97x | 0.97x | 1.00x | 1.03x | 1.03x | 1.03x | 1.05x | 1.07x | 1.06x | 1.04x | 1.04x | 1.03x | 1.03x | 1.04x | 1.04x | 1.03x | 1.03x | 0.94x | cap16k (median: cap1m)
1 B | 1000 | 1000 B | 1.3 us | 165.55x | 75.87x | 75.00x | 75.00x | 75.18x | 76.58x | 75.70x | 76.94x | 76.41x | 76.94x | 77.30x | 77.67x | 77.49x | 77.49x | 78.23x | 77.49x | 77.12x | 75.00x | doubling
1 B | 1000000 | 976.6 KB | 1.3 ms | 176.89x | 99.08x | 99.07x | 102.31x | 103.32x | 100.34x | 69.11x | 97.84x | 123.74x | 140.39x | 141.03x | 107.21x | 106.84x | 100.67x | 100.34x | 100.03x | 100.67x | 100.67x | doubling
(24 rows)

# Debian 13.5 on an Intel Pentium Silver J5005, 4 MB L2 cache, no L3
# cache, 16 GB RAM, gcc 14.2.0 -O2
jan=# select * from repeat_bench();
source | repeats | output | master | doubling | nocap | cap512 | cap1k | cap2k | cap4k | cap8k | cap16k | cap32k | cap64k | cap128k | cap256k | cap512k | cap1m | cap2m | cap4m | cap8m | cap16m | fastest
--------+-----------+----------+-----------+----------+--------+---------+---------+---------+---------+---------+---------+--------+--------+---------+---------+---------+--------+--------+--------+--------+--------+-------------------------
32 B | 2 | 64 B | 12 ns | 1.03x | 0.83x | 0.83x | 0.83x | 0.83x | 0.83x | 0.83x | 0.83x | 0.83x | 0.83x | 0.83x | 0.83x | 0.83x | 0.83x | 0.83x | 0.83x | 0.83x | 0.83x | doubling
32 B | 4 | 128 B | 21 ns | 1.18x | 1.00x | 1.00x | 1.00x | 1.00x | 1.00x | 1.00x | 1.00x | 1.00x | 1.00x | 1.00x | 1.00x | 1.00x | 1.00x | 1.00x | 1.00x | 1.00x | 1.00x | doubling
32 B | 6 | 192 B | 31 ns | 1.23x | 1.07x | 1.07x | 1.07x | 1.07x | 1.07x | 1.07x | 1.07x | 1.07x | 1.07x | 1.07x | 1.07x | 1.07x | 1.07x | 1.07x | 1.07x | 1.07x | 1.07x | doubling
32 B | 7 | 224 B | 35 ns | 1.43x | 1.25x | 1.25x | 1.25x | 1.25x | 1.25x | 1.25x | 1.25x | 1.25x | 1.25x | 1.25x | 1.25x | 1.25x | 1.25x | 1.25x | 1.25x | 1.25x | 1.25x | doubling
32 B | 8 | 256 B | 40 ns | 1.62x | 1.42x | 1.42x | 1.42x | 1.42x | 1.42x | 1.42x | 1.42x | 1.42x | 1.42x | 1.42x | 1.42x | 1.42x | 1.42x | 1.42x | 1.42x | 1.42x | 1.42x | doubling
32 B | 9 | 288 B | 45 ns | 1.52x | 1.34x | 1.34x | 1.34x | 1.34x | 1.34x | 1.34x | 1.34x | 1.34x | 1.34x | 1.34x | 1.34x | 1.34x | 1.34x | 1.34x | 1.34x | 1.34x | 1.34x | doubling
32 B | 12 | 384 B | 59 ns | 1.89x | 1.67x | 1.67x | 1.67x | 1.67x | 1.67x | 1.67x | 1.67x | 1.67x | 1.67x | 1.67x | 1.67x | 1.67x | 1.67x | 1.67x | 1.67x | 1.67x | 1.67x | doubling
32 B | 16 | 512 B | 83 ns | 2.31x | 2.08x | 2.08x | 2.08x | 2.08x | 2.08x | 2.08x | 2.08x | 2.08x | 2.08x | 2.08x | 2.08x | 2.08x | 2.08x | 2.08x | 2.08x | 2.08x | 2.08x | doubling
32 B | 64 | 2 KB | 316 ns | 3.79x | 3.59x | 3.36x | 3.59x | 3.59x | 3.59x | 3.59x | 3.59x | 3.59x | 3.59x | 3.59x | 3.59x | 3.59x | 3.59x | 3.59x | 3.59x | 3.59x | 3.59x | doubling
32 B | 4096 | 128 KB | 19.5 us | 2.11x | 2.12x | 2.83x | 3.00x | 3.09x | 2.88x | 2.93x | 2.63x | 2.15x | 2.12x | 2.11x | 2.11x | 2.11x | 2.11x | 2.11x | 2.11x | 2.11x | 2.11x | cap2k
1 B | 16777216 | 16 MB | 114.9 ms | 56.25x | 43.67x | 51.54x | 50.64x | 41.78x | 49.36x | 49.53x | 48.76x | 47.56x | 47.26x | 47.26x | 47.51x | 47.52x | 52.33x | 56.72x | 46.89x | 43.29x | 43.32x | cap2m
10 B | 1677721 | 16 MB | 12.8 ms | 4.67x | 4.83x | 5.89x | 5.76x | 5.48x | 5.50x | 5.51x | 5.38x | 5.31x | 5.27x | 5.27x | 5.28x | 5.33x | 6.06x | 6.14x | 4.93x | 4.87x | 4.84x | cap2m
100 B | 167772 | 16 MB | 2.2 ms | 0.84x | 0.85x | 1.04x | 1.00x | 0.94x | 0.93x | 0.93x | 0.90x | 0.89x | 0.90x | 0.90x | 0.90x | 0.90x | 1.02x | 1.00x | 0.85x | 0.85x | 0.85x | cap512
1 KB | 16384 | 16 MB | 2.3 ms | 0.87x | 0.87x | 1.00x | 1.00x | 0.84x | 0.99x | 0.99x | 0.99x | 0.95x | 0.94x | 0.95x | 0.95x | 0.95x | 1.03x | 1.14x | 0.93x | 0.87x | 0.87x | cap2m
64 KB | 256 | 16 MB | 2.4 ms | 0.87x | 0.89x | 1.00x | 1.00x | 0.97x | 0.97x | 0.96x | 0.96x | 0.97x | 0.97x | 0.98x | 0.97x | 0.98x | 1.05x | 1.15x | 0.95x | 0.89x | 0.89x | cap2m
1 MB | 16 | 16 MB | 2.3 ms | 0.87x | 0.86x | 1.01x | 1.08x | 1.08x | 1.08x | 1.08x | 1.08x | 1.08x | 1.08x | 1.08x | 1.08x | 1.08x | 1.08x | 1.07x | 0.91x | 0.83x | 0.85x | cap64k (median: cap1m)
1 B | 268435456 | 256 MB | 1849.7 ms | 63.78x | 39.96x | 48.86x | 42.71x | 34.30x | 49.08x | 48.94x | 48.57x | 46.89x | 46.73x | 46.64x | 46.83x | 46.89x | 56.84x | 56.49x | 45.49x | 40.60x | 40.35x | doubling
10 B | 26843545 | 256 MB | 207.7 ms | 4.48x | 4.52x | 5.46x | 5.24x | 5.50x | 5.49x | 5.47x | 5.38x | 5.25x | 5.25x | 5.24x | 5.24x | 5.25x | 6.39x | 6.39x | 4.73x | 4.53x | 4.48x | cap1m
100 B | 2684354 | 256 MB | 38.6 ms | 0.83x | 0.83x | 1.01x | 0.97x | 1.02x | 1.02x | 1.01x | 0.98x | 0.98x | 0.98x | 0.97x | 0.98x | 0.97x | 1.19x | 1.18x | 0.85x | 0.85x | 0.83x | cap1m
1 KB | 262144 | 256 MB | 37.4 ms | 0.80x | 0.81x | 1.00x | 0.99x | 0.70x | 0.99x | 0.99x | 0.98x | 0.95x | 0.94x | 0.95x | 0.95x | 0.95x | 1.15x | 1.15x | 1.03x | 0.82x | 0.82x | cap2m
64 KB | 4096 | 256 MB | 39.1 ms | 0.85x | 0.85x | 1.00x | 1.00x | 1.00x | 1.00x | 1.00x | 1.00x | 1.00x | 1.00x | 0.99x | 0.99x | 0.99x | 1.20x | 1.20x | 1.03x | 0.86x | 0.86x | cap2m
1 MB | 256 | 256 MB | 32.6 ms | 0.68x | 0.68x | 1.00x | 1.01x | 1.01x | 1.01x | 1.01x | 1.01x | 1.01x | 1.01x | 1.01x | 1.01x | 1.01x | 1.01x | 1.00x | 0.88x | 0.67x | 0.67x | cap512k (median: cap1m)
1 B | 1000 | 1000 B | 6.8 us | 240.81x | 74.12x | 74.42x | 74.14x | 74.15x | 74.15x | 74.15x | 74.15x | 74.15x | 74.15x | 74.15x | 74.14x | 74.15x | 74.15x | 74.15x | 74.15x | 74.15x | 74.15x | doubling
1 B | 1000000 | 976.6 KB | 6.8 ms | 134.60x | 91.03x | 113.81x | 126.83x | 131.21x | 125.34x | 127.56x | 117.56x | 94.91x | 91.75x | 91.65x | 91.60x | 91.57x | 91.57x | 91.53x | 91.53x | 91.45x | 91.57x | doubling
(24 rows)

Regarding your question whether the preferred block size changes with
the output size: in my measurements, for source lengths from 10 B to 64
KB, it changes with the machine rather than with the output size.

16 MB output 256 MB output
M5 Max 64k, 64k, 64k, 128k 64k, 64k, 128k, 128k
J5005 2m, 512, 2m, 2m 1m, 1m, 2m, 2m

The M5 prefers something around 64 KB - 128 KB at both output sizes,
and the J5005 prefers 1 MB - 2 MB. So the preference looks roughly
stable across output sizes here. However, the two machines are a
factor of 16 apart from each other. Together with your i5 and i9
numbers, the optimum now spans 64 KB to 16 MB.

I am curious what other people see when repeating these benchmarks. So
far, I don't see a good recommendation for a particular block size.

Best regards
Jan

--
Jan Nidzwetzki
PlanetScale Postgres Core Team