mailing list of musl libc
 help / color / mirror / code / Atom feed
* [musl] [PATCH v3] add qsort_r and make qsort a wrapper around it
@ 2021-03-09 21:02 Érico Nogueira
  2021-09-24  0:18 ` Rich Felker
  0 siblings, 1 reply; 2+ messages in thread
From: Érico Nogueira @ 2021-03-09 21:02 UTC (permalink / raw)
  To: musl; +Cc: Érico Nogueira

we make qsort a wrapper by providing a wrapper_cmp function that uses
the extra argument as a function pointer. should be optimized to a tail
call on most architectures, as long as it's built with
-fomit-frame-pointer, so the performance impact should be minimal.

to keep the git history clean, for now qsort_r is implemented in qsort.c
and qsort is implemented in qsort_nr.c.  qsort.c also received a few
trivial cleanups, including replacing (*cmp)() calls with cmp().
qsort_nr.c contains only wrapper_cmp and qsort as a qsort_r wrapper
itself.
---

Following suggestions from IRC, as few changes as possible to the files,
a final clean up commit after this one would involve some git mv's (I
won't make a patch for it). Added weak_alias to force qsort to use
libc's qsort_r.

If this can't be accepted due to the overhead on some archs (ppc, mips,
arm in some situations?), maybe we could revisit v2 of the patch?

 include/stdlib.h      |  1 +
 src/include/stdlib.h  |  1 +
 src/stdlib/qsort.c    | 37 ++++++++++++++++++++-----------------
 src/stdlib/qsort_nr.c | 14 ++++++++++++++
 4 files changed, 36 insertions(+), 17 deletions(-)
 create mode 100644 src/stdlib/qsort_nr.c

diff --git a/include/stdlib.h b/include/stdlib.h
index b54a051f..0c0ced5f 100644
--- a/include/stdlib.h
+++ b/include/stdlib.h
@@ -158,6 +158,7 @@ struct __locale_struct;
 float strtof_l(const char *__restrict, char **__restrict, struct __locale_struct *);
 double strtod_l(const char *__restrict, char **__restrict, struct __locale_struct *);
 long double strtold_l(const char *__restrict, char **__restrict, struct __locale_struct *);
+void qsort_r (void *, size_t, size_t, int (*)(const void *, const void *, void *), void *);
 #endif
 
 #if defined(_LARGEFILE64_SOURCE) || defined(_GNU_SOURCE)
diff --git a/src/include/stdlib.h b/src/include/stdlib.h
index e9da2015..812b04de 100644
--- a/src/include/stdlib.h
+++ b/src/include/stdlib.h
@@ -8,6 +8,7 @@ hidden void __env_rm_add(char *, char *);
 hidden int __mkostemps(char *, int, int);
 hidden int __ptsname_r(int, char *, size_t);
 hidden char *__randname(char *);
+hidden void __qsort_r (void *, size_t, size_t, int (*)(const void *, const void *, void *), void *);
 
 hidden void *__libc_malloc(size_t);
 hidden void *__libc_malloc_impl(size_t);
diff --git a/src/stdlib/qsort.c b/src/stdlib/qsort.c
index da58fd31..20e40dda 100644
--- a/src/stdlib/qsort.c
+++ b/src/stdlib/qsort.c
@@ -24,6 +24,7 @@
 /* Smoothsort, an adaptive variant of Heapsort.  Memory usage: O(1).
    Run time: Worst case O(n log n), close to O(n) in the mostly-sorted case. */
 
+#define _GNU_SOURCE
 #include <stdint.h>
 #include <stdlib.h>
 #include <string.h>
@@ -31,7 +32,7 @@
 #include "atomic.h"
 #define ntz(x) a_ctz_l((x))
 
-typedef int (*cmpfun)(const void *, const void *);
+typedef int (*cmpfun)(const void *, const void *, void *);
 
 static inline int pntz(size_t p[2]) {
 	int r = ntz(p[0] - 1);
@@ -88,7 +89,7 @@ static inline void shr(size_t p[2], int n)
 	p[1] >>= n;
 }
 
-static void sift(unsigned char *head, size_t width, cmpfun cmp, int pshift, size_t lp[])
+static void sift(unsigned char *head, size_t width, cmpfun cmp, void *arg, int pshift, size_t lp[])
 {
 	unsigned char *rt, *lf;
 	unsigned char *ar[14 * sizeof(size_t) + 1];
@@ -99,10 +100,10 @@ static void sift(unsigned char *head, size_t width, cmpfun cmp, int pshift, size
 		rt = head - width;
 		lf = head - width - lp[pshift - 2];
 
-		if((*cmp)(ar[0], lf) >= 0 && (*cmp)(ar[0], rt) >= 0) {
+		if(cmp(ar[0], lf, arg) >= 0 && cmp(ar[0], rt, arg) >= 0) {
 			break;
 		}
-		if((*cmp)(lf, rt) >= 0) {
+		if(cmp(lf, rt, arg) >= 0) {
 			ar[i++] = lf;
 			head = lf;
 			pshift -= 1;
@@ -115,7 +116,7 @@ static void sift(unsigned char *head, size_t width, cmpfun cmp, int pshift, size
 	cycle(width, ar, i);
 }
 
-static void trinkle(unsigned char *head, size_t width, cmpfun cmp, size_t pp[2], int pshift, int trusty, size_t lp[])
+static void trinkle(unsigned char *head, size_t width, cmpfun cmp, void *arg, size_t pp[2], int pshift, int trusty, size_t lp[])
 {
 	unsigned char *stepson,
 	              *rt, *lf;
@@ -130,13 +131,13 @@ static void trinkle(unsigned char *head, size_t width, cmpfun cmp, size_t pp[2],
 	ar[0] = head;
 	while(p[0] != 1 || p[1] != 0) {
 		stepson = head - lp[pshift];
-		if((*cmp)(stepson, ar[0]) <= 0) {
+		if(cmp(stepson, ar[0], arg) <= 0) {
 			break;
 		}
 		if(!trusty && pshift > 1) {
 			rt = head - width;
 			lf = head - width - lp[pshift - 2];
-			if((*cmp)(rt, stepson) >= 0 || (*cmp)(lf, stepson) >= 0) {
+			if(cmp(rt, stepson, arg) >= 0 || cmp(lf, stepson, arg) >= 0) {
 				break;
 			}
 		}
@@ -150,11 +151,11 @@ static void trinkle(unsigned char *head, size_t width, cmpfun cmp, size_t pp[2],
 	}
 	if(!trusty) {
 		cycle(width, ar, i);
-		sift(head, width, cmp, pshift, lp);
+		sift(head, width, cmp, arg, pshift, lp);
 	}
 }
 
-void qsort(void *base, size_t nel, size_t width, cmpfun cmp)
+void __qsort_r(void *base, size_t nel, size_t width, cmpfun cmp, void *arg)
 {
 	size_t lp[12*sizeof(size_t)];
 	size_t i, size = width * nel;
@@ -173,16 +174,16 @@ void qsort(void *base, size_t nel, size_t width, cmpfun cmp)
 
 	while(head < high) {
 		if((p[0] & 3) == 3) {
-			sift(head, width, cmp, pshift, lp);
+			sift(head, width, cmp, arg, pshift, lp);
 			shr(p, 2);
 			pshift += 2;
 		} else {
 			if(lp[pshift - 1] >= high - head) {
-				trinkle(head, width, cmp, p, pshift, 0, lp);
+				trinkle(head, width, cmp, arg, p, pshift, 0, lp);
 			} else {
-				sift(head, width, cmp, pshift, lp);
+				sift(head, width, cmp, arg, pshift, lp);
 			}
-			
+
 			if(pshift == 1) {
 				shl(p, 1);
 				pshift = 0;
@@ -191,12 +192,12 @@ void qsort(void *base, size_t nel, size_t width, cmpfun cmp)
 				pshift = 1;
 			}
 		}
-		
+
 		p[0] |= 1;
 		head += width;
 	}
 
-	trinkle(head, width, cmp, p, pshift, 0, lp);
+	trinkle(head, width, cmp, arg, p, pshift, 0, lp);
 
 	while(pshift != 1 || p[0] != 1 || p[1] != 0) {
 		if(pshift <= 1) {
@@ -208,11 +209,13 @@ void qsort(void *base, size_t nel, size_t width, cmpfun cmp)
 			pshift -= 2;
 			p[0] ^= 7;
 			shr(p, 1);
-			trinkle(head - lp[pshift] - width, width, cmp, p, pshift + 1, 1, lp);
+			trinkle(head - lp[pshift] - width, width, cmp, arg, p, pshift + 1, 1, lp);
 			shl(p, 1);
 			p[0] |= 1;
-			trinkle(head - width, width, cmp, p, pshift, 1, lp);
+			trinkle(head - width, width, cmp, arg, p, pshift, 1, lp);
 		}
 		head -= width;
 	}
 }
+
+weak_alias(__qsort_r, qsort_r);
diff --git a/src/stdlib/qsort_nr.c b/src/stdlib/qsort_nr.c
new file mode 100644
index 00000000..fe408fb1
--- /dev/null
+++ b/src/stdlib/qsort_nr.c
@@ -0,0 +1,14 @@
+#define _GNU_SOURCE
+#include <stdlib.h>
+
+typedef int (*cmpfun)(const void *, const void *);
+
+static int wrapper_cmp(const void *v1, const void *v2, void *cmp)
+{
+	return ((cmpfun)cmp)(v1, v2);
+}
+
+void qsort(void *base, size_t nel, size_t width, cmpfun cmp)
+{
+	__qsort_r(base, nel, width, wrapper_cmp, cmp);
+}
-- 
2.30.2


^ permalink raw reply	[flat|nested] 2+ messages in thread

* Re: [musl] [PATCH v3] add qsort_r and make qsort a wrapper around it
  2021-03-09 21:02 [musl] [PATCH v3] add qsort_r and make qsort a wrapper around it Érico Nogueira
@ 2021-09-24  0:18 ` Rich Felker
  0 siblings, 0 replies; 2+ messages in thread
