From mboxrd@z Thu Jan 1 00:00:00 1970 Received: from SHSQR01.spreadtrum.com (unknown [222.66.158.135]) (using TLSv1.2 with cipher ECDHE-RSA-AES256-GCM-SHA384 (256/256 bits)) (No client certificate requested) by smtp.subspace.kernel.org (Postfix) with ESMTPS id 22295311956 for ; Tue, 12 May 2026 04:09:20 +0000 (UTC) Authentication-Results: smtp.subspace.kernel.org; arc=none smtp.client-ip=222.66.158.135 ARC-Seal:i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1778558965; cv=none; b=AwF2iQkt4jzoswztLHaingeMwZ7cw9h3M52F8LdSLCBlUQPSOT19v3sMMsp48EWbPldZpjE2W3cLlf1vDSpesfxs9BaOOTDgebjzI1AA+qrNht6rYRJdvNcQWT/EnnjfMEgCau2oTkeLY32yN2Ynqoy4urX4UhpCpZwIeBOyKpg= ARC-Message-Signature:i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1778558965; c=relaxed/simple; bh=MFFL0zsK8+D8Q2Z0Spu8E/2XYXlfYTIBume92Nz1bHY=; h=From:To:CC:Subject:Date:Message-ID:MIME-Version:Content-Type; b=Scals3x96EtS9TFVoWVDwh+eN35+obT+tcIhufNRzp8zp3mOQxjcNnIwL418Ce1xjWbBtC0V6rPFCAbBNbg8RFd5wMb/+Sa72W4APPOgxb3tNvNKUEfByGZXlf6j+OEWqSpxOXKoQzqZ47bGkLvR2XP5jMpaug+wp+eByPEhT9k= ARC-Authentication-Results:i=1; smtp.subspace.kernel.org; dmarc=pass (p=quarantine dis=none) header.from=unisoc.com; spf=pass smtp.mailfrom=unisoc.com; dkim=pass (2048-bit key) header.d=unisoc.com header.i=@unisoc.com header.b=u/jKErfZ; arc=none smtp.client-ip=222.66.158.135 Authentication-Results: smtp.subspace.kernel.org; dmarc=pass (p=quarantine dis=none) header.from=unisoc.com Authentication-Results: smtp.subspace.kernel.org; spf=pass smtp.mailfrom=unisoc.com Authentication-Results: smtp.subspace.kernel.org; dkim=pass (2048-bit key) header.d=unisoc.com header.i=@unisoc.com header.b="u/jKErfZ" Received: from SHSQR01.spreadtrum.com (localhost [127.0.0.2] (may be forged)) by SHSQR01.spreadtrum.com with ESMTP id 64C49HJV016200 for ; Tue, 12 May 2026 12:09:17 +0800 (+08) (envelope-from Yi.Sun@unisoc.com) Received: from dlp.unisoc.com ([10.29.3.86]) by SHSQR01.spreadtrum.com with ESMTP id 64C4754n006277; Tue, 12 May 2026 12:07:05 +0800 (+08) (envelope-from Yi.Sun@unisoc.com) Received: from SHDLP.spreadtrum.com (BJMBX02.spreadtrum.com [10.0.64.8]) by dlp.unisoc.com (SkyGuard) with ESMTPS id 4gF2yR4K0Fz2M3YFM; Tue, 12 May 2026 12:03:43 +0800 (CST) Received: from localhost.localdomain (10.5.32.15) by BJMBX02.spreadtrum.com (10.0.64.8) with Microsoft SMTP Server (TLS) id 15.0.1497.48; Tue, 12 May 2026 12:07:02 +0800 From: Yi Sun To: , , CC: , , Subject: [PATCH 0/2] Improve the performance of bitmap_find_next_zero_area_off() Date: Tue, 12 May 2026 12:06:57 +0800 Message-ID: <20260512040659.2992142-1-yi.sun@unisoc.com> X-Mailer: git-send-email 2.34.1 Precedence: bulk X-Mailing-List: linux-kernel@vger.kernel.org List-Id: List-Subscribe: List-Unsubscribe: MIME-Version: 1.0 Content-Transfer-Encoding: 8bit Content-Type: text/plain X-ClientProxiedBy: SHCAS03.spreadtrum.com (10.0.1.207) To BJMBX02.spreadtrum.com (10.0.64.8) X-MAIL:SHSQR01.spreadtrum.com 64C4754n006277 DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=unisoc.com; s=default; t=1778558835; bh=qgEukGVMBn6kfGR3JTePqUF+lXWq3gzsNeEJJiVZNWo=; h=From:To:CC:Subject:Date; b=u/jKErfZ88Avv6FKEaZcnp3JjgPDWRotBOAcA6w6CwTtWRfMFtommODQFJH4Jupr+ N03mMM19MgDlUGzXBN+YGmzmSBZwnJH/BEjF7sKsMiFXyUthCWBJGbl1r5L8afQf8M sYv0bPGsTlhqncisqsh7FOD0r35QFy/pk9I+AGbKrFLsjeZyT7hbcQt7c1uvXUAK4L kBjyJn0VvLLx7a9EeJjE74vJdORAPyo3iK6Y0p7gQhQ5dc7sAVxfVZUt4MJ0Z4+PGK Jkn73CDUIUvFxejQM7+wdUp9JnaU4knLMcPz4CyiX15IbpYsnMtrs9Z6OJ1AI8Hz/p Pb36x8iY8k5iQ== Replacing find_next_bit() with find_last_bit_range() can improve performance by an average of 50%. =========== Test result: cnt old_a_cnt new_a_cnt cnt_ratio old_time(ns) new_time(ns) time_ratio test1 8 71 34 52.1% 51357 25019 51.3% test2 8 1 1 0% 1150 1153 around 0% test1 32 81925 10402 87.3% 23103730 2910315 87.4% test2 32 1 1 0% 434 434 around 0% test1 128 82166 2572 96.9% 23054634 731453 96.8% test2 128 1 1 0% 434 438 around 0% test1 1024 81620 321 99.6% 23035192 234330 99% test2 1024 14 7 50% 4257 2257 47% test1 4096 80923 81 99.9% 22700265 57861 99.7% test2 4096 648 92 85.8% 192854 27177 85.9% ============ Test result explanation: @test1: The bitmap is filled with random numbers, so the bitmap is very messy. @test2: Sparse bitmap. @cnt: The expected number of consecutive clear bits. @old_a_cnt: Total number of "goto again" when using find_next_bit(). @new_a_cnt: Total number of "goto again" when using find_last_bit_range(). Finding @cnt consecutive clear bits in the bitmap may require multiple attempts. The number of repetitions should be recorded. @cnt_ratio = (old_a_cnt - new_a_cnt) / old_a_cnt. @old_time(ns): The total time consumed by bitmap_find_next_zero_area_off() when using find_next_bit(). @new_time(ns): The total time consumed by bitmap_find_next_zero_area_off() when using find_last_bit_range(). @time_ratio = (old_time - new_time) / old_time. ============== Test case(refer to lib/find_bit_benchmark.c): define BITMAP_LEN (4096UL * 8 * 10) define SPARSE 500 static DECLARE_BITMAP(bitmap, BITMAP_LEN); static void test_main() { unsigned long nbits = BITMAP_LEN / SPARSE; //test1 get_random_bytes(bitmap, sizeof(bitmap)); __test_all(); //test2 bitmap_zero(bitmap, BITMAP_LEN); while (nbits--) __set_bit(get_random_u32_below(BITMAP_LEN), bitmap); __test_all(); } static void __test_all() { //Expected number of consecutive clear bits. u32 cnt = 8; //Ignore the results of this test. __test_new(cnt); //To mitigate the impact of caching, //we will use the results of this test. __test_new(cnt); //Ignore the results of this test. __test_old(cnt); //To mitigate the impact of caching, //we will use the results of this test. __test_old(cnt); } //Add time-consuming statistics to bitmap_find_next_zero_area_off(). static ktime_t __test_old/__test_new(u32 nr) { unsigned long *map = bitmap; unsigned long size = BITMAP_LEN; unsigned long start = 0; unsigned long align_mask = 0; unsigned long align_offset = 0; unsigned long index, end, i, again_cnt = 0; //Here add time-consuming statistics. ktime_t time = ktime_get(); again: again_cnt++; 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) { //Here add time-consuming statistics. time = ktime_get() - time; return time; } //__test_old() use this. i = find_next_bit(map, end, index); //__test_new() use this. i = find_last_bit_range(map, end, index); if (i < end) { start = i + 1; goto again; } //Here add time-consuming statistics. time = ktime_get() - time; return time; } Yi Sun (2): lib: bitmap: add find_last_bit_range() and _find_last_bit_range() lib: bitmap: reduce the number of goto again in bitmap_find_next_zero_area_off() include/linux/find.h | 35 +++++++++++++++++++++++++++++++++++ lib/bitmap.c | 2 +- lib/find_bit.c | 30 ++++++++++++++++++++++++++++++ 3 files changed, 66 insertions(+), 1 deletion(-) -- 2.34.1