This is the mail archive of the libc-alpha@sourceware.org mailing list for the glibc project.


Index Nav: [Date Index] [Subject Index] [Author Index] [Thread Index]
Message Nav: [Date Prev] [Date Next] [Thread Prev] [Thread Next]
Other format: [Raw text]

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


Index Nav: [Date Index] [Subject Index] [Author Index] [Thread Index]
Message Nav: [Date Prev] [Date Next] [Thread Prev] [Thread Next]