From nobody Sat Apr 4 06:04:25 2026 Received: from mail-pf1-f176.google.com (mail-pf1-f176.google.com [209.85.210.176]) (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 1BD1C3DEFF2 for ; Fri, 20 Mar 2026 18:10:04 +0000 (UTC) Authentication-Results: smtp.subspace.kernel.org; arc=none smtp.client-ip=209.85.210.176 ARC-Seal: i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1774030210; cv=none; b=Qtmfl6OFtU2Fnrl2v6fQp5/xKUckmmWtVkluZEG5WZnMgiW0s/MVZ1NNvAIgFhsUqr+fQSWprFWrAu5AK4ERIOqkfXnTLy3E6dFOhYEu3kaUaYW8m3gbpBEAc6B5tRhtbl/C+qoUtw2XcVLjHfAUcDD2ybjgiuBsZTMMb0VPhFg= ARC-Message-Signature: i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1774030210; c=relaxed/simple; bh=QLhWqOPHfOFL/nrkycXFnDQr+Ve6lbu6MGgYyX8axaI=; h=From:To:Cc:Subject:Date:Message-ID:In-Reply-To:References: MIME-Version; b=XcIdQyDrVAU71SLzrejSU/Ft6RM4cvbNihrdzW6Ylm/VO5YAvmdpVMz5ung94F9nsJfMN8zGq8bZC55jXXqBo3v35yJMYcrgeetWI5bBIkGk2mfFl7yB+lw6NQ0CJv/fcoILj5DZzfhq1vAH6D9naeJioxRCFcd5Aocqo1Nw7fc= 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=Hi6BayeI; arc=none smtp.client-ip=209.85.210.176 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="Hi6BayeI" Received: by mail-pf1-f176.google.com with SMTP id d2e1a72fcca58-82985f42664so1580475b3a.0 for ; Fri, 20 Mar 2026 11:10:04 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20230601; t=1774030204; x=1774635004; darn=vger.kernel.org; h=content-transfer-encoding:mime-version:references:in-reply-to :message-id:date:subject:cc:to:from:from:to:cc:subject:date :message-id:reply-to; bh=UMdcBuBMskRutNA8N3biKduuLjw+8mQjfcLCAfh2HNM=; b=Hi6BayeIxxdU+7xUxwLuuTeJviwUVuZQrB70ogsoDRFICTn7Iu4kho7NeTcrjawLeq HaKWHeDgpg28K+TVcWfnxPrYIkqqD1nCPPOS7UNbzNu9Unj3rPLGrXFSUz+ZvED/DsLc Z5PTtO7nIXWzUyuJs602Wa0//eOnYS+TxBh5kmz13kievhwsOddrYHITuEe586dJn+RP 4HA4jtgNhvH8cjUIZvSZQN98hskEfuCRPTPNJ9fpdAAJVH+9ve/EjPCvU6FM2q/WUMBt DX529Z9b/psqczc5ZpRWxaLYFy34OuFGRuZEQz79Xy8KtvgIR972Vhphh9IW9DUoojyr rQ2w== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20251104; t=1774030204; x=1774635004; h=content-transfer-encoding:mime-version:references:in-reply-to :message-id:date:subject:cc:to:from:x-gm-gg:x-gm-message-state:from :to:cc:subject:date:message-id:reply-to; bh=UMdcBuBMskRutNA8N3biKduuLjw+8mQjfcLCAfh2HNM=; b=O+JxotCRD1HbCNKpi1C8+WSdSjNoOwDEG65S8BqgjKhgGNPH5iyNeCRDL680MnyaX8 6TZ75CVi0x2Loh6niDO9O89gdzplHW3LzlNJWo/Sy3AFIrb9gkWVZ2UuQ+spPVvS9fY1 kMzk5VRsYWNS4s0xLB+fmlogjFm9sXCyUoZatzI+MfWBMdOYHcEzj2k2SSoyXbhvETqg TLvEw+yGRw2hDNunzwtcYEMoPfLx33R3GAJjn0OHGInow6UGiKB7mbbI0D0CqMpIKEHI cISgznme+ODY5vSSIDmHUfSWjYKHL13sdtwg+jL2WwPwXTvWwT5JavApA3WLBdFrADkc W2ow== X-Forwarded-Encrypted: i=1; AJvYcCVnvxXTHOVs6nyXPMwhLojJaH6NUVcGKEplj9PJCrup7RMkr5VuKkzdaa/v3DNSjrmZTuGDynpipQ9+T3g=@vger.kernel.org X-Gm-Message-State: AOJu0YziP4kTKTdX6KWfBLi6EowbkuwI8+aW7rytiy68NBB7Bc2ydMcm n7WXwFe6eCyMebJ6sUglHUayTocQZaBJev1VzJqYK7FZPfm/Z2BOLdhm X-Gm-Gg: ATEYQzzcuaJGPY8tglhQg39oa5nj33cDmmSGA0NsCmO4uD8j/DszDmNFm9XyoTaARNN cNGqhNvj+jC2kD2nK0Al9mWWVWz2ooueVlRMKnB8UgJap9aWp+5vubphd/soaM4wB8Kq4DQFg4z zmo6Bojzcn7QPBjlMh8YgkJWnFZLYoNG92/88k9/FmivBzeO8BDC7VAziywBCs01A1JzM1H6lBz GNb5BNde0+x2SbYhF9+OZ+YvRaLdodf9jaf4YqvFLUbSDvmWlygPzQlUR2Cuc13J3yIkbz8aBgf b+qs0C7rBYi7hoMBxqh2YBbDB04GkdMpXqSefSpE9imgqNifLzVegtkrW1Qj9p19mLMiZwUyt2n 818oRXhgJ8WmjmDoCs+Xu71xvkR00pA+qQQJOJrLU0e/h1fjUVXvHRv4rrhXXXFBxpli7SCkGlJ cgTTkprNpN/l+itMN5kFBoTcnMqz61n58kE+Fa31ZaMpUB5WHa7nDl/6lh/SBVb+FWzzrbU7yrD zP4zJHbI8rphBeL0vYubbUs9PTs10uJw2fLA9I= X-Received: by 2002:a05:6a00:2d05:b0:82a:6125:728f with SMTP id d2e1a72fcca58-82a8c22de9emr3410942b3a.10.1774030204035; Fri, 20 Mar 2026 11:10:04 -0700 (PDT) Received: from visitorckw-work01.c.googlers.com.com (100.130.194.35.bc.googleusercontent.com. [35.194.130.100]) by smtp.gmail.com with ESMTPSA id d2e1a72fcca58-82b040d7e56sm2582318b3a.40.2026.03.20.11.10.02 (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256); Fri, 20 Mar 2026 11:10:03 -0700 (PDT) From: Kuan-Wei Chiu To: richard@nod.at, akpm@linux-foundation.org Cc: chengzhihao1@huawei.com, hch@infradead.org, jserv@ccns.ncku.edu.tw, eleanor15x@gmail.com, marscheng@google.com, linux-mtd@lists.infradead.org, linux-kernel@vger.kernel.org, Kuan-Wei Chiu Subject: [PATCH v3 2/2] lib/list_sort: Remove dummy cmp() calls to speed up merge_final() Date: Fri, 20 Mar 2026 18:09:38 +0000 Message-ID: <20260320180938.1827148-3-visitorckw@gmail.com> X-Mailer: git-send-email 2.53.0.959.g497ff81fa9-goog In-Reply-To: <20260320180938.1827148-1-visitorckw@gmail.com> References: <20260320180938.1827148-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-Transfer-Encoding: quoted-printable Content-Type: text/plain; charset="utf-8" Historically, list_sort() implemented a hack in merge_final(): if (unlikely(!++count)) cmp(priv, b, b); This was introduced 16 years ago in commit 835cc0c8477f ("lib: more scalable list_sort()") so that callers could periodically invoke cond_resched() within their comparison functions when merging highly unbalanced lists. An audit of the kernel tree reveals that fs/ubifs/ was the sole user of this mechanism. Recent discussions and inspections by Richard Weinberger confirm that UBIFS lists are strictly bounded in size (a few thousand elements at most), meaning it does not strictly rely on these dummy callbacks to prevent soft lockups. For the vast majority of list_sort() users (such as block layer IO schedulers and file systems), this hack results in completely wasted function calls. In the worst-case scenario (merging an already sorted list where 'a' is exhausted quickly), it results in approximately (N/2)/256 unnecessary cmp() invocations. Remove the dummy cmp(priv, b, b) fallback from merge_final(). This saves unnecessary function calls, avoids branching overhead in the tight loop, and slightly speeds up the final merge step for all generic list_sort() users. Signed-off-by: Kuan-Wei Chiu Reviewed-by: Christoph Hellwig --- lib/list_sort.c | 9 --------- 1 file changed, 9 deletions(-) diff --git a/lib/list_sort.c b/lib/list_sort.c index a310ecb7ccc0..e8ff17c9b2d0 100644 --- a/lib/list_sort.c +++ b/lib/list_sort.c @@ -76,15 +76,6 @@ static void merge_final(void *priv, list_cmp_func_t cmp,= struct list_head *head, /* Finish linking remainder of list b on to tail */ tail->next =3D b; do { - /* - * If the merge is highly unbalanced (e.g. the input is - * already sorted), this loop may run many iterations. - * Continue callbacks to the client even though no - * element comparison is needed, so the client's cmp() - * routine can invoke cond_resched() periodically. - */ - if (unlikely(!++count)) - cmp(priv, b, b); b->prev =3D tail; tail =3D b; b =3D b->next; --=20 2.53.0.959.g497ff81fa9-goog