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
