From: Andy Shevchenko <andriy.shevchenko@linux.intel.com>
To: George Spelvin <lkml@sdf.org>
Cc: linux-kernel@vger.kernel.org,
Andrew Morton <akpm@linux-foundation.org>,
Andrey Abramov <st5pub@yandex.ru>,
Geert Uytterhoeven <geert@linux-m68k.org>,
Daniel Wagner <daniel.wagner@siemens.com>,
Rasmus Villemoes <linux@rasmusvillemoes.dk>,
Don Mullis <don.mullis@gmail.com>,
Dave Chinner <dchinner@redhat.com>
Subject: Re: [PATCH 4/5] lib/list_sort: Simplify and remove MAX_LIST_LENGTH_BITS
Date: Thu, 14 Mar 2019 11:10:41 +0200 [thread overview]
Message-ID: <20190314091041.GU9224@smile.fi.intel.com> (raw)
In-Reply-To: <dd447448384883bd42c41f0de6a83430b6435dc1.1552097842.git.lkml@sdf.org>
On Tue, Mar 05, 2019 at 03:06:44AM +0000, George Spelvin wrote:
> Rather than a fixed-size array of pending sorted runs, use the ->prev
> links to keep track of things. This reduces stack usage, eliminates
> some ugly overflow handling, and reduces the code size.
>
> Also:
> * merge() no longer needs to handle NULL inputs, so simplify.
> * The same applies to merge_and_restore_back_links(), which is renamed
> to the less ponderous merge_final(). (It's a static helper function,
> so we don't need a super-descriptive name; comments will do.)
>
> x86-64 code size 1086 -> 740 bytes (-346)
> + do {
> + size_t bit;
> struct list_head *cur = list;
> +
> + /* Extract the head of "list" as a single-element list "cur" */
> list = list->next;
> cur->next = NULL;
>
> + /* Do merges corresponding to set lsbits in count */
> + for (bit = 1; count & bit; bit <<= 1) {
> + cur = merge(priv, (cmp_func)cmp, pending, cur);
> + pending = pending->prev; /* Untouched by merge() */
> }
Wouldn't be it the same to
bit = ffz(count);
while (bit--) {
...
}
?
Though I dunno which one is generating better code.
> + /* And place the result at the head of "pending" */
> + cur->prev = pending;
> + pending = cur;
> + count++;
> + } while (list->next);
> +
> + /* Now merge together last element with all pending lists */
> + while (pending->prev) {
> + list = merge(priv, (cmp_func)cmp, pending, list);
> + pending = pending->prev;
> }
--
With Best Regards,
Andy Shevchenko
next prev parent reply other threads:[~2019-03-14 9:10 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
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 [this message]
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=20190314091041.GU9224@smile.fi.intel.com \
--to=andriy.shevchenko@linux.intel.com \
--cc=akpm@linux-foundation.org \
--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=lkml@sdf.org \
--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).