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 55670346AC1 for ; Thu, 14 May 2026 09:07:22 +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=1778749646; cv=none; b=pGfFYJ5z6MzNn2bIJQF7D/rx9zLOp7sYTGq9DCx9t9n6QIgbJZuGcwOw+b0oGngJPxpPkJujHYq9rW3ti3/ybgasNBJabNwgjhjo1UHlO/ySQ9Vj3BLENZe44PVAbgpD0qPCKoJviiSf3jVsvvLCjS6nmOUz5zIeZXFXoU9n9z0= ARC-Message-Signature:i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1778749646; c=relaxed/simple; bh=1HEy+LCyXpGz4zQanaLewzvDCl7NODmcLnU1mTUc6lM=; h=From:To:CC:Subject:Date:Message-ID:MIME-Version:Content-Type; b=EVwyf0L7AKYsYWz3xgDaTBIaulCRXKx7ZCh1VPFYnMs09B56S37/wWyJIBa8GTsUytOIsX4n/J7eu0by5aUL+InH2Rw+Ww3bIF7OW5W7obT+UyWahPPgFA3hykZFOav4gcqUE8ZD5JlYKByOcfm9pr+sVrBqoDJUC8LCJz51NDs= 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=M61bUGSf; 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="M61bUGSf" Received: from dlp.unisoc.com ([10.29.3.86]) by SHSQR01.spreadtrum.com with ESMTP id 64E96BmD011913; Thu, 14 May 2026 17:06:11 +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 4gGPVY5nNJz2Msdqx; Thu, 14 May 2026 17:02:45 +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; Thu, 14 May 2026 17:06:09 +0800 From: Yi Sun To: , CC: , , , , Subject: [PATCH v3 0/2] Improve the performance of bitmap_find_next_zero_area_off() Date: Thu, 14 May 2026 17:06:05 +0800 Message-ID: <20260514090607.231387-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-Type: text/plain; charset="UTF-8" Content-Transfer-Encoding: 8bit X-ClientProxiedBy: SHCAS03.spreadtrum.com (10.0.1.207) To BJMBX02.spreadtrum.com (10.0.64.8) X-MAIL:SHSQR01.spreadtrum.com 64E96BmD011913 DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=unisoc.com; s=default; t=1778749584; bh=NHQq38+P6RP9LfOhsunTs+66myJsZrxXGpR7GdqURaU=; h=From:To:CC:Subject:Date; b=M61bUGSfXnycp3nTzKNgUUW4VSblXgb0uMM2NtoI0EPYBWzNRXVC56rDE6uPtNQUX KYlQFFVQoGYDyFJeUVzIoWfKHUBvmi4Q18qG/0LNCiV/GAClCmsS858YT1j4odXrc1 XUGauHqqRwfwbQQfgDgTtcE2IrjWPMt5kpB9iJxr5Zb+DJobfAtF56foKgxu/ghnUe vza9fKzqqJIjfaKh7ZVSWf3H26Uc6csmvnL7mGc5pBiE3tv8n1NQA28OHQcB3YqMjL rpInsyjAuIYplLKeIiXSTVl51pT58GzFDjJ2qRkjzOqAVpJ5k5U12/0MrJX8gX9sxv 0dvVNMmGPnvpw== Based on Michał Nazarewicz's suggestion, code optimization was performed on PATCH v1. Replacing find_next_bit() with find_last_bit_from() can improve performance by an average of 50%. The test results can be viewed in PATCH v1. This section compares the performance of PATCH v2 and PATCH v3. Test results show that PATCH v3 performs slightly better than PATCH v2 in most cases. When the number of 'goto again' loops is large, PATCH v3's advantage becomes more apparent. Test result: cnt again_cnt v2_time(ns) v3_time(ns) time_ratio test1 8 9 230 242 -5.2% test2 8 1 75 76 around 0% test1 8 329 4452 4242 4.7% test2 8 1 46 47 around 0% test1 32 10414 139015 132700 4.5% test2 32 1 47 47 around 0% test1 128 2570 34163 32711 4.3% test2 128 1 46 46 around 0% test1 1024 321 4293 4098 4.5% test2 1024 6 126 122 3.2% test1 4096 81 1087 1046 3.8% test2 4096 92 1656 1570 5.2% 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. @again_cnt: The number of 'goto again'. @v2_time(ns): The total time consumed by bitmap_find_next_zero_area_off() when using PATCH v2. @v3_time(ns): The total time consumed by bitmap_find_next_zero_area_off() when using PATCH v3. @time_ratio = (v2_time - v3_time) / v2_time. --- 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 find_last_bit_from() and _find_last_bit_from() lib: bitmap: reduce the number of goto again in bitmap_find_next_zero_area_off() include/linux/find.h | 33 +++++++++++++++++++++++++++++++++ lib/bitmap.c | 2 +- lib/find_bit.c | 22 ++++++++++++++++++++++ 3 files changed, 56 insertions(+), 1 deletion(-) -- 2.34.1