* [PATCH v6 0/2] Improve the performance of bitmap_find_next_zero_area_off() @ 2026-06-18 13:35 Yi Sun 2026-06-18 13:35 ` [PATCH v6 1/2] lib: bitmap: add tests for bitmap_find_next_zero_area_off() Yi Sun 2026-06-18 13:35 ` [PATCH v6 2/2] lib: bitmap: optimize bitmap_find_next_zero_area_off() Yi Sun 0 siblings, 2 replies; 4+ messages in thread From: Yi Sun @ 2026-06-18 13:35 UTC (permalink / raw) To: yury.norov Cc: yi.sun, 279644543, mina86, mnazarewicz, akpm, akinobu.mita, linux-kernel, tjmercier, qiang.zhao, scottwood, fvdl, tglx, song, hch, minchan, jstultz Use lib/find_bit_benchmark.c for testing. Test results showed a 40% improvement in dense cases, and almost no change in sparse cases. Performance test results on my hardware: before(ns) after(ns) change p-value dense 1211 688 -43.2% 8.3e-11 sparse 13.3 13.4 0.8% 0.27 --- v5: https://lore.kernel.org/all/20260618015252.3601554-1-yi.sun@unisoc.com - Improve test code. - Change the "goto again" code structure to a for loop. v4: https://lore.kernel.org/all/20260601094234.103863-1-yi.sun@unisoc.com - Test code has been added to PATCH v2. v3: https://lore.kernel.org/all/20260514090607.231387-1-yi.sun@unisoc.com - Code optimization was performed on PATCH v1. v2: https://lore.kernel.org/all/20260514035644.4118050-1-yi.sun@unisoc.com - Do not introduce find_last_bit_from(). v1: https://lore.kernel.org/all/20260512040659.2992142-1-yi.sun@unisoc.com Yi Sun (2): lib: bitmap: add tests for bitmap_find_next_zero_area_off() lib: bitmap: optimize bitmap_find_next_zero_area_off() lib/bitmap.c | 31 ++++++++++++++++--------------- lib/find_bit_benchmark.c | 31 ++++++++++++++++++++++++------- lib/test_bitmap.c | 38 ++++++++++++++++++++++++++++++++++++++ 3 files changed, 78 insertions(+), 22 deletions(-) -- 2.34.1 ^ permalink raw reply [flat|nested] 4+ messages in thread
* [PATCH v6 1/2] lib: bitmap: add tests for bitmap_find_next_zero_area_off() 2026-06-18 13:35 [PATCH v6 0/2] Improve the performance of bitmap_find_next_zero_area_off() Yi Sun @ 2026-06-18 13:35 ` Yi Sun 2026-06-18 17:31 ` Yury Norov 2026-06-18 13:35 ` [PATCH v6 2/2] lib: bitmap: optimize bitmap_find_next_zero_area_off() Yi Sun 1 sibling, 1 reply; 4+ messages in thread From: Yi Sun @ 2026-06-18 13:35 UTC (permalink / raw) To: yury.norov Cc: yi.sun, 279644543, mina86, mnazarewicz, akpm, akinobu.mita, linux-kernel, tjmercier, qiang.zhao, scottwood, fvdl, tglx, song, hch, minchan, jstultz Add functional and performance tests for bitmap_find_next_zero_area_off(). performance tests partial output: Start testing find_bit() with random-filled bitmap [ 0.310073] bitmap_find_next_zero_area_off: 852731 ns, 1154 iterations [ 0.311435] find_next_bit: 1356654 ns, 163975 iterations Start testing find_bit() with sparse bitmap [ 0.316267] bitmap_find_next_zero_area_off: 4426808 ns, 322479 iterations [ 0.316292] find_next_bit: 15154 ns, 656 iterations Signed-off-by: Yi Sun <yi.sun@unisoc.com> --- lib/find_bit_benchmark.c | 31 ++++++++++++++++++++++++------- lib/test_bitmap.c | 38 ++++++++++++++++++++++++++++++++++++++ 2 files changed, 62 insertions(+), 7 deletions(-) diff --git a/lib/find_bit_benchmark.c b/lib/find_bit_benchmark.c index 00d9dc61cd46..cde7c09de05c 100644 --- a/lib/find_bit_benchmark.c +++ b/lib/find_bit_benchmark.c @@ -46,7 +46,7 @@ static int __init test_find_first_bit(const void *bitmap, unsigned long len) __clear_bit(i, cp); } time = ktime_get() - time; - pr_err("find_first_bit: %18llu ns, %6ld iterations\n", time, cnt); + pr_err("find_first_bit: %14llu ns, %6ld iterations\n", time, cnt); return 0; } @@ -66,7 +66,7 @@ static int __init test_find_first_and_bit(const void *bitmap, const void *bitmap __clear_bit(i, cp); } time = ktime_get() - time; - pr_err("find_first_and_bit: %18llu ns, %6ld iterations\n", time, cnt); + pr_err("find_first_and_bit: %14llu ns, %6ld iterations\n", time, cnt); return 0; } @@ -80,7 +80,7 @@ static int __init test_find_next_bit(const void *bitmap, unsigned long len) for (cnt = i = 0; i < BITMAP_LEN; cnt++) i = find_next_bit(bitmap, BITMAP_LEN, i) + 1; time = ktime_get() - time; - pr_err("find_next_bit: %18llu ns, %6ld iterations\n", time, cnt); + pr_err("find_next_bit: %14llu ns, %6ld iterations\n", time, cnt); return 0; } @@ -94,7 +94,7 @@ static int __init test_find_next_zero_bit(const void *bitmap, unsigned long len) for (cnt = i = 0; i < BITMAP_LEN; cnt++) i = find_next_zero_bit(bitmap, len, i) + 1; time = ktime_get() - time; - pr_err("find_next_zero_bit: %18llu ns, %6ld iterations\n", time, cnt); + pr_err("find_next_zero_bit: %14llu ns, %6ld iterations\n", time, cnt); return 0; } @@ -113,7 +113,7 @@ static int __init test_find_last_bit(const void *bitmap, unsigned long len) len = l; } while (len); time = ktime_get() - time; - pr_err("find_last_bit: %18llu ns, %6ld iterations\n", time, cnt); + pr_err("find_last_bit: %14llu ns, %6ld iterations\n", time, cnt); return 0; } @@ -129,7 +129,7 @@ static int __init test_find_nth_bit(const unsigned long *bitmap, unsigned long l WARN_ON(l >= len); } time = ktime_get() - time; - pr_err("find_nth_bit: %18llu ns, %6ld iterations\n", time, w); + pr_err("find_nth_bit: %14llu ns, %6ld iterations\n", time, w); return 0; } @@ -144,7 +144,22 @@ static int __init test_find_next_and_bit(const void *bitmap, for (cnt = i = 0; i < BITMAP_LEN; cnt++) i = find_next_and_bit(bitmap, bitmap2, BITMAP_LEN, i + 1); time = ktime_get() - time; - pr_err("find_next_and_bit: %18llu ns, %6ld iterations\n", time, cnt); + pr_err("find_next_and_bit: %14llu ns, %6ld iterations\n", time, cnt); + + return 0; +} + +static int __init +test_bitmap_find_next_zero_area_off(unsigned long *bitmap, unsigned long len) +{ + unsigned long i, cnt; + ktime_t time; + + time = ktime_get(); + for (cnt = i = 0; i < BITMAP_LEN; cnt++) + i = bitmap_find_next_zero_area_off(bitmap, BITMAP_LEN, i, 8, 0, 0) + 1; + time = ktime_get() - time; + pr_err("bitmap_find_next_zero_area_off: %14llu ns, %6ld iterations\n", time, cnt); return 0; } @@ -158,6 +173,7 @@ static int __init find_bit_test(void) get_random_bytes(bitmap, sizeof(bitmap)); get_random_bytes(bitmap2, sizeof(bitmap2)); + test_bitmap_find_next_zero_area_off(bitmap, BITMAP_LEN); test_find_next_bit(bitmap, BITMAP_LEN); test_find_next_zero_bit(bitmap, BITMAP_LEN); test_find_last_bit(bitmap, BITMAP_LEN); @@ -181,6 +197,7 @@ static int __init find_bit_test(void) __set_bit(get_random_u32_below(BITMAP_LEN), bitmap2); } + test_bitmap_find_next_zero_area_off(bitmap, BITMAP_LEN); test_find_next_bit(bitmap, BITMAP_LEN); test_find_next_zero_bit(bitmap, BITMAP_LEN); test_find_last_bit(bitmap, BITMAP_LEN); diff --git a/lib/test_bitmap.c b/lib/test_bitmap.c index 69813c10e6c0..8665df77c960 100644 --- a/lib/test_bitmap.c +++ b/lib/test_bitmap.c @@ -234,6 +234,43 @@ static void __init test_find_nth_bit(void) } } +static void __init +test_bitmap_find_next_zero_area_off(void) +{ + DECLARE_BITMAP(bmap, 192); + + bitmap_set(bmap, 0, 192); + + bitmap_clear(bmap, 0, 8); + __clear_bit(50, bmap); + bitmap_clear(bmap, 60, 18); + __set_bit(69, bmap); + __clear_bit(80, bmap); + bitmap_clear(bmap, 100, 10); + __clear_bit(120, bmap); + bitmap_clear(bmap, 145, 8); + bitmap_clear(bmap, 160, 32); + + expect_eq_uint(0, + bitmap_find_next_zero_area_off(bmap, 192, 0, 8, 0, 0)); + expect_eq_uint(0, + bitmap_find_next_zero_area_off(bmap, 192, 0, 8, 3, 0)); + expect_eq_uint(163, + bitmap_find_next_zero_area_off(bmap, 192, 0, 8, 3, 1)); + expect_eq_uint(60, + bitmap_find_next_zero_area_off(bmap, 192, 1, 8, 0, 0)); + expect_eq_uint(160, + bitmap_find_next_zero_area_off(bmap, 192, 1, 8, 7, 0)); + expect_eq_uint(60, + bitmap_find_next_zero_area_off(bmap, 192, 1, 8, 7, 4)); + expect_eq_uint(100, + bitmap_find_next_zero_area_off(bmap, 192, 0, 10, 0, 0)); + expect_eq_uint(160, + bitmap_find_next_zero_area_off(bmap, 192, 0, 32, 0, 0)); + expect_eq_uint(1, + !!(bitmap_find_next_zero_area_off(bmap, 192, 0, 33, 0, 0) >= 192)); +} + static void __init test_fill_set(void) { DECLARE_BITMAP(bmap, 1024); @@ -1559,6 +1596,7 @@ static void __init selftest(void) test_for_each_clear_bitrange_from(); test_for_each_set_clump8(); test_for_each_set_bit_wrap(); + test_bitmap_find_next_zero_area_off(); } KSTM_MODULE_LOADERS(test_bitmap); -- 2.34.1 ^ permalink raw reply related [flat|nested] 4+ messages in thread
* Re: [PATCH v6 1/2] lib: bitmap: add tests for bitmap_find_next_zero_area_off() 2026-06-18 13:35 ` [PATCH v6 1/2] lib: bitmap: add tests for bitmap_find_next_zero_area_off() Yi Sun @ 2026-06-18 17:31 ` Yury Norov 0 siblings, 0 replies; 4+ messages in thread From: Yury Norov @ 2026-06-18 17:31 UTC (permalink / raw) To: Yi Sun Cc: yury.norov, 279644543, mina86, mnazarewicz, akpm, akinobu.mita, linux-kernel, tjmercier, qiang.zhao, scottwood, fvdl, tglx, song, hch, minchan, jstultz On Thu, Jun 18, 2026 at 09:35:17PM +0800, Yi Sun wrote: > Add functional and performance tests > for bitmap_find_next_zero_area_off(). > > performance tests partial output: > Start testing find_bit() with random-filled bitmap > [ 0.310073] bitmap_find_next_zero_area_off: 852731 ns, 1154 iterations > [ 0.311435] find_next_bit: 1356654 ns, 163975 iterations > Start testing find_bit() with sparse bitmap > [ 0.316267] bitmap_find_next_zero_area_off: 4426808 ns, 322479 iterations > [ 0.316292] find_next_bit: 15154 ns, 656 iterations > > Signed-off-by: Yi Sun <yi.sun@unisoc.com> > --- > lib/find_bit_benchmark.c | 31 ++++++++++++++++++++++++------- > lib/test_bitmap.c | 38 ++++++++++++++++++++++++++++++++++++++ > 2 files changed, 62 insertions(+), 7 deletions(-) > > diff --git a/lib/find_bit_benchmark.c b/lib/find_bit_benchmark.c > index 00d9dc61cd46..cde7c09de05c 100644 > --- a/lib/find_bit_benchmark.c > +++ b/lib/find_bit_benchmark.c > @@ -46,7 +46,7 @@ static int __init test_find_first_bit(const void *bitmap, unsigned long len) > __clear_bit(i, cp); > } > time = ktime_get() - time; > - pr_err("find_first_bit: %18llu ns, %6ld iterations\n", time, cnt); > + pr_err("find_first_bit: %14llu ns, %6ld iterations\n", time, cnt); No need to change the existing code. Just add your test and make sure it looks aligned with the existing format. > > return 0; > } > @@ -66,7 +66,7 @@ static int __init test_find_first_and_bit(const void *bitmap, const void *bitmap > __clear_bit(i, cp); > } > time = ktime_get() - time; > - pr_err("find_first_and_bit: %18llu ns, %6ld iterations\n", time, cnt); > + pr_err("find_first_and_bit: %14llu ns, %6ld iterations\n", time, cnt); > > return 0; > } > @@ -80,7 +80,7 @@ static int __init test_find_next_bit(const void *bitmap, unsigned long len) > for (cnt = i = 0; i < BITMAP_LEN; cnt++) > i = find_next_bit(bitmap, BITMAP_LEN, i) + 1; > time = ktime_get() - time; > - pr_err("find_next_bit: %18llu ns, %6ld iterations\n", time, cnt); > + pr_err("find_next_bit: %14llu ns, %6ld iterations\n", time, cnt); > > return 0; > } > @@ -94,7 +94,7 @@ static int __init test_find_next_zero_bit(const void *bitmap, unsigned long len) > for (cnt = i = 0; i < BITMAP_LEN; cnt++) > i = find_next_zero_bit(bitmap, len, i) + 1; > time = ktime_get() - time; > - pr_err("find_next_zero_bit: %18llu ns, %6ld iterations\n", time, cnt); > + pr_err("find_next_zero_bit: %14llu ns, %6ld iterations\n", time, cnt); > > return 0; > } > @@ -113,7 +113,7 @@ static int __init test_find_last_bit(const void *bitmap, unsigned long len) > len = l; > } while (len); > time = ktime_get() - time; > - pr_err("find_last_bit: %18llu ns, %6ld iterations\n", time, cnt); > + pr_err("find_last_bit: %14llu ns, %6ld iterations\n", time, cnt); > > return 0; > } > @@ -129,7 +129,7 @@ static int __init test_find_nth_bit(const unsigned long *bitmap, unsigned long l > WARN_ON(l >= len); > } > time = ktime_get() - time; > - pr_err("find_nth_bit: %18llu ns, %6ld iterations\n", time, w); > + pr_err("find_nth_bit: %14llu ns, %6ld iterations\n", time, w); > > return 0; > } > @@ -144,7 +144,22 @@ static int __init test_find_next_and_bit(const void *bitmap, > for (cnt = i = 0; i < BITMAP_LEN; cnt++) > i = find_next_and_bit(bitmap, bitmap2, BITMAP_LEN, i + 1); > time = ktime_get() - time; > - pr_err("find_next_and_bit: %18llu ns, %6ld iterations\n", time, cnt); > + pr_err("find_next_and_bit: %14llu ns, %6ld iterations\n", time, cnt); > + > + return 0; > +} > + > +static int __init > +test_bitmap_find_next_zero_area_off(unsigned long *bitmap, unsigned long len) > +{ > + unsigned long i, cnt; > + ktime_t time; > + > + time = ktime_get(); > + for (cnt = i = 0; i < BITMAP_LEN; cnt++) > + i = bitmap_find_next_zero_area_off(bitmap, BITMAP_LEN, i, 8, 0, 0) + 1; > + time = ktime_get() - time; > + pr_err("bitmap_find_next_zero_area_off: %14llu ns, %6ld iterations\n", time, cnt); > > return 0; > } > @@ -158,6 +173,7 @@ static int __init find_bit_test(void) > get_random_bytes(bitmap, sizeof(bitmap)); > get_random_bytes(bitmap2, sizeof(bitmap2)); > > + test_bitmap_find_next_zero_area_off(bitmap, BITMAP_LEN); > test_find_next_bit(bitmap, BITMAP_LEN); > test_find_next_zero_bit(bitmap, BITMAP_LEN); > test_find_last_bit(bitmap, BITMAP_LEN); > @@ -181,6 +197,7 @@ static int __init find_bit_test(void) > __set_bit(get_random_u32_below(BITMAP_LEN), bitmap2); > } > > + test_bitmap_find_next_zero_area_off(bitmap, BITMAP_LEN); > test_find_next_bit(bitmap, BITMAP_LEN); > test_find_next_zero_bit(bitmap, BITMAP_LEN); > test_find_last_bit(bitmap, BITMAP_LEN); > diff --git a/lib/test_bitmap.c b/lib/test_bitmap.c > index 69813c10e6c0..8665df77c960 100644 > --- a/lib/test_bitmap.c > +++ b/lib/test_bitmap.c > @@ -234,6 +234,43 @@ static void __init test_find_nth_bit(void) > } > } > > +static void __init > +test_bitmap_find_next_zero_area_off(void) > +{ > + DECLARE_BITMAP(bmap, 192); > + > + bitmap_set(bmap, 0, 192); > + > + bitmap_clear(bmap, 0, 8); > + __clear_bit(50, bmap); > + bitmap_clear(bmap, 60, 18); > + __set_bit(69, bmap); > + __clear_bit(80, bmap); > + bitmap_clear(bmap, 100, 10); > + __clear_bit(120, bmap); > + bitmap_clear(bmap, 145, 8); > + bitmap_clear(bmap, 160, 32); > + > + expect_eq_uint(0, > + bitmap_find_next_zero_area_off(bmap, 192, 0, 8, 0, 0)); > + expect_eq_uint(0, > + bitmap_find_next_zero_area_off(bmap, 192, 0, 8, 3, 0)); > + expect_eq_uint(163, > + bitmap_find_next_zero_area_off(bmap, 192, 0, 8, 3, 1)); > + expect_eq_uint(60, > + bitmap_find_next_zero_area_off(bmap, 192, 1, 8, 0, 0)); > + expect_eq_uint(160, > + bitmap_find_next_zero_area_off(bmap, 192, 1, 8, 7, 0)); > + expect_eq_uint(60, > + bitmap_find_next_zero_area_off(bmap, 192, 1, 8, 7, 4)); > + expect_eq_uint(100, > + bitmap_find_next_zero_area_off(bmap, 192, 0, 10, 0, 0)); > + expect_eq_uint(160, > + bitmap_find_next_zero_area_off(bmap, 192, 0, 32, 0, 0)); > + expect_eq_uint(1, > + !!(bitmap_find_next_zero_area_off(bmap, 192, 0, 33, 0, 0) >= 192)); > +} > + > static void __init test_fill_set(void) > { > DECLARE_BITMAP(bmap, 1024); > @@ -1559,6 +1596,7 @@ static void __init selftest(void) > test_for_each_clear_bitrange_from(); > test_for_each_set_clump8(); > test_for_each_set_bit_wrap(); > + test_bitmap_find_next_zero_area_off(); > } > > KSTM_MODULE_LOADERS(test_bitmap); > -- > 2.34.1 ^ permalink raw reply [flat|nested] 4+ messages in thread
* [PATCH v6 2/2] lib: bitmap: optimize bitmap_find_next_zero_area_off() 2026-06-18 13:35 [PATCH v6 0/2] Improve the performance of bitmap_find_next_zero_area_off() Yi Sun 2026-06-18 13:35 ` [PATCH v6 1/2] lib: bitmap: add tests for bitmap_find_next_zero_area_off() Yi Sun @ 2026-06-18 13:35 ` Yi Sun 1 sibling, 0 replies; 4+ messages in thread From: Yi Sun @ 2026-06-18 13:35 UTC (permalink / raw) To: yury.norov Cc: yi.sun, 279644543, mina86, mnazarewicz, akpm, akinobu.mita, linux-kernel, tjmercier, qiang.zhao, scottwood, fvdl, tglx, song, hch, minchan, jstultz Finding a contiguous free region in a highly fragmented bitmap is not easy and may require many repeated attempts. Therefore, find_next_bit(map, end, index) is not the optimal choice. This is because there may be multiple scattered free regions within the range [index, end) and none of them will meet the length requirement of @nr. Instead, it's sufficient to directly find the last bit within the range [index, end), thus reducing unnecessary repeated calls. An example of a bitmap: Bits 0-3: cleared(4 bits) Bits 4-5: set (2 bits) Bits 6-8: cleared(4 bits) Bits 9-10: set (2 bits) Bits 11-20: cleared(10 bits) The goal is to find a 10-bit free region. The old code logic is as follows: find_next_zero_bit(start = 0, find bit 0) -> find_next_bit(find bit 4) -> next loop -> find_next_zero_bit(start = 5, find bit 6) -> find_next_bit(find bit 9) -> next loop -> find_next_zero_bit(start = 10, find bit 11) -> success The new code logic is as follows: find_next_zero_bit(start = 0, find bit 0) -> find_last_bit(find bit 9) -> next loop -> find_next_zero_bit(start = 10, find bit 11) -> success Performance test results on my hardware(use lib/find_bit_benchmark.c): before after change p-value dense 1211 688 -43.2% 8.3e-11 sparse 13.3 13.4 0.8% 0.27 Co-developed-by: Yury Norov <yury.norov@gmail.com> Signed-off-by: Yury Norov <yury.norov@gmail.com> Signed-off-by: Yi Sun <yi.sun@unisoc.com> --- lib/bitmap.c | 31 ++++++++++++++++--------------- 1 file changed, 16 insertions(+), 15 deletions(-) diff --git a/lib/bitmap.c b/lib/bitmap.c index b9bfa157e095..a00a71f2b7bb 100644 --- a/lib/bitmap.c +++ b/lib/bitmap.c @@ -432,22 +432,23 @@ unsigned long bitmap_find_next_zero_area_off(unsigned long *map, unsigned long align_mask, unsigned long align_offset) { - unsigned long index, end, i; -again: - index = find_next_zero_bit(map, size, start); - - /* Align allocation */ - index = __ALIGN_MASK(index + align_offset, align_mask) - align_offset; - - end = index + nr; - if (end > size) - return end; - i = find_next_bit(map, end, index); - if (i < end) { - start = i + 1; - goto again; + unsigned long end, i, off; + + for_each_clear_bit_from(start, map, size) { + start = __ALIGN_MASK(start + align_offset, align_mask) - align_offset; + end = start + nr; + if (end > size) + break; + + off = round_down(start, BITS_PER_LONG); + i = find_last_bit(map + start / BITS_PER_LONG, end - off) + off; + if (i >= end || i < start) + return start; + + start = i; } - return index; + + return size; } EXPORT_SYMBOL(bitmap_find_next_zero_area_off); -- 2.34.1 ^ permalink raw reply related [flat|nested] 4+ messages in thread
end of thread, other threads:[~2026-06-18 17:31 UTC | newest] Thread overview: 4+ messages (download: mbox.gz follow: Atom feed -- links below jump to the message on this page -- 2026-06-18 13:35 [PATCH v6 0/2] Improve the performance of bitmap_find_next_zero_area_off() Yi Sun 2026-06-18 13:35 ` [PATCH v6 1/2] lib: bitmap: add tests for bitmap_find_next_zero_area_off() Yi Sun 2026-06-18 17:31 ` Yury Norov 2026-06-18 13:35 ` [PATCH v6 2/2] lib: bitmap: optimize bitmap_find_next_zero_area_off() Yi Sun
This is an external index of several public inboxes, see mirroring instructions on how to clone and mirror all data and code used by this external index.