[PATCH] bsearch: simplify and optimize

[PATCH] bsearch: simplify and optimize

[Fāng-ruì Sòng]

[-- Attachment #1: Type: text/plain, Size: 0 bytes --]



[-- Attachment #2: bsearch.patch --]
[-- Type: text/x-diff, Size: 906 bytes --]

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

Re: [PATCH] bsearch: simplify and optimize

[Rich Felker]

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

Re: [PATCH] bsearch: simplify and optimize

[Ray]

[-- Attachment #1: Type: text/plain, Size: 2115 bytes --]

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
>

[-- Attachment #2: Type: text/html, Size: 2878 bytes --]