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

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