[<prev] [next>] [thread-next>] [day] [month] [year] [list]
```Date: Fri,  9 Jul 2021 13:26:28 +0200 (CEST)
From: jason <jason@...omnia247.nl>
To: musl@...ts.openwall.com
Cc: jason@...omnia247.nl
Subject: Improvements to qsort

I've been trying to understand ngmalloc, and it's a struggle, so for
relaxation I had a look at qsort, and have a few suggestions.

To avoid burying the lead, the following reduces comparisons by

--- a/qsort.c
+++ b/qsort.c
@@ -100,18 +100,16 @@ static void sift(unsigned char *head, size_t width, cmpfun cmp, int pshift, size
lf = head - width - lp[pshift - 2];

-		if((*cmp)(ar, lf) >= 0 && (*cmp)(ar, rt) >= 0) {
-			break;
-		}
if((*cmp)(lf, rt) >= 0) {
-			ar[i++] = lf;
pshift -= 1;
} else {
-			ar[i++] = rt;
pshift -= 2;
}
+			break;
}
cycle(width, ar, i);
}

Basically, instead of doing two comparisons to see if ar is greater
than both the left and right children and then comparing the children
with each other to find the greater one, find the greater child and
compare ar with that one.

I have several other less-significant changes that I wonder if musl is
interested in:

* I notice than pntz() is always used in the following context:
trail = pntz(p);
shr(p, trail);
pshift += trail;
both pntz() and shr() have branches conditional on whether the shift
is more or less than 8*sizeof(size_t) bits.  I have replaced this
by a single function, which allows the conditional branch to be
shared:

/*
* Re-normalize p[].  Ignore the low-order bit (which must be set!),
* find the position of the next-least-significant bit, and shift p[]
* down by that much.  Return the number of bits shifted.
*
* There must be a penultimate trailing bit; i.e. p[] must not be {1, 0}.
*/
static inline int normalize(size_t p)
{
int s;
size_t t = p - 1;

if (t == 0) {
t = p;
s = ntz(t);
p = t >> s;
p = 0;
s += 8*sizeof(size_t);
} else {
s = ntz(t);
p = t >> s | p << (8*sizeof(size_t) - s);
p >>= s;
}
return s;
}

which is used simply as:
pshift += normalize(p);

in general, the meaning of p[] and pindex, what a "stepson" is,
when it's okay to use sift() instead of trinkle(), what the "trusty"
flag means, how cycle() is used, etc.  Would these be worth cleaning
up and submitting?

* In my private copy, I have changed the type of "trusty" to bool,
a data type I'm quite fond of as it concisely documents the limited
range of values.  I notice, however, that musl is completely devoid of
any use of <stdbool.h>, although it uses other C99 features.  Is this
a conscious decision?

* Likewise, I notice that most musl code has a space in "keyword (condition)"
like "if (foo != 0)", "while (bar < N)" and "for (i=0; i < N; i++)".
But the qsort() code, with one single exception, omits the space.

Likewise, most msul code is quite happy to "if (condition) break;"
on a single line, with no braces, but the original sift() function
above puts the break on a second line and a closing brace on a third.

The musl code base is inconsistent enough that it's hard to infer code
formatting conventions.  Are these discrepancies in qsort a problem
worth fixing?

* The way the heap-building loop maintains its loop invariants is a trifle
peculiar.  It begins with the element at *head included in p[] and pindex,
but excluded from the heap ordering invariants.  Then it establishes
the ordering invariants (with sift() or trinkle()) and immediately adds
another (un-ordered) element to p[] and pindex.

After the main loop exits, a standalone call to trinkle() places the
final element in heap order.

I have a more conventional (add, then sift) ordering working which
seems to simplify the code:
+		bool notrinkle = false;
+
+		/* Append an element to the heap */
if((p & 3) == 3) {
-			sift(head, width, cmp, pshift, lp);
shr(p, 2);
pshift += 2;
-		} else {
-			if(lp[pshift - 1] >= high - head) {
-				trinkle(head, width, cmp, p, pshift, 0, lp);
-			} else {
+			if((size_t)(high - head) > lp[pshift - 1]) {
+				notrinkle = true;
}
-
-			if(pshift == 1) {
-				shl(p, 1);
-				pshift = 0;
-			} else {
-				shl(p, pshift - 1);
-				pshift = 1;
-			}
+		} else if(pshift == 1) {
+			/* order-1 exists; new tree is order-0 */
+			shl(p, 1);
+			pshift = 0;
+			notrinkle = (high != head);
+		} else {
+			/* new tree is order-1 */
+			shl(p, pshift - 1);
+			pshift = 1;
+			notrinkle = ((size_t)(high - head) > lp);
}
-
p |= 1;
+
+		/* Re-establish the heap using trinkle */
+		if(!notrinkle)
+			trinkle(head, width, cmp, p, pshift, false, lp);
}

-	trinkle(head, width, cmp, p, pshift, 0, lp);

If the original ordering is wanted, then the loop initialization
can be changed to start with two elements (p = 3, pindex = 0,
head = base + width), since two elements automatically fulfil the
required loop invariants.

Does anyone have a preference?

* Since the first test in qsort() excludes width == 0, the loop over
width in cycle() can be changed to "do { ... } while (width);".

* The ar[] array in sift() only has to be as large as the lp[]
array in qsort(), not 1/6 larger.

* The ar[] array in trinkle() only has to be half as large, plus one.

* The pindex > 1 case in the heap-consuming loop contains some
redundant left-then-right shifting:
shl(p, 2);
pshift -= 2;
p ^= 7;
shr(p, 1);
This can be optimized.

* There are several cases where variables can be moved into
smaller local scopes, particularly the "stepson", "rt" and "lf"
variables in trinkle().  This is another change I've made privately
as I think it makes the code more reasonable.  Worth submitting?

* GCC emits a couple of signed/unsigned comparison warnings with
-W -Wall.  Worth fixing?
```

Confused about mailing lists and their use? Read about mailing lists on Wikipedia and check out these guidelines on proper formatting of your messages.