From: Rich Felker @ 2021-09-24  0:18 UTC (permalink / raw)
  To: Érico Nogueira; +Cc: musl

On Tue, Mar 09, 2021 at 06:02:13PM -0300, Érico Nogueira wrote:
> we make qsort a wrapper by providing a wrapper_cmp function that uses
> the extra argument as a function pointer. should be optimized to a tail
> call on most architectures, as long as it's built with
> -fomit-frame-pointer, so the performance impact should be minimal.
> 
> to keep the git history clean, for now qsort_r is implemented in qsort.c
> and qsort is implemented in qsort_nr.c.  qsort.c also received a few
> trivial cleanups, including replacing (*cmp)() calls with cmp().
> qsort_nr.c contains only wrapper_cmp and qsort as a qsort_r wrapper
> itself.
> ---
> 
> Following suggestions from IRC, as few changes as possible to the files,
> a final clean up commit after this one would involve some git mv's (I
> won't make a patch for it). Added weak_alias to force qsort to use
> libc's qsort_r.
> 
> If this can't be accepted due to the overhead on some archs (ppc, mips,
> arm in some situations?), maybe we could revisit v2 of the patch?
> 
>  include/stdlib.h      |  1 +
>  src/include/stdlib.h  |  1 +
>  src/stdlib/qsort.c    | 37 ++++++++++++++++++++-----------------
>  src/stdlib/qsort_nr.c | 14 ++++++++++++++
>  4 files changed, 36 insertions(+), 17 deletions(-)
>  create mode 100644 src/stdlib/qsort_nr.c
> 
> diff --git a/include/stdlib.h b/include/stdlib.h
> index b54a051f..0c0ced5f 100644
> --- a/include/stdlib.h
> +++ b/include/stdlib.h
> @@ -158,6 +158,7 @@ struct __locale_struct;
>  float strtof_l(const char *__restrict, char **__restrict, struct __locale_struct *);
>  double strtod_l(const char *__restrict, char **__restrict, struct __locale_struct *);
>  long double strtold_l(const char *__restrict, char **__restrict, struct __locale_struct *);
> +void qsort_r (void *, size_t, size_t, int (*)(const void *, const void *, void *), void *);
>  #endif
> [...]

I'm merging this now with the change from only exposing it under
_GNU_SOURCE to _BSD_SOURCE (default). As it's been accepted for POSIX
future, I'd like to make it visible under baseline POSIX profile too,
but I think that's a potentially riskier change that we can do later.

As noted many times, the issue of GCC refusing to tail call on some
archs is unfortunate, but we should get this fixed on the GCC side
rather than doing ugly things trying to work around it.

Rich

^ permalink raw reply	[flat|nested] 2+ messages in thread

end of thread, other threads:[~2021-09-24  0:18 UTC | newest]

Thread overview: 2+ messages (download: mbox.gz / follow: Atom feed)
-- links below jump to the message on this page --
2021-03-09 21:02 [musl] [PATCH v3] add qsort_r and make qsort a wrapper around it Érico Nogueira
2021-09-24  0:18 ` Rich Felker

Code repositories for project(s) associated with this public inbox

	https://git.vuxu.org/mirror/musl/

This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox;
as well as URLs for NNTP newsgroup(s).