Ping: [PATCH] Add inline bsearch expansion

[OndÅej BÃlka <neleai at seznam dot cz>]

Ping
On Sun, Jan 06, 2013 at 09:59:11PM +0100, OndÅej BÃlka wrote:
> On Sun, Jan 06, 2013 at 08:28:06PM +0100, Andreas Jaeger wrote:
> > On 01/05/2013 04:26 PM, OndÅej BÃlka wrote:
> > >On Sat, Jan 05, 2013 at 02:19:37PM +0100, Jakub Jelinek wrote:
> > >>On Sat, Jan 05, 2013 at 01:51:30PM +0100, OndÅej BÃlka wrote:
> > >>>I looked into qsort/bsearch functions. Here I
> > >>>added inline version of bsearch.
> > >>>
> > >>>It saves multiplications instructions as size is
> > >>>most of time known in advance.
> > >>>When compiled with gcc-4.7.1 and icc 12.1.4 with -O2
> > >>>it can inline ccmp functions from example below.
> > >>>gcc-4.5.3 does not inline ccmp.
> > >>
> > >>I don't comment on whether it is a good idea or not etc.,
> > >>just nits that you should guard it with
> > >>#ifdef __USE_EXTERN_INLINES
> > >>and use
> > >>__extern_inline
> > >>instead of extern inline.
> > >OK
> > >>
> > >>	Jakub
> > >
> > >I also added gcc-4.7 requirement as element size can be probably
> > >better handled separately. When I profiled my system bsearch was
> > >mostly used by firefox. There element sizes were from 90% 8,16,32
> > >and  10% 40,56.
> > >
> > >---
> > >  stdlib/stdlib.h |   33 +++++++++++++++++++++++++++++++++
> > >  1 files changed, 33 insertions(+), 0 deletions(-)
> > >
> > >diff --git a/stdlib/stdlib.h b/stdlib/stdlib.h
> > >index fc83f4e..bcb504e 100644
> > >--- a/stdlib/stdlib.h
> > >+++ b/stdlib/stdlib.h
> > >@@ -755,6 +755,39 @@ extern void *bsearch (const void *__key, const void *__base,
> > >  		      size_t __nmemb, size_t __size, __compar_fn_t __compar)
> > >       __nonnull ((1, 2, 5)) __wur;
> > >
> > >+
> > >+#ifdef __USE_EXTERN_INLINES
> > >+/* From gcc-4.7 we can inline __compar function.  */
> > >+#if __GNUC_PREREQ (4, 7)
> > 
> > What exactly is the dependency on GCC 4.7? Just that 4.7 inlines
> > this and previous versions not?
> Only this. When inline is changed into macro then gcc-4.6 can remove
> indirection in comparsion function but does not inline it.
> > 
> > What about other compilers that inline it?
> both icc and debian llvm-gcc-4.2 inline it.
> > 
> > I guess we can drop the dependency on 4.7, can't we?
> Can. Here is updated version. I hope that everything is correct now.
> 
> 
> ---
>  stdlib/stdlib.h |   30 ++++++++++++++++++++++++++++++
>  1 files changed, 30 insertions(+), 0 deletions(-)
> 
> diff --git a/stdlib/stdlib.h b/stdlib/stdlib.h
> index fc83f4e..566edf6 100644
> --- a/stdlib/stdlib.h
> +++ b/stdlib/stdlib.h
> @@ -755,6 +755,36 @@ extern void *bsearch (const void *__key, const void *__base,
>  		      size_t __nmemb, size_t __size, __compar_fn_t __compar)
>       __nonnull ((1, 2, 5)) __wur;
>  
> +
> +#ifdef __USE_EXTERN_INLINES
> +__extern_inline
> +void *
> +bsearch (const void *__key, const void *__base, size_t __nmemb, size_t __size,
> +   int (*__compar) (const void *, const void *))
> +{
> +  size_t __l, __u, __idx;
> +  const void *__p;
> +  int __comparison;
> +
> +  __l = 0;
> +  __u = __nmemb;
> +  while (__l < __u)
> +    {
> +      __idx = (__l + __u) / 2;
> +      __p = (void *) (((const char *) __base) + (__idx * __size));
> +      __comparison = (*__compar) (__key, __p);
> +      if (__comparison < 0)
> +	__u = __idx;
> +      else if (__comparison > 0)
> +	__l = __idx + 1;
> +      else
> +	return (void *) __p;
> +    }
> +
> +  return NULL;
> +}
> +#endif
> +
>  /* Sort NMEMB elements of BASE, of SIZE bytes each,
>     using COMPAR to perform the comparisons.  */
>  extern void qsort (void *__base, size_t __nmemb, size_t __size,
> -- 
> 1.7.4.4