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

1 files 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 */