From mboxrd@z Thu Jan 1 00:00:00 1970 Received: from mail-pl1-f174.google.com (mail-pl1-f174.google.com [209.85.214.174]) (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 0FBE13C463 for ; Thu, 23 Jan 2025 22:39:48 +0000 (UTC) Authentication-Results: smtp.subspace.kernel.org; arc=none smtp.client-ip=209.85.214.174 ARC-Seal:i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1737671990; cv=none; b=XDXxhNSZ1ATlAAE1ESRGSg3cV1goVuGejzu5dnQijgNCJb5/yFIx/5+E4uR9q2iVklBbdtQgssvBFKXy4k+dX0SF2Qv2XMG90PcMfy410yV2hijJdu0AgdT91H1QiNo6l/xr8CzlCDlhHqOVqcIn7I/YMj/HfYWQnJq9jWVnBG0= ARC-Message-Signature:i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1737671990; c=relaxed/simple; bh=nmRFoRbJP45VnGR6ErSL81sW8GbjKP9D4G9Ev+yWXLA=; h=Date:From:To:Cc:Subject:Message-ID:References:MIME-Version: Content-Type:Content-Disposition:In-Reply-To; b=q2kwwiYhYM0AQI8Hee+bwVYb0HSCekhivea/MKPC8SHW/c2EEYSNf3BerLZFF4jtPYl3QzBGKsn91wIsNeovPtzC4+ULZl2J2VKldYvhNSZWTL21TL78Ed33PEadjGY8psZU1wBPzR4GvfALAuVq8rSvIuPp3bnoKiqe4BRlGFc= 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=XWKEyfxA; arc=none smtp.client-ip=209.85.214.174 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="XWKEyfxA" Received: by mail-pl1-f174.google.com with SMTP id d9443c01a7336-216634dd574so18358475ad.2 for ; Thu, 23 Jan 2025 14:39:48 -0800 (PST) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20230601; t=1737671988; x=1738276788; darn=vger.kernel.org; h=in-reply-to:content-disposition:mime-version:references:message-id :subject:cc:to:from:date:from:to:cc:subject:date:message-id:reply-to; bh=WbV2jijvrEW4dFR6vf42t4dBOQ6im7uDd90um6GuggY=; b=XWKEyfxAk5BOin9aGgy/QN+L7115U3eIZ/l9nPr2KrtE1WwT+l5KCO+QqsKlLC7n0+ dlGHSO+DBR4A8ZMDDtcARHxIOgYWeLYjW7vWiHaJi+Pnb9qzzMzkjw7DjmY1EVQn2aXR UntCxVqxIsEQFZ+R1XqFE3IZX0xYcbTdca3n65RDBUdTLpI/s9Wlm6aDY3YKfjAW6HvP K5Sxj97Ba+YbvJNC6aNnnE9qH72jdS6xtfbLCTgNWO/raxUcFMHk4MPQQKiVUmoaTIAc uOxRIAIfYF/wfZER39bhVb1m97wOxq7pazuIECR7ZN0ujMBX9QNJSKjWKc1ueAK9lFbv k/2g== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20230601; t=1737671988; x=1738276788; h=in-reply-to:content-disposition:mime-version:references:message-id :subject:cc:to:from:date:x-gm-message-state:from:to:cc:subject:date :message-id:reply-to; bh=WbV2jijvrEW4dFR6vf42t4dBOQ6im7uDd90um6GuggY=; b=k4YXJKz7UyWe44yUpZ/GlLgoEtzbE9bXDZ4ojkSAk99rQE0nIoO2KE4el57eLqLdlb simLshixtT5FTLuFOufStJ/0V9H4StFm/GAmRHlstL5T1AePJXxGRnUQ3dFkC3mxdqKv C0HsU+4gYBHR+/K0UotRr7rDg5IandZs6gSbj+caLdhd2TzOgYh7urGs2ebxVNfcn+dz 1GLKtB3b4302F3JwhlKDKDEZqED3gPfgREyuilJ8uKSp1n2rV7L/+MkhQNOwtNboouW+ HvIk8TxFGcc/mqGAWq32WPBCJdO9RNpR7FhSlLN/EmGy8RlipJ/qtTUCXzrjB0bnhEDZ QwRQ== X-Forwarded-Encrypted: i=1; AJvYcCUxZRtFDwfVEzvs2zq0y+581dSOrbwZO9RUjk4l+mF8zIREyGBMMHzBBs/g5YUOx/LyW4SB7o66NyIgcRk=@vger.kernel.org X-Gm-Message-State: AOJu0Yz5fEIP30rOhv2krpGMKnYntgy35cY30gydm8FqTyakfz2mmnzY U6vDYT3eqa+snZfIH3+MF4wmpZ/64wDe8unMupxtXvVq9iH22/r0 X-Gm-Gg: ASbGncvjuQz4TNrcRG59sjXBCZH4wdvegpGcc35lZgSy8x/APMNmcTfKBL1WBYbyVv5 wVn+Zl12SW94f+2zPJ65AhOu67yAp/ymD2PCKRQSRuoz+AI/fvD+BXw9DKfiHlDWmAIoyagaXkX X5vF9btnWPj7ZxrCdDFaxMsOAiJ90Vovob0Virgi3oKOWdBS6CngBvsb82sM0k5IWEJGbAkt5oJ owCNPls1cQgosllYByEhpxea4de/g4PGsZbhNvFmC4x+jOWzwt+shwMuXgUTBBN1tjssak8PdTu NWPwc6jBPkAzHaQ8JBLCPiX0zHIh X-Google-Smtp-Source: AGHT+IEySfEruKkclKCflAS7o7wnVAQyigh2nDh1zq41vL2dPJRx045Lx6gQIlJyTRcTwJghtsPnQw== X-Received: by 2002:a17:903:22ce:b0:216:1ad2:1d5 with SMTP id d9443c01a7336-21c355bb34amr457887295ad.41.1737671987995; Thu, 23 Jan 2025 14:39:47 -0800 (PST) Received: from localhost (maglev-oncall.nvidia.com. [216.228.125.128]) by smtp.gmail.com with ESMTPSA id d9443c01a7336-21da424ecd8sm4034825ad.245.2025.01.23.14.39.46 (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256); Thu, 23 Jan 2025 14:39:47 -0800 (PST) Date: Thu, 23 Jan 2025 17:39:45 -0500 From: Yury Norov To: Kuan-Wei Chiu Cc: I Hsin Cheng , linux@rasmusvillemoes.dk, jserv@ccns.ncku.edu.tw, mark.rutland@arm.com, linux-kernel@vger.kernel.org, eleanor15x@gmail.com Subject: Re: [PATCH] cpumask: Optimize cpumask_any_but() Message-ID: References: <20250117142658.297325-1-visitorckw@gmail.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: On Sat, Jan 18, 2025 at 03:32:29PM +0800, Kuan-Wei Chiu wrote: > Hi Yury, > > On Fri, Jan 17, 2025 at 11:32:54AM -0500, Yury Norov wrote: > > On Fri, Jan 17, 2025 at 10:59:31PM +0800, I Hsin Cheng wrote: > > > On Fri, Jan 17, 2025 at 10:26:58PM +0800, Kuan-Wei Chiu wrote: > > > > The cpumask_any_but() function can avoid using a loop to determine the > > > > CPU index to return. If the first set bit in the cpumask is not equal > > > > to the specified CPU, we can directly return the index of the first set > > > > bit. Otherwise, we return the next set bit's index. > > > > > > > > This optimization replaces the loop with a single if statement, > > > > allowing the compiler to generate more concise and efficient code. > > > > I thought compilers are smart enough to unroll loop in this case. Can > > you show disassembled code before and after? > > > Since cpumask_any_but() is an inline function, I added the following to > lib/cpumask.c for convenience: > > unsigned int non_inline_cpumask_any_but(const struct cpumask *mask, unsigned int cpu); > unsigned int non_inline_cpumask_any_but(const struct cpumask *mask, unsigned int cpu) > { > return cpumask_any_but(mask, cpu); > } > > I used objdump -d ./lib/cpumask.o to compare the differences. > > * Before the patch: > > 00000000000001f0 : > 1f0: f3 0f 1e fa endbr64 > 1f4: 48 8b 3f mov (%rdi),%rdi > 1f7: b8 40 00 00 00 mov $0x40,%eax > 1fc: 48 85 ff test %rdi,%rdi > 1ff: 74 4b je 24c > 201: f3 48 0f bc d7 tzcnt %rdi,%rdx > 206: 89 d0 mov %edx,%eax > 208: 39 d6 cmp %edx,%esi > 20a: 75 40 jne 24c > 20c: 83 fa 3f cmp $0x3f,%edx > 20f: 77 3b ja 24c > 211: 41 b8 01 00 00 00 mov $0x1,%r8d > 217: 83 c0 01 add $0x1,%eax > 21a: 83 f8 40 cmp $0x40,%eax > 21d: 74 2d je 24c > 21f: 89 c1 mov %eax,%ecx > 221: 4c 89 c2 mov %r8,%rdx > 224: 48 d3 e2 shl %cl,%rdx > 227: 48 89 d0 mov %rdx,%rax > 22a: 48 f7 d8 neg %rax > 22d: 48 21 f8 and %rdi,%rax > 230: 74 15 je 247 > 232: f3 48 0f bc d0 tzcnt %rax,%rdx > 237: 89 d0 mov %edx,%eax > 239: 39 d6 cmp %edx,%esi > 23b: 75 0f jne 24c > 23d: 83 fa 3f cmp $0x3f,%edx > 240: 76 d5 jbe 217 > 242: e9 00 00 00 00 jmp 247 > 247: b8 40 00 00 00 mov $0x40,%eax > 24c: e9 00 00 00 00 jmp 251 > > * After the patch: > > 00000000000001f0 : > 1f0: f3 0f 1e fa endbr64 > 1f4: 48 8b 17 mov (%rdi),%rdx > 1f7: 48 85 d2 test %rdx,%rdx > 1fa: 74 34 je 230 > 1fc: f3 48 0f bc ca tzcnt %rdx,%rcx > 201: 89 c8 mov %ecx,%eax > 203: 39 ce cmp %ecx,%esi > 205: 75 2e jne 235 > 207: 83 c1 01 add $0x1,%ecx > 20a: 83 f9 3f cmp $0x3f,%ecx > 20d: 77 21 ja 230 > 20f: 48 c7 c0 ff ff ff ff mov $0xffffffffffffffff,%rax > 216: 48 d3 e0 shl %cl,%rax > 219: 48 89 c1 mov %rax,%rcx > 21c: b8 40 00 00 00 mov $0x40,%eax > 221: 48 21 d1 and %rdx,%rcx > 224: 74 0f je 235 > 226: f3 48 0f bc c1 tzcnt %rcx,%rax > 22b: e9 00 00 00 00 jmp 230 > 230: b8 40 00 00 00 mov $0x40,%eax > 235: e9 00 00 00 00 jmp 23a > > > > > > > > > As a result, the size of the bzImage built with x86 defconfig is > > > > reduced by 4096 bytes: > > > > > > > > * Before: > > > > $ size arch/x86/boot/bzImage > > > > text data bss dec hex filename > > > > 13537280 1024 0 13538304 ce9400 arch/x86/boot/bzImage > > > > > > > > * After: > > > > $ size arch/x86/boot/bzImage > > > > text data bss dec hex filename > > > > 13533184 1024 0 13534208 ce8400 arch/x86/boot/bzImage > > > > Comparing zipped images tells little about code generation. Please use > > scripts/bloat-o-meter. > > > $ ./scripts/bloat-o-meter ./old_cpumask.o ./new_cpumask.o > add/remove: 0/0 grow/shrink: 0/1 up/down: 0/-23 (-23) > Function old new delta > non_inline_cpumask_any_but 97 74 -23 > Total: Before=522, After=499, chg -4.41% No need to introduce a wrapper. You need to build allyesconfig (or defconfig) before and after your patch, and then run bloat-o-meter against old and new vmlinux. And specifically for cpumasks, can you please run this experiment with NR_CPUS == 32 and NR_CPUS == 4096, for example. That way you will test the change against small_cpumask_bits optimization. Thanks, Yury