On Fri, Apr 13, 2018 at 2:40 PM, Han Zhou <[email protected]> wrote: > > > > On Fri, Apr 13, 2018 at 1:42 PM, Ben Pfaff <[email protected]> wrote: > > > > On Fri, Apr 13, 2018 at 01:33:26PM -0700, Han Zhou wrote: > > > On Fri, Apr 13, 2018 at 12:54 PM, Ben Pfaff <[email protected]> wrote: > > > > I think that sync_address_sets() is O(n**2) in n_ipv4_addrs and > > > > n_ipv6_addrs, because of the allocation strategy. If port groups get > > > > big (and they will eventually even if they do not today, because scale) > > > > I think that it would be better to expand the allocations exponentially. > > > > > > Sorry that I didn't find it a problem. For each group, there are i ports, > > > and for each port there are j address groups (e.g. mac ip1 ip2 ip3 ...), > > > and for each address group there are k addresses (some of them can be ipv4 > > > and some can be ipv6). > > > Although there are nested loops, this implementation iterates each ipv4 and > > > ipv6 address only once, so if the total number of ipv4 and ipv6 addresses > > > are n, then it should be O(n). Please correct me if I missed something here. > > > > I agree that the function visits and inserts each ipv4 and ipv6 address > > once, which is O(n). The issue is that xrealloc() has to copy all of > > the addresses each time. Suppose, for example, that there are 50 > > addresses in an address set, 1 per port. This yields a sequence of 50 > > xrealloc() calls that copy 0, 1, 2, ..., 49 addresses, respectively, > > which is O(n**2) copies. The usual solution is to expand the array by > > (roughly) doubling, so that there are only 0 + 1 + 2 + 4 + 8 + 16 + 32 > > copies total, which is O(n) copies. > > Now I got your point! I will send V3 with this addressed. Thanks Ben!
Hi Ben, V3 is here: https://patchwork.ozlabs.org/patch/898123/ All comments are addressed except that I kept the xcalloc() there as initial allocation for the exponential allocations. Please take a look. Thanks, Han _______________________________________________ dev mailing list [email protected] https://mail.openvswitch.org/mailman/listinfo/ovs-dev
