Re: [PATCH] lib/list_sort: introduce list_sort_nonatomic() and remove dummy cmp() calls

From: Richard Weinberger <richard@nod.at>
To: Kuan-Wei Chiu <visitorckw@gmail.com>
Cc: Andrew Morton <akpm@linux-foundation.org>,
	 chengzhihao1 <chengzhihao1@huawei.com>,
	jserv@ccns.ncku.edu.tw,  eleanor15x@gmail.com,
	marscheng@google.com,  linux-mtd <linux-mtd@lists.infradead.org>,
	 linux-kernel <linux-kernel@vger.kernel.org>
Subject: Re: [PATCH] lib/list_sort: introduce list_sort_nonatomic() and remove dummy cmp() calls
Date: Mon, 16 Mar 2026 08:25:57 +0100 (CET)	[thread overview]
Message-ID: <1295583760.42468.1773645957126.JavaMail.zimbra@nod.at> (raw)
In-Reply-To: <20260315193900.218737-1-visitorckw@gmail.com>

----- Ursprüngliche Mail -----
> Von: "Kuan-Wei Chiu" <visitorckw@gmail.com>
> Historically, list_sort() implemented a hack in merge_final():
>    if (unlikely(!++count))
>        cmp(priv, b, b);
> 
> This was designed specifically so that callers could periodically
> invoke cond_resched() within their comparison functions when merging
> highly unbalanced lists.
> 
> However, an audit of the kernel tree reveals that only fs/ubifs/ relies
> on this mechanism. For the vast majority of list_sort() users (such as
> block layer IO schedulers and file systems), this results in completely
> wasted function calls. In the worst-case scenario (merging an already
> sorted list where 'a' is exhausted quickly), this results in
> approximately (N/2)/256 unnecessary cmp() calls.

Why isn't this a problem for other users of list_sort()?
Are the lists they sort guaranteed to be short?

Or did nobody test hard enough on slow machines without preempt? ;-)

Thanks,
//richard

______________________________________________________
Linux MTD discussion mailing list
http://lists.infradead.org/mailman/listinfo/linux-mtd/