Date: Sun, 02 Aug 2026 12:10:50 +0000 From: Robert Clausecker <fuz@FreeBSD.org> To: src-committers@FreeBSD.org, dev-commits-src-all@FreeBSD.org, dev-commits-src-main@FreeBSD.org Cc: Minsoo Choo <minsoochoo0122@proton.me> Subject: git: 00a79975c062 - main - libc/merge.c: use memcpy() for copying Message-ID: <6a6f33ca.1f0f3.c2ca741@gitrepo.freebsd.org>
index | next in thread | raw e-mail
The branch main has been updated by fuz: URL: https://cgit.FreeBSD.org/src/commit/?id=00a79975c062650ba15e432e30776d42fc44fbaa commit 00a79975c062650ba15e432e30776d42fc44fbaa Author: Minsoo Choo <mchoo@FreeBSD.org> AuthorDate: 2026-07-02 19:47:33 +0000 Commit: Robert Clausecker <fuz@FreeBSD.org> CommitDate: 2026-08-02 11:17:45 +0000 libc/merge.c: use memcpy() for copying Currently mergesort() uses ICOPY_*() to copy data as four byte blocks instead of one byte. However, this is only achievable when both size and base arguments are aligned to four bytes. Use of memcpy() is ideal as 1) it is cleaner and 2) the library will use SIMD for copying when the hardware supports it. Compared to ICOPY_*(), SIMD can support up to 64 bytes. When the SIMD-backed memcpy() find the address is unaligned, it can first copy data up to the nearest aligned address, and then use SIMD operations for faster transfer. Thus memcpy() can give better performance than mergesort()'s own implementation. This is benchmarked on amd64 where there isn't a SIMD-backed implementation yet. However, the baseline implementation in assembly already delivers better performance in unaligned cases although there is some performance drops in aligned cases. The benchmark results and script is available in the Phabricator review. Ideally, more performance improvements will come when amd64 gets SIMD implementation of memcpy(). Signed-off-by: Minsoo Choo <minsoochoo0122@proton.me> Reviewed by: fuz MFC after: 1 week Differential Revision: https://reviews.freebsd.org/D58002 --- lib/libc/stdlib/merge.c | 69 +++++++++++++++---------------------------------- 1 file changed, 21 insertions(+), 48 deletions(-) diff --git a/lib/libc/stdlib/merge.c b/lib/libc/stdlib/merge.c index e07a3947e741..7c15fa7953f9 100644 --- a/lib/libc/stdlib/merge.c +++ b/lib/libc/stdlib/merge.c @@ -66,25 +66,19 @@ typedef int (*cmp_t)(const void *, const void *); static void setup(u_char *, u_char *, size_t, size_t, cmp_t); static void insertionsort(u_char *, size_t, size_t, cmp_t); -#define ISIZE sizeof(int) #define PSIZE sizeof(u_char *) -#define ICOPY_LIST(src, dst, last) \ - do \ - *(int*)dst = *(int*)src, src += ISIZE, dst += ISIZE; \ - while(src < last) -#define ICOPY_ELT(src, dst, i) \ - do \ - *(int*) dst = *(int*) src, src += ISIZE, dst += ISIZE; \ - while (i -= ISIZE) - -#define CCOPY_LIST(src, dst, last) \ - do \ - *dst++ = *src++; \ - while (src < last) -#define CCOPY_ELT(src, dst, i) \ - do \ - *dst++ = *src++; \ - while (i -= 1) +#define COPY_LIST(src, dst, last) \ + do { \ + memcpy(dst, src, last - src); \ + dst += last - src; \ + src += last - src; \ + } while (0) +#define COPY_ELT(src, dst, i) \ + do { \ + memcpy(dst, src, i); \ + src += i; \ + dst += i; \ + } while (0) /* * Find the next possible pointer head. (Trickery for forcing an array @@ -112,7 +106,7 @@ mergesort(void *base, size_t nmemb, size_t size, cmp_t cmp) { size_t i, nbytes, asize; int sense; - int big, iflag; + int big; u_char *f1, *f2, *t, *b, *tp2, *q, *l1, *l2; u_char *list2, *list1, *p2, *p, *last, **p1; @@ -129,10 +123,6 @@ mergesort(void *base, size_t nmemb, size_t size, cmp_t cmp) return (-1); } - iflag = 0; - if (__is_aligned(size, ISIZE) && __is_aligned(base, ISIZE)) - iflag = 1; - if ((list2 = malloc(asize)) == NULL) return (-1); @@ -200,34 +190,17 @@ COPY: b = t; } i = size; if (q == f1) { - if (iflag) { - ICOPY_LIST(f2, tp2, b); - ICOPY_ELT(f1, tp2, i); - } else { - CCOPY_LIST(f2, tp2, b); - CCOPY_ELT(f1, tp2, i); - } + COPY_LIST(f2, tp2, b); + COPY_ELT(f1, tp2, i); } else { - if (iflag) { - ICOPY_LIST(f1, tp2, b); - ICOPY_ELT(f2, tp2, i); - } else { - CCOPY_LIST(f1, tp2, b); - CCOPY_ELT(f2, tp2, i); - } + COPY_LIST(f1, tp2, b); + COPY_ELT(f2, tp2, i); } } - if (f2 < l2) { - if (iflag) - ICOPY_LIST(f2, tp2, l2); - else - CCOPY_LIST(f2, tp2, l2); - } else if (f1 < l1) { - if (iflag) - ICOPY_LIST(f1, tp2, l1); - else - CCOPY_LIST(f1, tp2, l1); - } + if (f2 < l2) + COPY_LIST(f2, tp2, l2); + else if (f1 < l1) + COPY_LIST(f1, tp2, l1); *p1 = l2; } tp2 = list1; /* swap list1, list2 */home | help
Want to link to this message? Use this
URL: <https://mail-archive.FreeBSD.org/cgi/mid.cgi?6a6f33ca.1f0f3.c2ca741>