From fa9ca80852b3b1ef830abad923797c4a84b10a9e Mon Sep 17 00:00:00 2001
From: millert <>
Date: Wed, 17 May 2017 16:58:20 +0000
Subject: The BSD qsort() performs tail recursion elimination on the second
 side of the array being partitioned to save on stack space.  Greater savings
 can be gained by choosing recursion for the smaller side of the partition and
 eliminating recursion for the larger side. This also results in a small but
 measurable performance gain. OK otto@ schwarze@

---
 src/lib/libc/stdlib/qsort.c | 35 +++++++++++++++++++++++++----------
 1 file changed, 25 insertions(+), 10 deletions(-)

(limited to 'src')

diff --git a/src/lib/libc/stdlib/qsort.c b/src/lib/libc/stdlib/qsort.c
index f16f9d0ebf..c97979ef01 100644
--- a/src/lib/libc/stdlib/qsort.c
+++ b/src/lib/libc/stdlib/qsort.c
@@ -1,4 +1,4 @@
-/*	$OpenBSD: qsort.c,v 1.14 2017/01/04 15:20:30 millert Exp $ */
+/*	$OpenBSD: qsort.c,v 1.15 2017/05/17 16:58:20 millert Exp $ */
 /*-
  * Copyright (c) 1992, 1993
  *	The Regents of the University of California.  All rights reserved.
@@ -85,7 +85,7 @@ qsort(void *aa, size_t n, size_t es, int (*cmp)(const void *, const void *))
 {
 	char *pa, *pb, *pc, *pd, *pl, *pm, *pn;
 	int cmp_result, swaptype;
-	size_t d, r;
+	size_t d, r, s;
 	char *a = aa;
 
 loop:	SWAPINIT(a, es);
@@ -139,14 +139,29 @@ loop:	SWAPINIT(a, es);
 	vecswap(a, pb - r, r);
 	r = min(pd - pc, pn - pd - es);
 	vecswap(pb, pn - r, r);
-	if ((r = pb - pa) > es)
-		qsort(a, r / es, es, cmp);
-	if ((r = pd - pc) > es) { 
-		/* Iterate rather than recurse to save stack space */
-		a = pn - r;
-		n = r / es;
-		goto loop;
+	/*
+	 * To save stack space we sort the smaller side of the partition first
+	 * using recursion and eliminate tail recursion for the larger side.
+	 */
+	r = pb - pa;
+	s = pd - pc;
+	if (r < s) {
+		/* Recurse for 1st side, iterate for 2nd side. */
+		if (s > es) {
+			if (r > es)
+				qsort(a, r / es, es, cmp);
+			a = pn - s;
+			n = s / es;
+			goto loop;
+		}
+	} else {
+		/* Recurse for 2nd side, iterate for 1st side. */
+		if (r > es) {
+			if (s > es)
+				qsort(pn - s, s / es, es, cmp);
+			n = r / es;
+			goto loop;
+		}
 	}
-/*		qsort(pn - r, r / es, es, cmp);*/
 }
 DEF_STRONG(qsort);
-- 
cgit v1.2.3-55-g6feb