From: Noah Goldstein <goldstein.w.n@gmail.com>
To: Adhemerval Zanella <adhemerval.zanella@linaro.org>
Cc: libc-alpha@sourceware.org
Subject: Re: [PATCH v4 2/6] stdlib: Move insertion sort out qsort
Date: Tue, 11 Jul 2023 18:46:40 -0500 [thread overview]
Message-ID: <CAFUsyfLHCY2=ttCUZU7RQg6p+oRYkU+2z605rdjKQ_UeMPxn=w@mail.gmail.com> (raw)
In-Reply-To: <20230711190722.4028821-3-adhemerval.zanella@linaro.org>
On Tue, Jul 11, 2023 at 2:09 PM Adhemerval Zanella via Libc-alpha
<libc-alpha@sourceware.org> wrote:
>
> ---
> stdlib/qsort.c | 100 ++++++++++++++++++++++++++-----------------------
> 1 file changed, 53 insertions(+), 47 deletions(-)
>
> diff --git a/stdlib/qsort.c b/stdlib/qsort.c
> index 8a3331fdb4..00637208ab 100644
> --- a/stdlib/qsort.c
> +++ b/stdlib/qsort.c
> @@ -153,6 +153,58 @@ typedef struct
> smaller partition. This *guarantees* no more than log (total_elems)
> stack size is needed (actually O(1) in this case)! */
>
> +static inline void
> +insertion_sort (void *const pbase, size_t total_elems, size_t size,
Maybe a less generic name would be better. Something like:
"insertion_sort_qsort_partions" to indicate this is not just standard
insertion sort but a helper for qsort. Just thinking about a reader
grepping around in a year or so.
> + 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;
> + 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)
> @@ -275,51 +327,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.34.1
>
next prev parent reply other threads:[~2023-07-11 23:46 UTC|newest]
Thread overview: 24+ messages / expand[flat|nested] mbox.gz Atom feed top
2023-07-11 19:07 [PATCH v4 0/6] Use introsort for qsort Adhemerval Zanella
2023-07-11 19:07 ` [PATCH v4 1/6] stdlib: Optimization qsort{_r} swap implementation (BZ 19305) Adhemerval Zanella
2023-07-11 23:40 ` Noah Goldstein
2023-07-12 19:40 ` Adhemerval Zanella Netto
2023-07-12 21:04 ` Paul Eggert
2023-07-13 11:07 ` Adhemerval Zanella Netto
2023-07-13 13:13 ` Alexander Monakov
2023-07-13 13:29 ` Adhemerval Zanella Netto
2023-07-11 19:07 ` [PATCH v4 2/6] stdlib: Move insertion sort out qsort Adhemerval Zanella
2023-07-11 23:46 ` Noah Goldstein [this message]
2023-07-12 7:28 ` Andreas Schwab
2023-07-12 20:35 ` Adhemerval Zanella Netto
2023-07-11 19:07 ` [PATCH v4 3/6] stdlib: qsort: Move some macros to inline function Adhemerval Zanella
2023-07-11 23:44 ` Noah Goldstein
2023-07-12 20:45 ` Adhemerval Zanella Netto
2023-07-11 19:07 ` [PATCH v4 4/6] stdlib: Implement introsort with qsort Adhemerval Zanella
2023-07-12 5:39 ` Alexander Monakov
2023-07-12 20:55 ` Adhemerval Zanella Netto
2023-07-12 21:55 ` Paul Eggert
2023-07-13 11:53 ` Adhemerval Zanella Netto
2023-07-11 19:07 ` [PATCH v4 5/6] stdlib: Remove use of mergesort on qsort (BZ 21719) Adhemerval Zanella
2023-07-12 22:04 ` Paul Eggert
2023-07-13 11:55 ` Adhemerval Zanella Netto
2023-07-11 19:07 ` [PATCH v4 6/6] stdlib: Add more qsort{_r} coverage Adhemerval Zanella
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
* Reply using the --to, --cc, and --in-reply-to
switches of git-send-email(1):
git send-email \
--in-reply-to='CAFUsyfLHCY2=ttCUZU7RQg6p+oRYkU+2z605rdjKQ_UeMPxn=w@mail.gmail.com' \
--to=goldstein.w.n@gmail.com \
--cc=adhemerval.zanella@linaro.org \
--cc=libc-alpha@sourceware.org \
/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).