From: Fangrui Song via Libc-alpha <libc-alpha@sourceware.org>
To: Adhemerval Zanella <adhemerval.zanella@linaro.org>
Cc: libc-alpha@sourceware.org
Subject: Re: [PATCH v3 4/7] stdlib: Move insertion sort out qsort
Date: Mon, 6 Sep 2021 13:48:01 -0700 [thread overview]
Message-ID: <20210906204801.rwwf7azfmo7dis24@google.com> (raw)
In-Reply-To: <20210906203514.oazjrmwr4cksgsc3@google.com>
On 2021-09-06, Fangrui Song wrote:
>On 2021-09-03, Adhemerval Zanella via Libc-alpha wrote:
>>---
>>stdlib/qsort.c | 100 ++++++++++++++++++++++++++-----------------------
>>1 file changed, 53 insertions(+), 47 deletions(-)
>>
>>diff --git a/stdlib/qsort.c b/stdlib/qsort.c
>>index 59458d151b..b69417dedd 100644
>>--- a/stdlib/qsort.c
>>+++ b/stdlib/qsort.c
>>@@ -150,6 +150,58 @@ typedef struct
>> smaller partition. This *guarantees* no more than log (total_elems)
>> stack size is needed (actually O(1) in this case)! */
>>
>>+static void
>>+insertion_sort (void *const pbase, size_t total_elems, size_t size,
>>+ swap_func_t swap_func,
>>+ __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;
>
>But I think MAX_THRESH being 4 is unfortunate.
>All modern architectures want a value larger than 4 :)
>
>Reviewed-by: Fangrui Song <maskray@google.com>
>
>>+ 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;
>>+ }
>
>The bytewise move is a bit unfortunate and may slow down the insertion sort
>quite a bit... But without allocation or code duplication I don't know a
>better approach...
If we want to optimize insertion sort for the common case,
perhaps also optimize the cases when the element size is <= SWAP_GENERIC_SIZE.
Use an unsigned char tmp[SWAP_GENERIC_SIZE];
as you do in another patch.
There will be a bit code bloat, though...
>
>>+ }
>>+ }
>>+}
>>+
>>void
>>_quicksort (void *const pbase, size_t total_elems, size_t size,
>> __compar_d_fn_t cmp, void *arg)
>>@@ -272,51 +324,5 @@ _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_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) ((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 (pbase, total_elems, size, swap_func, cmp, arg);
>>}
>>--
>>2.30.2
>>
next prev parent reply other threads:[~2021-09-06 20:51 UTC|newest]
Thread overview: 41+ messages / expand[flat|nested] mbox.gz Atom feed top
2021-09-03 17:11 [PATCH v3 0/7] Use introsort for qsort Adhemerval Zanella via Libc-alpha
2021-09-03 17:11 ` [PATCH v3 1/7] benchtests: Add bench-qsort Adhemerval Zanella via Libc-alpha
2021-09-04 9:09 ` Alexander Monakov via Libc-alpha
2021-09-06 18:30 ` Adhemerval Zanella via Libc-alpha
2021-10-13 3:19 ` Noah Goldstein via Libc-alpha
2021-10-15 12:52 ` Adhemerval Zanella via Libc-alpha
2021-10-15 16:39 ` Noah Goldstein via Libc-alpha
2021-10-15 17:19 ` Adhemerval Zanella via Libc-alpha
2021-09-03 17:11 ` [PATCH v3 2/7] support: Fix getopt_long with CMDLINE_OPTIONS Adhemerval Zanella via Libc-alpha
2021-09-03 17:11 ` [PATCH v3 3/7] stdlib: Optimization qsort{_r} swap implementation (BZ #19305) Adhemerval Zanella via Libc-alpha
2021-10-13 3:29 ` Noah Goldstein via Libc-alpha
2021-10-13 3:39 ` Noah Goldstein via Libc-alpha
2021-10-15 13:29 ` Adhemerval Zanella via Libc-alpha
2021-10-15 17:17 ` Noah Goldstein via Libc-alpha
2021-10-15 17:34 ` Adhemerval Zanella via Libc-alpha
2021-10-15 17:45 ` Noah Goldstein via Libc-alpha
2021-10-15 17:56 ` Adhemerval Zanella via Libc-alpha
2021-10-15 13:12 ` Adhemerval Zanella via Libc-alpha
2021-10-15 16:45 ` Noah Goldstein via Libc-alpha
2021-10-15 17:21 ` Adhemerval Zanella via Libc-alpha
2021-09-03 17:11 ` [PATCH v3 4/7] stdlib: Move insertion sort out qsort Adhemerval Zanella via Libc-alpha
2021-09-06 20:35 ` Fangrui Song via Libc-alpha
2021-09-06 20:48 ` Fangrui Song via Libc-alpha [this message]
2021-09-03 17:11 ` [PATCH v3 5/7] stdlib: qsort: Move some macros to inline function Adhemerval Zanella via Libc-alpha
2021-09-03 17:11 ` [PATCH v3 6/7] stdlib: Implement introsort with qsort Adhemerval Zanella via Libc-alpha
2021-09-04 9:17 ` Alexander Monakov via Libc-alpha
2021-09-06 18:43 ` Adhemerval Zanella via Libc-alpha
2021-09-06 20:23 ` Fangrui Song via Libc-alpha
2021-10-13 3:53 ` Noah Goldstein via Libc-alpha
2021-09-03 17:11 ` [PATCH v3 7/7] stdlib: Remove use of mergesort on qsort (BZ #21719) Adhemerval Zanella via Libc-alpha
2021-09-03 19:18 ` [PATCH v3 0/7] Use introsort for qsort Paul Eggert
2021-09-06 14:13 ` Carlos O'Donell via Libc-alpha
2021-09-06 17:03 ` Zack Weinberg via Libc-alpha
2021-09-06 18:19 ` Adhemerval Zanella via Libc-alpha
2021-09-07 0:14 ` Paul Eggert
2021-09-07 14:32 ` Adhemerval Zanella via Libc-alpha
2021-09-07 17:39 ` Paul Eggert
2021-09-07 18:07 ` Adhemerval Zanella via Libc-alpha
2021-09-07 19:28 ` Paul Eggert
2021-09-08 11:56 ` Adhemerval Zanella via Libc-alpha
2021-09-09 0:39 ` Paul Eggert
Reply instructions:
You may reply publicly to this message via plain-text email
using any one of the following methods:
* Save the following mbox file, import it into your mail client,
and reply-to-all from there: mbox
Avoid top-posting and favor interleaved quoting:
https://en.wikipedia.org/wiki/Posting_style#Interleaved_style
List information: https://www.gnu.org/software/libc/involved.html
* Reply using the --to, --cc, and --in-reply-to
switches of git-send-email(1):
git send-email \
--in-reply-to=20210906204801.rwwf7azfmo7dis24@google.com \
--to=libc-alpha@sourceware.org \
--cc=adhemerval.zanella@linaro.org \
--cc=maskray@google.com \
/path/to/YOUR_REPLY
https://kernel.org/pub/software/scm/git/docs/git-send-email.html
* If your mail client supports setting the In-Reply-To header
via mailto: links, try the mailto: link
Be sure your reply has a Subject: header at the top and a blank line
before the message body.
This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox;
as well as URLs for read-only IMAP folder(s) and NNTP newsgroup(s).