From nobody Sun Feb 8 14:51:58 2026 Return-Path: X-Spam-Checker-Version: SpamAssassin 3.4.0 (2014-02-07) on aws-us-west-2-korg-lkml-1.web.codeaurora.org Received: from vger.kernel.org (vger.kernel.org [23.128.96.18]) by smtp.lore.kernel.org (Postfix) with ESMTP id 86ABDC6FD1F for ; Sat, 25 Mar 2023 12:32:54 +0000 (UTC) Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S231194AbjCYMcx (ORCPT ); Sat, 25 Mar 2023 08:32:53 -0400 Received: from lindbergh.monkeyblade.net ([23.128.96.19]:35858 "EHLO lindbergh.monkeyblade.net" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S229674AbjCYMcv (ORCPT ); Sat, 25 Mar 2023 08:32:51 -0400 Received: from mail-pl1-x635.google.com (mail-pl1-x635.google.com [IPv6:2607:f8b0:4864:20::635]) by lindbergh.monkeyblade.net (Postfix) with ESMTPS id 25B6710AA8 for ; Sat, 25 Mar 2023 05:32:50 -0700 (PDT) Received: by mail-pl1-x635.google.com with SMTP id f22so65490plr.0 for ; Sat, 25 Mar 2023 05:32:50 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20210112; t=1679747569; 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=rch3xYeG6DW9krPGWOTHk/HlZRTT0Lo7FDRCIHvxzBM=; b=iA6Dbjd9N731A7vonAEnSIfWCUqbLY9wEJDMC+7U/sB4Rwz6WAsT04sEvBo38q+YuH xWOYYPDCLYcCso4jv3/7BCVFkzzJmwjA55ixMMU9rdz99xpveX8aX9aeLXSL/wiifBu3 JE7keyQkrz8wjiUBtbq0AXWbAQJLkg6XvqkGwPmg50x4vhAaeJlZbKeB4LZfvT5hO7BG EExy5W4ThSYz9b1kGtwlfto7GDSSK1u0LYs+SFx0O4PRNUMzWBSu5IUQ81xDTIF7FWI3 CJZvWX2TrMtVzumxtiuI7C/DUz//HPaxxj04+xLd//2YIyBOqf8TX3VoeYlD6ekI53JS 0hLw== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20210112; t=1679747569; h=content-transfer-encoding:mime-version:references:in-reply-to :message-id:date:subject:cc:to:from:x-gm-message-state:from:to:cc :subject:date:message-id:reply-to; bh=rch3xYeG6DW9krPGWOTHk/HlZRTT0Lo7FDRCIHvxzBM=; b=yAZLsiY5iWQRVSpR2tqtIxftGfICPYfpd2syKw/ObM5pDvpykMVC6fMdKUbZ2ZkK8A hJQdV/B/73pYfBBiB5LHcyXjLb3MYh1H3PEOpGm5QY7ZNEyoHyuZI6jgiKbYagVXfsqU oZqdryHtgoFUuSpNckhCU+r9KY2YjdcKmsMer23xiaoNXF2r81BG6A5yxDg4DglnsPB5 B3NQyO/jT/23U5oSFBDTt5R2XTevCNDW/CS13uBqYxAea+mIC65ztJY+8m/JSbkrVXu9 /GdPxKhsfk9IvifH2mALEhrE27mDsuRUwCVjkda5oyUQUaibKEhRE/ldY5T3Bg/U13s4 s9Dg== X-Gm-Message-State: AAQBX9eJtENEEoukicEdPZM06XliQ4OyVjqi08+ivIEemOFcNoirQsFV 5CpWMqA7oUxCAk4KmTcAvCo/s2y9B4w= X-Google-Smtp-Source: AKy350ZnRk0irYtRxvgTqRS9Bhou8b3jvF/ZcJZgoLfDeil+OxYjWvaFMsIMsZZD1rYvA+GOD+UwtA== X-Received: by 2002:a17:902:ba88:b0:19e:25b4:7740 with SMTP id k8-20020a170902ba8800b0019e25b47740mr5173078pls.28.1679747569394; Sat, 25 Mar 2023 05:32:49 -0700 (PDT) Received: from Dommie-Laptop.. (111-248-124-24.dynamic-ip.hinet.net. [111.248.124.24]) by smtp.gmail.com with ESMTPSA id l18-20020a170902d35200b0019468fe44d3sm15807134plk.25.2023.03.25.05.32.48 (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256); Sat, 25 Mar 2023 05:32:49 -0700 (PDT) From: Yan-Jie Wang To: linux-kernel@vger.kernel.org Cc: Yan-Jie Wang Subject: [PATCH v3] lib/list_sort: reduce if-statements Date: Sat, 25 Mar 2023 20:32:16 +0800 Message-Id: <20230325123216.226120-1-yanjiewtw@gmail.com> X-Mailer: git-send-email 2.34.1 In-Reply-To: <20230325091654.106040-1-yanjiewtw@gmail.com> References: <20230325091654.106040-1-yanjiewtw@gmail.com> MIME-Version: 1.0 Content-Transfer-Encoding: quoted-printable Precedence: bulk List-ID: X-Mailing-List: linux-kernel@vger.kernel.org Content-Type: text/plain; charset="utf-8" Reduce if-statements in merge and merge_final functions by using indirect pointers and bitwise operations. This will make the code more elegant and reduce the number of branch instructions in compiled code. Signed-off-by: Yan-Jie Wang --- Changes since v2: * Remove unnecessory assignments to the variable, node. Changes since v1: * Use do-while instead of for-loop to avoid an unnecessory check at the beginning of the loop. * After moving *node to the next node, just check whether *node is NULL or not instead of checking both a && b to determine whether to continue. * Above changes further reduces the compiled code size and branch instructions. lib/list_sort.c | 55 ++++++++++++------------------------------- tools/lib/list_sort.c | 55 ++++++++++++------------------------------- 2 files changed, 30 insertions(+), 80 deletions(-) diff --git a/lib/list_sort.c b/lib/list_sort.c index 0fb59e92ca2d..9a2745a1a44b 100644 --- a/lib/list_sort.c +++ b/lib/list_sort.c @@ -16,28 +16,15 @@ __attribute__((nonnull(2,3,4))) static struct list_head *merge(void *priv, list_cmp_func_t cmp, struct list_head *a, struct list_head *b) { - struct list_head *head, **tail =3D &head; + struct list_head *head, **tail =3D &head, **node; =20 - for (;;) { + do { /* if equal, take 'a' -- important for sort stability */ - if (cmp(priv, a, b) <=3D 0) { - *tail =3D a; - tail =3D &a->next; - a =3D a->next; - if (!a) { - *tail =3D b; - break; - } - } else { - *tail =3D b; - tail =3D &b->next; - b =3D b->next; - if (!b) { - *tail =3D a; - break; - } - } - } + node =3D cmp(priv, a, b) <=3D 0 ? &a : &b; + *tail =3D *node; + tail =3D &(*node)->next; + } while ((*node =3D (*node)->next)); + *tail =3D (struct list_head *) ((uintptr_t) a | (uintptr_t) b); return head; } =20 @@ -52,29 +39,17 @@ __attribute__((nonnull(2,3,4,5))) static void merge_final(void *priv, list_cmp_func_t cmp, struct list_head = *head, struct list_head *a, struct list_head *b) { - struct list_head *tail =3D head; + struct list_head *tail =3D head, **node; u8 count =3D 0; =20 - for (;;) { + do { /* if equal, take 'a' -- important for sort stability */ - if (cmp(priv, a, b) <=3D 0) { - tail->next =3D a; - a->prev =3D tail; - tail =3D a; - a =3D a->next; - if (!a) - break; - } else { - tail->next =3D b; - b->prev =3D tail; - tail =3D b; - b =3D b->next; - if (!b) { - b =3D a; - break; - } - } - } + node =3D cmp(priv, a, b) <=3D 0 ? &a : &b; + tail->next =3D *node; + (*node)->prev =3D tail; + tail =3D *node; + } while ((*node =3D (*node)->next)); + b =3D (struct list_head *) ((uintptr_t) a | (uintptr_t) b); =20 /* Finish linking remainder of list b on to tail */ tail->next =3D b; diff --git a/tools/lib/list_sort.c b/tools/lib/list_sort.c index 10c067e3a8d2..5054b2196981 100644 --- a/tools/lib/list_sort.c +++ b/tools/lib/list_sort.c @@ -15,28 +15,15 @@ __attribute__((nonnull(2,3,4))) static struct list_head *merge(void *priv, list_cmp_func_t cmp, struct list_head *a, struct list_head *b) { - struct list_head *head, **tail =3D &head; + struct list_head *head, **tail =3D &head, **node; =20 - for (;;) { + do { /* if equal, take 'a' -- important for sort stability */ - if (cmp(priv, a, b) <=3D 0) { - *tail =3D a; - tail =3D &a->next; - a =3D a->next; - if (!a) { - *tail =3D b; - break; - } - } else { - *tail =3D b; - tail =3D &b->next; - b =3D b->next; - if (!b) { - *tail =3D a; - break; - } - } - } + node =3D cmp(priv, a, b) <=3D 0 ? &a : &b; + *tail =3D *node; + tail =3D &(*node)->next; + } while ((*node =3D (*node)->next)); + *tail =3D (struct list_head *) ((uintptr_t) a | (uintptr_t) b); return head; } =20 @@ -51,29 +38,17 @@ __attribute__((nonnull(2,3,4,5))) static void merge_final(void *priv, list_cmp_func_t cmp, struct list_head = *head, struct list_head *a, struct list_head *b) { - struct list_head *tail =3D head; + struct list_head *tail =3D head, **node; u8 count =3D 0; =20 - for (;;) { + do { /* if equal, take 'a' -- important for sort stability */ - if (cmp(priv, a, b) <=3D 0) { - tail->next =3D a; - a->prev =3D tail; - tail =3D a; - a =3D a->next; - if (!a) - break; - } else { - tail->next =3D b; - b->prev =3D tail; - tail =3D b; - b =3D b->next; - if (!b) { - b =3D a; - break; - } - } - } + node =3D cmp(priv, a, b) <=3D 0 ? &a : &b; + tail->next =3D *node; + (*node)->prev =3D tail; + tail =3D *node; + } while ((*node =3D (*node)->next)); + b =3D (struct list_head *) ((uintptr_t) a | (uintptr_t) b); =20 /* Finish linking remainder of list b on to tail */ tail->next =3D b; base-commit: 65aca32efdcb0965502d3db2f1fa33838c070952 --=20 2.34.1