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

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
> >> >
>