From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: 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 9CBA03858D34 for ; Wed, 27 Mar 2024 19:45:40 +0000 (GMT) DMARC-Filter: OpenDMARC Filter v1.4.2 sourceware.org 9CBA03858D34 Authentication-Results: sourceware.org; dmarc=pass (p=none dis=none) header.from=linaro.org Authentication-Results: sourceware.org; spf=pass smtp.mailfrom=linaro.org ARC-Filter: OpenARC Filter v1.0.0 sourceware.org 9CBA03858D34 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=1711568742; cv=none; b=ARtj/uVOR/iB5zWhvDQNGKuygieqnStDMW+4MF/hoUNMxH6NunaBEwt1Tc0AtsFobEGePdK6QKhcB1tp+b1eAU3PIaRpGrZZDC46NwhwZ4HbLYaOHuw02dovb4nHPPzubxy8nYvKuJRkZ924WSFW+JhRyn1Dgux2TnJ/xXoh3zY= ARC-Message-Signature: i=1; a=rsa-sha256; d=sourceware.org; s=key; t=1711568742; c=relaxed/simple; bh=HJblkq9GJWHCwfWiCqkVpUd2bIxWM4hPGdC/hfn+190=; h=DKIM-Signature:Message-ID:Date:MIME-Version:Subject:To:From; b=ReLjFujLoVuopjqJDvtsKOOT8iTXpmO7vd5reb1lmI+SpvUb1xPjOoNMpspndPd6aqXoXQwC27+lQ/u4w/2j9pjbOm7rIYXm9DQj4FIv/VhettXvUODXLflsLwHlwASNhkL2eMbiOzZcwMXO3V9fhi9RVxTDRkBn0JedngJUmpQ= ARC-Authentication-Results: i=1; server2.sourceware.org Received: by mail-pg1-x529.google.com with SMTP id 41be03b00d2f7-5dcc4076c13so180079a12.0 for ; Wed, 27 Mar 2024 12:45:40 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=linaro.org; s=google; t=1711568740; x=1712173540; darn=sourceware.org; h=content-transfer-encoding:in-reply-to:organization:from :content-language:references:cc:to:subject:user-agent:mime-version :date:message-id:from:to:cc:subject:date:message-id:reply-to; bh=Pv1OuMloAyfAbQ8Np75SCRRJGnOuLdRvpHHY7toS51o=; b=wcJJVFfJ9Upor8yVHmlhCPJAYeFpPqHDUBUGWk1V7EP9s/vENTi0uI56rWn2cCpEnN bd0UgLyoADXg9d9cqKeLohhA+EiW+cHT8h02dcGPGCZ6hFHNy8gmcRnR9y9utp1yHCLJ OJsxEGT7NT+hrmyRbD24OIx6WrS4IFy4SPOZJKvd36WUeUsgvbRZW9Dv+9qNtLcDYtrC 7OKzl2E5sTxYyx06UH3S53PncsRBvsORO2RTHW+bHRLSsWNze6AdWQXlrOEv7gPyCUJX VZ1bv7lj9bbkUIJ2ICP4++abz0F/X4L+mwNsR1/0x+Hj7FLCeoqvwAHGKLG7Pqw1EbIB iK7w== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20230601; t=1711568740; x=1712173540; h=content-transfer-encoding:in-reply-to:organization:from :content-language:references:cc:to:subject:user-agent:mime-version :date:message-id:x-gm-message-state:from:to:cc:subject:date :message-id:reply-to; bh=Pv1OuMloAyfAbQ8Np75SCRRJGnOuLdRvpHHY7toS51o=; b=JQcU2OBibYovQPXRd4+D9ks+OTBYMsNwSwINPpA4qCcfTS/w10lFlkSy/nyuAXcAXs HWl4Z76CnGC+N6J1tm0VjSWIJiZUC4za9uADXNCLBhwJXvVzBsLM1nb8zc0+BDOm/C0J +i5fUQEED+83TOPyCegeAbqIM0PX3sCyFXsCxI8o7iUFtDnJTYrqyxzwGK0v4zupiowj 81bMHBxKn/VO9Nuge8zo95GKbjU3hEjeXFXv8BP6vby1ZMR62U9Q2MFS86SejPYxQSPb 2DFAaJjhCDt1scCNxnAPIaj1mulyq3Ul7aBDrDSR+PTJZkbdFqcMOU1+Sc/ZbolKBOII 5i3Q== X-Forwarded-Encrypted: i=1; AJvYcCV/lJ0kS8tNUS3SECkmfDsTYkvHt8Yj4ScM90VjZhYxOiJNcYFugQ0BSkLnxyrWhhgaDgDqbhEZeaiI49di7k1a1lIYuh5ByTTA X-Gm-Message-State: AOJu0YwnVy0l7RQ+3/Y4f12cSB39wJClTfWl9cRcdJ8zBbaUHjnlVqMd dlqjpu0Gdmrx6iv/CT37fC4aop5gSAmRF/OE3LqkIJHFMAufh+fa3NtRZhlU5Bc= X-Google-Smtp-Source: AGHT+IHh1oyDBa/V9l0xtM41KZujmJvgsSlDMEtzM2A/RAHRwksTFuceJJK3DFphON0kAKLTn7BKEg== X-Received: by 2002:a17:90b:b12:b0:2a1:fbdd:421d with SMTP id bf18-20020a17090b0b1200b002a1fbdd421dmr327352pjb.11.1711568739677; Wed, 27 Mar 2024 12:45:39 -0700 (PDT) Received: from [192.168.15.31] ([187.56.129.71]) by smtp.gmail.com with ESMTPSA id f17-20020a17090ace1100b0029fff4ff6c3sm2126741pju.41.2024.03.27.12.45.36 (version=TLS1_3 cipher=TLS_AES_128_GCM_SHA256 bits=128/128); Wed, 27 Mar 2024 12:45:38 -0700 (PDT) Message-ID: Date: Wed, 27 Mar 2024 16:45:35 -0300 MIME-Version: 1.0 User-Agent: Mozilla Thunderbird Subject: Re: [PATCH] stdlib: Optimize number of calls to comparison function To: Kuan-Wei Chiu , libc-alpha@sourceware.org Cc: goldstein.w.n@gmail.com, fweimer@redhat.com, zack@owlfolio.org References: <20231202214839.2634493-1-visitorckw@gmail.com> <20240216070835.GA1028715@sivslab-System-Product-Name> Content-Language: en-US From: Adhemerval Zanella Netto Organization: Linaro In-Reply-To: <20240216070835.GA1028715@sivslab-System-Product-Name> Content-Type: text/plain; charset=UTF-8 Content-Transfer-Encoding: 7bit X-Spam-Status: No, score=-10.8 required=5.0 tests=BAYES_00,DKIM_SIGNED,DKIM_VALID,DKIM_VALID_AU,DKIM_VALID_EF,GIT_PATCH_0,KAM_SHORT,RCVD_IN_BARRACUDACENTRAL,RCVD_IN_DNSWL_NONE,SPF_HELO_NONE,SPF_PASS,TXREP autolearn=ham autolearn_force=no version=3.4.6 X-Spam-Checker-Version: SpamAssassin 3.4.6 (2021-04-09) on server2.sourceware.org List-Id: On 16/02/24 04:08, Kuan-Wei Chiu wrote: > On Sun, Dec 03, 2023 at 05:48:39AM +0800, Kuan-Wei Chiu wrote: >> 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); >> } >> } >> >> -- >> 2.25.1 >> > > Since we still retain heapsort as a fallback for mergesort, should we > reconsider applying this patch? > > Thanks, > Kuan-Wei Yes, I think it is work and it looks great to me.