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

Hi Jan,

Thanks for the detailed benchmark and for sharing the repeatbench extension.

I reproduced the same general behavior on my machines. In particular, removing
the small-count branch seems to be a good idea, and the single-byte memset() fast
path gives a clear improvement. I have updated the patch with these two changes.

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.

I tested on the following two systems:

Intel Core i5-13500H, 32 GB LPDDR5
Intel Core i9-12900H, 64 GB DDR5-4800

I ran the benchmark five times on each system and observed the same overall trends. The tables below show the third run from each system.

On the i5-13500H, the larger-output cases generally prefer a block size around 1-2 MB.
For example, for 256 MB outputs, cap2m is consistently among the best choices for
most source lengths.

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 | 1.07x | 0.88x | 0.85x | 0.87x | 0.88x | 0.85x | 0.85x | 0.85x | 0.85x | 0.88x | 0.85x | 0.85x | 0.85x | 0.85x | 0.85x | 0.90x | 0.85x | 0.85x | doubling (median: master)
32 B | 4 | 128 B | 6 ns | 1.16x | 1.09x | 1.12x | 1.12x | 1.12x | 1.12x | 1.08x | 1.12x | 1.12x | 1.08x | 1.12x | 1.12x | 1.12x | 1.12x | 1.08x | 1.12x | 1.12x | 1.12x | doubling
32 B | 6 | 192 B | 9 ns | 1.24x | 1.16x | 1.16x | 1.16x | 1.16x | 1.16x | 1.16x | 1.16x | 1.16x | 1.16x | 1.16x | 1.16x | 1.16x | 1.16x | 1.16x | 1.16x | 1.16x | 1.16x | doubling
32 B | 7 | 224 B | 9 ns | 1.36x | 1.28x | 1.28x | 1.28x | 1.28x | 1.28x | 1.28x | 1.28x | 1.28x | 1.28x | 1.28x | 1.28x | 1.28x | 1.28x | 1.28x | 1.28x | 1.28x | 1.28x | doubling
32 B | 8 | 256 B | 10 ns | 1.51x | 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 | 13 ns | 1.37x | 1.30x | 1.30x | 1.30x | 1.30x | 1.30x | 1.30x | 1.30x | 1.30x | 1.30x | 1.30x | 1.30x | 1.30x | 1.30x | 1.30x | 1.30x | 1.30x | 1.30x | doubling
32 B | 12 | 384 B | 16 ns | 1.56x | 1.49x | 1.49x | 1.49x | 1.49x | 1.49x | 1.49x | 1.49x | 1.49x | 1.49x | 1.49x | 1.49x | 1.49x | 1.48x | 1.49x | 1.49x | 1.46x | 1.49x | doubling
32 B | 16 | 512 B | 22 ns | 2.18x | 2.12x | 2.12x | 2.05x | 2.12x | 2.12x | 2.12x | 2.12x | 2.12x | 2.12x | 2.12x | 2.12x | 2.13x | 2.12x | 2.12x | 2.12x | 2.12x | 2.12x | doubling
32 B | 64 | 2 KB | 71 ns | 3.62x | 3.56x | 3.28x | 3.57x | 3.57x | 3.56x | 3.57x | 3.58x | 3.56x | 3.57x | 3.57x | 3.57x | 3.57x | 3.57x | 3.57x | 3.57x | 3.57x | 3.56x | doubling (median: cap1k)
32 B | 4096 | 128 KB | 5.7 us | 2.92x | 2.91x | 2.24x | 2.89x | 3.18x | 3.37x | 3.70x | 3.73x | 2.94x | 2.93x | 2.91x | 2.92x | 2.91x | 2.92x | 2.92x | 2.91x | 2.92x | 2.91x | cap16k
1 B | 16777216 | 16 MB | 18.3 ms | 30.41x | 28.14x | 25.33x | 34.68x | 41.80x | 27.21x | 33.67x | 35.85x | 32.59x | 34.50x | 40.08x | 38.09x | 34.90x | 27.07x | 38.68x | 36.72x | 29.04x | 28.75x | cap2k (median: cap2m)
10 B | 1677721 | 16 MB | 1.6 ms | 2.61x | 2.69x | 2.09x | 2.04x | 2.13x | 2.42x | 2.91x | 3.40x | 3.32x | 2.96x | 3.12x | 3.08x | 2.81x | 2.35x | 3.17x | 2.87x | 2.69x | 2.78x | cap16k (median: cap2m)
100 B | 167772 | 16 MB | 899.9 us | 1.43x | 1.53x | 1.21x | 1.27x | 1.04x | 1.36x | 1.77x | 1.81x | 1.71x | 1.82x | 1.83x | 1.78x | 1.45x | 1.96x | 1.83x | 1.55x | 1.50x | 1.50x | cap1m
1 KB | 16384 | 16 MB | 719.9 us | 1.09x | 1.10x | 0.98x | 1.04x | 1.52x | 0.94x | 1.19x | 1.36x | 1.21x | 1.34x | 1.21x | 1.37x | 1.07x | 0.99x | 1.47x | 1.36x | 1.09x | 1.09x | cap2k (median: cap2m)
64 KB | 256 | 16 MB | 608.4 us | 0.92x | 0.93x | 0.85x | 0.80x | 1.03x | 1.28x | 1.22x | 1.16x | 0.97x | 1.04x | 1.01x | 1.09x | 1.10x | 0.88x | 1.21x | 1.18x | 0.95x | 0.93x | cap4k (median: cap2m)
1 MB | 16 | 16 MB | 931.1 us | 1.41x | 1.39x | 1.06x | 1.03x | 1.23x | 1.35x | 1.32x | 1.40x | 1.39x | 1.54x | 1.52x | 1.43x | 1.46x | 1.39x | 1.85x | 1.73x | 1.44x | 1.41x | cap2m
1 B | 268435456 | 256 MB | 303.9 ms | 22.57x | 25.11x | 17.18x | 17.80x | 17.10x | 16.71x | 19.49x | 21.68x | 20.89x | 22.71x | 21.99x | 22.84x | 21.38x | 17.81x | 40.98x | 41.67x | 36.89x | 26.75x | cap4m (median: cap2m)
10 B | 26843545 | 256 MB | 28.4 ms | 2.30x | 2.28x | 1.66x | 1.63x | 1.37x | 1.80x | 2.08x | 2.08x | 1.95x | 2.21x | 2.12x | 2.14x | 2.09x | 1.67x | 3.88x | 3.54x | 3.29x | 2.32x | cap2m
100 B | 2684354 | 256 MB | 17.9 ms | 1.48x | 1.45x | 1.05x | 1.04x | 1.01x | 1.06x | 1.32x | 1.22x | 1.33x | 1.34x | 1.24x | 1.21x | 1.11x | 2.57x | 2.47x | 2.33x | 1.87x | 1.72x | cap1m
1 KB | 262144 | 256 MB | 16.5 ms | 1.41x | 1.35x | 0.96x | 0.94x | 0.95x | 0.95x | 1.05x | 1.23x | 1.16x | 1.20x | 1.26x | 1.21x | 1.11x | 1.00x | 2.29x | 2.25x | 2.11x | 1.51x | cap2m
64 KB | 4096 | 256 MB | 15.4 ms | 1.31x | 1.28x | 1.04x | 1.05x | 0.99x | 1.05x | 1.01x | 1.10x | 1.12x | 1.09x | 1.01x | 1.11x | 1.03x | 0.91x | 2.22x | 2.11x | 1.80x | 1.33x | cap2m
1 MB | 256 | 256 MB | 16.9 ms | 1.41x | 1.38x | 1.02x | 1.08x | 1.05x | 1.04x | 1.06x | 1.05x | 1.04x | 1.04x | 1.11x | 1.04x | 1.07x | 1.05x | 2.49x | 2.32x | 2.14x | 1.42x | cap2m
1 B | 1000 | 1000 B | 1.1 us | 178.24x | 30.42x | 30.57x | 30.64x | 30.61x | 30.63x | 30.64x | 30.66x | 30.71x | 30.61x | 30.40x | 30.38x | 30.00x | 30.04x | 30.02x | 30.03x | 30.00x | 30.02x | doubling
1 B | 1000000 | 976.6 KB | 1.1 ms | 82.97x | 70.75x | 59.01x | 72.08x | 74.37x | 75.58x | 79.78x | 80.32x | 69.05x | 70.56x | 71.15x | 71.37x | 71.60x | 71.53x | 71.55x | 71.41x | 71.64x | 71.81x | doubling (median: cap8k)

