`On Wed, 13 Mar 2019 at 23:29:40 +0100, Rasmus Villemoes wrote:> On 21/02/2019 09.21, George Spelvin wrote:>> +/**>> + * parent - given the offset of the child, find the offset of the parent.>> + * @i: the offset of the heap element whose parent is sought.  Non-zero.>> + * @lsbit: a precomputed 1-bit mask, equal to "size & -size">> + * @size: size of each element>> + *>> + * In terms of array indexes, the parent of element j = i/size is simply>> + * (j-1)/2.  But when working in byte offsets, we can't use implicit>> + * truncation of integer divides.>> + *>> + * Fortunately, we only need one bit of the quotient, not the full divide.>> + * size has a least significant bit.  That bit will be clear if i is>> + * an even multiple of size, and set if it's an odd multiple.>> + *>> + * Logically, we're doing "if (i & lsbit) i -= size;", but since the>> + * branch is unpredictable, it's done with a bit of clever branch-free>> + * code instead.>> + */>> +__attribute_const__ __always_inline>> +static size_t parent(size_t i, unsigned int lsbit, size_t size)>> +{>> +	i -= size;>> +	i -= size & -(i & lsbit);>> +	return i / 2;>> +}>> +>> Really nice :) I had to work through this by hand, but it's solid.Thank you!  Yes, the way the mask doesn't include the low-order bitsthat don't matter anyway is a bit subtle.When the code is subtle, use lots of comments.  The entire reasonfor making this a separate helper function is to leave room forthe large comment.>> +	unsigned const lsbit = size & -size;	/* Used to find parent */>> Nit: qualifier before type, "const unsigned". And this sets ZF, so a> paranoid check for zero size (cf. the other mail) by doing "if (!lsbit)> return;" is practically free. Though it's probably a bit obscure doing> it that way...Actually, this is a personal style thing which I can ignore for the sakeof the kernel, but I believe that it's better to put the qualifier*after* the type.  This is due to C's pointer declaration syntax.The standard example of the issue is:	typedef char *pointer;	const char *a;	char const *b;	char * const c;	const pointer d;	pointer const e;Now, which variables are the same types?The answer is that a & b are the same (mutable pointer to constchar), and c, d & e are the same (const pointer to mutable char).I you make a habit of putting the qualifier *after* the type, thena simple "textual substitution" mental model for the typedef works,and it's clear that c and e are the same.It's also clear that b cannot be represented by the typedef becausethe const is between "char" and "*", and you obviously can't do thatwith the typedef.But if you put the qualifier first, it's annoying to rememeber whya and d are not the same type.So I've deliberately cultivated the style of putting the qualifierafter the type.But if the kernel prefers it before...>> +	if (!n)>> +		return;>> I'd make that n <= 1. Shouldn't be much more costly.(Actually, it's "num <= 1"; n is the pre-multiplied form son <= 1 can only happen when sorting one one-byte value.)I actually thought about this and decided not to bother.  I did itthis way during development to stress the general-case code.  Butshould I change it?=== NEVER MIND ===I had written a long reply justifying leaving it alone to save oneinstruction when the light dawned: I can do *both* tests in onestep with	size_t n = num * size, a = (num/2) * size;	unsigned const lsbit = size & -size;	/* Used to find parent */	if (!a)		/* num < 2 || size == 0 */		return;So now everyone's happy.> Nice!Thank you.  May I translate that into Acked-by?`