From mboxrd@z Thu Jan 1 00:00:00 1970 Received: from mail-yw1-f181.google.com (mail-yw1-f181.google.com [209.85.128.181]) (using TLSv1.2 with cipher ECDHE-RSA-AES128-GCM-SHA256 (128/128 bits)) (No client certificate requested) by smtp.subspace.kernel.org (Postfix) with ESMTPS id 9B3DC3B14BF for ; Mon, 8 Jun 2026 22:15:06 +0000 (UTC) Authentication-Results: smtp.subspace.kernel.org; arc=none smtp.client-ip=209.85.128.181 ARC-Seal:i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1780956908; cv=none; b=bcG78Yy7Mx9O9mra4NzZWL3Gbv8mm2ILIjZE6L5dmYUXthT0tMKdBH06rsjCialiSvPm8HRAU1cWeQREDvkqUAYYe+iXQJfG2i/ZQ9e68OufJnXgj+Lot2F5PxrPDbBQ3uBue4BVCXXp4ACqeQ+o8aLlj0WBfIhEVbLXxagVQCw= ARC-Message-Signature:i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1780956908; c=relaxed/simple; bh=JgYvW5DFvsMROeUPyR4J/wW5A0cy4mz7xjguD1/8ZZA=; h=From:Date:To:Cc:Subject:Message-ID:References:MIME-Version: Content-Type:Content-Disposition:In-Reply-To; b=B/pJsN5tzFf9ipDS2/HpqNwnmTWhcXtPzlmCAazJ2OuTlOvS0hUlIgJVe6PAo7unekHjldl7vFjNXQbJPscnoGpdL/MPyR3ww2mSx8aHB5UQzeSoOGW7DEkLDaSA02mUUGfx6CyQefn8H8yzP64xaByaq7QNaLL6g1CdxiKZn4g= ARC-Authentication-Results:i=1; smtp.subspace.kernel.org; dmarc=pass (p=none dis=none) header.from=gmail.com; spf=pass smtp.mailfrom=gmail.com; dkim=pass (2048-bit key) header.d=gmail.com header.i=@gmail.com header.b=M0zWN92U; arc=none smtp.client-ip=209.85.128.181 Authentication-Results: smtp.subspace.kernel.org; dmarc=pass (p=none dis=none) header.from=gmail.com Authentication-Results: smtp.subspace.kernel.org; spf=pass smtp.mailfrom=gmail.com Authentication-Results: smtp.subspace.kernel.org; dkim=pass (2048-bit key) header.d=gmail.com header.i=@gmail.com header.b="M0zWN92U" Received: by mail-yw1-f181.google.com with SMTP id 00721157ae682-7dfceeaf168so45721877b3.0 for ; Mon, 08 Jun 2026 15:15:06 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20251104; t=1780956906; x=1781561706; darn=vger.kernel.org; h=in-reply-to:content-disposition:mime-version:references:message-id :subject:cc:to:date:from:from:to:cc:subject:date:message-id:reply-to; bh=PfgttJjeI3kGZmy3BCCDRPnSpWMqJqGOcHRN2MbRAYU=; b=M0zWN92UgmEhuhWrHS2Z3JQjhb/liO/rbc3CU2LwPQ0C+Kp2WgtXO/VVIZrg0QiAv/ 5n1dECFNeEmlRQ/l78fK3mfe48HNKV5o9qJ70gGyQ6cmyrIw1qD2QU6QOAsFPYT/McqC mdGL1C31wDd1id2Ju0TtlD1IThS2mpL+lUdmJDJNWm/WORfCSaMgyZamvXt+gGrmaGAz K5I1m+Ec3ewIXM7uPNa8HzUkLKIBazYsmXuq7n6zQrmhZSx/vMHdkSvYvgPH5fwcpiJm FK+FT6R02sEq5S/ra7KisJ0BvKf+EkaVoVJSgE8pGcnIy0gW3xs9y/Krkfz6lSdaJT1F MG4A== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20251104; t=1780956906; x=1781561706; h=in-reply-to:content-disposition:mime-version:references:message-id :subject:cc:to:date:from:x-gm-gg:x-gm-message-state:from:to:cc :subject:date:message-id:reply-to; bh=PfgttJjeI3kGZmy3BCCDRPnSpWMqJqGOcHRN2MbRAYU=; b=m29viP2c45Myu1PWqhadXXvSW6bGbO8XcT5xHoqmg+vbhHFwLe+a5Pf5xGmGsMXdvc 94wY8mhDxz7PnRTHn+v2vsFlo37ORjpzDPJhIJzSfR+jV6xdB4St3PoRprqI+Rdj4hNK B9hI0GWfXU7fQxWB5Wp+FDA/XbDZgRTkqi2ENKGv5AMRvxnU3othblagOcC+hgchPex8 Dp7FGi/0d8oK62WQgWxbaEFWrdOghEh9Nld8gz1JurqeZnLNZ2Hmu26GItUYyQKLzqMK g/AIJHuTsnjYQHUekSX4aMTnN9yylLStfhc8FuLGofJ6Zf0ufXXd/RdtY+E2LmrCEhrF aDNg== X-Forwarded-Encrypted: i=1; AFNElJ+9clc/qVhFfkI6VNWj5EDIL5xAnm9gO+6gy1JJqaEb3JnfSh0srUglz+qNd7D/G6oExNe5YS3LXJA/mmc=@vger.kernel.org X-Gm-Message-State: AOJu0YxKTqU58TpApTLIgy86GlNgmO9jkSYGyC61Rj+7YNoHIHAUmJ2x qlAjAtLisHMPnz/GyXi8/UdDIFtJJ33CUbeLxUcIBKyS3rI1zbAWvUtK X-Gm-Gg: Acq92OF1nO62N2TfK7DIw1QfqTailZlGiiPrV4loSu7iJ62P36Ii5CVRQh66ViNy3YB AI02+BAxrBMKqyUkb0o+Jijvl431g1e1b1N16XAZ+cXJYdXM/hHdAjXYJMDBtd5PyC/CiOkzxxN RiboclB61Wd8bXwVKVp66XSFjLaGMP63frGkNtNvoAQM8b+s/LONJkdAhu+0AaH5HliMa0sbWmL PDUrRuKtVXyWt0v3BnYq/P9nsQh2Ve4C1cRO5fvVKX6xdwHnDx6yMwtH64hDxbHslefKZ7KLGst Pp9fNdk7hU1eto9tw/QL96q4kWmh8F2ehCiFstTbNeojSSibm/69POEVD0dJ/7gMotn7O7Dm2yC 8/Gj1O71G2YA0D+EXo8pxO5jTXPbX2zWK5WzNtEXY8rnUeg9IM4u/9tHgR58E8OGkF21c1YVtYl uMaubpGmwCVn3Yo9ZH78B0UMBSJPo8 X-Received: by 2002:a05:690c:6e89:b0:7f0:1d63:9cda with SMTP id 00721157ae682-7f01d63a07dmr74454367b3.33.1780956905567; Mon, 08 Jun 2026 15:15:05 -0700 (PDT) Received: from localhost ([50.221.107.122]) by smtp.gmail.com with ESMTPSA id 00721157ae682-7ea23b91689sm88098887b3.40.2026.06.08.15.15.05 (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256); Mon, 08 Jun 2026 15:15:05 -0700 (PDT) From: Yury Norov X-Google-Original-From: Yury Norov Date: Mon, 8 Jun 2026 18:15:04 -0400 To: Yi Sun Cc: yury.norov@gmail.com, mnazarewicz@gmail.com, akpm@linux-foundation.org, mina86@mina86.com, akinobu.mita@gmail.com, linux-kernel@vger.kernel.org Subject: Re: [PATCH v4 1/2] lib: bitmap: reduce the number of goto again in bitmap_find_next_zero_area_off() Message-ID: References: <20260601094234.103863-1-yi.sun@unisoc.com> <20260601094234.103863-2-yi.sun@unisoc.com> 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=us-ascii Content-Disposition: inline In-Reply-To: <20260601094234.103863-2-yi.sun@unisoc.com> On Mon, Jun 01, 2026 at 05:42:33PM +0800, Yi Sun wrote: > 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 "goto again" calls. > > Signed-off-by: Yi Sun > --- > lib/bitmap.c | 10 +++++++--- > 1 file changed, 7 insertions(+), 3 deletions(-) > > diff --git a/lib/bitmap.c b/lib/bitmap.c > index b9bfa157e095..7d0fbcbe6973 100644 > --- a/lib/bitmap.c > +++ b/lib/bitmap.c > @@ -432,7 +432,7 @@ unsigned long bitmap_find_next_zero_area_off(unsigned long *map, > unsigned long align_mask, > unsigned long align_offset) > { > - unsigned long index, end, i; > + unsigned long index, end, i, index_bits_align, index_idx; > again: Can you make an extra step, and remove the 'goto again' completely with the more high-level for(), do-while() or similar? > index = find_next_zero_bit(map, size, start); > > @@ -442,8 +442,12 @@ unsigned long bitmap_find_next_zero_area_off(unsigned long *map, > end = index + nr; > if (end > size) > return end; > - i = find_next_bit(map, end, index); > - if (i < end) { > + > + index_bits_align = round_down(index, BITS_PER_LONG); > + index_idx = index / BITS_PER_LONG; Too many indexes here. Can you find some better, meaningful names? > + > + i = find_last_bit(map + index_idx, end - index_bits_align) + index_bits_align; > + if (i > index && i < end) { > start = i + 1; > goto again; > } I spent a couple cycles trying to understand why it works better, comparing to find_next_bit(). The thing is that the distance between first set bit and the beginning of the area is greater than between the last bit and the beginning, so we make bigger steps traversing the butmap. Is that right? Can you add a step-by-step explanation in the commit message for both versions, for clarity? Still wondering why the 'last_bit' version is slower here. Looking at the find_bit_benchmark output, the 'last_bit' is generally faster than the 'next_bit'... Thanks, Yury > -- > 2.34.1