lkml.org 
[lkml]   [2008]   [Apr]   [1]   [last100]   RSS Feed
Views: [wrap][no wrap]   [headers]  [forward] 
 
Messages in this thread
    Patch in this message
    /
    Date
    From
    Subject[PATCH] x86: optimize find_first_bit for small bitmaps
    [PATCH] x86: optimize find_first_bit for small bitmaps

    Avoid a call to find_first_bit if the bitmap size is know at
    compile time and small enough to fit in a single long integer.
    Modeled after an optimization in the original x86_64-specific
    code.

    Signed-off-by: Alexander van Heukelum <heukelum@fastmail.fm>

    ---
    include/linux/bitops.h | 29 +++++++++++++++++++++++++++++
    1 files changed, 29 insertions(+), 0 deletions(-)

    diff --git a/include/linux/bitops.h b/include/linux/bitops.h
    index 355d67b..48bde60 100644
    --- a/include/linux/bitops.h
    +++ b/include/linux/bitops.h
    @@ -127,6 +127,20 @@ extern unsigned long __find_first_bit(const unsigned long *addr,
    static __always_inline unsigned long
    find_first_bit(const unsigned long *addr, unsigned long size)
    {
    + /* Avoid a function call if the bitmap size is a constant */
    + /* and not bigger than BITS_PER_LONG. */
    +
    + /* insert a sentinel so that __ffs returns size if there */
    + /* are no set bits in the bitmap */
    + if (__builtin_constant_p(size) && (size < BITS_PER_LONG))
    + return __ffs((*addr) | (1ul << size));
    +
    + /* the result of __ffs(0) is undefined, so it needs to be */
    + /* handled separately */
    + if (__builtin_constant_p(size) && (size == BITS_PER_LONG))
    + return ((*addr) == 0) ? BITS_PER_LONG : __ffs(*addr);
    +
    + /* size is not constant or too big */
    return __find_first_bit(addr, size);
    }

    @@ -143,6 +157,21 @@ extern unsigned long __find_first_zero_bit(const unsigned long *addr,
    static __always_inline unsigned long
    find_first_zero_bit(const unsigned long *addr, unsigned long size)
    {
    + /* Avoid a function call if the bitmap size is a constant */
    + /* and not bigger than BITS_PER_LONG. */
    +
    + /* insert a sentinel so that __ffs returns size if there */
    + /* are no set bits in the bitmap */
    + if (__builtin_constant_p(size) && (size < BITS_PER_LONG)) {
    + return __ffs(~(*addr) | (1ul << size));
    + }
    +
    + /* the result of __ffs(0) is undefined, so it needs to be */
    + /* handled separately */
    + if (__builtin_constant_p(size) && (size == BITS_PER_LONG))
    + return (~(*addr) == 0) ? BITS_PER_LONG : __ffs(~(*addr));
    +
    + /* size is not constant or too big */
    return __find_first_zero_bit(addr, size);
    }
    #endif /* CONFIG_GENERIC_FIND_FIRST_BIT */
    --
    1.5.2.5



    \
     
     \ /
      Last update: 2008-04-01 17:47    [W:0.023 / U:29.716 seconds]
    ©2003-2016 Jasper Spaans. hosted at Digital OceanAdvertise on this site