bsearch: simplify and optimize

Submitted by Ray on July 22, 2018, 12:47 a.m.

Details

Message ID 20180722004358.6q7kegg7sx6q2p7e@google.com
State New
Series "bsearch: simplify and optimize"
Headers show

Commit Message

Ray July 22, 2018, 12:47 a.m.

Patch hide | download patch | download mbox

From 64d86f96fa404dbaa40de8a1979ecadca6add4ca Mon Sep 17 00:00:00 2001
From: Fangrui Song <i@maskray.me>
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 = (char *)base + width*(nel/2);
 		sign = cmp(key, try);
-		if (!sign) return try;
-		else if (nel == 1) break;
-		else if (sign < 0)
+		if (sign < 0)
 			nel /= 2;
-		else {
-			base = try;
-			nel -= nel/2;
-		}
+		else if (sign > 0) {
+			base = (char *)try + width;
+			nel -= nel/2+1;
+		} else
+			return try;
 	}
 	return NULL;
 }
-- 
2.17.1


Comments

Rich Felker July 22, 2018, 6:51 p.m.
On Sat, Jul 21, 2018 at 05:47:32PM -0700, Fāng-ruì Sòng wrote:

> >From 64d86f96fa404dbaa40de8a1979ecadca6add4ca Mon Sep 17 00:00:00 2001
> From: Fangrui Song <i@maskray.me>
> 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 = (char *)base + width*(nel/2);
>  		sign = cmp(key, try);
> -		if (!sign) return try;
> -		else if (nel == 1) break;
> -		else if (sign < 0)
> +		if (sign < 0)
>  			nel /= 2;
> -		else {
> -			base = try;
> -			nel -= nel/2;
> -		}
> +		else if (sign > 0) {
> +			base = (char *)try + width;
> +			nel -= 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 != but nel==1 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
Ray July 22, 2018, 11:03 p.m.
Thanks!

On Sun, Jul 22, 2018 at 11:51 AM, Rich Felker <dalias@libc.org> wrote:

> On Sat, Jul 21, 2018 at 05:47:32PM -0700, Fāng-ruì Sòng wrote:
>
> > >From 64d86f96fa404dbaa40de8a1979ecadca6add4ca Mon Sep 17 00:00:00 2001
> > From: Fangrui Song <i@maskray.me>
> > 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 = (char *)base + width*(nel/2);
> >               sign = cmp(key, try);
> > -             if (!sign) return try;
> > -             else if (nel == 1) break;
> > -             else if (sign < 0)
> > +             if (sign < 0)
> >                       nel /= 2;
> > -             else {
> > -                     base = try;
> > -                     nel -= nel/2;
> > -             }
> > +             else if (sign > 0) {
> > +                     base = (char *)try + width;
> > +                     nel -= 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 != but nel==1 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
>