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! > > Thanks, > > Ben. _______________________________________________ dev mailing list [email protected] https://mail.openvswitch.org/mailman/listinfo/ovs-dev
