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

[Ben Pfaff]

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?