Re: [PATCH v2 7/8] lib: move bsearch code

[Julien Grall <julien@xxxxxxx>]

Hi Andrew,

Thank you for the detailed explanation :).

On 24/11/2020 00:40, Andrew Cooper wrote:
> On 23/11/2020 22:49, Julien Grall wrote:
> > Hi Jan,
> >
> > On 19/11/2020 10:27, Jan Beulich wrote:
> > > On 18.11.2020 19:09, Julien Grall wrote:
> > > > On 23/10/2020 11:19, Jan Beulich wrote:
> > > > > --- a/xen/include/xen/compiler.h
> > > > > +++ b/xen/include/xen/compiler.h
> > > > > @@ -12,6 +12,7 @@
> > > > >        #define inline        __inline__
> > > > >     #define always_inline __inline__ __attribute__
> > > > > ((__always_inline__))
> > > > > +#define gnu_inline    __inline__ __attribute__ ((__gnu_inline__))
> > > > bsearch() is only used by Arm and I haven't seen anyone so far
> > > > complaining about the perf of I/O emulation.
> > > >
> > > > Therefore, I am not convinced that there is enough justification to
> > > > introduce a GNU attribute just for this patch.
> > > Please settle this with Andrew: He had asked for the function to
> > > become inline. I don't view making it static inline in the header
> > > as an option here - if the compiler decides to not inline it, we
> > > should not end up with multiple instances in different CUs.
> > That's the cons of static inline... but then why is it suddenly a
> > problem with this helper?
> >
> > > And
> > > without making it static inline the attribute needs adding; at
> > > least I'm unaware of an alternative which works with the various
> > > compiler versions.
> > The question we have to answer is: What is the gain with this approach?
> Substantial.
>
> > If it is not quantifiable, then introducing compiler specific
> > attribute is not an option.
> >
> > IIRC, there are only two callers (all in Arm code) of this function.
> > Even inlined, I don't believe you would drastically reduce the number
> > of instructions compare to a full blown version. To be generous, I
> > would say you may save ~20 instructions per copy.
> >
> > Therefore, so far, the compiler specific attribute doesn't look
> > justified to me. As usual, I am happy to be proven wrong
> There is a very good reason why this is the classic example used for
> extern inline's in various libc's.
>
> The gains are from the compiler being able to optimise away the function
> pointer(s) entirely.  Instead of working on opaque objects, it can see
> the accesses directly, implement compares as straight array reads, (for
> sorting, the swap() call turns into memcpy()) and because it can see all
> the memory accesses, doesn't have to assume that every call to cmp()
> modifies arbitrary data in the array (i.e. doesn't have to reload the
> objects from memory every iteration).
>
> extern inline allows the compiler full flexibility to judge whether
> inlining is a net win, based on optimisation settings and observing what
> the practical memory access pattern would be from not inlining.
>
> extern inline is the appropriate thing to use here, except for the big
> note in the GCC manual saying "always use gnu_inline in this case" which
> appears to be working around a change in the C99 standard which forces
> any non-static inline to emit a body even when its not called, due to
> rules about global symbols.
>
> Therefore, Reviewed-by: Andrew Cooper <andrew.cooper3@xxxxxxxxxx>
>
> Some further observations:
>
> For arch/arm/io.c, the handlers are sorted, so find_mmio_handler() will
> be O(lg n), but it will surely be faster with the inlined version, and
> this is the fastpath.
>
> register_mmio_handler() OTOH is massively expensive, because sort()
> turns the array into a heap and back into an array on every insertion,
> just to insert an entry into an already sorted array.  It would be more
> efficient to library-fy the work I did for VT-x MSR load/save lists
> (again, extern inline) and reuse
> "insert_$FOO_into_sorted_list_of_FOOs()" which is a search, single
> memmove() to make a gap, and a memcpy() into place.
>
> When you compile io.c with this patch in place, the delta is:
>
> add/remove: 0/1 grow/shrink: 1/0 up/down: 92/-164 (-72)
> Function                                     old     new   delta
> try_handle_mmio                              720     812     +92
> bsearch                                      164       -    -164
> Total: Before=992489, After=992417, chg -0.01%
>
> The reason cmp_mmio_handler (140 bytes) doesn't drop out is because it
> is referenced by register_mmio_hanlder()'s call to sort().  All in all,
> the inlined version is less than 1/3 the size of the out-of-lined
> version, but I haven't characterised it further than that.
>
>
> On a totally separate point,  I wonder if we'd be better off compiling
> with -fgnu89-inline because I can't see any case we're we'd want the C99
> inline semantics anywhere in Xen.
This was one of my point above. It feels that if we want to use the 
behavior in Xen, then it should be everywhere rather than just this helper.
Cheers,

--
Julien Grall