From mboxrd@z Thu Jan 1 00:00:00 1970 X-Msuck: nntp://news.gmane.org/gmane.linux.lib.musl.general/13072 Path: news.gmane.org!.POSTED!not-for-mail From: Ray Newsgroups: gmane.linux.lib.musl.general Subject: Re: [PATCH] bsearch: simplify and optimize Date: Sun, 22 Jul 2018 16:03:34 -0700 Message-ID: References: <20180722004358.6q7kegg7sx6q2p7e@google.com> <20180722185131.GW1392@brightrain.aerifal.cx> Reply-To: musl@lists.openwall.com NNTP-Posting-Host: blaine.gmane.org Mime-Version: 1.0 Content-Type: multipart/alternative; boundary="000000000000d8be7305719e89d0" X-Trace: blaine.gmane.org 1532300547 13497 195.159.176.226 (22 Jul 2018 23:02:27 GMT) X-Complaints-To: usenet@blaine.gmane.org NNTP-Posting-Date: Sun, 22 Jul 2018 23:02:27 +0000 (UTC) To: musl@lists.openwall.com Original-X-From: musl-return-13088-gllmg-musl=m.gmane.org@lists.openwall.com Mon Jul 23 01:02:23 2018 Return-path: Envelope-to: gllmg-musl@m.gmane.org Original-Received: from mother.openwall.net ([195.42.179.200]) by blaine.gmane.org with smtp (Exim 4.84_2) (envelope-from ) id 1fhNMt-0003OT-3E for gllmg-musl@m.gmane.org; Mon, 23 Jul 2018 01:02:23 +0200 Original-Received: (qmail 16161 invoked by uid 550); 22 Jul 2018 23:04:29 -0000 Mailing-List: contact musl-help@lists.openwall.com; run by ezmlm Precedence: bulk List-Post: List-Help: List-Unsubscribe: List-Subscribe: List-ID: Original-Received: (qmail 15964 invoked from network); 22 Jul 2018 23:04:26 -0000 DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20161025; h=mime-version:sender:in-reply-to:references:from:date:message-id :subject:to; bh=2u+T86CoXG4ozzF6OEwAvl2PT1ERnlCMaPlzsLBU+vU=; b=kupIx+KyPIklgY0Q6p2sxD/LYId+Rl6wC2BoAVMbqwOYr/+2XExcor9b2+2lZAdBIt Mcx2I/LWl3g7YhrpZ0rX4oPwBzpWTvU0a2TfOBInunqpgp7tsy4YBnx4oVevQzlNSnDE Flr+BfjPcpp/sbGYVC0WI+TNtD0F2V05J0IKqi1LUxMb1ZfeOu4euDNEjHByrhlWKV8Y KHgcTI0VrcwxZbO3PCqBksicd/xVbPvJXWJE760aG0DNZ35xaB6qmilmFfXKeBzuUg3n ie+g9w1ewTxtLr2HmTRJpPnKpwSpQpRmzTGPAckm4AzIOzUCfVmi1EFCTHvrTU48Qige VtBA== DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=maskray-me.20150623.gappssmtp.com; s=20150623; h=mime-version:sender:in-reply-to:references:from:date:message-id :subject:to; bh=2u+T86CoXG4ozzF6OEwAvl2PT1ERnlCMaPlzsLBU+vU=; b=s8uFD2amdnnSnR9gqGfdHc8b8mCg8OMPjbwRvS68BDXalP4YLE+slDyL/C8EBna0R9 Tw9anD9OnGtDpG/MEiLaeGEb4lQpuZF3aQrgFpCfUlf4n5umgWtPcJ2AfyuIchHYxitv 0Qk0obDu9fT/W5g0QwUsi77Jf9gXMIh3r+ElZSQRwLqLHq0wcJmPbm5ak9mMr1nlLvfG myhvqkHHQtGbn0M5LKxNLvQBO0iJwwxqrSLo08aLuQPROIgQVWgrcOXUXp66z09X8bW8 C1hhj2I0YxhMtgPsvKt/EZ/rDO+rBVblhhyij/+/HJIYh0WYc16a2L/vhvtSch6TdwAA P4mw== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20161025; h=x-gm-message-state:mime-version:sender:in-reply-to:references:from :date:message-id:subject:to; bh=2u+T86CoXG4ozzF6OEwAvl2PT1ERnlCMaPlzsLBU+vU=; b=UGry1Z22yqPLLBa2gUQNPalwlarcuPLhZHj1edtPFSeCRVBZiU/5SGWJsiiKp9SZ/7 zd5qxUfhdVivIZ+7z02b3autGtC4e8NOGvpCnQzQKmode4qVeZCjD28zZ5lJd3hNH80S +lj/TeWXWF0sQMB2LkvmgtssdGLlK6yipSH1d80Eob0sdMc85Sdmc5HpeeZbkN04IoO/ BMfjMDUxWCcccCEznPq5pn0H9zGSsSejJL5B3GElfCy7496HK2rI2slwOkRVqZLBgBwU XYTG1xaeB57aA/QvmOKb3T3KCedp4WMVVbHmIDWKEDpJ20HIJBrmNv6zK7ZTLVXrzjDS 6zbA== X-Gm-Message-State: AOUpUlFl56D283pr0vE52Cla6B2FZSY0sI+F+nKMTLZZHyGnvNqLyUEl v03t4aFbxgk7rLvi/fIxLTUSwdKhMAr0OsJAJDJbng== X-Google-Smtp-Source: AAOMgpexIgkV4m8RvOAE/yfVBjHbY4surmB7l3I+b8qmgwF87UZu3LlBpIKeHI+F/CPcXSNg33r3NKG/YafMV+6g/NM= X-Received: by 2002:a54:4406:: with SMTP id k6-v6mr6901667oiw.75.1532300615006; Sun, 22 Jul 2018 16:03:35 -0700 (PDT) Original-Sender: emacsray@gmail.com In-Reply-To: <20180722185131.GW1392@brightrain.aerifal.cx> X-Google-Sender-Auth: UblgquG_3fzUvGL1hU45rajh-uU Xref: news.gmane.org gmane.linux.lib.musl.general:13072 Archived-At: --000000000000d8be7305719e89d0 Content-Type: text/plain; charset="UTF-8" Content-Transfer-Encoding: quoted-printable Thanks! On Sun, Jul 22, 2018 at 11:51 AM, Rich Felker wrote: > On Sat, Jul 21, 2018 at 05:47:32PM -0700, F=C4=81ng-ru=C3=AC S=C3=B2ng wr= ote: > > > >From 64d86f96fa404dbaa40de8a1979ecadca6add4ca Mon Sep 17 00:00:00 2001 > > From: Fangrui Song > > Date: Sat, 21 Jul 2018 17:34:00 -0700 > > Subject: [PATCH] bsearch: simplify and optimize > > > > --- > > src/stdlib/bsearch.c | 13 ++++++------- > > 1 file changed, 6 insertions(+), 7 deletions(-) > > > > diff --git a/src/stdlib/bsearch.c b/src/stdlib/bsearch.c > > index 61d89367..2a998cc6 100644 > > --- a/src/stdlib/bsearch.c > > +++ b/src/stdlib/bsearch.c > > @@ -7,14 +7,13 @@ void *bsearch(const void *key, const void *base, > size_t nel, size_t width, int ( > > while (nel > 0) { > > try =3D (char *)base + width*(nel/2); > > sign =3D cmp(key, try); > > - if (!sign) return try; > > - else if (nel =3D=3D 1) break; > > - else if (sign < 0) > > + if (sign < 0) > > nel /=3D 2; > > - else { > > - base =3D try; > > - nel -=3D nel/2; > > - } > > + else if (sign > 0) { > > + base =3D (char *)try + width; > > + nel -=3D nel/2+1; > > + } else > > + return try; > > } > > return NULL; > > } > > The change here looks correct -- what it's doing is observing that the > compared element is the first slot of the second ceil(half) of the > array, and thus can be removed for further comparison, so that we > descend into the second ceil(half)-1 rather than ceil(half) elements. > This change ensures that nel strictly decreases with each iteration, > so that the case of !=3D but nel=3D=3D1 does not need to be special-cased > anymore. > > Only change I would make is minor style: generally when if/else > construct uses braces for one case, we use them for all. If there are > no other objections I can apply this change when merging. > > Rich > --000000000000d8be7305719e89d0 Content-Type: text/html; charset="UTF-8" Content-Transfer-Encoding: quoted-printable
Thanks!

