From patchwork Tue Dec 5 03:22:06 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: 81327 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 AE6203884F4C for ; Tue, 5 Dec 2023 03:22:47 +0000 (GMT) X-Original-To: libc-alpha@sourceware.org Delivered-To: libc-alpha@sourceware.org Received: from mail-pg1-x529.google.com (mail-pg1-x529.google.com [IPv6:2607:f8b0:4864:20::529]) by sourceware.org (Postfix) with ESMTPS id 5851C385B524 for ; Tue, 5 Dec 2023 03:22:20 +0000 (GMT) DMARC-Filter: OpenDMARC Filter v1.4.2 sourceware.org 5851C385B524 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 5851C385B524 Authentication-Results: server2.sourceware.org; arc=none smtp.remote-ip=2607:f8b0:4864:20::529 ARC-Seal: i=1; a=rsa-sha256; d=sourceware.org; s=key; t=1701746550; cv=none; b=TH86oHMk2LPfpLOg4MAE06xoY5XphsNAdAS8+o975jao9IYiBurMElcKW6Ry3CI6KggvR9PL/ktqHfqwjaZS1zw29B2iJ/1Wgh7EINZNCW8HXvLO/yPr3OtuAQTcD+fpsD2aFk0HJJACLq/PDhl7nbptfjdxOjfoTw/YIR0FwO4= ARC-Message-Signature: i=1; a=rsa-sha256; d=sourceware.org; s=key; t=1701746550; c=relaxed/simple; bh=I0Ix89+rQdaouz7BfcFRKyyncYkQ+Qs0j8jFGiwpVww=; h=DKIM-Signature:From:To:Subject:Date:Message-Id:MIME-Version; b=Og5mlG0c9cttikJWtDexCwuugzV8lEb7m28M7wsIw0X1w35yx1ZzyfdU/sXKGD5A6+kVbU5OllEdM81kmsoCt9SWCL6aYUnXE4dljMxTpQfd+gcM36l6R8xBQ38kZ/3y3gJk/WZAUIizxODsq9YuhjApdXPXgndS1sVz9U9P2Xw= ARC-Authentication-Results: i=1; server2.sourceware.org Received: by mail-pg1-x529.google.com with SMTP id 41be03b00d2f7-5c6910e93e3so169052a12.1 for ; Mon, 04 Dec 2023 19:22:20 -0800 (PST) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20230601; t=1701746539; x=1702351339; darn=sourceware.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=j0W/QkWsX7n38uv64wY4VA+0rKNJ08bFArPdvH+TMbQ=; b=ZMu5QxwbTFEE7hL3He0DnYRBlSVnLkMrusAZU0LH3HKuwCW+AKtmDKBtz/r0DMysWY 7pOVoNp0EGfC1Fx3kCNmNCjDXBEZZr5cnLbd2fIac8z0PQshE1unH9cZ6t8ymPQ9aaEy Q4z38y63ytk6KNRTKbyRtRCLtf/hAoT55z46Guf+vSpxY/LJLHmhPsW0p0U/PaV1lNxA b/bFLkG2GAn366jp/nS41ECWRTkfTUcU4HEEB3NduSeuogVII2Xe3UmLx1fBnZRXOSKS zAJ1eWOvLW6aFXcglWsOOqXpy0iDHQVlI/z5u/GsxOpukNrhn5v4LsBRzWVIAyrV9HMD SIlw== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20230601; t=1701746539; x=1702351339; 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=j0W/QkWsX7n38uv64wY4VA+0rKNJ08bFArPdvH+TMbQ=; b=SMRkbkO0lM0t8b4FtxplvF4RqpAcwRoD0dnQYPy6YdO8kPwheWd5du2eg+jDqYR9TJ /DcrqeWwQe0k52C+WZ07u6hovDho4t3WOD4lAZq3hwUW8SdfpvZixsd0bOlVdqc8nH89 hKYo7803UswWVlE7yMKwysAEtO/VZHc8JQHaWd5mcxFRvzMO+kVcKQ/Q5zAboEwQBbCN sbQj0FtD9LooQ6OFPiL32Vg83QnSXjstj2tuUWHjhXCw4x+vuh+UwTd/53ZG3CtZyoeV zFpQ2HH0fKoML0gKwZeAo3jXuDfixH+4XdGreuCpz056v+UuhAOmDlaag65pJy3hs3V2 hjJQ== X-Gm-Message-State: AOJu0Yx55wL0JbjzydRsN5AuXSkao6lunSzFbgqxS8w1xVWN9V59nxRf poROGucFhIQYG2kSeJl90N0= X-Google-Smtp-Source: AGHT+IEMyo+JKN4Bws9gLXAeLMRD5GkkNHbNaQlSQ8C/o0E4/HfrRqW43vu0v0+NK/lJTZWiwur7pw== X-Received: by 2002:a05:6a00:939f:b0:6ce:6052:17d1 with SMTP id ka31-20020a056a00939f00b006ce605217d1mr3169235pfb.0.1701746538936; Mon, 04 Dec 2023 19:22:18 -0800 (PST) Received: from localhost.localdomain ([140.116.154.65]) by smtp.gmail.com with ESMTPSA id fn9-20020a056a002fc900b006ce41b15613sm4574pfb.112.2023.12.04.19.22.17 (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256); Mon, 04 Dec 2023 19:22:18 -0800 (PST) From: Kuan-Wei Chiu To: fweimer@redhat.com Cc: libc-alpha@sourceware.org, adhemerval.zanella@linaro.org, goldstein.w.n@gmail.com, Kuan-Wei Chiu Subject: [PATCH v2 1/2] stdlib: Optimize number of calls to comparison function in qsort Date: Tue, 5 Dec 2023 11:22:06 +0800 Message-Id: <20231205032207.3183789-2-visitorckw@gmail.com> X-Mailer: git-send-email 2.25.1 In-Reply-To: <20231205032207.3183789-1-visitorckw@gmail.com> References: <87y1eaxtst.fsf@oldenburg.str.redhat.com> <20231205032207.3183789-1-visitorckw@gmail.com> MIME-Version: 1.0 X-Spam-Status: No, score=-11.3 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 --- Changes from v1: * Use a more concise title. * Correct the error in asymptotic notation from little-o to big-O. stdlib/qsort.c | 36 ++++++++++++++++++------------------ 1 file changed, 18 insertions(+), 18 deletions(-) diff --git a/stdlib/qsort.c b/stdlib/qsort.c index 62477010b6..0d924f5e2d 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); } } From patchwork Tue Dec 5 03:22:07 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: 81328 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 46F59388A024 for ; Tue, 5 Dec 2023 03:23:06 +0000 (GMT) X-Original-To: libc-alpha@sourceware.org Delivered-To: libc-alpha@sourceware.org Received: from mail-pf1-x433.google.com (mail-pf1-x433.google.com [IPv6:2607:f8b0:4864:20::433]) by sourceware.org (Postfix) with ESMTPS id 81F60386184A for ; Tue, 5 Dec 2023 03:22:24 +0000 (GMT) DMARC-Filter: OpenDMARC Filter v1.4.2 sourceware.org 81F60386184A 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 81F60386184A Authentication-Results: server2.sourceware.org; arc=none smtp.remote-ip=2607:f8b0:4864:20::433 ARC-Seal: i=1; a=rsa-sha256; d=sourceware.org; s=key; t=1701746554; cv=none; b=Hi4An0tMaafnJ4A8yha2KiSqdQ3SIJjB+Db4WW+ZLpdd752ygR/q2PnxVxgRNqd0Gr5anpCTNUq8Um1wCtX1ihxgrjYim86GjbNju4oyETHnpRrOrc71DHOqozoYzi6MO1BD3XJirezcrpqVog/wKazNojV1VWcO2UTMOxdzFtc= ARC-Message-Signature: i=1; a=rsa-sha256; d=sourceware.org; s=key; t=1701746554; c=relaxed/simple; bh=POg9OKPk1qeemwM/PcxKwu7LBEnOKSUYsoURiGWh18o=; h=DKIM-Signature:From:To:Subject:Date:Message-Id:MIME-Version; b=QXj5xSKRK0f/yU2h/hGcItSvsvGf79KA1fSzTrfTSHQGwdUBuSeOrYPKucJoyfWV8gzlGJ0X8D/su0E/YsVvQWKfCXqWJ0QaxhQGpKIKMmLlhgwAeWX0esCyGxhtOsRAhxDb/AM420VPSUr7fCP9E69MXcrqe083OQCaRzJn3go= ARC-Authentication-Results: i=1; server2.sourceware.org Received: by mail-pf1-x433.google.com with SMTP id d2e1a72fcca58-6ce40061e99so317761b3a.0 for ; Mon, 04 Dec 2023 19:22:24 -0800 (PST) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20230601; t=1701746543; x=1702351343; darn=sourceware.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=u5aepBfYde+xMeGIqmX1LMeLYJ6oslEjXVdG9W3Y0pk=; b=gafwAQYuuS24QuTWkLilucO4TFTeKBAMnPFcSfKvWqte3a0Z03u4YGI0wGH2qgrSRU cJ7/sNRQqlSd1WN9N5k5HNn3l32c/fwLipE/IZaG7nJgfDo6MdgjpIyjywG5bziVeQGo WZXBblC0DkANX4VQl6BfdOJTnpcNL2SVXfFoPgj84qwExQMwMZVJy6/FwlJcHFuY8lXv IiRYwtoKUGr6CIOGAXv0GS1lTGRAG27SdZUA8+kHwDZM7Gn2HfpRybQ2nWltJvDFbvSd Jmm0qumkXG63EnQUUx/VE5FpMj5jslwNShFRyraNES9sWohCfsEUY26YFVx2qMykEWIY 0K9Q== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20230601; t=1701746543; x=1702351343; 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=u5aepBfYde+xMeGIqmX1LMeLYJ6oslEjXVdG9W3Y0pk=; b=ZfVEYMz85HPBv/XFLtVARvRZuWZUQNBsCGJXZvmbaNYw3G4bPHOnR3jSBrNNu2wvEw 9ExSt2z2CL/VbNN7gg3ARlfC1KawZg3t4Jq84tRGklsWUg/1mInZTYf/8JtJN8A0Os9y GdLF3U0UYx3eqR4gPDej8wrWyEk4iSKL5AWvlmIgYUPH9SrWAuZNQp0GYgmyy1idShNx 8HgEFlSUhzO3z5HTnM8ZwLIJfS3FUgKwDYf9LiF0epxWBpTFaSd2rJ47PvT9+mplNSQ0 KPZ5tA93VIO9xaFJKvcmH02RU88yBkn0XF9BFYH1xJlePgVyGkfaJUPd03SL0uQuOP6f SUKg== X-Gm-Message-State: AOJu0YwR3UHanUp/y6Q3Di9zKzO6OvHkfJsk3qmAGatiQTfIPAOuya44 +bWQLTHwOMOmCyzPp7jzHseQdIvdWPA= X-Google-Smtp-Source: AGHT+IFn+CVwXN4IuGNwFV4KewfQW9TZnu90Lv8isbtP2BPiqjuYvNUfInkm+WzEPHsznb1K/O56jw== X-Received: by 2002:a62:844e:0:b0:6ce:720e:23e with SMTP id k75-20020a62844e000000b006ce720e023emr87289pfd.1.1701746543026; Mon, 04 Dec 2023 19:22:23 -0800 (PST) Received: from localhost.localdomain ([140.116.154.65]) by smtp.gmail.com with ESMTPSA id fn9-20020a056a002fc900b006ce41b15613sm4574pfb.112.2023.12.04.19.22.21 (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256); Mon, 04 Dec 2023 19:22:22 -0800 (PST) From: Kuan-Wei Chiu To: fweimer@redhat.com Cc: libc-alpha@sourceware.org, adhemerval.zanella@linaro.org, goldstein.w.n@gmail.com, Kuan-Wei Chiu Subject: [PATCH v2 2/2] stdlib: Adjust the factor in tst-qsort5 Date: Tue, 5 Dec 2023 11:22:07 +0800 Message-Id: <20231205032207.3183789-3-visitorckw@gmail.com> X-Mailer: git-send-email 2.25.1 In-Reply-To: <20231205032207.3183789-1-visitorckw@gmail.com> References: <87y1eaxtst.fsf@oldenburg.str.redhat.com> <20231205032207.3183789-1-visitorckw@gmail.com> MIME-Version: 1.0 X-Spam-Status: No, score=-11.2 required=5.0 tests=BAYES_00, DKIM_SIGNED, DKIM_VALID, DKIM_VALID_AU, DKIM_VALID_EF, FREEMAIL_FROM, GIT_PATCH_0, KAM_NUMSUBJECT, 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 Adjust the factor in the tst-qsort5 from 4.5 to 3.5 to better align with the current implementation characteristics. This refinement is prompted by the adoption of the bottom-up heapsort optimization, as it significantly reduces the required comparisons. Signed-off-by: Kuan-Wei Chiu --- Changes from v1: * Adjusted the factor in tst-qsort5 from 4.5 to 3.5. stdlib/tst-qsort5.c | 2 +- 1 file changed, 1 insertion(+), 1 deletion(-) diff --git a/stdlib/tst-qsort5.c b/stdlib/tst-qsort5.c index d3a88c30f8..63590967a6 100644 --- a/stdlib/tst-qsort5.c +++ b/stdlib/tst-qsort5.c @@ -155,7 +155,7 @@ check_one_n (size_t n) n, count, factor); /* This is an arbitrary factor which is true for the current implementation across a wide range of sizes. */ - TEST_VERIFY (factor <= 4.5); + TEST_VERIFY (factor <= 3.5); } static int