lkml.org 
[lkml]   [2022]   [Jul]   [28]   [last100]   RSS Feed
Views: [wrap][no wrap]   [headers]  [forward] 
 
Messages in this thread
/
From
Date
SubjectRe: [PATCH 0/5] lib/find: optimize find_bit() functions
On Thu, Jul 28, 2022 at 9:12 AM Yury Norov <yury.norov@gmail.com> wrote:
>
> In the recent discussion [1], it was noticed that find_next_bit()
> functions may be improved by adding wrappers around common
> __find_next_bit().

So looking at the end result, this generates fairly good code.

I say "fairly good" because _find_next_and_bit() ends up being disgusting.

The reason? That

if (addr2)
tmp &= addr2[start / BITS_PER_LONG];

generates horrific code when 'addr2' isn't seen to be always NULL.

So this doesn't affect the regular _find_next_bit case, because the
inliner sees that addr2 is always NULL and doesn't generate extra code
for it.

But the code that actually *does* have two incoming bitmasks will now
pointlessly test that second bitmask pointer all the time.

Now, that particular function probably doesn't matter, but this code
seems to be unnecessarily written to try to be overly generic, and
that

(a) makes it hard to read the source code because the source code
doesn't do the obvious thing

(b) clearly generates suboptimal code too

so I'm really not a huge fan of this "try to share code". Not when the
resulting shared code is harder to read, and impossible for the
compiler to do a great job at.

And the code sharing really doesn't help all that much.

If you really want to generate good code, use macros, and share the
logic that way. Not hugely readable either, but I think it's actually
not bad.

I think something like this would work:

#define BIT_FIND_SETUP(addr, size, start) \
unsigned long val, idx; \
if (unlikely(start >= size)) \
return size; \
idx = start / BITS_PER_LONG;

#define BIT_FIND_FIRST_WORD(addr, size, start, EXPRESSION) \
if (!IS_ALIGNED(start, BITS_PER_LONG)) { \
unsigned long mask; \
mask = BITMAP_FIRST_WORD_MASK(start); \
if ((val = mask & (EXPRESSION)) != 0) \
goto found; \
idx++; \
}

#define BIT_WORD_LOOP(ptr, size, idx, val, EXPRESSION) \
do { \
if ((val = (EXPRESSION)) != 0) \
goto found; \
idx++; \
} while ((idx)*BITS_PER_LONG < (size));

#define BIT_FIND_BODY(addr, size, start, EXPRESSION) \
BIT_FIND_SETUP(addr, size, start) \
BIT_FIND_FIRST_WORD(addr, size, start, EXPRESSION) \
BIT_WORD_LOOP(addr, size, idx, val, EXPRESSION) \
return size; \
found: BIT_WORD_SWAB(val); \
return min((idx)*BITS_PER_LONG + __ffs(val), size)

#define BIT_WORD_SWAB(x) /* Nothing */

and then for the BE versions you just use the same macros, but you
make BIT_WORD_SWAB() do the swab.

I'm attaching an UNTESTED version of lib/find_bit.c that works the
above way (note: it is based on your header file changes!)

It builds for me and seems to generate reasonable code, although I
notice that clang messes up the "__ffs()" inline asm and forces the
source into memory.

(Gcc doesn't do that, but gcc follows the code exactly and generates
"shl $6" instructions, while clang seems to figure out that it can
just add 64 instead)

Linus
// SPDX-License-Identifier: GPL-2.0-or-later
/* bit search implementation
*
* Copyright (C) 2004 Red Hat, Inc. All Rights Reserved.
* Written by David Howells (dhowells@redhat.com)
*
* Copyright (C) 2008 IBM Corporation
* 'find_last_bit' is written by Rusty Russell <rusty@rustcorp.com.au>
* (Inspired by David Howell's find_next_bit implementation)
*
* Rewritten by Yury Norov <yury.norov@gmail.com> to decrease
* size and improve performance, 2015.
*/

