• Y
    lib: add find_nth{,_and,_andnot}_bit() · 3cea8d47
    Yury Norov 提交于
    Kernel lacks for a function that searches for Nth bit in a bitmap.
    Usually people do it like this:
    	for_each_set_bit(bit, mask, size)
    		if (n-- == 0)
    			return bit;
    
    We can do it more efficiently, if we:
    1. find a word containing Nth bit, using hweight(); and
    2. find the bit, using a helper fns(), that works similarly to
       __ffs() and ffz().
    
    fns() is implemented as a simple loop. For x86_64, there's PDEP instruction
    to do that: ret = clz(pdep(1 << idx, num)). However, for large bitmaps the
    most of improvement comes from using hweight(), so I kept fns() simple.
    
    New find_nth_bit() is ~70 times faster on x86_64/kvm in find_bit benchmark:
    find_nth_bit:                  7154190 ns,  16411 iterations
    for_each_bit:                505493126 ns,  16315 iterations
    
    With all that, a family of 3 new functions is added, and used where
    appropriate in the following patches.
    Signed-off-by: NYury Norov <yury.norov@gmail.com>
    3cea8d47
find_bit.c 6.3 KB