From patchwork Tue Dec 5 03:22:05 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: 56454 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 1D422382EF0C for ; Tue, 5 Dec 2023 03:22:43 +0000 (GMT) X-Original-To: libc-alpha@sourceware.org Delivered-To: libc-alpha@sourceware.org Received: from mail-pf1-x431.google.com (mail-pf1-x431.google.com [IPv6:2607:f8b0:4864:20::431]) by sourceware.org (Postfix) with ESMTPS id A749A3858424 for ; Tue, 5 Dec 2023 03:22:14 +0000 (GMT) DMARC-Filter: OpenDMARC Filter v1.4.2 sourceware.org A749A3858424 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 A749A3858424 Authentication-Results: server2.sourceware.org; arc=none smtp.remote-ip=2607:f8b0:4864:20::431 ARC-Seal: i=1; a=rsa-sha256; d=sourceware.org; s=key; t=1701746546; cv=none; b=EG96XSwKupfu3z0+zePfIlGE+lYRjYvIM5ShhTnEmzeTvk+SLgfdTBm0FTqB1Fge+VsFqOYWfmjp0mM694/7rO1F9odk4yWqWlw0gRZJkMUojxWSfiqd6cOg8qFLgHFQbgFV3nxtHpiUeyuT1mSRcCWb4KVRyHJNKiisVm0PeTU= ARC-Message-Signature: i=1; a=rsa-sha256; d=sourceware.org; s=key; t=1701746546; c=relaxed/simple; bh=4urSbtgjd9K9vYuvAWnGEwWIFJDqOjhXWabcr7mgt6A=; h=DKIM-Signature:From:To:Subject:Date:Message-Id:MIME-Version; b=m0x0sSlCNBpgTcm4I7DCw3JujMP7ihhZp59xqPEAItKujTOCoMR4POycAbZrV32sCFydPXQ4xw6lu9VToIu6eSNSIgCT6M3aR8J+b4CxEmrKdFpk9mOD6LqmjrLubfhy4cOKP/lKCxC1tN9euEkOB2hNnV246IsFvNMqp2nUzic= ARC-Authentication-Results: i=1; server2.sourceware.org Received: by mail-pf1-x431.google.com with SMTP id d2e1a72fcca58-6ce40061e99so317739b3a.0 for ; Mon, 04 Dec 2023 19:22:14 -0800 (PST) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20230601; t=1701746533; x=1702351333; 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=lKT6+Q5z3BRguXpCicsAZskWPw+bFIIX9JOE3jgPy+Y=; b=hh8AY0qneNnUXIvVCSfDQxgIvBiK17MiJWKC9azDh/d52fmfDw9fwLZRZW7rAumAXk N6delVkc1WkgIxr8fXlV9V6soJaguueFxMy9yR/LV8/e/gwK+DC4PAkvNobiixxupyLw GLjbBw4BzlIftIuxlPc5v34FVd+LtllT6/xavUnkXv0lbpQDa1HBX+ZT2XjwamuLm60l hA08x2FATY2ap++ZhhkEHK5VTPAk5vvoCDzeO/GVXL6RMUdxu6VGxXHDa9eWrpvc3JYx q7iA0rqY9RtvXGy09qJy0mA2W+kvKs/J70Y9Xl55rs6lZouIU5ciLgh713BdPD0RdVfc PBMA== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20230601; t=1701746533; x=1702351333; 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=lKT6+Q5z3BRguXpCicsAZskWPw+bFIIX9JOE3jgPy+Y=; b=sMmyUm+t6kSRhV+jByCF5T0kFuxj6fmmsI06XE2DksU8Zz5nyD6qAg8LMGZrH6VmGS RWVLaepzlgIUso6ZC/ymNHcpw+XzjL2bqiH1GVDeLXq7Z0mPTxVA3D3AI0WvF5ionp5b +9l3rO4YsWfyWJKy0qZiZ3mEULE4gz+Pl7iksRqR2TnCo+VpJT0q4UVRXKLKSMH22ZK+ diKyittjrTzb3pVBoJ3W5we10S4H8X8mnBJdY69x7r0NqhsY8nDCaCi510mCVbGkbRwW LDr3DcjNVaLqlYBYNRNdm2O9KTMHg2Nx/ZzzETGVufDfLiwWPz3/eJxc+RiFLgZmdvu0 lBUg== X-Gm-Message-State: AOJu0YwqRStt5na7R68mpndOPVhv6lV8h/xTcqQXwH62Z2tWHD6eBOKJ POKiufV2wpRGMBrCBG1ehF0= X-Google-Smtp-Source: AGHT+IFnkORs4XkqyoA8fLFqZM0vqfOAQx9SmNmOAo4YxKzvXC2iFrUIErxrLj2CPX35YXoU2rNrjg== X-Received: by 2002:a62:844e:0:b0:6ce:720e:23e with SMTP id k75-20020a62844e000000b006ce720e023emr86972pfd.1.1701746533357; Mon, 04 Dec 2023 19:22:13 -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.11 (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256); Mon, 04 Dec 2023 19:22:12 -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 0/2] stdlib: Optimize number of calls to comparison function in qsort Date: Tue, 5 Dec 2023 11:22:05 +0800 Message-Id: <20231205032207.3183789-1-visitorckw@gmail.com> X-Mailer: git-send-email 2.25.1 In-Reply-To: <87y1eaxtst.fsf@oldenburg.str.redhat.com> References: <87y1eaxtst.fsf@oldenburg.str.redhat.com> MIME-Version: 1.0 X-Spam-Status: No, score=-5.1 required=5.0 tests=BAYES_00, DKIM_SIGNED, DKIM_VALID, DKIM_VALID_AU, DKIM_VALID_EF, FREEMAIL_FROM, 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 Changes from v1: * Use a more concise title. * Correct the error in asymptotic notation from little-o to big-O. * Adjusted the factor in tst-qsort5 from 4.5 to 3.5. Kuan-Wei Chiu (2): stdlib: Optimize number of calls to comparison function in qsort stdlib: Adjust the factor in tst-qsort5 stdlib/qsort.c | 36 ++++++++++++++++++------------------ stdlib/tst-qsort5.c | 2 +- 2 files changed, 19 insertions(+), 19 deletions(-)