[<prev] [next>] [day] [month] [year] [list]
Message-ID: <20261031225431.29980-1-parker@cronstable.dev>
Date: Sat, 31 Oct 2026 18:54:31 -0400
From: Parker Loflin <parker@...nstable.dev>
To: musl@...ts.openwall.com
Subject: [PATCH] x86_64 memmove: replace backward std; rep movsb with a 16-byte loop
the backward path, taken when dst overlaps src from above, set the
direction flag and used rep movsb. fast-string operation does not
apply with the direction flag set, so on current cpus this copies one
byte per iteration, and std/cld add a fixed cost to every call, even
for tiny moves. commit 2bf46931 anticipated going back to this if
performance problems turned up.
copy backward 16 bytes at a time with unaligned sse2 loads and stores
instead. the first 16 source bytes are loaded before the loop and
stored last, covering whatever the loop leaves at the bottom, so there
is no remainder loop. 8 to 15 bytes use two overlapping 8-byte moves,
and shorter moves a byte loop. since dst > src, every store lands
above every later load, so this is correct for any overlap. the
forward path is unchanged.
---
The backward path of x86_64 memmove set the direction flag and used
rep movsb. There's no fast-string operation with DF=1, so it copies
one byte at a time, and every call pays a fixed 40-65 ns even for a
4-byte move. Overlapping moves with dst > src are common: inserting
into a sorted array or vector, shifting a buffer right in place, gap
buffers.
Numbers, ns per call, min over runs, pinned to one cpu. Zen 5 is a
Ryzen 7 9800X3D under WSL2; Emerald Rapids is a Xeon KVM guest.
Zen 5 Emerald Rapids
before after before after
d=1 n=4 41.0 1.4 65.3 3.7
d=1 n=16 43.8 3.0 69.6 6.1
d=1 n=256 90.4 4.7 146.2 9.2
d=1 n=4k 853 59 1277 85
d=1 n=64k 13002 805 20252 1581
d=1 n=2M 415522 26387 630946 72260
d=n/2+1 n=64k 12986 811 19736 2100
random backward,
n=0..511 90.6 4.0 145.7 16.0
Forward and non-overlapping moves run the same code as before and
time the same within noise on both machines.
Sorted insertion of 100k random ints into an int array (binary
search, then memmove the tail up by one): 2026 -> 130 ms on Zen 5,
3265 -> 249 ms on Emerald Rapids.
Tested against a naive reference for every length 0..4096 with
overlap distances -80..80 plus distances near +-n and +-n/2, 16
source alignments, guard bytes on both sides and the return value,
plus 220k random cases up to 1 MiB, static and shared. libc-test
results are the same before and after.
As far as I can tell this would be the first use of sse registers in
musl's string asm. sse2 is baseline on x86_64, but if you'd rather
keep it gpr-only, the same loop with 8-byte gpr moves is about half
as fast from 1k up (64k: 1594 vs 805 ns on Zen 5) and still about 8x
faster than the current code; I can send that version instead.
Dropping the asm for src/string/memmove.c doesn't help: its backward
loop is still byte-at-a-time unless the distance is a multiple of 8,
and its forward path is slower than __memcpy_fwd for overlapping
moves.
i386 memmove.s has the same std; rep movsb backward path. sse2 isn't
baseline there, so the matching fix would be a 4-byte gpr loop; I can
send it if this approach is acceptable.
src/string/x86_64/memmove.s | 32 +++++++++++++++++++++++++-------
1 file changed, 25 insertions(+), 7 deletions(-)
diff --git a/src/string/x86_64/memmove.s b/src/string/x86_64/memmove.s
index 172c0252..8960bb8b 100644
--- a/src/string/x86_64/memmove.s
+++ b/src/string/x86_64/memmove.s
@@ -6,11 +6,29 @@ memmove:
cmp %rdx,%rax
.hidden __memcpy_fwd
jae __memcpy_fwd
- mov %rdx,%rcx
- lea -1(%rdi,%rdx),%rdi
- lea -1(%rsi,%rdx),%rsi
- std
- rep movsb
- cld
- lea 1(%rdi),%rax
+ mov %rdi,%rax
+ cmp $16,%rdx
+ jb 2f
+ movups (%rsi),%xmm1
+ sub $16,%rdx
+ jbe 1f
+3: movups (%rsi,%rdx),%xmm0
+ movups %xmm0,(%rdi,%rdx)
+ sub $16,%rdx
+ ja 3b
+1: movups %xmm1,(%rdi)
+ ret
+2: cmp $8,%edx
+ jb 2f
+ mov (%rsi),%rcx
+ mov -8(%rsi,%rdx),%rsi
+ mov %rsi,-8(%rdi,%rdx)
+ mov %rcx,(%rdi)
ret
+2: test %edx,%edx
+ jz 1f
+3: dec %edx
+ movzbl (%rsi,%rdx),%ecx
+ mov %cl,(%rdi,%rdx)
+ jnz 3b
+1: ret
--
2.43.0
Powered by blists - more mailing lists
Confused about mailing lists and their use?
Read about mailing lists on Wikipedia
and check out these
guidelines on proper formatting of your messages.
