[PATCH] Add inline bsearch expansion

[Ondřej Bílka]

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)
+__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
+#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