lkml.org 
[lkml]   [2019]   [Mar]   [14]   [last100]   RSS Feed
Views: [wrap][no wrap]   [headers]  [forward] 
 
Messages in this thread
/
Date
From
SubjectRe: [PATCH 4/5] lib/list_sort: Simplify and remove MAX_LIST_LENGTH_BITS
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


\
 
 \ /
  Last update: 2019-03-14 10:11    [W:0.221 / U:12.748 seconds]
©2003-2020 Jasper Spaans|hosted at Digital Ocean and TransIP|Read the blog|Advertise on this site