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

[Han Zhou]

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++) {
+        for (ofs_byte = start_byte; ofs_byte <= end_byte; ofs_byte++) {
+            if ((target && s[ofs_byte])
+                    || (!target && (s[ofs_byte] != 0xff))) {
+               break;
+            }
+        }
+        if (ofs_byte > end_byte) {
+            return end;
+        }
 
-    for (ofs = start; ofs > end; ofs--) {
-        if (bitwise_get_bit(p, len, ofs) == target) {
-            break;
+        uint8_t the_byte = s[ofs_byte];
+        int ofs;
+        for (ofs = 7; ofs >= 0; ofs--) {
+            if (((the_byte & (1u << ofs)) != 0) == target) {
+                break;
+            }
+        }
+        int ret = (len - ofs_byte) * 8 - (8 - ofs);
+        if (ret < end) {
+            return end;
+        } else if (ret <= start) {
+            return ret;
         }
     }
-    return ofs;
+    return -1; /* Should never reach here */
 }
 
 /* Copies the 'n_bits' low-order bits of 'value' into the 'n_bits' bits
-- 
2.1.0