From: George Spelvin <lkml@sdf.org>
To: linux-kernel@vger.kernel.org, linux@rasmusvillemoes.dk, lkml@sdf.org
Cc: akpm@linux-foundation.org, andriy.shevchenko@linux.intel.com,
daniel.wagner@siemens.com, dchinner@redhat.com,
don.mullis@gmail.com, geert@linux-m68k.org, st5pub@yandex.ru
Subject: Re: [PATCH 2/5] lib/sort: Use more efficient bottom-up heapsort variant
Date: Thu, 14 Mar 2019 00:03:31 GMT [thread overview]
Message-ID: <201903140003.x2E03VZO028625@sdf.org> (raw)
In-Reply-To: <472510ad-77f9-49e8-4122-52f447cb1c15@rasmusvillemoes.dk>
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 bits
that don't matter anyway is a bit subtle.
When the code is subtle, use lots of comments. The entire reason
for making this a separate helper function is to leave room for
the 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 sake
of 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 const
char), and c, d & e are the same (const pointer to mutable char).
I you make a habit of putting the qualifier *after* the type, then
a 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 because
the const is between "char" and "*", and you obviously can't do that
with the typedef.
But if you put the qualifier first, it's annoying to rememeber why
a and d are not the same type.
So I've deliberately cultivated the style of putting the qualifier
after 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 so
n <= 1 can only happen when sorting one one-byte value.)
I actually thought about this and decided not to bother. I did it
this way during development to stress the general-case code. But
should I change it?
=== NEVER MIND ===
I had written a long reply justifying leaving it alone to save one
instruction when the light dawned: I can do *both* tests in one
step 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?
next prev parent reply other threads:[~2019-03-14 0:03 UTC|newest]
Thread overview: 44+ messages / expand[flat|nested] mbox.gz Atom feed top
2019-03-09 2:17 [PATCH 0/5] lib/sort & lib/list_sort: faster and smaller George Spelvin
2019-02-21 6:30 ` [PATCH 1/5] lib/sort: Make swap functions more generic George Spelvin
[not found] ` <20190309140653.GO9224@smile.fi.intel.com>
2019-03-09 15:53 ` lkml
2019-03-09 20:19 ` Andrey Abramov
2019-03-14 9:29 ` Andy Shevchenko
2019-03-14 10:09 ` George Spelvin
2019-03-14 10:41 ` Geert Uytterhoeven
2019-03-14 11:53 ` George Spelvin
2019-03-14 12:18 ` Andy Shevchenko
2019-03-14 19:59 ` Andrey Abramov
2019-03-15 3:35 ` George Spelvin
2019-03-15 8:27 ` Geert Uytterhoeven
2019-03-14 10:11 ` George Spelvin
2019-03-09 21:02 ` George Spelvin
2019-03-13 21:23 ` Rasmus Villemoes
2019-03-13 22:02 ` Geert Uytterhoeven
2019-03-13 23:15 ` George Spelvin
2019-02-21 8:21 ` [PATCH 2/5] lib/sort: Use more efficient bottom-up heapsort variant George Spelvin
2019-03-13 22:29 ` Rasmus Villemoes
2019-03-14 0:03 ` George Spelvin [this message]
2019-03-14 0:15 ` Rasmus Villemoes
2019-02-21 8:21 ` [PATCH 3/5] lib/sort: Avoid indirect calls to built-in swap George Spelvin
2019-03-05 3:06 ` [PATCH 4/5] lib/list_sort: Simplify and remove MAX_LIST_LENGTH_BITS George Spelvin
2019-03-10 21:54 ` Rasmus Villemoes
2019-03-10 22:29 ` George Spelvin
2019-03-14 9:10 ` Andy Shevchenko
2019-03-14 9:41 ` George Spelvin
2019-03-15 4:33 ` George Spelvin
2019-03-15 8:20 ` Geert Uytterhoeven
2019-03-15 10:23 ` George Spelvin
2019-03-15 12:57 ` Geert Uytterhoeven
2019-03-15 16:59 ` George Spelvin
2019-03-15 17:47 ` Geert Uytterhoeven
2019-03-15 18:53 ` Andrey Abramov
2019-03-15 19:06 ` Andy Shevchenko
2019-03-15 19:23 ` Andrey Abramov
2019-03-15 19:56 ` Andy Shevchenko
2019-03-16 3:49 ` George Spelvin
2019-03-05 5:58 ` [PATCH 5/5] lib/list_sort: Optimize number of calls to comparison function George Spelvin
2019-03-13 23:28 ` Rasmus Villemoes
2019-03-14 1:58 ` George Spelvin
2019-06-21 23:12 ` Rasmus Villemoes
2019-12-08 8:01 ` George Spelvin
2019-03-15 19:54 ` [PATCH 0/5] lib/sort & lib/list_sort: faster and smaller Andrey Abramov
Reply instructions:
You may reply publicly to this message via plain-text email
using any one of the following methods:
* Save the following mbox file, import it into your mail client,
and reply-to-all from there: mbox
Avoid top-posting and favor interleaved quoting:
https://en.wikipedia.org/wiki/Posting_style#Interleaved_style
* Reply using the --to, --cc, and --in-reply-to
switches of git-send-email(1):
git send-email \
--in-reply-to=201903140003.x2E03VZO028625@sdf.org \
--to=lkml@sdf.org \
--cc=akpm@linux-foundation.org \
--cc=andriy.shevchenko@linux.intel.com \
--cc=daniel.wagner@siemens.com \
--cc=dchinner@redhat.com \
--cc=don.mullis@gmail.com \
--cc=geert@linux-m68k.org \
--cc=linux-kernel@vger.kernel.org \
--cc=linux@rasmusvillemoes.dk \
--cc=st5pub@yandex.ru \
/path/to/YOUR_REPLY
https://kernel.org/pub/software/scm/git/docs/git-send-email.html
* If your mail client supports setting the In-Reply-To header
via mailto: links, try the mailto: link
Be sure your reply has a Subject: header at the top and a blank line
before the message body.
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).