[PATCH v2 0/2] Optimize RISC-V memset() port for speed

[Kito Cheng]

Pushed to trunk, thanks :)

On Mon, May 26, 2025 at 2:18 PM Kito Cheng <kito.cheng@sifive.com> wrote:
>
> LGTM, thanks :)
>
> On Sat, May 24, 2025 at 6:05 AM Eric Salem <ericsalem@gmail.com> wrote:
>>
>> The existing memset() implementation does not take advantage of various
>> RISC-V extensions like Zba, Zbkb, and Zilsd/Zclsd, so adding these
>> instructions when available improves the performance independent of any
>> other changes.
>>
>> At the same time, the current loop unrolling can be expanded further for
>> greater speed gains. Following the same technique for byte stores,
>> another table of instructions is used for single or double word stores.
>>
>> To ensure that the benchmarking is objective as possible, a range of
>> addresses with various alignments were tested so neither algorithm had
>> an advantage. Addresses divided by eight with a remainder of 0-7 were
>> used for the benchmark. For example:
>>
>> 0x20002a80
>> 0x20003289
>> 0x20003a92
>> 0x2000429b
>> 0x20004aa4
>> 0x200052b5
>> 0x20005ac6
>> 0x200062d7
>>
>> The existing implementation aligns the starting address to be 16-byte
>> aligned, whereas the proposed implementation aligns it to be either 4-
>> or 8-byte aligned, depending on the store instruction used.
>>
>> The implementations were benchmarked using actual RISC-V hardware,
>> specifically a Raspberry Pi Pico 2. This was chosen since Newlib is a C
>> standard library targeted for use on embedded systems. It's also the
>> only RISC-V hardware I had access to.
>>
>> I tested a range of counts from 0 to 2,048 for each alignment, for a
>> total of 16,384 tests, for both zero (null) being passed in as the byte
>> to set the buffer to, and also a non-zero value. The null case is the
>> more important of the two, since that's the value most often passed to
>> memset().
>>
>> Overwhelmingly, the proposed implementation is faster than the existing.
>> The four scenarios tested are null with extensions, non-null with
>> extensions, null without extensions, and non-null without extensions
>> (all extension benchmarking excludes Zilsd):
>>
>>                    BENCHMARK RESULTS
>> +------+-----------+----------+------------+----------+
>> |      |Null       |Non-null  |Null        |Non-null  |
>> |      |with       |with      |without     |without   |
>> |      |extensions |extensions|extensions  |extensions|
>> +------+-----------+----------+------------+----------+
>> |Slower|32, 1-8 cy.|2, 1-2 cy.|56, 1-10 cy.|7, 2-6 cy.|
>> +------+-----------+----------+------------+----------+
>> |Tied  |6          |1         |139         |12        |
>> +------+-----------+----------+------------+----------+
>> |Faster|16,346     |16,381    |16,189      |16,365    |
>> +------+-----------+----------+------------+----------+
>>
>> (Number of cases, with slower cases followed by cycle ranges)
>>
>> The cases where the existing implementation was faster were
>> circumstances that favored it, where the buffer is already 16-byte
>> aligned (14 cases were exceptions to this for the
>> null-without-extensions scenario, and it was only 2 cycles slower), and
>> either the number of bytes to copy was a multiple of 16 (the unrolled
>> loop size), or it was a small number to be copied (16 <= n <= 96, not a
>> continuous range but 56 values). For copying relatively large amounts of
>> bytes (more than 96), the proposed implementation is the clear winner,
>> and the improvement increases as the number of bytes grows. The proposed
>> implementation with extensions is also faster for counts from 0 to 15,
>> so it's at least an improvement for very small copies.
>>
>> It's impossible to be faster for both small and large copies, without
>> creating an inordinate number of unrolled loops for every combination of
>> alignment and number of bytes to copy below a certain threshold. The
>> proposed implementation is a reasonable trade-off between the two.
>>
>> The following architectures were tested for correctness:
>>
>> rv32ec-ext-zilsd
>> rv32ec-ext-no-zilsd
>> rv32ec-no-ext-zilsd
>> rv32ec-no-ext-no-zilsd
>> rv32ic-ext-zilsd
>> rv32ic-ext-no-zilsd
>> rv32ic-no-ext-zilsd
>> rv32ic-no-ext-no-zilsd
>> rv64ec-ext
>> rv64ec-no-ext
>> rv64ic-ext
>> rv64ic-no-ext
>>
>> If extensions are enabled (excluding Zilsd), "ext" is present.
>> Otherwise, "no-ext" is present. Zilsd is tested separately with either
>> "zilsd" or "no-zilsd" (the latter not testing Zilsd). QEMU and spike
>> with pk were the simulators used. pk does not support the E base ISA, so
>> QEMU was used to test those binaries.
>>
>> Changes in v2:
>> - Rename macros used for register size and store instruction
>> - Move whitespace changes for size optimized version to separate patch
>> - Link to v1: https://sourceware.org/pipermail/newlib/2025/021706.html
>>
>> Eric Salem (2):
>>   newlib: riscv: Optimize memset() for speed
>>   newlib: riscv: Align whitespace of size optimized memset()
>>
>>  newlib/libc/machine/riscv/memset.S | 341 ++++++++++++++++++++++-------
>>  1 file changed, 266 insertions(+), 75 deletions(-)
>>
>> --
>> 2.49.0
>>