Messages in this thread | | | Date | Fri, 15 Mar 2019 04:33:09 GMT | From | George Spelvin <> | Subject | Re: [PATCH 4/5] lib/list_sort: Simplify and remove MAX_LIST_LENGTH_BITS |
| |
On Thu, 14 Mar 2019 at 11:10:41 +0200, Andy Shevchenko wrote: > On Tue, Mar 05, 2019 at 03:06:44AM +0000, George Spelvin wrote: >> + 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.
One question I should ask everyone: should "count" be 32 or 64 bits on 64-bit machines? That would let x86 save a few REX bytes. (815 vs. 813 byte code, if anyone cares.)
Allegedy ARM can save a few pJ by gating the high 32 bits of the ALU.
Most other 64-bit processors would prefer 64-bit operations as it saves masking operations.
If we never sort a list with more than 2^32 entries, it makes no difference.
If we use a 32-bit count and we *do* sort a list with more than 2^32 entries, then it still sorts, but the performance degrades to O((n/2^32)^2).
Just how often do we expect the kernel to face lists that long? (Note that the old code was O((n/2^20)^2).)
In the code, I could do something like
#ifdef CONFIG_X86_64 /* Comment explaining why */ typedef uint32_t count_t; #else typedef size_t count_t; #endif
... count_t count = 0;
| |