Re: [PATCH 0/5] RISC-V: Optimize memmove() for speed

Yes, memcpy has more restrictions on the inputs, it should only accept
two __restrict source and destination, however RISC-V port has our own
memcpy implementation, so we can guarantee that it is safe when it's
non-destructive overlap.

Also you can take a closer look on newlib/libc/string/memmove.c and
newlib/libc/string/memcpy.c, then you can found the  non-destructive
overlap part in memmove are almost same as memcpy, just different name
on the variable :)

On Tue, Jun 3, 2025 at 7:33 PM m fally <[email protected]> wrote:
>
> Thank you, Kito!
>
> I was wondering: memcpy() is using pointers qualified with __restrict for source and destination. Could this not cause problems when being called by memmove(), because of the possible non-destructive overlap?
> I did run some tests (for rv32/rv64 gcc and rv32 clang, both at -O3) and they all passed without errors, but I don't know if it will still work as for example compilers change?
>
> Or was it your suggestion to still let memmove() handle the non-destructive overlap case and add a third, seperate check for the non-overlap case and only redirect to memcpy() then?
>
> Op ma 2 jun 2025 om 11:04 schreef Kito Cheng <[email protected]>:
>>
>> Hi M:
>>
>> Let you know I don't have further comments :)
>>
>> On Wed, May 28, 2025 at 8:05 PM m fally <[email protected]> wrote:
>> >
>> > Hi Kito,
>> >
>> > thank you for the early feedback :)
>> > I am happy to work on another proposal based on what you suggested!
>> >
>> > Also, a little side note: In the comments in memmove.c I wrote that the (increased) loop-unrolling does not degrade performance for lengths < SZREG*9.
>> > However, this is not entirely correct as in a few cases, this does introduce a small penalty of 1-2 instructions retired when the function is compiled with -mno-strict-align.
>> > In the affected cases, copied lengths were between 11 to 15 bytes for rv32 and 24 to 31 bytes for rv64 (according to my tests).
>> > My apologies for that, I was a bit quick to write that comment and then forgot to correct it. I'll change it along with any other feedback you may have after finishing the review.
>> >
>> > Best,
>> > M
>> >
>> > Op wo 28 mei 2025 om 11:51 schreef Kito Cheng <[email protected]>:
>> >>
>> >> Hi Fally:
>> >>
>> >> Thanks for your patch! I am still under review yet, I wonder if it is
>> >> possible to just redirect to memcpy when both regions are proven not
>> >> overlapped? I guess that may add few extra instruction count, but
>> >> memcpy also do lots of similar optimization with many different
>> >> extension combination as well, it would be great to just maintain one
>> >> implementation for that pat :)
>> >>
>> >>
>> >> On Mon, May 26, 2025 at 11:06 PM m fally <[email protected]> wrote:
>> >> >
>> >> > This patch series optimizes the RISC-V port of memmove() for speed.
>> >> > The implementation is based on the generic port of the function,
>> >> > since that is what is currently used when compiling newlib for RISC-V.
>> >> >
>> >> > In the stock implementation, an unroll-factor of 4 is used for
>> >> > the word-copy-loop in the case where both source and destination
>> >> > addresses are aligned on a long-boundary, and the memory areas
>> >> > overlap non-destructively or not at all. No unrolling is done in
>> >> > the destructive-overlap case. The proposed implementation uses an
>> >> > unroll-factor of 9 for both overlap-cases when both addresses are
>> >> > aligned to xlen. The unroll-factor was chosen to match memcpy() and
>> >> > speeds up the copying-process for lengths >= 9*SZREG, while almost
>> >> > not at all degrading performance for shorter lengths.
>> >> >
>> >> > If at least one address is unaligned, misaligned accesses are slow
>> >> > or prohibited, and there are >= 2*SZREG bytes left to copy, the
>> >> > proposed implementation first aligns the source address. Then, one
>> >> > whole word (or doubleword for rv64) is loaded at a time and individual
>> >> > bytes are stored back to the destination. The threshold of 2*SZREG was
>> >> > chosen in order to keep the negative effect on shorter copies caused
>> >> > by the additional overhead of the alignment operation low.
>> >> >
>> >> > Furthermore, the function now only uses fixed-width types.
>> >> > Macros from the generic port are replaced with RISC-V-specific macros
>> >> > and static inline functions.
>> >> >
>> >> >
>> >> > The proposed implementation was tested on spike with pk for each of the
>> >> > following configurations (compiled with gcc):
>> >> >
>> >> > rv32ic -mtune=thead-c906 -mstrict-align -O3
>> >> > rv32ic -mtune=thead-c906 -mno-strict-align -O3
>> >> > rv64ic -mtune=thead-c906 -mstrict-align -O3
>> >> > rv64ic -mtune=thead-c906 -mno-strict-align -O3
>> >> >
>> >> >
>> >> > For each configuration, the following cases were considered when comparing
>> >> > the old and new implementations:
>> >> >
>> >> > both addresses are xlen-aligned
>> >> > both addresses are unaligned
>> >> > source address is xlen-aligned, destination address is not
>> >> > destination address is xlen-aligned, source address is not
>> >> >
>> >> >
>> >> > For each configuration, 65520 tests were run. In total, there were 67 cases
>> >> > where the new implementation was slower than the original, with a maximum
>> >> > difference of 10 retired instructions. In 145 cases the implementations were
>> >> > equally fast. In all cases where the new implementation was slower, copied
>> >> > lengths were < 32 bytes.
>> >> > In all other cases, the new implementation was faster than the original.
>> >> >
>> >> > Please see here for graphical comparisons between the two implementations:
>> >> > https://cloud.servus.at/s/BA8ZJoPnE3nCtAK
>> >> >
>> >> > Below tables show the number of cases where the new implementation was
>> >> > faster, slower, or equally fast as the current implementation, as well as
>> >> > the max. differences in instructions retired between the implementations.
>> >> > The graphs and tables show the differences for copied lengths between
>> >> > 2 and 8191 bytes. For lengths < 2, old and new implementations were
>> >> > equally fast.
>> >> >
>> >> > --------- BENCHMARKING RESULTS ---------
>> >> >
>> >> > +--------------------------------------+
>> >> > |        rv32ic -mstrict-align         |
>> >> > +--------------------------------------+
>> >> > |      |Number   |Max. difference in   |
>> >> > |      |of cases |instructions retired |
>> >> > +------+---------+---------------------+
>> >> > |Faster|   65496 |              -18411 |
>> >> > +------+---------+---------------------+
>> >> > |Slower|      13 |                  10 |
>> >> > +------+---------+---------------------+
>> >> > |Tied  |      11 |                     |
>> >> > +------+---------+---------------------+
>> >> >
>> >> > +--------------------------------------+
>> >> > |        rv64ic -mstrict-align         |
>> >> > +--------------------------------------+
>> >> > |      |Number   |Max. difference in   |
>> >> > |      |of cases |instructions retired |
>> >> > +------+---------+---------------------+
>> >> > |Faster|   65509 |              -21474 |
>> >> > +------+---------+---------------------+
>> >> > |Slower|       6 |                   2 |
>> >> > +------+---------+---------------------+
>> >> > |Tied  |       5 |                     |
>> >> > +------+---------+---------------------+
>> >> >
>> >> > +--------------------------------------+
>> >> > |        rv32ic -mno-strict-align      |
>> >> > +--------------------------------------+
>> >> > |      |Number   |Max. difference in   |
>> >> > |      |of cases |instructions retired |
>> >> > +------+---------+---------------------+
>> >> > |Faster|   65488 |               -5231 |
>> >> > +------+---------+---------------------+
>> >> > |Slower|      16 |                   1 |
>> >> > +------+---------+---------------------+
>> >> > |Tied  |      16 |                     |
>> >> > +------+---------+---------------------+
>> >> >
>> >> > +--------------------------------------+
>> >> > |        rv64ic -mno-strict-align      |
>> >> > +--------------------------------------+
>> >> > |      |Number   |Max. difference in   |
>> >> > |      |of cases |instructions retired |
>> >> > +------+---------+---------------------+
>> >> > |Faster|   65375 |               -2609 |
>> >> > +------+---------+---------------------+
>> >> > |Slower|      32 |                   2 |
>> >> > +------+---------+---------------------+
>> >> > |Tied  |     113 |                     |
>> >> > +------+---------+---------------------+
>> >> >
>> >> >
>> >> > m fally (5):
>> >> >   RISC-V: memmove() speed optimized: Add implementation
>> >> >   RISC-V: memmove() speed optimized: Replace macros and use fixed-width
>> >> >     types
>> >> >   RISC-V: memmove() speed optimized: Add loop-unrolling
>> >> >   RISC-V: memmove() speed optimized: Align source address
>> >> >   newlib: Regenerate configuration files
>> >> >
>> >> >  newlib/Makefile.in                            |  52 ++--
>> >> >  newlib/libc/machine/riscv/Makefile.inc        |   2 +-
>> >> >  .../riscv/{memmove.S => memmove-asm.S}        |   0
>> >> >  newlib/libc/machine/riscv/memmove-stub.c      |  14 --
>> >> >  newlib/libc/machine/riscv/memmove.c           | 232 ++++++++++++++++++
>> >> >  5 files changed, 259 insertions(+), 41 deletions(-)
>> >> >  rename newlib/libc/machine/riscv/{memmove.S => memmove-asm.S} (100%)
>> >> >  delete mode 100644 newlib/libc/machine/riscv/memmove-stub.c
>> >> >  create mode 100644 newlib/libc/machine/riscv/memmove.c
>> >> >
>> >> > --
>> >> > 2.49.0
>> >> >