#include <linux/bitops.h>
#include <linux/bitmap.h>
#include <linux/export.h>
#include <linux/math.h>
#include <linux/minmax.h>
#include <linux/swab.h>

#define BIT_FIND_SETUP(addr, size, start) \
unsigned long val, idx; \
if (unlikely(start >= size)) \
return size; \
idx = start / BITS_PER_LONG;

#define BIT_FIND_FIRST_WORD(addr, size, start, EXPRESSION) \
if (!IS_ALIGNED(start, BITS_PER_LONG)) { \
unsigned long mask; \
mask = BITMAP_FIRST_WORD_MASK(start); \
if ((val = mask & (EXPRESSION)) != 0) \
goto found; \
idx++; \
}

#define BIT_WORD_LOOP(ptr, size, idx, val, EXPRESSION) \
do { \
if ((val = (EXPRESSION)) != 0) \
goto found; \
idx++; \
} while ((idx)*BITS_PER_LONG < (size));

#define BIT_FIND_BODY(addr, size, start, EXPRESSION) \
BIT_FIND_SETUP(addr, size, start) \
BIT_FIND_FIRST_WORD(addr, size, start, EXPRESSION) \
BIT_WORD_LOOP(addr, size, idx, val, EXPRESSION) \
return size; \
found: BIT_WORD_SWAB(val); \
return min((idx)*BITS_PER_LONG + __ffs(val), size)

#define BIT_WORD_SWAB(x) /* Nothing */

unsigned long _find_first_bit(const unsigned long *addr, unsigned long size)
{ BIT_FIND_BODY(addr, size, 0, addr[idx]); }

unsigned long _find_first_zero_bit(const unsigned long *addr, unsigned long size)
{ BIT_FIND_BODY(addr, size, 0, ~addr[idx]); }

unsigned long _find_next_bit(const unsigned long *addr, unsigned long size, unsigned long start)
{ BIT_FIND_BODY(addr, size, start, addr[idx]); }

unsigned long _find_next_zero_bit(const unsigned long *addr, unsigned long size, unsigned long start)
{ BIT_FIND_BODY(addr, size, start, ~addr[idx]); }

unsigned long _find_first_and_bit(const unsigned long *addr1, const unsigned long *addr2, unsigned long size)
{ BIT_FIND_BODY(addr, size, 0, addr1[idx] & addr2[idx]); }

unsigned long _find_next_and_bit(const unsigned long *addr1, const unsigned long *addr2, unsigned long size, unsigned long start)
{ BIT_FIND_BODY(addr, size, start, addr1[idx] & addr2[idx]); }

#ifdef __BIG_ENDIAN

#undef BIT_WORD_SWAB
#define BIT_WORD_SWAB(val) val = swab(val)

.. FIXME: same as above, now with _find_first_bit_le() etc ..

#endif

#ifndef find_last_bit
unsigned long _find_last_bit(const unsigned long *addr, unsigned long size)
{
if (size) {
unsigned long val = BITMAP_LAST_WORD_MASK(size);
unsigned long idx = (size-1) / BITS_PER_LONG;

do {
val &= addr[idx];
if (val)
return idx * BITS_PER_LONG + __fls(val);

val = ~0ul;
} while (idx--);
}
return size;
}
EXPORT_SYMBOL(_find_last_bit);
#endif

unsigned long find_next_clump8(unsigned long *clump, const unsigned long *addr,
unsigned long size, unsigned long offset)
{
offset = find_next_bit(addr, size, offset);
if (offset == size)
return size;

offset = round_down(offset, 8);
*clump = bitmap_get_value8(addr, offset);

return offset;
}
EXPORT_SYMBOL(find_next_clump8);
\
 
 \ /
  Last update: 2022-07-28 20:50    [W:0.074 / U:0.116 seconds]
©2003-2020 Jasper Spaans|hosted at Digital Ocean and TransIP|Read the blog|Advertise on this site