The results on the i9-12900H are quite different. For 16 MB outputs, much smaller blocks,
generally from a few KB to a few hundred KB, tend to perform better. However, for 256 MB outputs,
the 16 MB cap is consistently the fastest among the capped variants I tested.

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.96x | 0.82x | 0.77x | 0.77x | 0.77x | 0.77x | 0.77x | 0.77x | 0.77x | 0.77x | 0.77x | 0.77x | 0.77x | 0.79x | 0.81x | 0.77x | 0.79x | 0.77x | master
32 B | 4 | 128 B | 5 ns | 1.09x | 0.96x | 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 | 7 ns | 1.21x | 1.16x | 1.16x | 1.16x | 1.16x | 1.16x | 1.16x | 1.16x | 1.16x | 1.16x | 1.16x | 1.16x | 1.16x | 1.16x | 1.16x | 1.16x | 1.16x | 1.16x | doubling
32 B | 7 | 224 B | 8 ns | 1.37x | 1.28x | 1.28x | 1.28x | 1.28x | 1.28x | 1.28x | 1.28x | 1.28x | 1.28x | 1.28x | 1.28x | 1.28x | 1.28x | 1.28x | 1.28x | 1.28x | 1.28x | doubling
32 B | 8 | 256 B | 9 ns | 1.54x | 1.44x | 1.44x | 1.44x | 1.44x | 1.44x | 1.44x | 1.44x | 1.44x | 1.44x | 1.44x | 1.44x | 1.44x | 1.44x | 1.44x | 1.44x | 1.44x | 1.44x | doubling
32 B | 9 | 288 B | 17 ns | 1.09x | 1.04x | 1.04x | 1.04x | 1.04x | 1.04x | 1.04x | 1.04x | 1.04x | 1.04x | 1.04x | 1.04x | 1.04x | 1.04x | 1.04x | 1.04x | 1.04x | 1.04x | doubling
32 B | 12 | 384 B | 19 ns | 1.76x | 1.68x | 1.68x | 1.68x | 1.68x | 1.68x | 1.68x | 1.68x | 1.68x | 1.68x | 1.68x | 1.68x | 1.68x | 1.68x | 1.68x | 1.68x | 1.68x | 1.68x | doubling
32 B | 16 | 512 B | 21 ns | 1.82x | 1.82x | 1.80x | 1.80x | 1.80x | 1.82x | 1.80x | 1.80x | 1.82x | 1.80x | 1.82x | 1.80x | 1.80x | 1.80x | 1.80x | 1.80x | 1.82x | 1.80x | cap8m (median: doubling)
32 B | 64 | 2 KB | 68 ns | 2.87x | 2.86x | 2.85x | 2.86x | 2.85x | 2.86x | 2.86x | 2.86x | 2.86x | 2.86x | 2.86x | 2.86x | 2.86x | 2.86x | 2.85x | 2.86x | 2.86x | 2.86x | doubling
32 B | 4096 | 128 KB | 5.5 us | 2.92x | 2.93x | 2.64x | 2.97x | 3.18x | 3.37x | 3.64x | 3.74x | 2.95x | 2.92x | 2.92x | 2.92x | 2.92x | 2.92x | 2.92x | 2.91x | 2.92x | 2.92x | cap16k
1 B | 16777216 | 16 MB | 17.5 ms | 47.30x | 30.19x | 42.27x | 44.17x | 42.53x | 37.90x | 42.22x | 45.73x | 38.79x | 39.85x | 38.99x | 38.71x | 38.13x | 31.69x | 31.59x | 30.84x | 30.10x | 31.77x | doubling (median: cap2k)
10 B | 1677721 | 16 MB | 1.4 ms | 2.51x | 2.50x | 3.61x | 3.65x | 3.03x | 3.40x | 3.49x | 3.75x | 3.24x | 3.23x | 3.25x | 3.02x | 2.85x | 2.59x | 2.64x | 2.56x | 2.57x | 2.64x | cap16k (median: cap1k)
100 B | 167772 | 16 MB | 611.2 us | 1.04x | 1.10x | 1.50x | 1.51x | 1.25x | 1.32x | 1.33x | 1.41x | 1.31x | 1.33x | 1.32x | 1.31x | 1.11x | 1.07x | 1.06x | 1.04x | 1.00x | 1.03x | cap1k
1 KB | 16384 | 16 MB | 394.3 us | 0.70x | 0.68x | 0.92x | 0.94x | 1.00x | 0.89x | 0.94x | 0.99x | 0.85x | 0.88x | 0.87x | 0.86x | 0.83x | 0.68x | 0.67x | 0.67x | 0.71x | 0.71x | cap2k (median: master)
64 KB | 256 | 16 MB | 456.4 us | 0.84x | 0.82x | 0.96x | 0.97x | 0.97x | 0.98x | 0.98x | 0.98x | 0.98x | 1.02x | 1.05x | 1.05x | 0.95x | 0.81x | 0.81x | 0.78x | 0.78x | 0.80x | cap256k (median: cap128k)
1 MB | 16 | 16 MB | 621.1 us | 1.05x | 1.07x | 1.01x | 1.02x | 1.01x | 1.00x | 1.02x | 1.05x | 1.02x | 1.07x | 1.09x | 1.05x | 1.04x | 1.04x | 1.08x | 1.08x | 1.04x | 1.09x | cap128k (median: cap64k)
1 B | 268435456 | 256 MB | 290.5 ms | 21.37x | 23.29x | 20.26x | 20.73x | 20.32x | 18.96x | 19.77x | 20.46x | 20.84x | 20.64x | 20.74x | 21.04x | 20.18x | 18.12x | 18.36x | 18.30x | 18.38x | 31.81x | cap16m
10 B | 26843545 | 256 MB | 26.1 ms | 1.98x | 2.02x | 1.82x | 1.81x | 1.52x | 1.75x | 1.81x | 1.86x | 1.86x | 1.88x | 1.88x | 1.87x | 1.80x | 1.69x | 1.67x | 1.61x | 1.54x | 2.30x | cap16m
100 B | 2684354 | 256 MB | 15.8 ms | 1.25x | 1.23x | 1.08x | 1.08x | 0.93x | 1.04x | 1.09x | 1.11x | 1.11x | 1.14x | 1.10x | 1.10x | 1.04x | 1.00x | 1.00x | 0.98x | 0.90x | 1.27x | cap16m
1 KB | 262144 | 256 MB | 14.3 ms | 1.12x | 1.11x | 0.98x | 0.96x | 0.98x | 0.92x | 0.97x | 0.99x | 0.99x | 1.01x | 1.03x | 1.03x | 1.00x | 0.90x | 0.89x | 0.89x | 0.87x | 1.55x | cap16m
64 KB | 4096 | 256 MB | 14.2 ms | 1.08x | 1.10x | 0.99x | 1.00x | 0.99x | 0.99x | 0.99x | 1.00x | 0.99x | 0.98x | 1.01x | 1.02x | 1.00x | 0.89x | 0.88x | 0.87x | 0.86x | 1.42x | cap16m
1 MB | 256 | 256 MB | 15.4 ms | 1.22x | 1.22x | 0.99x | 0.98x | 0.98x | 0.98x | 1.00x | 0.99x | 1.00x | 0.97x | 0.99x | 0.99x | 0.99x | 0.99x | 0.97x | 0.98x | 0.94x | 1.68x | cap16m
1 B | 1000 | 1000 B | 1.0 us | 188.01x | 25.89x | 26.12x | 25.94x | 25.97x | 25.94x | 25.94x | 25.93x | 25.94x | 25.94x | 25.98x | 25.97x | 25.98x | 25.99x | 25.92x | 25.92x | 25.99x | 26.11x | doubling
1 B | 1000000 | 976.6 KB | 1.0 ms | 80.26x | 64.00x | 61.04x | 66.58x | 69.91x | 70.56x | 74.70x | 77.56x | 63.71x | 65.65x | 65.98x | 66.34x | 66.17x | 66.59x | 66.89x | 67.00x | 67.19x | 67.30x | doubling (median: cap16k)

So it seems that the performance-optimal block size depends not only on the machine,
but also on the total output size on the same machine. This makes me hesitant to
choose a fixed cap primarily as a performance optimization.

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.

This also makes me wonder whether the cap should mainly be chosen to bound the interval
between CHECK_FOR_INTERRUPTS() calls, rather than to optimize memcpy() throughput. Any
performance improvement from the cap could then be treated as a secondary benefit.

The attached patch contains the memset() fast path and removes the small-count branch. I have
not added a block-size cap yet, since I would like to get more data and feedback before choosing one.

I have also attached the updated repeatbench extension used for the tests above.

Thanks,
Chenhui