From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: from mail-ot1-x331.google.com (mail-ot1-x331.google.com [IPv6:2607:f8b0:4864:20::331]) by sourceware.org (Postfix) with ESMTPS id 6EBDF3858D20 for ; Tue, 29 Aug 2023 13:59:52 +0000 (GMT) DMARC-Filter: OpenDMARC Filter v1.4.2 sourceware.org 6EBDF3858D20 Authentication-Results: sourceware.org; dmarc=pass (p=none dis=none) header.from=linaro.org Authentication-Results: sourceware.org; spf=pass smtp.mailfrom=linaro.org Received: by mail-ot1-x331.google.com with SMTP id 46e09a7af769-6bd0a96e63dso3388613a34.2 for ; Tue, 29 Aug 2023 06:59:52 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=linaro.org; s=google; t=1693317592; x=1693922392; h=content-transfer-encoding:in-reply-to:organization:from:references :cc:to:content-language:subject:user-agent:mime-version:date :message-id:from:to:cc:subject:date:message-id:reply-to; bh=3gJT0ZXbblL2T88Hx1K1D8Inl6JYfAdzIpaz1xhAFN0=; b=cAVrPWPzWKJH0Wy8lMcaoXtM8pgbxo7FMc2x+6OCiHyvX6hCjsTE1WXQ2bcLqu85AZ O3NV8TCbDzl7IfNFTY98ujccUU+nfYb37YaX2MReZzaBgtyNnBbWaD7X53Mf6zREsq3B NbDh8Y/SORi7O/vkTLwbnaZfR2Cba6f8Kzc66nbWoyADJM7Imw4nGvFlRPwOp9riYJAR iZ39qcydUOabISw3SWKgnROb0FqmROKclUF5KM7Jsu9BrjXKRSOIYpH0KnH6QLv7NCFO td5pnQ64q092HarbYqXyW6fmLHzMzO81FmfnYbrqyGT4R+axKIo9xrZl9T6/wPhraNsm 8avA== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20221208; t=1693317592; x=1693922392; h=content-transfer-encoding:in-reply-to:organization:from:references :cc:to:content-language:subject:user-agent:mime-version:date :message-id:x-gm-message-state:from:to:cc:subject:date:message-id :reply-to; bh=3gJT0ZXbblL2T88Hx1K1D8Inl6JYfAdzIpaz1xhAFN0=; b=j+DEKLXmvgN0n3fFeotVeS5YwFNvdusX3beyXxqrHjOLq128A4rWbFVY4EkxuC9XZX udHvvnVOSW0uiAdlgr3rSzeJgJoZyTOaztg9Xbg9AX0n6CuZh69/1XRgxoRpmNNedj1f iceiVl6Zq+MDMXtsMKZPCNMOsDNOV5I5wajsbBxObDH3q2SE3eIAIHYJcCnEgCjR3xus uaK2vEldHEKccBzS4WFzAuXUbUQBkI8EpJ94VxszUBs6WuZVjqxAVUzZ/U7/W13cHHMP Yi4n5KyLB7Z+G0ZqusFsD7zH+dvKm1r1lfRgwnRXgrjv71+V9ZIBRWKJ4zDWuiT21fff Dq7A== X-Gm-Message-State: AOJu0Yzbfmim5s+tBAp1w5hkCITAKg5k8Wxxyuh+Tnf6mFUmPLo698O5 uEfXc+OSZvz/DC5cBx0JZ5qdFp2fQfvtXTEqNY/l0A== X-Google-Smtp-Source: AGHT+IGaEKCeKxZ5LrS5d7s2vxZQG+XNxDb714NSyYasRveE7WIfEGx6PoCWLpIkoqBJitM38weoFA== X-Received: by 2002:a9d:6651:0:b0:6b0:c67c:96f3 with SMTP id q17-20020a9d6651000000b006b0c67c96f3mr15829315otm.18.1693317591752; Tue, 29 Aug 2023 06:59:51 -0700 (PDT) Received: from ?IPV6:2804:1b3:a7c3:578c:599:b56:4f03:5a7f? ([2804:1b3:a7c3:578c:599:b56:4f03:5a7f]) by smtp.gmail.com with ESMTPSA id d5-20020a056830044500b006b89dafb721sm1897106otc.78.2023.08.29.06.59.49 (version=TLS1_3 cipher=TLS_AES_128_GCM_SHA256 bits=128/128); Tue, 29 Aug 2023 06:59:51 -0700 (PDT) Message-ID: <964a9b3f-5088-1713-494d-73eb53428720@linaro.org> Date: Tue, 29 Aug 2023 10:59:47 -0300 MIME-Version: 1.0 User-Agent: Mozilla/5.0 (Macintosh; Intel Mac OS X 10.15; rv:102.0) Gecko/20100101 Thunderbird/102.14.0 Subject: Re: [PATCH v6 2/6] stdlib: Move insertion sort out qsort Content-Language: en-US To: Noah Goldstein Cc: libc-alpha@sourceware.org, Paul Eggert , Alexander Monakov References: <20230718141543.3925254-1-adhemerval.zanella@linaro.org> <20230718141543.3925254-3-adhemerval.zanella@linaro.org> From: Adhemerval Zanella Netto Organization: Linaro In-Reply-To: Content-Type: text/plain; charset=UTF-8 Content-Transfer-Encoding: 8bit X-Spam-Status: No, score=-13.7 required=5.0 tests=BAYES_00,DKIM_SIGNED,DKIM_VALID,DKIM_VALID_AU,DKIM_VALID_EF,GIT_PATCH_0,NICE_REPLY_A,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 29/08/23 04:39, Noah Goldstein wrote: > On Tue, Jul 18, 2023 at 9:17 AM Adhemerval Zanella via Libc-alpha > wrote: >> >> --- >> stdlib/qsort.c | 101 ++++++++++++++++++++++++++----------------------- >> 1 file changed, 54 insertions(+), 47 deletions(-) >> >> diff --git a/stdlib/qsort.c b/stdlib/qsort.c >> index 5bcc287c79..77630951df 100644 >> --- a/stdlib/qsort.c >> +++ b/stdlib/qsort.c >> @@ -156,6 +156,58 @@ typedef struct >> smaller partition. This *guarantees* no more than log (total_elems) >> stack size is needed (actually O(1) in this case)! */ >> > > Imo this comment block should be moved down to just before `qsort`. Ack. >> +static inline void >> +insertion_sort_qsort_partitions (void *const pbase, size_t total_elems, >> + size_t size, enum swap_type_t swap_func, > nit: swap_func -> swap_type/swap_method. Ack. >> + __compar_d_fn_t cmp, void *arg) >> +{ >> + char *base_ptr = (char *) pbase; >> + char *const end_ptr = &base_ptr[size * (total_elems - 1)]; >> + char *tmp_ptr = base_ptr; >> +#define min(x, y) ((x) < (y) ? (x) : (y)) >> + const size_t max_thresh = MAX_THRESH * size; >> + char *thresh = min(end_ptr, base_ptr + max_thresh); >> + char *run_ptr; >> + >> + /* Find smallest element in first threshold and place it at the >> + array's beginning. This is the smallest array element, >> + and the operation speeds up insertion sort's inner loop. */ >> + >> + for (run_ptr = tmp_ptr + size; run_ptr <= thresh; run_ptr += size) >> + if (cmp (run_ptr, tmp_ptr, arg) < 0) >> + tmp_ptr = run_ptr; >> + >> + if (tmp_ptr != base_ptr) >> + do_swap (tmp_ptr, base_ptr, size, swap_func); >> + >> + /* Insertion sort, running from left-hand-side up to right-hand-side. */ >> + >> + run_ptr = base_ptr + size; >> + while ((run_ptr += size) <= end_ptr) >> + { >> + tmp_ptr = run_ptr - size; >> + while (cmp (run_ptr, tmp_ptr, arg) < 0) >> + tmp_ptr -= size; >> + >> + tmp_ptr += size; >> + if (tmp_ptr != run_ptr) >> + { >> + char *trav; >> + >> + trav = run_ptr + size; >> + while (--trav >= run_ptr) >> + { >> + char c = *trav; >> + char *hi, *lo; >> + >> + for (hi = lo = trav; (lo -= size) >= tmp_ptr; hi = lo) >> + *hi = *lo; >> + *hi = c; >> + } >> + } >> + } >> +} >> + >> void >> _quicksort (void *const pbase, size_t total_elems, size_t size, >> __compar_d_fn_t cmp, void *arg) >> @@ -278,51 +330,6 @@ _quicksort (void *const pbase, size_t total_elems, size_t size, >> for partitions below MAX_THRESH size. BASE_PTR points to the beginning >> of the array to sort, and END_PTR points at the very last element in >> the array (*not* one beyond it!). */ >> - >> -#define min(x, y) ((x) < (y) ? (x) : (y)) >> - >> - { >> - char *const end_ptr = &base_ptr[size * (total_elems - 1)]; >> - char *tmp_ptr = base_ptr; >> - char *thresh = min(end_ptr, base_ptr + max_thresh); >> - char *run_ptr; >> - >> - /* Find smallest element in first threshold and place it at the >> - array's beginning. This is the smallest array element, >> - and the operation speeds up insertion sort's inner loop. */ >> - >> - for (run_ptr = tmp_ptr + size; run_ptr <= thresh; run_ptr += size) >> - if ((*cmp) ((void *) run_ptr, (void *) tmp_ptr, arg) < 0) >> - tmp_ptr = run_ptr; >> - >> - if (tmp_ptr != base_ptr) >> - do_swap (tmp_ptr, base_ptr, size, swap_type); >> - >> - /* Insertion sort, running from left-hand-side up to right-hand-side. */ >> - >> - run_ptr = base_ptr + size; >> - while ((run_ptr += size) <= end_ptr) >> - { >> - tmp_ptr = run_ptr - size; >> - while ((*cmp) ((void *) run_ptr, (void *) tmp_ptr, arg) < 0) >> - tmp_ptr -= size; >> - >> - tmp_ptr += size; >> - if (tmp_ptr != run_ptr) >> - { >> - char *trav; >> - >> - trav = run_ptr + size; >> - while (--trav >= run_ptr) >> - { >> - char c = *trav; >> - char *hi, *lo; >> - >> - for (hi = lo = trav; (lo -= size) >= tmp_ptr; hi = lo) >> - *hi = *lo; >> - *hi = c; >> - } >> - } >> - } >> - } >> + insertion_sort_qsort_partitions (pbase, total_elems, size, swap_type, cmp, >> + arg); >> } >> -- >> 2.34.1 >>