On Wed, Mar 16, 2016 at 10:38:46PM -0700, Han Zhou wrote:
> On Wed, Mar 16, 2016 at 10:03 PM, Ben Pfaff <b...@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 <zhou...@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.
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.
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.
_______________________________________________
dev mailing list
dev@openvswitch.org
http://openvswitch.org/mailman/listinfo/dev
