This is the mail archive of the
libc-alpha@sourceware.org
mailing list for the glibc project.
Re: [PATCH] Add inline bsearch expansion
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