From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: from mail-oa1-x30.google.com (mail-oa1-x30.google.com [IPv6:2001:4860:4864:20::30]) by sourceware.org (Postfix) with ESMTPS id 9826B3858C00 for ; Mon, 30 Oct 2023 19:03:34 +0000 (GMT) DMARC-Filter: OpenDMARC Filter v1.4.2 sourceware.org 9826B3858C00 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 9826B3858C00 Authentication-Results: server2.sourceware.org; arc=none smtp.remote-ip=2001:4860:4864:20::30 ARC-Seal: i=1; a=rsa-sha256; d=sourceware.org; s=key; t=1698692622; cv=none; b=O9lxahI30wryxaKqF+KLqNLz5WE4Yn8wOOgfSGYCOi7xP4FvjCOwL9a0jRhZBkLFzkVzkEsKnXnuWAdvB4e6enSBe1IiTN6bb/5UfW3IC5n87aM+Ln0SK2NLFsvdENS2QMpzLEeTTdIenVa/I4/lfVLjOf7cRG3HhxWBGsC0G7Q= ARC-Message-Signature: i=1; a=rsa-sha256; d=sourceware.org; s=key; t=1698692622; c=relaxed/simple; bh=CqEp1m4SupycZHbFsmlvI+SH28tIBsEjR5ovDBGnxso=; h=DKIM-Signature:MIME-Version:From:Date:Message-ID:Subject:To; b=nCBjYz22Cz66DrWZYh6kN/fCgZZeTldAsbcRX/grRvptLvyI6bqNWv4h8e824TI6dcZlYkSHpwnwRm4bSjfwAUJWWV8Ux/4Fb+6Ob7iwoEIoRu4KEXORaUFZFmfoA8IBEconqSUd8q//fF48KGKIxwlpbxiIXCs0+AN3yvc5S9E= ARC-Authentication-Results: i=1; server2.sourceware.org Received: by mail-oa1-x30.google.com with SMTP id 586e51a60fabf-1eb6c559ab4so2987255fac.0 for ; Mon, 30 Oct 2023 12:03:34 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20230601; t=1698692614; x=1699297414; darn=sourceware.org; h=content-transfer-encoding:cc:to:subject:message-id:date:from :in-reply-to:references:mime-version:from:to:cc:subject:date :message-id:reply-to; bh=aLgnEu0YKMw9KkaWYbKwyq9TrJOiJsdCB1139DA6nEk=; b=bquyawDetMvOhT1gDg20NL4IvMGIppGBp72YHJQDQkV2Dwov5xIT+sXN/lc+dnDROZ a6Y5GrXsVZAvVdCOdhyOoxuWolktGbTnCIYjVVDCj9Is4Dc9d7C3MQNeTXYDjIeluYqL frozTyctq15UuIlRr1IwVReN9c6J04UI7i3a1IEKzED0VRECrQlqR7hoSA4aQBlkzvtf KCnS64SDAiU1FEwDPhuuZaOYZKHm8iOygS4rmyW5Lx3J1K55ETulivE1ad36bSllWK5R sV5JjamUrlq9FqGy4euGcn0v5iVbHqonsSvDVCF3rGqA5/tI8O4wkGT3DlkfvFHWpUQN 61ag== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20230601; t=1698692614; x=1699297414; h=content-transfer-encoding:cc:to:subject:message-id:date:from :in-reply-to:references:mime-version:x-gm-message-state:from:to:cc :subject:date:message-id:reply-to; bh=aLgnEu0YKMw9KkaWYbKwyq9TrJOiJsdCB1139DA6nEk=; b=d8Ep+ABou2lcB3QTgWL3maoJ01HcXN7bL/zvUCPok39SlIfYddxM5F7K0Wr8zplvaj hGm+zGkfgxidQs5ngOAZL1xFfI5fc6eSMLLWAe0iF7pO9ifuo2qlDokQsoMflR3u2Om0 mv2fW01OL5CDn7cJbgJEy/Kecd5Oe+RmCu7+5iIrhKFA/HNoOtMuLEIOsBFjl06NtSCI pWfOWXcHaTqelHY7XHfBlzBWN87kY1gsyAwkoEuZ3UvVM3SxRSrF/X6+LvhzStLdj2Rt sEdN8HZr0MGJlert76HUTfVy5xVPsi1HokPfTgvl2YjW8G8zVTJOsKx5fYHMrkzSNtvl BHpA== X-Gm-Message-State: AOJu0YxqQw8PZohnIapnQCdGy8TK2NfE5OKLhFBBvTyC8akAAAKb8DEm deWZ3DqdxdllMcvFKiYYzbG/wmBBVnQOyTkT1Qs= X-Google-Smtp-Source: AGHT+IG5PUEmFIXDUQAcSY7nP17zMhLCrn35Q8D7lE52FQQNf6cPOw/CtSEmdRQE0OL6G+aOa1rJVwipM86GOCl3p8Q= X-Received: by 2002:a05:6871:1cb:b0:1c1:e6da:f88d with SMTP id q11-20020a05687101cb00b001c1e6daf88dmr12439637oad.56.1698692613800; Mon, 30 Oct 2023 12:03:33 -0700 (PDT) MIME-Version: 1.0 References: <20231003122251.3325435-1-adhemerval.zanella@linaro.org> <20231003122251.3325435-4-adhemerval.zanella@linaro.org> In-Reply-To: <20231003122251.3325435-4-adhemerval.zanella@linaro.org> From: Noah Goldstein Date: Mon, 30 Oct 2023 14:03:21 -0500 Message-ID: Subject: Re: [PATCH v8 3/7] stdlib: Move insertion sort out qsort To: Adhemerval Zanella Cc: libc-alpha@sourceware.org, Paul Eggert , Florian Weimer Content-Type: text/plain; charset="UTF-8" Content-Transfer-Encoding: quoted-printable X-Spam-Status: No, score=-9.3 required=5.0 tests=BAYES_00,DKIM_SIGNED,DKIM_VALID,DKIM_VALID_AU,DKIM_VALID_EF,FREEMAIL_FROM,GIT_PATCH_0,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 Tue, Oct 3, 2023 at 7:23=E2=80=AFAM Adhemerval Zanella wrote: > > --- > stdlib/qsort.c | 101 ++++++++++++++++++++++++++----------------------- > 1 file changed, 54 insertions(+), 47 deletions(-) > > diff --git a/stdlib/qsort.c b/stdlib/qsort.c > index 072ccdfb95..5691249a9b 100644 > --- a/stdlib/qsort.c > +++ b/stdlib/qsort.c > @@ -111,6 +111,58 @@ typedef struct > #define STACK_NOT_EMPTY (stack < top) > > > +static inline void > +insertion_sort_qsort_partitions (void *const pbase, size_t total_elems, > + size_t size, enum swap_type_t swap_type, > + __compar_d_fn_t cmp, void *arg) > +{ > + char *base_ptr =3D (char *) pbase; > + char *const end_ptr =3D &base_ptr[size * (total_elems - 1)]; > + char *tmp_ptr =3D base_ptr; > +#define min(x, y) ((x) < (y) ? (x) : (y)) > + const size_t max_thresh =3D MAX_THRESH * size; > + char *thresh =3D 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 =3D tmp_ptr + size; run_ptr <=3D thresh; run_ptr +=3D siz= e) > + if (cmp (run_ptr, tmp_ptr, arg) < 0) > + tmp_ptr =3D run_ptr; > + > + if (tmp_ptr !=3D 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 =3D base_ptr + size; > + while ((run_ptr +=3D size) <=3D end_ptr) > + { > + tmp_ptr =3D run_ptr - size; > + while (cmp (run_ptr, tmp_ptr, arg) < 0) > + tmp_ptr -=3D size; > + > + tmp_ptr +=3D size; > + if (tmp_ptr !=3D run_ptr) > + { > + char *trav; > + > + trav =3D run_ptr + size; > + while (--trav >=3D run_ptr) > + { > + char c =3D *trav; > + char *hi, *lo; > + > + for (hi =3D lo =3D trav; (lo -=3D size) >=3D tmp_ptr; hi = =3D lo) > + *hi =3D *lo; > + *hi =3D c; > + } > + } > + } > +} > + > /* Order size using quicksort. This implementation incorporates > four optimizations discussed in Sedgewick: > > @@ -257,51 +309,6 @@ _quicksort (void *const pbase, size_t total_elems, s= ize_t size, > for partitions below MAX_THRESH size. BASE_PTR points to the beginn= ing > of the array to sort, and END_PTR points at the very last element i= n > the array (*not* one beyond it!). */ > - > -#define min(x, y) ((x) < (y) ? (x) : (y)) > - > - { > - char *const end_ptr =3D &base_ptr[size * (total_elems - 1)]; > - char *tmp_ptr =3D base_ptr; > - char *thresh =3D 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 =3D tmp_ptr + size; run_ptr <=3D thresh; run_ptr +=3D s= ize) > - if ((*cmp) ((void *) run_ptr, (void *) tmp_ptr, arg) < 0) > - tmp_ptr =3D run_ptr; > - > - if (tmp_ptr !=3D 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 =3D base_ptr + size; > - while ((run_ptr +=3D size) <=3D end_ptr) > - { > - tmp_ptr =3D run_ptr - size; > - while ((*cmp) ((void *) run_ptr, (void *) tmp_ptr, arg) < 0) > - tmp_ptr -=3D size; > - > - tmp_ptr +=3D size; > - if (tmp_ptr !=3D run_ptr) > - { > - char *trav; > - > - trav =3D run_ptr + size; > - while (--trav >=3D run_ptr) > - { > - char c =3D *trav; > - char *hi, *lo; > - > - for (hi =3D lo =3D trav; (lo -=3D size) >=3D tmp_ptr; hi= =3D lo) > - *hi =3D *lo; > - *hi =3D c; > - } > - } > - } > - } > + insertion_sort_qsort_partitions (pbase, total_elems, size, swap_type, = cmp, > + arg); > } > -- > 2.34.1 > LGTM Reviewed-by: Noah Goldstein