[ovs-dev] [PATCH] lib/util.c: Optimise bitwise_rscan.

[Han Zhou]

On Thu, Mar 17, 2016 at 8:59 AM, Ben Pfaff <blp at ovn.org> wrote:
>
> On Wed, Mar 16, 2016 at 10:38:46PM -0700, Han Zhou wrote:
> > On Wed, Mar 16, 2016 at 10:03 PM, Ben Pfaff <blp at ovn.org> wrote:
> >
> > > On Wed, Mar 16, 2016 at 08:55:35PM -0700, Han Zhou wrote:
> > > > bitwise_rscan() is found to be hot spot in ovn-controller during OVN
> > > > scalability tests. It is triggered by lflow_run() when processing
> > > > lflow updates from SB ovsdb. The perf result shows:
> > > >
> > > > +  34.21%  ovn-controller  ovn-controller      [.] bitwise_rscan
> > > > +  16.08%  ovn-controller  libc-2.15.so        [.] 0x80810
> > > > +   7.39%  ovn-controller  [kernel.kallsyms]   [k]
0xffffffff8103e0ba
> > > > +   5.74%  ovn-controller  ovn-controller      [.] lex_token_parse
> > > > +   4.31%  ovn-controller  ovn-controller      [.]
ovsdb_idl_next_row
> > > > +   2.84%  ovn-controller  ovn-controller      [.] lflow_run
> > > >
> > > > After optimization, bitwise_rscan percentage dropped from 34% to
less
> > > > than 5%:
> > > >
> > > > +  23.69%  ovn-controller  libc-2.15.so        [.] 0x13a586
> > > > +  13.47%  ovn-controller  [kernel.kallsyms]   [k]
0xffffffff8103e0ba
> > > > +   5.44%  ovn-controller  ovn-controller      [.]
ovsdb_idl_next_row
> > > > +   5.03%  ovn-controller  ovn-controller      [.] lex_token_parse
> > > > +   4.81%  ovn-controller  ovn-controller      [.] bitwise_rscan
> > > > +   3.62%  ovn-controller  ovn-controller      [.] lflow_run
> > > >
> > > > Signed-off-by: Han Zhou <zhouhan at gmail.com>
> > > > ---
> > > >  lib/util.c | 33 ++++++++++++++++++++++++++++-----
> > > >  1 file changed, 28 insertions(+), 5 deletions(-)
> > > >
> > > > diff --git a/lib/util.c b/lib/util.c
> > > > index f06dee5..b0887fb 100644
> > > > --- a/lib/util.c
> > > > +++ b/lib/util.c
> > > > @@ -1400,14 +1400,37 @@ bitwise_scan(const void *p, unsigned int
len,
> > > bool target, unsigned int start,
> > > >  int
> > > >  bitwise_rscan(const void *p, unsigned int len, bool target, int
start,
> > > int end)
> > > >  {
> > > > -    int ofs;
> > > > +    const uint8_t *s = p;
> > > > +    int start_byte = len - (start / 8 + 1);
> > > > +    int end_byte = len - (end / 8 + 1);
> > > > +    int ofs_byte;
> > > > +    int try;
> > > > +    for (try = 0; try < 2; try++) {
> > >
> > > Why does the code need two tries?
> > >
> >
> > The first try doesn't check if the first found bit is in "start_byte"
but
> > before the "start" bit. In such case, the second try will do the real
job
> > to find the correct bit.
> > I will add some documentation.
>
> Why would bitwise_rscan() want to scan for bits before the start?  It
> should only scan for bits from start to end.

Yes. The algorithm here just did the check lazily and then do a second try.
I had tests comparing with the old implementation verified the correctness.
However, I think I can make it more straightforward (more readable). I made
it unnecessarily complicated. Will come up with a new version.

>
> While you're at it, could you add a test to test-util.c comparable to
> the one for test_bitwise_is_all_zeros() or another suitable bitwise test
> case?  We didn't have one for bitwise_rscan() before because it was
> trivial, but with a sophisticated algorithm it's more necessary.

Agree, I will add test cases.

>
> By the way, I forgot to say "thank you" for doing the work to track down
> this performance issue.  I suspect that in fact we should not be making
> so many bitwise_rscan() calls (there are far too many of them), but
> optimizing bitwise_rscan() is reasonable either way and I appreciate it
> too.

My pleasure :)


--
Best regards,
Han