[ovs-dev] [PATCH v2] lib/util.c: Optimise bitwise_rscan.
Ben Pfaff
blp at ovn.org
Wed Mar 23 20:00:18 UTC 2016
On Sun, Mar 20, 2016 at 12:08:48AM -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:
>
> + 35.90% ovn-controller ovn-controller [.] bitwise_rscan
> + 13.39% ovn-controller [kernel.kallsyms] [k] 0xffffffff8104f45a
> + 5.02% ovn-controller libc-2.19.so [.] _int_malloc
> + 3.47% ovn-controller libc-2.19.so [.] _int_free
>
> After optimization, bitwise_rscan percentage dropped from 36% to less
> than 6%:
>
> + 11.34% ovn-controller [kernel.kallsyms] [k] 0xffffffff8104f45a
> + 8.15% ovn-controller libc-2.19.so [.] _int_malloc
> + 5.77% ovn-controller ovn-controller [.] bitwise_rscan
> + 5.49% ovn-controller libc-2.19.so [.] _int_free
>
> Signed-off-by: Han Zhou <zhouhan at gmail.com>
> ---
>
> Notes:
> v1->v2:
> - Refactor code and fixed a bug in v1
> - Unit test
Thanks.
I enhanced the test, as below, and applied this to master.
diff --git a/tests/test-util.c b/tests/test-util.c
index 88d7cba..ef45903 100644
--- a/tests/test-util.c
+++ b/tests/test-util.c
@@ -1,5 +1,5 @@
/*
- * Copyright (c) 2011, 2012, 2013, 2014, 2015 Nicira, Inc.
+ * Copyright (c) 2011, 2012, 2013, 2014, 2015, 2016 Nicira, Inc.
*
* Licensed under the Apache License, Version 2.0 (the "License");
* you may not use this file except in compliance with the License.
@@ -462,6 +462,20 @@ test_bitwise_is_all_zeros(struct ovs_cmdl_context *ctx OVS_UNUSED)
}
}
+static int
+trivial_bitwise_rscan(const void *p, unsigned int len, bool target,
+ int start, int end)
+{
+ int ofs;
+
+ for (ofs = start; ofs > end; ofs--) {
+ if (bitwise_get_bit(p, len, ofs) == target) {
+ break;
+ }
+ }
+ return ofs;
+}
+
static void
test_bitwise_rscan(struct ovs_cmdl_context *ctx OVS_UNUSED)
{
@@ -508,6 +522,44 @@ test_bitwise_rscan(struct ovs_cmdl_context *ctx OVS_UNUSED)
ovs_assert(-1 == bitwise_rscan(s4, 3, 1, 23, -1));
/* Target is 0 ..., start is 0 */
ovs_assert(0 == bitwise_rscan(s4, 3, 0, 0, -1));
+
+ int n_loops;
+ for (n_loops = 0; n_loops < 100; n_loops++) {
+ ovs_be64 x = htonll(0);
+ int i;
+
+ for (i = 0; i < 64; i++) {
+ ovs_be64 bit;
+
+ /* Change a random 0-bit into a 1-bit. */
+ do {
+ bit = htonll(UINT64_C(1) << (random_range(64)));
+ } while (x & bit);
+ x |= bit;
+
+ for (int end = -1; end <= 63; end++) {
+ for (int start = end; start <= 63; start++) {
+ for (int target = 0; target < 2; target++) {
+ bool expect = trivial_bitwise_rscan(
+ &x, sizeof x, target, start, end);
+ bool answer = bitwise_rscan(
+ &x, sizeof x, target, start, end);
+ if (expect != answer) {
+ fprintf(stderr,
+ "bitwise_rscan(0x%016"PRIx64",8,%s,%d,%d) "
+ "returned %s instead of %s\n",
+ ntohll(x),
+ target ? "true" : "false",
+ start, end,
+ answer ? "true" : "false",
+ expect ? "true" : "false");
+ abort();
+ }
+ }
+ }
+ }
+ }
+ }
}
static void
More information about the dev
mailing list