Messages in this thread | | | From | Geert Uytterhoeven <> | Date | Fri, 15 Mar 2019 09:20:58 +0100 | Subject | Re: [PATCH 4/5] lib/list_sort: Simplify and remove MAX_LIST_LENGTH_BITS |
| |
Hi George,
On Fri, Mar 15, 2019 at 5:33 AM George Spelvin <lkml@sdf.org> wrote: > 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).)
Using size_t sounds most logical to me (argument of least surprise).
> 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;
Using different types makes it more complex, e.g. to print the value in debug code. And adding more typedefs is frowned upon.
Just my 0.02€.
Gr{oetje,eeting}s,
Geert
-- Geert Uytterhoeven -- There's lots of Linux beyond ia32 -- geert@linux-m68k.org
In personal conversations with technical people, I call myself a hacker. But when I'm talking to journalists I just say "programmer" or something like that. -- Linus Torvalds
| |