From mboxrd@z Thu Jan 1 00:00:00 1970 Received: from mail-wm1-f53.google.com (mail-wm1-f53.google.com [209.85.128.53]) (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 4B92941D656 for ; Thu, 16 Jul 2026 11:58:11 +0000 (UTC) Authentication-Results: smtp.subspace.kernel.org; arc=none smtp.client-ip=209.85.128.53 ARC-Seal:i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1784203095; cv=none; b=cXRr7qncsx5qW0U+61jh22qT+8xWrZO6x8E/pAIceDGEY5nehdy2whXEVpHjS6fI5Gfl6gb8xSY+jgly5zh3V8AMrpIdzQazCJgl0/EsUNH7w/QJXx6MJzyRjFW3IRBQSvcF75lufvKUy+BspYZm5906dXaCot07yd3yGu4R0wM= ARC-Message-Signature:i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1784203095; c=relaxed/simple; bh=2xQLGfGVdiQpZakUbCijnRbuq6n9M6NjUtD1FGhFliE=; h=Date:From:To:Cc:Subject:Message-ID:References:MIME-Version: Content-Type:Content-Disposition:In-Reply-To; b=uwZYcOBzCRLpzYe1Cw5Pz7BTrIDRaEWFI2Tcano3qE0xpcd7l5hwTuqr/Ik2ZhoG8TlZ9Qzt/eAZXENLtiM86xeb5NE1xYydml3JKKfSPXqxssBDAoa1Y90DBm2kxSTawYchEB5poaTHTI/N1T4z/6RUZEGMEizTcVGeuDADNsA= ARC-Authentication-Results:i=1; smtp.subspace.kernel.org; dmarc=pass (p=none dis=none) header.from=cmpxchg.org; spf=pass smtp.mailfrom=cmpxchg.org; dkim=pass (2048-bit key) header.d=cmpxchg.org header.i=@cmpxchg.org header.b=ZgRdMTuB; arc=none smtp.client-ip=209.85.128.53 Authentication-Results: smtp.subspace.kernel.org; dmarc=pass (p=none dis=none) header.from=cmpxchg.org Authentication-Results: smtp.subspace.kernel.org; spf=pass smtp.mailfrom=cmpxchg.org Authentication-Results: smtp.subspace.kernel.org; dkim=pass (2048-bit key) header.d=cmpxchg.org header.i=@cmpxchg.org header.b="ZgRdMTuB" Received: by mail-wm1-f53.google.com with SMTP id 5b1f17b1804b1-493f45e206dso1375955e9.1 for ; Thu, 16 Jul 2026 04:58:11 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=cmpxchg.org; s=google; t=1784203090; x=1784807890; darn=vger.kernel.org; h=in-reply-to:content-disposition:content-type:mime-version :references:message-id:subject:cc:to:from:date:from:to:cc:subject :date:message-id:reply-to:content-type; bh=smB1Wub3do3Ht1+5O0kRCaE6wVK0Ph5Z3e7aTwQkcIU=; b=ZgRdMTuB/+HPpFJeYjaMtBuU2pdh0M6SssuefqYMhuNBbpXJU0dK84uDD29QGsMI9O Zvh+TT/Wb6XE0ObGq9tbB0KFg3v3WIe0lbA9kQ867AGYQIfYm2O1ukf2/4Nv0RpOvmdi 8P/uC+MNRBMh2erh7sLAtMpnAo4+PTEvQgvQ5Kq9Dxw5GfR5O9Utuoar8WhezU4U9VIr gLF9TezawbWb6crSq1l0+bav418KXpFtEvqKoj9C9Nc+X1pOpJ5Iz3uDXAOylvwMMa5i Ir3NEet4w3qS2by6cz7j2Xa+ows8DRUTateY1rnT/c9L2rJf/CexDJjIaMcawIJbn7Nz 1R5g== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20251104; t=1784203090; x=1784807890; h=in-reply-to:content-disposition:content-type:mime-version :references:message-id:subject:cc:to:from:date:x-gm-gg :x-gm-message-state:from:to:cc:subject:date:message-id:reply-to :content-type; bh=smB1Wub3do3Ht1+5O0kRCaE6wVK0Ph5Z3e7aTwQkcIU=; b=mfOlVPdCKUJdZN1ZkLX4B6FpZpWUlqBGPdamhow3jbhSj4qJc95Q7HHPG+Frofbnh/ 10SBQkWTnCfPp5hMX4aM1LscBzOqVqyC4B2VBtwoGoSifgA3YyA+5pPpEab/zIDZ++mi YSlBluCdlQ+9p2hFZndtXfcUEabDIjF/D6gla/hHvuXgeTPYMg/XbuJKPZPztFTiopv9 JH46epfqxOaRBzFCQ9GmucgD8Wo6q59KPEh1tQNuPGJyj8Wr8U1hk0WImT7hOOprpD8L 4GOZqrzlLK+K5YHdqEvMLOtfCFNQwW/OShjF6TbMwU1Y2EgPMxGBUzBxdEL9hriXuxO5 yn4Q== X-Forwarded-Encrypted: i=1; AHgh+Rqt+A9wBsRw0SeNYvtYICI4iTxkDumWCtbhWyFjtjgmbsIcYPnONtjp92iC8JVGYGsV9geJ2rPRCmSZ6o0=@vger.kernel.org X-Gm-Message-State: AOJu0YwoLcpv0sJwUTWS15HgZL1o1lq8a7zn5QLd78pLIt3Y9xCTwAJo RPw0PgKWfEgryhzvbrFd8RY8Ta77DLN6ry03hY4Il+kKkKsLK19JSbNQcjHpo8dEioE= X-Gm-Gg: AfdE7clb8iklouxXgkOL6cLh1C85OZhZlZe/ZrQ+g/XKzUyOrMJJZfU9T5LvNttyLtI L6CPmWoLt2WBdKBHKhk1+h0eR5INqep9lYlUFcYggdlnFCIGQCd8cnLxJ1zm7YlBN05Fc9H374j KwMcmZryyeIfmiFg7KOZBegr7hbTCVsYkeETpYVOnYwowvF9xr7cJl86qmeLCOnV2pzACgGhsgR 3tSMTx1uvVGuLKDM6zMIt4XSLtDMuGB9iMhUWNDrYR4aLaqwsovEFPJUZ+EnMb60jdhnc0ypFhY uoCqMepX5qlxUAFkCP9ajTQVP9J7LT1hLN+WSE6VvjoT+7Jmic4xKZwDmNBIL8e0ytzoCCJzKSJ B/2wFOS5pM53oz2DrYUKP2DJ38G2K4I2yOSlxcUur5RXopXVxGgfY4xvpOBho6tAw5jjXfRP7GY ZwJGEhAJbmK2g= X-Received: by 2002:a05:600c:6291:b0:495:3a52:71b1 with SMTP id 5b1f17b1804b1-49542871f51mr24741645e9.5.1784203089883; Thu, 16 Jul 2026 04:58:09 -0700 (PDT) Received: from localhost ([2a02:8071:6401:180:d892:bf43:a0b4:83b]) by smtp.gmail.com with ESMTPSA id 5b1f17b1804b1-49541e53680sm47876735e9.0.2026.07.16.04.58.08 (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256); Thu, 16 Jul 2026 04:58:09 -0700 (PDT) Date: Thu, 16 Jul 2026 13:58:04 +0200 From: Johannes Weiner To: Usama Arif Cc: bsegall@google.com, dietmar.eggemann@arm.com, juri.lelli@redhat.com, kprateek.nayak@amd.com, linux-kernel@vger.kernel.org, mgorman@suse.de, mingo@redhat.com, peterz@infradead.org, rostedt@goodmis.org, surenb@google.com, vincent.guittot@linaro.org, vschneid@redhat.com, shakeel.butt@linux.dev, riel@surriel.com, kernel-team@meta.com Subject: Re: [PATCH] sched/psi: use for_each_set_bit() in psi_group_change() task-count walk Message-ID: <20260716115804.GS276793@cmpxchg.org> References: <20260714142057.181135-1-usama.arif@linux.dev> <20260715135412.GN276793@cmpxchg.org> <347756df-f5d3-4c6f-85b0-ec04fc7d2e72@linux.dev> 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: <347756df-f5d3-4c6f-85b0-ec04fc7d2e72@linux.dev> On Wed, Jul 15, 2026 at 06:03:57PM +0100, Usama Arif wrote: > > > On 15/07/2026 14:54, Johannes Weiner wrote: > > On Tue, Jul 14, 2026 at 07:20:57AM -0700, Usama Arif wrote: > >> psi_group_change() walks the @clear and @set bitmasks to > >> decrement/increment groupc->tasks[t]. Both masks are at most > >> NR_PSI_TASK_COUNTS (=4) wide, dense at [0, 4), and typically > >> sparse. Today's form visits every position up to the highest set > >> bit: > >> > >> for (t = 0, m = clear; m; m &= ~(1 << t), t++) { > >> if (!(m & (1 << t))) > >> continue; > >> ... > >> } > >> > >> so a mask with only bit 3 set still spins four times; the same > >> open-coded shape repeats for @set. The code is also unnecessarily > >> hard to read. > >> > >> Switch both walks to for_each_set_bit() which is easier to read > >> and also more efficient. As NR_PSI_TASK_COUNTS is a compile-time > >> constant <= BITS_PER_LONG, find_next_bit() folds into its > >> small_const_nbits() fast path (single load + GENMASK + __ffs), lowering > >> to a bit-scan where one exists (x86 TZCNT/BSF, arm64 RBIT+CLZ). > >> > >> psi_group_change() runs from psi_task_switch() and psi_task_change() > >> once per ancestor psi_group per event, so the saved iterations > >> multiply out on any hot scheduler workload. > >> > >> No functional change intended. > > > > This actually started out using ffs. Because the performance is so > > sensitive in this path, this was handtuned to scheduler benchmarks. > > > > https://lore.kernel.org/all/20180718120318.GC2476@hirez.programming.kicks-ass.net/ > > > > Not the worst idea to revisit this, but you have to be careful, look > > at the asm, and benchmark it. gcc is producing more code for me with > > your patch. > > > So I tried with claude to create a kernel module that benchmarks the 3 > implementations, the current one, for_each_set_bit and __ffs [1]: > __ffs actually performs best. > > psi_bench: running on cpu 1, iters=2000000, trials=10 > psi_bench empty (clear=0x0, set=0x0) original=3.68 foreach=3.81 ffs=3.68 (for=+3% ffs=+0%) > psi_bench sleep (clear=0x4, set=0x0) original=9.60 foreach=5.18 ffs=3.74 (for=-46% ffs=-61%) > psi_bench iowait-sleep (clear=0x4, set=0x1) original=12.32 foreach=6.90 ffs=4.45 (for=-43% ffs=-63%) > psi_bench memstall-sleep (clear=0xc, set=0x0) original=11.87 foreach=5.98 ffs=5.54 (for=-49% ffs=-53%) > psi_bench wake (clear=0x0, set=0x4) original=7.10 foreach=5.17 ffs=3.70 (for=-27% ffs=-47%) > psi_bench iowait-wake (clear=0x1, set=0x4) original=10.83 foreach=6.91 ffs=4.48 (for=-36% ffs=-58%) > psi_bench: done > psi_bench: unloaded > > [1] https://gist.github.com/uarif1/e1bf78b54f50099b354b84684f880fda > > > I built the below patch and the code size reduces as well by > 67 bytes from 756B to 689B. If it looks ok, I can send it as v2? > > > From 052c845707f65d58d5cf8cb1da6515e268159e83 Mon Sep 17 00:00:00 2001 > From: Usama Arif > Date: Sat, 11 Jul 2026 03:57:01 -0700 > Subject: [PATCH] sched/psi: use __ffs() to walk task-count bitmasks in > psi_group_change() > > psi_group_change() walks the @clear and @set bitmasks to > decrement/increment groupc->tasks[t]. Both masks are at most > NR_PSI_TASK_COUNTS (=4) wide and typically have one or two bits > set. Today's form visits every position up to the highest set bit: > > for (t = 0, m = clear; m; m &= ~(1 << t), t++) { > if (!(m & (1 << t))) > continue; > ... > } > > so a mask with only bit 3 set still spins four times through the > skip path. Switch both walks to __ffs() + m &= m-1 form: > > while (clear) { > t = __ffs(clear); > clear &= clear - 1; > ... > } > > which iterates only over the set bits and terminates naturally on > m == 0. m & (m - 1) clears the lowest set bit. This code is easier > to read as well. > > An in-kernel microbench (noinline, same body, IRQs off, pinned CPU > on Zen4c/Bergamo, min-of-10 cyc/call) over mask distributions > produced by common scheduler PSI paths: > > mask pattern old new delta > empty (clear=0x0, set=0x0) 3.68 3.68 +0% > sleep (clear=0x4, set=0x0) 9.60 3.74 -61% > iowait-sleep (clear=0x4, set=0x1) 12.32 4.45 -63% > memstall-sleep (clear=0xc, set=0x0) 11.87 5.54 -53% > wake (clear=0x0, set=0x4) 7.10 3.70 -47% > iowait-wake (clear=0x1, set=0x4) 10.83 4.48 -58% > > Every non-empty case wins 47-63%: old cost tracks the highest set bit > (linear walk), new cost tracks the count of set bits (skip zeros via > TZCNT). Single-bit patterns run at the empty-case floor. > > The generated psi_group_change() text also shrinks by 67 bytes under > -O2 -march=x86-64 (756 -> 689): no scratch register for a "constant 1" > (only __ffs's operand is needed), simpler bit-clear (LEA+AND vs > SHL+NOT+AND after the test), and no skip-if-unset check per position. This looks great, thanks for digging deeper into it. > No functional change intended. ... he says right after large performance deltas lol. Drop that line? > Signed-off-by: Usama Arif Acked-by: Johannes Weiner