Messages in this thread | | | Date | Thu, 14 Mar 2019 11:10:41 +0200 | From | Andy Shevchenko <> | Subject | Re: [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
| |