lkml.org 
[lkml]   [2019]   [Mar]   [15]   [last100]   RSS Feed
Views: [wrap][no wrap]   [headers]  [forward] 
 
Messages in this thread
    /
    From
    Date
    SubjectRe: [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

    \
     
     \ /
      Last update: 2019-03-15 09:22    [W:2.523 / U:0.012 seconds]
    ©2003-2020 Jasper Spaans|hosted at Digital Ocean and TransIP|Read the blog|Advertise on this site