From mboxrd@z Thu Jan 1 00:00:00 1970 Received: from lithops.sigma-star.at (mailout.nod.at [116.203.167.152]) (using TLSv1.2 with cipher ECDHE-RSA-AES256-GCM-SHA384 (256/256 bits)) (No client certificate requested) by smtp.subspace.kernel.org (Postfix) with ESMTPS id 2E8DF21B185 for ; Mon, 16 Mar 2026 07:25:59 +0000 (UTC) Authentication-Results: smtp.subspace.kernel.org; arc=none smtp.client-ip=116.203.167.152 ARC-Seal:i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1773645962; cv=none; b=jJPliDLhDUJz5iux0Z/2jp0cYCWQ7hpfcLHz2/+3armOVj/jgGLOUstp02zZ/n46Dz4RY5YphnWuq3TGtEiuWjHcLl12b+2geiLD2qaVIpKtfJVJbaMyJ30tbHXE2iCPcaJ0UhH6ueX4SKk8aSyr7jFKlRrJaf0fNJWKaFhnvXA= ARC-Message-Signature:i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1773645962; c=relaxed/simple; bh=RHx19wlmROQ+ItfY6Vl9cn+RpY2pSq94lLj/Z0L+wxM=; h=Date:From:To:Cc:Message-ID:In-Reply-To:References:Subject: MIME-Version:Content-Type; b=a0uJP4o4G4zNI9SGgyyeomvQDC4Noht+IxOfYuBFTEei6Egwtmj3tTZElfgET1gHdFURX0Bp12a1pnQdgLi4Y02SrXWa/QrH9UJ83DNmiXcBjmpJT1SiGcXB7H1VrXqDVVMjsGrezAFrrEChvCoM4Qg/AAP7E6Prc9Gs2n5dyD4= ARC-Authentication-Results:i=1; smtp.subspace.kernel.org; dmarc=none (p=none dis=none) header.from=nod.at; spf=fail smtp.mailfrom=nod.at; arc=none smtp.client-ip=116.203.167.152 Authentication-Results: smtp.subspace.kernel.org; dmarc=none (p=none dis=none) header.from=nod.at Authentication-Results: smtp.subspace.kernel.org; spf=fail smtp.mailfrom=nod.at Received: from localhost (localhost [127.0.0.1]) by lithops.sigma-star.at (Postfix) with ESMTP id 012BA2A8813; Mon, 16 Mar 2026 08:25:58 +0100 (CET) Received: from lithops.sigma-star.at ([127.0.0.1]) by localhost (lithops.sigma-star.at [127.0.0.1]) (amavisd-new, port 10032) with ESMTP id 1kHUCoMHY-SB; Mon, 16 Mar 2026 08:25:57 +0100 (CET) Received: from localhost (localhost [127.0.0.1]) by lithops.sigma-star.at (Postfix) with ESMTP id 86776BE33F; Mon, 16 Mar 2026 08:25:57 +0100 (CET) Received: from lithops.sigma-star.at ([127.0.0.1]) by localhost (lithops.sigma-star.at [127.0.0.1]) (amavisd-new, port 10026) with ESMTP id U_QzWOIkbGqx; Mon, 16 Mar 2026 08:25:57 +0100 (CET) Received: from lithops.sigma-star.at (lithops.sigma-star.at [195.201.40.130]) by lithops.sigma-star.at (Postfix) with ESMTP id 4E5C2298580; Mon, 16 Mar 2026 08:25:57 +0100 (CET) Date: Mon, 16 Mar 2026 08:25:57 +0100 (CET) From: Richard Weinberger To: Kuan-Wei Chiu Cc: Andrew Morton , chengzhihao1 , jserv@ccns.ncku.edu.tw, eleanor15x@gmail.com, marscheng@google.com, linux-mtd , linux-kernel Message-ID: <1295583760.42468.1773645957126.JavaMail.zimbra@nod.at> In-Reply-To: <20260315193900.218737-1-visitorckw@gmail.com> References: <20260315193900.218737-1-visitorckw@gmail.com> Subject: Re: [PATCH] lib/list_sort: introduce list_sort_nonatomic() and remove dummy cmp() calls 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=utf-8 Content-Transfer-Encoding: quoted-printable X-Mailer: Zimbra 8.8.12_GA_3807 (ZimbraWebClient - FF148 (Linux)/8.8.12_GA_3809) Thread-Topic: lib/list_sort: introduce list_sort_nonatomic() and remove dummy cmp() calls Thread-Index: yka9mQdudGGmgf615CanqWIVMhGQsQ== ----- Urspr=C3=BCngliche Mail ----- > Von: "Kuan-Wei Chiu" > Historically, list_sort() implemented a hack in merge_final(): > if (unlikely(!++count)) > cmp(priv, b, b); >=20 > This was designed specifically so that callers could periodically > invoke cond_resched() within their comparison functions when merging > highly unbalanced lists. >=20 > 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