From patchwork Sat Dec 2 21:48:39 2023 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Kuan-Wei Chiu X-Patchwork-Id: 81209 Return-Path: X-Original-To: patchwork@sourceware.org Delivered-To: patchwork@sourceware.org Received: from server2.sourceware.org (localhost [IPv6:::1]) by sourceware.org (Postfix) with ESMTP id EE24738582BE for ; Sat, 2 Dec 2023 21:49:02 +0000 (GMT) X-Original-To: libc-alpha@sourceware.org Delivered-To: libc-alpha@sourceware.org Received: from mail-pl1-x633.google.com (mail-pl1-x633.google.com [IPv6:2607:f8b0:4864:20::633]) by sourceware.org (Postfix) with ESMTPS id 0564D3858D33 for ; Sat, 2 Dec 2023 21:48:49 +0000 (GMT) DMARC-Filter: OpenDMARC Filter v1.4.2 sourceware.org 0564D3858D33 Authentication-Results: sourceware.org; dmarc=pass (p=none dis=none) header.from=gmail.com Authentication-Results: sourceware.org; spf=pass smtp.mailfrom=gmail.com ARC-Filter: OpenARC Filter v1.0.0 sourceware.org 0564D3858D33 Authentication-Results: server2.sourceware.org; arc=none smtp.remote-ip=2607:f8b0:4864:20::633 ARC-Seal: i=1; a=rsa-sha256; d=sourceware.org; s=key; t=1701553730; cv=none; b=CEuSuSd3ZdSg+Aktd6zBd13Hh2VJ0CMU+ndQctkRxfKNb7f/xS36WmHNpS5wKS+phX5uT+YVGgVfaXt0m4mddar6sQiOnzwZUBPQvDiSXCXt3GWbntiS+TV9aHJ3ssa/MYwCWZTx7HhrOsbI6wuti9Ic5FYRmmNEDYsiVZMVHp0= ARC-Message-Signature: i=1; a=rsa-sha256; d=sourceware.org; s=key; t=1701553730; c=relaxed/simple; bh=E97r2H9w0YEH/+SWnJUGk7i3s4cfTHk7FndCj64sr7U=; h=DKIM-Signature:From:To:Subject:Date:Message-Id:MIME-Version; b=futlSQD/8ja+f8fVHcLRUmFPuBjkRLniyu/huLTLxaqf9fzCqqJ0f1axi1kZL8fvAxCiNzzolco45+rxZ/M7w2aJJ+CMnvof/IpVNyMrgBMKbLKt/DldZi3D2kdKt9Rq6dj6xIsytGMlnf0mwScCiPa9/A26jtuDee73bwOwfO0= ARC-Authentication-Results: i=1; server2.sourceware.org Received: by mail-pl1-x633.google.com with SMTP id d9443c01a7336-1d03f03cda9so4984205ad.0 for ; Sat, 02 Dec 2023 13:48:48 -0800 (PST) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20230601; t=1701553727; x=1702158527; darn=sourceware.org; h=content-transfer-encoding:mime-version:message-id:date:subject:cc :to:from:from:to:cc:subject:date:message-id:reply-to; bh=OXsgQ1uPn20Hnj5IoIPAM62Gt6IOYbPV7QdhyE/h9Ng=; b=k/3gsc9Ug3nigDZr9TljEQKWrvPY/MlDpMAFsi17LESKsW2i9+45eW70Eg4V90Yg93 5Ck2Q0RC+F12RcQ62ptlDQNxSxcfaV7ajpMYUZEcD+tHoTqGgo95+g8+AWpIWQQTB6Ey 83Q48Jp5acff2YplbQy5f9TXtLcr5IZY5mrGN/owy4HIWn5zufTIAKedtvHawi9PewAA nUZDoL3hEW3oa1gvcmNsAWje8iSTB0lfuLTxnHRn8+Hk8ar4LXteuqFuJjBRgjRuD5pG sLH2ZEBLnedDnmeY0EOIzMctYY/iXqtaonDQq/rPd0GfoUPptJ88ShO16keUiBLH+2zz K6FQ== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20230601; t=1701553727; x=1702158527; h=content-transfer-encoding:mime-version:message-id:date:subject:cc :to:from:x-gm-message-state:from:to:cc:subject:date:message-id :reply-to; bh=OXsgQ1uPn20Hnj5IoIPAM62Gt6IOYbPV7QdhyE/h9Ng=; b=ONsSV62ndYM2MGDKBzax43L7nhamaePv18DI86Gu0w5fuNUK5M3NCLBWLPJ6ZxsW2i Ppf7JPa3Lur53FrcTzqWtHwG9PIXN4lE/PYl89kV69lU4dU1KmbASDMaLW31wW8ZVq8Z 8oDDb6L4QAMbVjemn/ZXgqkhiRdlgNylnXLcqksMxx16ZDEf4FQD5Zn5N5CkF8A5qfXS 2Bba7EAsIzDBlAbwbgVTsYbzOQ8zBhWswPRR89J1vpycHX+atKB0cgnPUKFbd37iUwXE WGepihrSYDJdrGmORgkdEZQI+c6j+du6uyE6cSKwAsf/Iwzefl3RlVzsvlOnTfmCz9sI xeMA== X-Gm-Message-State: AOJu0YzmQxKguD+C5nUzDeD1SNtzNpwS4f25bnE7vIfS0X0B63epw5P3 khLtpLat3KNQY27DhoQdO5VbBcPlfWQ= X-Google-Smtp-Source: AGHT+IFkR+R2oGD1KWpN7ulh/GrllYg6QnoHcW9+SYViEw+XL+3ClXRFRdFqEhd+73qBfilw79YY3g== X-Received: by 2002:a17:902:cec9:b0:1cf:cbf4:6f7c with SMTP id d9-20020a170902cec900b001cfcbf46f7cmr9448502plg.6.1701553726958; Sat, 02 Dec 2023 13:48:46 -0800 (PST) Received: from localhost.localdomain ([140.116.154.65]) by smtp.gmail.com with ESMTPSA id s6-20020a170902a50600b001d08e080042sm34508plq.43.2023.12.02.13.48.45 (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256); Sat, 02 Dec 2023 13:48:46 -0800 (PST) From: Kuan-Wei Chiu To: libc-alpha@sourceware.org Cc: adhemerval.zanella@linaro.org, goldstein.w.n@gmail.com, Kuan-Wei Chiu Subject: [PATCH] stdlib: Optimize number of calls to comparison function Date: Sun, 3 Dec 2023 05:48:39 +0800 Message-Id: <20231202214839.2634493-1-visitorckw@gmail.com> X-Mailer: git-send-email 2.25.1 MIME-Version: 1.0 X-Spam-Status: No, score=-12.1 required=5.0 tests=BAYES_00, DKIM_SIGNED, DKIM_VALID, DKIM_VALID_AU, DKIM_VALID_EF, FREEMAIL_FROM, GIT_PATCH_0, KAM_SHORT, RCVD_IN_DNSWL_NONE, SPF_HELO_NONE, SPF_PASS, TXREP, T_SCC_BODY_TEXT_LINE autolearn=ham autolearn_force=no version=3.4.6 X-Spam-Checker-Version: SpamAssassin 3.4.6 (2021-04-09) on server2.sourceware.org X-BeenThere: libc-alpha@sourceware.org X-Mailman-Version: 2.1.30 Precedence: list List-Id: Libc-alpha mailing list List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , Errors-To: libc-alpha-bounces+patchwork=sourceware.org@sourceware.org The current heapsort implementation in the siftdown function follows the standard textbook version, necessitating two comparisons at each level. Transitioning to the Bottom-up heapsort version allows us to decrease the required comparisons to just one per level. On average, this modification significantly reduces the comparison count from 2nlog2(n) - 3n + o(n) to nlog2(n) + 0.37*n + o(n). Refs: BOTTOM-UP-HEAPSORT, a new variant of HEAPSORT beating, on an average, QUICKSORT (if n is not very small) Ingo Wegener Theoretical Computer Science, 118(1); Pages 81-98, 13 September 1993 https://doi.org/10.1016/0304-3975(93)90364-Y Signed-off-by: Kuan-Wei Chiu --- stdlib/qsort.c | 36 ++++++++++++++++++------------------ 1 file changed, 18 insertions(+), 18 deletions(-) diff --git a/stdlib/qsort.c b/stdlib/qsort.c index be01fb5598..f5babef150 100644 --- a/stdlib/qsort.c +++ b/stdlib/qsort.c @@ -132,26 +132,26 @@ static inline void siftdown (void *base, size_t size, size_t k, size_t n, enum swap_type_t swap_type, __compar_d_fn_t cmp, void *arg) { - /* There can only be a heap condition violation if there are - children. */ - while (2 * k + 1 <= n) - { - /* Left child. */ - size_t j = 2 * k + 1; - /* If the right child is larger, use it. */ - if (j < n && cmp (base + (j * size), base + ((j + 1) * size), arg) < 0) - j++; - - /* If k is already >= to its children, we are done. */ - if (j == k || cmp (base + (k * size), base + (j * size), arg) >= 0) - break; + size_t i, j; + + /* Find the sift-down path all the way to the leaves. */ + for (i = k; j = 2 * i + 1, j + 1 <= n;) + i = cmp (base + j * size, base + (j + 1) * size, arg) >= 0 ? j : (j + 1); - /* Heal the violation. */ - do_swap (base + (size * j), base + (k * size), size, swap_type); + /* Special case for the last leaf with no sibling. */ + if (j == n) + i = j; - /* Swapping with j may have introduced a violation at j. Fix - it in the next loop iteration. */ - k = j; + /* Backtrack to the correct location. */ + while (i != k && cmp (base + k * size, base + i * size, arg) > 0) + i = (i - 1) / 2; + + /* Shift the element into its correct place. */ + j = i; + while (i != k) + { + i = (i - 1) / 2; + do_swap (base + i * size, base + j * size, size, swap_type); } }