On Thu, Mar 17, 2016 at 8:59 AM, Ben Pfaff <b...@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 <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.
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
_______________________________________________
dev mailing list
dev@openvswitch.org
http://openvswitch.org/mailman/listinfo/dev