On Sun, Jul 22, 2018 at 11:51 AM, Rich Felker <dalias@libc.org<= /a>> wrote:
On Sat, Jul 21, 201= 8 at 05:47:32PM -0700, F=C4=81ng-ru=C3=AC S=C3=B2ng wrote:

> >From 64d86f96fa404dbaa40de8a1979ecadca6add4ca Mon Sep 17 00:0= 0:00 2001
> From: Fangrui Song <i@maskray.me>
> Date: Sat, 21 Jul 2018 17:34:00 -0700
> Subject: [PATCH] bsearch: simplify and optimize
>
> ---
>=C2=A0 src/stdlib/bsearch.c | 13 ++++++-------
>=C2=A0 1 file changed, 6 insertions(+), 7 deletions(-)
>
> diff --git a/src/stdlib/bsearch.c b/src/stdlib/bsearch.c
> index 61d89367..2a998cc6 100644
> --- a/src/stdlib/bsearch.c
> +++ b/src/stdlib/bsearch.c
> @@ -7,14 +7,13 @@ void *bsearch(const void *key, const void *base, siz= e_t nel, size_t width, int (
>=C2=A0 =C2=A0 =C2=A0 =C2=A0while (nel > 0) {
>=C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0try =3D (char *)= base + width*(nel/2);
>=C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0sign =3D cmp(key= , try);
> -=C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0if (!sign) return try= ;
> -=C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0else if (nel =3D=3D 1= ) break;
> -=C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0else if (sign < 0)=
> +=C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0if (sign < 0)
>=C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 = =C2=A0 =C2=A0nel /=3D 2;
> -=C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0else {
> -=C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0= =C2=A0base =3D try;
> -=C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0= =C2=A0nel -=3D nel/2;
> -=C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0}
> +=C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0else if (sign > 0)= {
> +=C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0= =C2=A0base =3D (char *)try + width;
> +=C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0= =C2=A0nel -=3D nel/2+1;
> +=C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0} else
> +=C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0= =C2=A0return try;
>=C2=A0 =C2=A0 =C2=A0 =C2=A0}
>=C2=A0 =C2=A0 =C2=A0 =C2=A0return NULL;
>=C2=A0 }

The change here looks correct -- what it's doing is observing that the<= br> compared element is the first slot of the second ceil(half) of the
array, and thus can be removed for further comparison, so that we
descend into the second ceil(half)-1 rather than ceil(half) elements.
This change ensures that nel strictly decreases with each iteration,
so that the case of !=3D but nel=3D=3D1 does not need to be special-cased anymore.

Only change I would make is minor style: generally when if/else
construct uses braces for one case, we use them for all. If there are
no other objections I can apply this change when merging.

Rich

--000000000000d8be7305719e89d0--